T1 四个质数的和
赛场亲测搜索+小剪枝可以得到 70pts。
考虑 $O(p(V)^2)$枚举任意两个质数的和，其中 $p(V)$ 表示 $V$ 以内质数的个数。
然后开个数组记录下对于每种和的记录有多少种情况，查询时 for 循环扫一遍即可，详见代码。
复杂度去掉质数筛 $O(p(V)^2+tn)$，代码贴在下面(100pts)：
#define N 100005
int t,n,cnt,pr[N];
long long ans,prs[N<<1];
int main(){
//pr 存储的是 V 以内的质数
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
prs[pr[i]+pr[j]]++;
scanf("%d",&t);
while(t--){
scanf("%d",&n),ans=0;
for(int i=1;i<n;i++) ans+=prs[i]*prs[n-i];
printf("%lld\n",ans);
}
}
T2 匹配最大异或
位运算的题我们考虑分离二进制下的每一位，这道题使用的是分治。
分治从 $[0,2^{m-1})$ 开始，这样我们可以保证当前枚举的这一层前面的二进制位都是相同的。
所以我们考虑当前枚举到的这一位中的两种情况：
第一种，$a$ 数组的这一位上的值都相同，此时这一位就无法对答案产生影响。
这个时候就要求对于这一位分别是 $0,1$ 且其它位相同的两个数所选定的 $p$ 值必须相同，才能保证这两个数都能取得最大取值。
第二种，$a$ 数组的这一位上的值有 $0$ 也有 $1$这个时候这一位上是 $0$ 就必须选 $1$，反之亦然。
这个时候就要求对于这一位分别是 $0,1$ 且其它位相同的两个数所选定的 $p$ 值必须不同，才能保证这两个数都能取得最大取值。
以上两种情况已经涵盖了全部，所以中途出现的其它情况直接返回 $0$ 即可。
时间复杂度 $O(n \log n)$，代码如下(100pts)：
long long solve(int l,int r){
if(l==r) return 1;
int cnt=0,mid=(l+r)>>1;
for(int i=l;i<=mid;i++) cnt+=(p[i]==p[i+mid-l+1]);
if(cnt==mid-l+1) return (solve(l,mid)<<1)%mod;
if(!cnt) return (solve(l,mid)*solve(mid+1,r))%mod;
return 0;
}
int main(){solve(1,(1<<m)-1);}
T3 虫食算
我代码在洛谷交是 AC 的，但是交 becoder 卡了好久死活 90pts 过不去。
这道题其实有高斯消元的正解，但是我们不管，考虑搜索+剪枝。
正常的搜索大家都会，直接 $O(n!)$ 枚举每一位上的数即可，这样就已经可以过掉 30pts 的数据了，然后我们考虑怎么剪枝。
搜索的时候我们选择从最低位开始进行搜索，因为这样我们能在搜索中直接把进位给算出来，就可以少考虑很多情况。
对于每一位我们直接枚举三个字母对应值，原本有就跳过，然后如果三个字母加上进位满足条件，就带着这个值往下搜索。
枚举字母值的时候我们则选择从大到小枚举，因为最高位是不能进位的，所以能进位的就优先放到低位。
通过如上代码就可以在洛谷的评测环境通过了，但是 becoder 的评测机不行，还要剪枝，但我不会了，希望来两个好心人帮我剪。
代码如下(becoder 90pts，Luogu 100pts)：
char a[30],b[30],c[30];
int n,f[30],go[30],s[100];
int gmod(int x,int &y){return x>=n?(y=1,x-n):(y=0,x);}
void dfs(int x){
if(!x){
for(int i=0;i<n;i++) printf("%d ",s['A'+i]);
exit(0);
}
for(int i=n-1,fl1=0;i>=0;i--){
if(s[a[x]]!=-1) fl1=1;
else if(f[i]) continue;
if(!fl1) f[i]=1,s[a[x]]=i;
for(int j=n-1,fl2=0;j>=0;j--){
if(s[b[x]]!=-1) fl2=1;
else if(f[j]) continue;
if(!fl2) f[j]=1,s[b[x]]=j;
int tmp=gmod(s[a[x]]+s[b[x]]+go[x+1],go[x]);
if(s[c[x]]!=-1&&tmp==s[c[x]]) dfs(x-1);
if(s[c[x]]==-1&&!f[tmp]) s[c[x]]=tmp,f[tmp]=1,dfs(x-1),f[tmp]=0,s[c[x]]=-1;
if(fl2) break;f[j]=0,s[b[x]]=-1;
}
if(fl1) break;f[i]=0,s[a[x]]=-1;
}
}
int main(){scanf("%d%s%s%s",&n,a+1,b+1,c+1),fill(s,s+100,-1),dfs(n);}
T4 染色相邻的边
NOIP 巩固练习 5,NOI2011 轻重边。
只不过输出的时候换成了用两点间的路径长减去原来的 ans 值而已，没啥好说的，跳过吧。
标签：tmp,int,题解,30,一位,枚举,becoder,8.31 From： https://www.cnblogs.com/tkdqmx/p/18395265