codeforces-1138 (div2)

佚名 6年前 (2019-04-09) 随笔 1780人围观抢沙发百度已收录

想法题是硬伤，面对卡题和卡bug的情况应对能力太差

A.求两个前缀和以及两个后缀和，相邻最小值的最大值。

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

#include<iostream>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int pre1[maxn],pre2[maxn],erp1[maxn],erp2[maxn];
int main(){
    int N; scanf("%d",&N);
    for(int i = 1; i <= N ; i ++){
        scanf("%d",&a[i]);
        if(a[i] == 1) pre1[i] = pre1[i - 1] + 1;
        else pre2[i] = pre2[i - 1] + 1;
    }
    for(int i = N; i >= 1; i --){
        if(a[i] == 1) erp1[i] = erp1[i + 1] + 1;
        else erp2[i] = erp2[i + 1] + 1;
    }
    int ans = 0;
    for(int i = 1; i <= N; i ++){
        ans = max(ans,min(pre1[i],erp2[i + 1]));
        ans = max(ans,min(pre2[i],erp1[i + 1]));
    }
    printf("%d",ans * 2);
    return 0;
}

B.将人分为00,10,01,11四种，总人数已知为ABCD，假设我们需要选择的分别为abcd。

得到方程1.a + b + c + d = n / 2 方程2 b + d = (C - c) + (D - d)

化简方程2得到b + c + 2d = C + D;

CD为已知常数，考虑暴力枚举dc，可推得b，根据方程1可推得a，然后check，时间复杂度O(n²)

#include<iostream>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
const int maxn = 5000;
struct Node{
    int a,b;
    int id;
}node[maxn];
char str[maxn];
int Stack[maxn],top;
vector<int>ans;
bool cmp(Node a,Node b){
    return a.a + a.b > b.a + b.b;
}
vector<int>aa,ab,ba,bb;
int main(){
    int N; scanf("%d",&N);
    scanf("%s",str + 1);
    for(int i = 1; i <= N ; i ++){
        node[i].a = str[i] - '0';
        node[i].id = i;
    }
    scanf("%s",str + 1);
    for(int i = 1; i <= N ; i ++) node[i].b = str[i] - '0';
    for(int i = 1; i <= N ; i ++){
        if(node[i].a + node[i].b == 0) aa.pb(i);
        else if(node[i].a == 1 && node[i].b == 0) ba.pb(i);
        else if(node[i].a == 0 && node[i].b == 1) ab.pb(i);
        else bb.pb(i);
    }
    int A = aa.size(),B = ba.size(),C = ab.size(),D = bb.size();
    for(int d = 0; 2 * d <= C + D && d <= D; d++){
        for(int c = 0; c <= C && c + 2 * d <= C + D;c++){
            int b = (C - c) + (D - d) - d;
            if(b < 0 || b > B) continue;
            int a = (N / 2) - b - c - d;
            if(a < 0 || a > A) continue;
            for(int i = 0 ; i < a; i ++) printf("%d ",aa[i]);
            for(int i = 0 ; i < b; i ++) printf("%d ",ba[i]);
            for(int i = 0 ; i < c; i ++) printf("%d ",ab[i]);
            for(int i = 0 ; i < d; i ++) printf("%d ",bb[i]);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

C.对每行每列分别离散化，对于一个点的x是交叉点在横竖往前排名较后的位置加上往后排名较前的位置。

#include<iostream>
#include<vector>
#include<algorithm>
#define pb push_back
#define LL long long 
using namespace std;
const int maxn = 2010;
int N,M;
LL MAP[maxn][maxn];
LL sr[maxn][maxn],sc[maxn][maxn],hr[maxn][maxn],hc[maxn][maxn];
LL Hash[maxn];
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; i ++){
        for(int j = 1; j <= M ; j ++){
            scanf("%lld",&MAP[i][j]);
        }
    }
    for(int i = 1;i <= N ; i ++){
        for(int j = 1; j <= M; j ++) Hash[j] = MAP[i][j];
        sort(Hash + 1,Hash + 1 + M);
        int cnt = unique(Hash + 1,Hash + 1 + M) - Hash - 1;
        for(int j = 1; j <= M ; j ++){
            int t = lower_bound(Hash + 1,Hash + 1 + cnt,MAP[i][j]) - Hash;
            sc[i][j] = t; hc[i][j] = cnt - t;
        }
    }
    for(int j = 1; j <= M ; j ++){
        for(int i = 1; i <= N ; i ++) Hash[i] = MAP[i][j];
        sort(Hash + 1,Hash + 1 + N);
        int cnt = unique(Hash + 1,Hash + 1 + N) - Hash - 1;
        for(int i = 1; i <= N; i ++){
            int t = lower_bound(Hash + 1,Hash + 1 + cnt,MAP[i][j]) - Hash;
            sr[i][j] = t; hr[i][j] = cnt - t;
        }
    }
    for(int i = 1; i <= N; i ++){
        for(int j = 1; j <= M; j ++){
            if(j != 1) printf(" ");
            printf("%lld",max(sc[i][j],sr[i][j]) + max(hr[i][j],hc[i][j]));
        }
        puts("");
    }
    return 0;
}

D.没看清楚题目意思为子串之间可以相互重叠，需要求出一个kmp的next数组，然后贪心的迭代最多能放下的数字。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define pb push_back
#define LL long long 
using namespace std;
const int maxn = 5e5 + 10;
int N,M;
char str1[maxn],str2[maxn];
int Z,O,z,o;
void get_next(char x[],int m,int nxt[]){
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m ; i ++){
        while(j && x[i] != x[j + 1]) j = nxt[j];
        if(x[j + 1] == x[i]) j ++;
        nxt[i] = j;
    }
}
int Next[maxn];
int main(){
    Z = O = z = o = 0;
    scanf("%s%s",str1 + 1,str2 + 1);
    for(int i = 1;str1[i]; i ++){
        if(str1[i] == '0') Z++;
        else O++;
    }
    for(int i = 1;str2[i]; i ++){
        if(str2[i] == '0') z++;
        else o++;
    }
    if(z > Z || o > O){
        for(int i = 0 ; i < O; i ++) printf("1");
        for(int i = 0 ; i < Z; i ++) printf("0");
    }else{
        Z -= z; O -= o;
        int l = strlen(str2 + 1);
        get_next(str2,l,Next);
        o = z = 0;
        int ans = 1;
        for(int i = Next[l] + 1; i <= l ; i ++){
            if(str2[i] == '1') o++;
            else z++;
        }
        while(Z - z >= 0 && O - o >= 0){
            ans++;
            Z -= z; O -= o;
        }
        printf("%s",str2 + 1);
        for(int i = 1 ; i < ans; i ++){
            for(int j = Next[l] + 1; j <= l; j ++) printf("%c",str2[j]);
        } 
        for(int i = 0 ; i < O; i ++) printf("1");
        for(int i = 0 ; i < Z; i ++) printf("0");
    }
    return 0;
}