Codeforces Round #496 (Div. 3)

A.
统计1的个数即可，注意最后一个数必定是某个台阶的最后一级也就是级数即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int main()
{
    int n,i,j,k;
    vector<int>c,ans;
    cin>>n;
    if(n==1){
        cout<<1<<endl<<1<<endl;return 0;
    }
    int cnt=0;
   for(i=1;i<=n;i++){
        cin>>j;c.push_back(j);if(j==1)cnt++;
    }
    cout<<cnt<<endl;
    for(i=0;i<c.size()-1;i++){
       if(c[i+1]==1)cout<<c[i]<<' ';
   }
   cout<<c.back()<<endl;

    return 0;
}

B.
把两个字符串反转以后统计最长的公共前缀即可，剩下的就是必须砍掉的长度

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string str1,str2;
    int i,j,k;
    cin>>str1>>str2;
    reverse(str1.begin(),str1.end());reverse(str2.begin(),str2.end());
    for(i=0;i<min(str1.size(),str2.size());i++){
        if(str1[i]!=str2[i])break;
    }
    cout<<str1.size()+str2.size()-i*2<<endl;

    return 0;
}

C.
预处理所有范围内2的幂次的值，然后扫一遍所有数，存入set中，同时一个map计数。
再扫一遍，对于每个数，在set里面查找2的幂次与其的差是否存在。注意如果2的幂次恰好是该数的两倍时还要注意是否真的存在两个相同的数。
时间复杂度n*30logn

#include <iostream>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
    int n, q1, q2, ans=0;
    int b[35], in[120005];
    set<int>a;
    map<int,int>num;
    cin >> n;
    b[0] = 1;
    for (int i = 1; i <= 30; i++) {
        b[i] = b[i - 1] * 2;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d",&in[i]);
        a.insert(in[i]);num[in[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        bool ck = false;
        for (int j = 0; j <= 30; j++) {
            if (a.find(b[j] - in[i]) != a.end())
            {
                if (( b[j] != in[i] * 2 ) || (b[j] == in[i] * 2 && num[in[i]] > 1)) {//注意是否真的有两个相同的数
                    ck = true;
                    break;
                }
            }
        }
        if (!ck)
            ans++;
    }
    cout << ans<<endl;

    return 0;
}

D.
动态规划。
令f[i+1]表示以str[i]为右端点的最大划分数，那么对于每一个f[i]，它首先可以由f[i-1]转移而来，即他不是某个3的倍数的划分的情况。
然后往前找到第一个左端点使这个区间能被3整除就是包含在某个整除3的划分中的情况，此时就可以break，因为之前的情况肯定不会大于之后的。（可以发现一个更长的3划分是肯定不如一个比较短的划分的）
所以找到第一个之后之前的就都不需要再找了（事实上如果不break会tle）。

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int f[200005];
int main()
{
    string str;int i,j,k;
    cin>>str;
    for(i=0;i<str.size();i++){
        int sum=0;f[i+1]=f[i];
        for(j=i;~j;j--){
            sum+=str[j]-'0';
            if(sum%3==0){
                f[i+1]=max(f[i+1],f[j]+1);break;
            }
        }
    }
    cout<<f[str.size()]<<endl;

    return 0;
}

E1.
对于每一个区间，如果他的中位数是给定的m，意味着这个区间中小于等于m的数的个数等于大于m的个数或者大1，那么其实对于每一个区间我们只要统计这两种数的个数就可以了，因此朴素的想法就是枚举每一个空间并统计。不幸的是这依然会tle，因此需要优化。
我们可以先统计位于中位数数列位置中左边的所有位置的两种数的个数的差，用一个map来统计。然后从中位数的数列位置往右扫，对于每一个位置我们会得到两种数的差（默认为小的数的个数-大的数的个数），记为k。于是如果左边的差中存在一个n使得n+k=0||n+k=1，那么左边差为n的位置数就可以加进答案里。注意单纯用左边也是有可能搞出符合条件的中位数的，因此答案要加上map[1]+map[0]。
以及，如果中位数位于数列的最右边，需要特判一下。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main()
{
    //vector<int>s,ma;
    int s=0,ma=0;
    int n,m,i,j,k;long long ans=0;
    cin>>n>>m;
    int num[200005];int pos;
    map<int,int>mp1;
    for(i=1;i<=n;i++){
        scanf("%d",&num[i]);
        if(num[i]==m)pos=i;
    }
    int l,r;
    for(l=pos;l;l--){
        if(num[l]<=num[pos])s++;
        else ma++;
        mp1[s-ma]++;
    }
    if(pos==n){
        ans=mp1[0]+mp1[1];cout<<ans<<endl;return 0;
    }
    s=0;ma=0;int cnt=0;
    for(r=pos+1;r<=n;r++){
        if(num[r]<=num[pos])s++;
        else ma++;
        if(mp1.count(1-(s-ma)))ans+=mp1[1-(s-ma)];
        if(mp1.count(0-(s-ma)))ans+=mp1[0-(s-ma)];
    }
    cout<<ans+mp1[1]+mp1[0]<<endl;

    return 0;
}