Menci的序列

题目大意

一个长度为n的字符串s，只包含+和×。

选出一个子序列，然后你有一个ret，初始为0，按顺序扫你选出的这个子序列。

如果碰到的是+，ret+1，否则ret*2。

最大化ret%2^k。

　　首先可以注意到，每一个＋对答案有２＾ｃ的贡献，ｃ为该＋后的×数量（因为遇到了×每次乘二）。

　从这个结论推广开来，可以得到×＋＋＋＝＋×＋这样一个性质（前者每个＋的贡献为２＾０＝１，总和为３，后者第一个加号的贡献为２＾１＝２，第二个＋的贡献为２＾０＝１，总和也为３）。

　　有了以上两种结论，我们可以把任意一个大于２的＋序列从中抽取两个＋，又前面的离他最近的一个×前添加一个＋。循环多次，就可以使得每一个＋序列的长度不超过２。

　　建立一个a[]，ａ［ｉ］表示后面×的数量为ｉ的＋有多少个，这样来存取每个＋的贡献。依第三段的结论可以推出，ａ［ｉ］＜＝２因此在二进制运算中，最多只能进一次位。

点击查看代码

#include<cstdio>

#include<algorithm>

#include<cstring>

#define fo(i,a,b) for(i=a;i<=b;i++)

#define fd(i,a,b) for(i=a;i>=b;i--)

using namespace std;

const int maxn=1000000+10;

char s[maxn];

int a[maxn],ans[maxn];

int i,j,k,l,t,n,m,p;

int main(){

    scanf("%d%d",&n,&k);

    scanf("%s",s+1);

    t=0;

    fd(i,n,1)

        if (s[i]=='*') t++;else a[t]++;

    n+=10;

    fo(i,0,n){

        t=(a[i]-1)/2;

        a[i]-=2*t;

        a[i+1]+=t;

    }//将多个加号组成的串转化成最多只有两个连续加号组成的串

    p=k-1;

    while (n>=0){

        while (n>=0&&!a[n]) n--;

        if (n<0) break;

        if (n>=p) ans[p--]=1;

        else{

            fo(i,0,p-1){

                t=a[i]/2;

                a[i]-=2*t;

                a[i+1]+=t;

            }

            fo(i,0,p) ans[i]=a[i];

            break;

        }

        n--;

    }

    p=k-1;

    while (p>=0&&!ans[p]) p--;

    if (p>=0){

        fd(i,p,0) printf("%d",ans[i]);

        printf("\n");

    }

    else printf("0\n");

}

巴特西

Menci的序列

题目大意

最新文章

热门文章