题解：AT_abc200_d [ABC200D] Happy Birthday! 2

wyyinput · 2025-06-20 22:20:20 · 题解

这个题我们可以先打一个暴力代码。我们枚举 B 序列和 C 序列的所有互异的情况。因为每一个 A_i 有两种情况，一共就有 2^N 种情况，所以时间复杂度为 O(2^N)。显然我们接受不了。我用的二进制枚举，2^{200} 根本存不下。所以提交结果是 WA，不是 TLE。如果你用 DFS，你就会 TLE。

暴力代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[201],q[201],p[201];
int t,ans1,ans2;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    for(int i=1;i<=(1<<n)-1;i++){
        for(int j=1;j<=(1<<n)-1;j++){
            if(i==j){
                continue;
            }
            ans1=0,ans2=0;
            t=1;
            q[0]=p[0]=0;
            while(t<=n){
                if(i&(1<<(t-1))){
                    ans1+=a[t];
                    q[++q[0]]=t;
                    ans1%=200;
                }
                if(j&(1<<(t-1))){
                    ans2+=a[t];
                    p[++p[0]]=t;
                    ans2%=200;
                }
                ++t;
            }
            if(ans1==ans2){
                puts("Yes");
                for(int j=0;j<q[0];j++){
                    printf("%d ",q[j]);
                }
                printf("%d\n",q[q[0]]);
                for(int j=0;j<p[0];j++){
                    printf("%d ",p[j]);
                }
                printf("%d\n",p[p[0]]);
                return 0;
            }
        }
    }
    puts("No");
    return 0;
}

我们考虑优化。前文已经提到，对于长度为 N 的序列 A，一共就有 2^N 种情况。因为模数为 200，所以如果总情况大于 200 种，它们的余数至少有一组是相等的。当 N 为 8 时，2^N = a^8 = 256。此时一定可以找到两个不同的序列 B 和 C，使它们的和除以 200 的余数相等。

这有什么用呢？当 N = 8 时，就一定有解了。换句话说就是如果 A 序列的长度大于 8，对于 i，8 < i \le N，A_i 对答案是没有贡献的。所以当 1 \le N \le 8 时，不变；当 8 < N \le 200 时，只输入前八个，时间复杂度降成了 O(2^8)，可以通过此题。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[9],q[9],p[9];
int t,ans1,ans2;
int main(){
    scanf("%d",&n);
    n=min(n,8);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    for(int i=1;i<=(1<<n)-1;i++){
        for(int j=1;j<=(1<<n)-1;j++){
            if(i==j){
                continue;
            }
            ans1=0,ans2=0;
            t=1;
            q[0]=p[0]=0;
            while(t<=n){
                if(i&(1<<(t-1))){
                    ans1+=a[t];
                    q[++q[0]]=t;
                    ans1%=200;
                }
                if(j&(1<<(t-1))){
                    ans2+=a[t];
                    p[++p[0]]=t;
                    ans2%=200;
                }
                ++t;
            }
            if(ans1==ans2){
                puts("Yes");
                for(int j=0;j<q[0];j++){
                    printf("%d ",q[j]);
                }
                printf("%d\n",q[q[0]]);
                for(int j=0;j<p[0];j++){
                    printf("%d ",p[j]);
                }
                printf("%d\n",p[p[0]]);
                return 0;
            }
        }
    }
    puts("No");
    return 0;
}