西安电子科技大学第16届程序设计竞赛 E Xieldy And His Password

链接：https://www.nowcoder.com/acm/contest/107/E
来源：牛客网

Xieldy And His Password

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

众所周知，Xieldy最常用的口令是******。
为了改变这一现状，他random了一个01串，并从中截取了一段作为自己的口令。
他选择的口令满足以下条件：
1. 口令串表示的二进制数在十进制下可以被表示为3k(k>=0)。
2. 口令串可以有前导零。
现已经random出了01串，他想知道有多少种口令方案可以选择（不同的子段即为不同）。

输入描述:

若干组数据，每组数据仅一行01串s，表示random出来的的串，|s|<=1e6。

输出描述:

输出口令的方案数。

输入例子:

输出例子:

-->

示例1

输入

输出

题解：

每次保存取模等于0，，2的情况数，然后迭代更新。

代码：  

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn=1e6+;

char t[maxn];

int a[maxn][];

int main()

{

    while(~scanf("%s",&t))

    {

        int L=strlen(t);

        ll a0=,a1=,a2=,b0=,b1=,b2=,la=,ans=;

        for(int i=,j=L-; j>=; j--,i++)

        {

            if(t[j]=='')

            {

                a0++;

                swap(a0,b0);swap(a1,b1);swap(a2,b2);

                ans=ans+a0+b0;la=a0+b0;

            }

            else

            {

                swap(a0,a1);swap(a0,a2);

                swap(b0,b2);swap(b0,b1);a1++;

                swap(a0,b0);swap(a1,b1);swap(a2,b2);

                la=a0+b0;ans+=la;

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}

其它类似简短代码：

#include <iostream>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;

char s[];

int main()

{

    int i,n,cnt;

    while(~scanf("%s",s)){

        cnt=;

        long long  ans=;

        map<int,int>mp;

        mp[]=;

        getchar();

        n=strlen(s);

        for(i=;i<n;i++){

            if(i&)cnt=(cnt+s[i]-''+)%;

            else cnt=(cnt-s[i]+''+)%;

            ans+=mp[cnt];

            mp[cnt]++;

        }

        printf("%lld\n",ans);

    }

    return ;

}

巴特西