D 题 卡数学 （常规操作）

E 题 pair<int,int>的sort只设置了一个关键字导致出现bug改了一年，原因至今不明

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

A.答案为字符串长度和a的数量 * 2 - 1的较小值。

codeforces-1146 (div2) 随笔 第1张 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
char str[maxn];
int main(){
    scanf("%s",str);
    int ans = strlen(str);
    int a = 0;
    for(int i = 0;str[i]; i ++){
        if(str[i] == 'a') a++;
    }
    ans = min(ans,a * 2 - 1);
    Pri(ans);
    return 0;
}
A

 

B.字符串长度加上a的数量为前面一个字符串扩充一倍的长度，检验前后是否一致即可。

codeforces-1146 (div2) 随笔 第3张 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
char str[maxn];
int main(){
    scanf("%s",str);
    int ans = strlen(str);
    int l = strlen(str);
    for(int i = 0;str[i]; i ++){
        if(str[i] == 'a') ans++;
    }
    bool flag = 1;
    if(ans & 1) flag = 0;
    else{
        ans /= 2;
        int cnt = ans;
        for(int i = 0 ; i < ans && flag; i ++){
            if(str[i] == 'a') continue;
            if(cnt < l && str[i] == str[cnt]){
                cnt++;
                continue;
            }
            flag = 0;
        }
        if(cnt < l) flag = 0;
    }
    if(flag) for(int i = 0; i < ans; i ++) printf("%c",str[i]);
    else puts(":(");
    return 0;
}
B

 

C.第一次做交互题，卡fflush(stdout)卡了很久。

一般交互题都逃不过二分，一个显而易见的想法是开始分50 + 50找最大值，然后各自分25 + 25和25 + 25,像完全二叉树一样下去。

但是这样询问次数远远不够9次，事实上可以发现，这颗二叉树的层树不会超过九层，所以说，两次25 + 25其实可以同时进行变为打乱顺序之后的50 + 50,也就是每一层来说，询问的集合是这一层所有左节点的集合和右节点的集合，这样9次统计最大值就可以了。

codeforces-1146 (div2) 随笔 第5张 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
vector<PII>Q[maxn],P[maxn];
void dfs(int l,int r,int dep,int dir){
    if(dir == 1) Q[dep].pb(mp(l,r));
    else if(dir == 2) P[dep].pb(mp(l,r));
    if(l >= r) return;
    int m = l + r >> 1;
    dfs(l,m,dep + 1,1);
    dfs(m + 1,r,dep + 1,2);
}
int L[maxn],R[maxn];
int main(){
    int T;Sca(T);
    while(T--){
        for(int i = 0 ; i < 20; i ++) Q[i].clear(),P[i].clear();
        Sca(N);
        dfs(1,N,0,0);
        int ans = 0;
        for(int i = 1 ;; i ++){
            int cnt1 = 0,cnt2 = 0;
            for(int j = 0 ; j < Q[i].size(); j ++){
                for(int k = Q[i][j].fi; k <= Q[i][j].se; k ++){
                    L[++cnt1] = k;
                }
            }
            for(int j = 0 ; j < P[i].size(); j ++){
                for(int k = P[i][j].fi; k <= P[i][j].se; k ++){
                    R[++cnt2] = k;
                }
            }
            if(!cnt1 || !cnt2) break;
            printf("%d %d",cnt1,cnt2);
            for(int j = 1 ; j <= cnt1; j ++) printf(" %d",L[j]);
            for(int j = 1 ; j <= cnt2; j ++) printf(" %d",R[j]);
            printf("\n");
            fflush(stdout);
            int x; Sca(x);
            ans = max(ans,x);
        }
        printf("-1 ");
        Pri(ans);
        fflush(stdout);
    }
    return 0;
}
C

 

E.发现可以从小到大排序给出序列，最终答案重排回来即可。

因此将整个数组按照绝对值从小到大排序，给出的操作分为四种情况。

分为 >  < 两种情况 和 x为正数负数两种情况组合起来四种情况。

四种情况分类讨论，用线段树维护序列的正负。

例如 < 4,就将 0 - 3全部置反,4 - +∞全部置正数。

全部操作完之后重排输出答案

codeforces-1146 (div2) 随笔 第7张 
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,K;
PII a[maxn];
int b[maxn],ans[maxn];
struct Tree{
    int l,r,lazy;
}tree[maxn * 4];
void Build(int t,int l,int r){
    tree[t].l = l; tree[t].r = r;
    tree[t].lazy = 0;
    if(l >= r){
        if(a[l].fi < 0) tree[t].lazy = -1;
        else tree[t].lazy = 1;
        return;
    }
    int m = l + r >> 1;
    Build(t << 1,l,m); 
    Build(t << 1 | 1,m + 1,r);
}
bool cmp(PII x,PII y){
    if(abs(x.fi) == abs(y.fi)) return x.se < y.se; //注释掉这行就tle，我也不知道为什么，有知道的可以留言 
    return abs(x.fi) <= abs(y.fi);
}
void change(int t,int flag){
    if(flag == 2){
        if(tree[t].lazy == -1) tree[t].lazy = 1;
        else if(tree[t].lazy == 1) tree[t].lazy = -1;
        else if(tree[t].lazy == 2) tree[t].lazy = 0;
        else if(tree[t].lazy == 0) tree[t].lazy = 2;
    }
    else if(flag == 1) tree[t].lazy = 1;
    else if(flag == -1) tree[t].lazy = -1;
}
void Pushdown(int t){
    if(!tree[t].lazy) return;
    change(t << 1,tree[t].lazy);
    change(t << 1 | 1,tree[t].lazy);
    tree[t].lazy = 0;
}
void update(int t,int l,int r,int flag){
    if(l > r || tree[t].l > tree[t].r) return;
    if(tree[t].l < 1 || tree[t].l > N) return;
    if(tree[t].r < 1 || tree[t].r > N) return;
    if(l <= tree[t].l && tree[t].r <= r){
        change(t,flag);
        return;
    }
    Pushdown(t);
    int m = (tree[t].l + tree[t].r) >> 1;
    if(r <= m) update(t << 1,l,r,flag);
    else if(l > m) update(t << 1 | 1,l,r,flag);
    else{
        update(t << 1,l,m,flag);
        update(t << 1 | 1,m + 1,r,flag);
    }
}
void query(int t){
    if(tree[t].l >= tree[t].r){
        b[tree[t].l] *= tree[t].lazy;
        return;
    }
    Pushdown(t);
    query(t << 1); query(t << 1 | 1);
}
int main(){
    Sca2(N,M);
    for(int i = 1; i <= N ; i ++){
        a[i].se = i; Sca(a[i].fi);
    }
    sort(a + 1,a + 1 + N,cmp);
    for(int i = 1; i <= N ; i ++) b[i] = abs(a[i].fi);
    Build(1,1,N);
    for(int i = 1; i <= M; i ++){
        char op[2]; 
        scanf("%s",op);int x; Sca(x);
        if(op[0] == '<'){
            if(x > 0){
                int p = lower_bound(b + 1,b + 1 + N,x) - b;
                if(p > 1) update(1,1,p - 1,2);  //2取反    
                if(p <= N) update(1,p,N,1);  //1全变正    
            }else{
                int p = upper_bound(b + 1,b + 1 + N,-x) - b;
                if(p <= N) update(1,p,N,1);  //1全变正
            }
        }else{
            if(x > 0){
                int p = upper_bound(b + 1,b + 1 + N,x) - b;
                if(p <= N) update(1,p,N,-1);  //-1全变负 
            }else{
                int p = lower_bound(b + 1,b + 1 + N,-x) - b;
                if(p > 1) update(1,1,p - 1,2);  //2取反    
                if(p <= N) update(1,p,N,-1);  //-1全变负 
            }
        }
    }
    query(1);
    for(int i = 1; i <= N; i ++){
        ans[a[i].se] = b[i];
    }
    for(int i = 1; i <= N ; i ++){
        printf("%d ",ans[i]);
    }
    return 0;
}
E

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄