The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - J

J、CONTINUE…?

連結：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5759

題意：長為n由0,1組成的字元串，Ai都有對應的權值i（1<=i<=n），0隻能分為1,2組，1隻能分為3，4組，要使第一組與第三組的權值和跟第二組與第四組的權值和相等，輸出對應的一種分組方案。若無方案，輸出-1.

思路：

兩個組的權值和相等，那麼總的權值和必為偶數，否則輸出-1.

設總的權值和為sum,要使兩個分組的權值和為sum/2，令tmp=1+2+……+k，并且前k個字元已做标記，假設tmp是比sum/2小的最大的那個數，那麼此時有兩種情況：

1.tmp+k+1==sum/2時，對第k+1個字元做标記

2.tmp+k+1>sum/2，對第k+1個字元做标記，将已經标記過的tmp+k+1-sum/2個字元的标記去掉

最後根據标記輸出就可以了。

代碼：

#include <bits/stdc++.h>
using namespace std;

#define mem(a,n) memset(a,n,sizeof(a))
#define rep(i,a,n) for(int i=a;i<n;i++)

typedef long long ll;
const double eps=;
const int N=+;
const int MOD=+;
const int INF=;
const int dir[][]= {,,-,,,,,-};

char a[N];
bool vis[N];
int main()
{
    ll T,n;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld %s",&n,a+);
        for(int i=; i<=n; i++)
        {
            vis[i]=;
        }
        ll ss=n*(n+)/,sum=;///注意計算時中間結果會溢出  即爆int
        if(ss%==)
        {
            puts("-1");
            continue;
        }
        ss/=;
        for(int i=; i<=n; i++)
        {
            if(sum+i<=ss)
            {
                sum+=i,vis[i]=;
                if(sum==ss) break;
            }
            else
            {
                vis[i]=;
                vis[sum+i-ss]=;
                break;
            }
        }
        for(int i=; i<=n; i++)
        {
            if(vis[i])
            {
                if(a[i]=='0') putchar('1');
                else putchar('3');
            }
            else
            {
                if(a[i]=='0') putchar('2');
                else putchar('4');
            }
        }
        puts("");
    }
    return ;
}