Codeforces Round #496 (Div. 3)

题目链接

A  00:02

B  00:08

C  00:23

D  --:--

E1 --:--

E2 --:--

F  --:--

A. Tanya and Stairways

每段序列都是从1开始依次递增
就统计1的数量和1后面的最大值输出即可

    int n = read();
    for(int i = 1 ; i <= n ; i ++){
        int x = read();
        if(x == 1) a.push_back(1);
        else a[Len(a) - 1] = x;
    }
    cout << Len(a) << endl;
    for(auto x : a) cout << x << " ";
    cout << endl;

B. Delete from the Left

计算两个字符串最长的公共后缀长度

    string s,t; cin >> s >> t;
    int r1 = Len(s) - 1, r2 = Len(t) - 1;
    while(r1 >= 0&& r2 >= 0 && s[r1] == t[r2]) r1 --, r2 --;
    cout << r1 + r2 + 2 << endl;

C. Summarize to the Power of Two

如果要删除一个数就需要这个数不存在和另一个数的和是2的幂

    mi[0] = 1;
    for(int i = 1 ; i <= 34 ; i ++) mi[i] = mi[i - 1] << 1;
    int n = read();
    for(int i = 1 ; i <= n ; i ++){
        int x = read();
        a.push_back(x);
        m[x]++;
    }
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++){
        int x = a[i - 1];
        m[x] --;
        bool flag = false;
        for(int j = 1 ; j <= 33 ; j ++){
            if(mi[j] <= x) continue;
            if(m[mi[j] - x]){
                flag = true;
                break;
            }
        }
        if(!flag){
            ans ++;
        }
        m[x] ++;
    }
    cout << ans << endl;

D. Polycarp and Div 3

你有一个字符序列,你需要将这个序列分成若干段,使存在一段字符序列数字和为3的倍数的段数尽可能多
经分析对于一段序列如果可以继续分成一段可以被3整除的序列我一定会继续分下去的
因此只需统计序列中存在多少种模3 为'0', '111','222','12','21'的序列即可
学习知识:^的优先级小于

    string s; cin >> s;
    int ans = 0;
    for(int i = 0 ; i < Len(s) ; i ++){
        int x = idz(s[i]) % 3;
        if(x == 0){
            ans ++;
        }else if(i + 1 < Len(s) && (x ^ 3) == (idz(s[i + 1]) % 3)){
            ans ++;
            i += 1;
        }else if(i + 2 < Len(s) && (x == (idz(s[i + 1]) % 3)) && (x == (idz(s[i + 2]) % 3))){
            ans ++;
            i += 2;
        }
    }
    cout << ans << endl;

E. Median on Segments

给你一段序列你需要找有多少种连续序列满足以m为中位数
直接求有多少序列是以m为中位数的很难求
因此可以转换一下,求有多少序列满足大于等于m的数为中位数-有多少序列满足大于m的数为中位数
求中位数序列大于等于m的操作很简单,只需要统计(1,i)中间大于等于m的个数减去小于m的个数就是当前是否满足,在找一个(1,j)中间大于等于m的个数减去小于m的个数,如果发现第一个数大于等于第二个数就表示(j,i)满足,显然这种情况可以用树状数组维护,但是我没有调出来,stO
因此就考虑贪心维护这个操作,维护一个区间和 和 区间和为p的区间和出现了多少次,当遇到一个大于等于m的就将当前区间和出现的次数的上一次维护上去,因为维护的时小于当前区间和的数量,若小于m则减去前一个维护的区间和数量,因为本身区间和本身就没有向上维护,

int get(int k){
    memset(c, 0, sizeof c);
    int res = 0;
    int sum = 0;
    int p = n + 1;
    c[p] ++;
    for(int i = 1 ; i <= n ; i ++){
        if(a[i] >= k){
            sum += c[p];
            p ++;
        }else{
             p --;
             sum -= c[p];
        }
        res += sum;
        c[p] ++;
    }
    return res;
}

F. Berland and the Shortest Paths

学习ing