浙江省赛 CONTINUE...?（思维）

CONTINUE…? 题意 班里有N名同学，编号为1、2、3……N，第i名同学有i个宝石。让我们将这N名学生分成G1,G2,G3,G4四个组，且满足以下规则 每一个同学仅且只能分到一个组女同学只能分到G1或者G2组，男同学只能分到G3或者G4组 （这N个同学的性别会以字符串的形式给出，‘1’表示男同学，‘0’表示女同学）G1+G3的宝石数量等于G2+G4的宝石数量允许有一个组为空

问这N个同学各自分到了那一组，如果答案有多种，随意输出一种即可。

思路

我们先考虑不可能的情况, 假设： G1的宝石数量是$su{m}_1$ G2的宝石数量是$su{m}_2$ G3的宝石数量是$su{m}_3$ G4的宝石数量是$su{m}_4$ 有$su{m}_1+su{m}_3==su{m}_2+su{m}_4$ $su{m}_1+su{m}_2+su{m}_3+su{m}_4==N\ast (N+1)/2$ 即$2\ast (su{m}_1+su{m}_3)==N\ast (N+1)/2$ 所以如果N*(N+1)/2不是偶数的直接输出-1了

如果可能的话，该如何分配呢？ 先考虑如何满足$su{m}_1+su{m}_3==su{m}_2+su{m}_4$ 因为宝石的数量是连续的1~N,我们可以这样分配，比如N=7，宝石 数量是 1 2 3 4 5 6 7，从后面两两分组(6,7),(4,5),(2,3),(1)

让7分给1、3(具体哪个看性别)，6分给2、4(具体哪个看性别) 让4分给1、3(具体哪个看性别)，5分给2、4(具体哪个看性别) 让3分给1、3(具体哪个看性别)，2分给2、4(具体哪个看性别)

这样能保证1、3和2、4的差值最大是1（只有N%4不为0的情况差值为1，这时前面的1还没用，正好补上这个差值）

代码 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long ul; typedef unsigned long long ull; #define pi acos(-1.0) #define e exp(1.0) #define pb push_back #define mk make_pair #define fir first #define sec second #define scf scanf #define prf printf typedef pair<ll,ll> pa; const ll INF=0x3f3f3f3f3f3f3f3f; const int MAX_N=1e5+7; int N,T; char s[MAX_N]; int res[MAX_N];//记录答案 int main() { // freopen(".../.txt","w",stdout); // freopen(".../.txt","r",stdin); ios::sync_with_stdio(false); cin>>T; int i,j; while(T--){ cin>>N; cin>>s+1; int sum=N*(N+1)/2; if(sum&1){ cout<<-1<<endl; continue; } bool flag=1; for(i=N;i>=1;i-=2){ if(flag){//大的放到1或者3里面 res[i]=(s[i]=='1'?3:1); res[i-1]=(s[i-1]=='1'?4:2); } else{//大的放到2或者4里面 res[i-1]=(s[i-1]=='1'?3:1); res[i]=(s[i]=='1'?4:2); } flag=!flag;//1、3和2、4交替着放大的，这样才能保证1、3的和与2、4的和最大相差1 } if(N%4){//没有分均衡，将最后一个1分配给2、4(因为我们先给1、3分配的，如果不够的话也是2、4不够) if(s[1]=='1') res[1]=4; else res[1]=2; } for(i=1;i<=N;i++){ cout<<res[i]; } cout<<endl; } return 0; }