T1 GCD和XOR 100/100
题意
规律题，打表找规律即可发现
a xor b >= a - b >= gcd(a, b)，
如果 a xor b = gcd(a, b) = c 则 c = a - b
枚举倍数c和a判断b即可
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
long long ans[maxn+10];
int T,n;
int main(){
for(int c=1;c<=maxn;++c){
for(int a=c*2;a<=maxn;a+=c){
int b=a-c;
if((a^b)==c) ans[a]++;
}
}
for(int i=1;i<=maxn;++i){
ans[i]+=ans[i-1];
}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("%d
",ans[n]);
}
return 0;
}
T2 30/0
一道数学题，考场打的2x2的暴力，结果发现推错了2x2这种情况，爆0。
解析
棋盘上黑白格染色。曼哈顿距离偶数：奇偶性相同。
枚举有几种颜色分到白格，组合数计算即可。
注意预处理，时间还是比较宽裕的。
为了不重复计数，考虑枚举严格用了i种颜色，我们再枚举分配j种给白集合。设白集合、黑集合大小分别为s1,s2，那么这种分配方案对答案的贡献为 (C^k_i) (C^k_i) (f_{s1,j}) (f_{s2,i-j}) (j!) ((i-j)!)
(f_{i,j}) 表示第二类斯特林数，表示将i个数分配到j个集合的方案数。
(f_{i,j}) = (f_{i-1,j-1}) + (f_{i-1,j}) ( imes j)
(f_{0,i}) = (0^i)
这些东西都可以预处理。
注意边界要开好，不然n=1,m=1情况会错。
时间复杂度$ O(n^2 m2+qK2) $。
代码
#include<bits/stdc++.h>
using namespace std;
const long long p=1000000007;
int T,n,m,k,s1,s2;
long long c[410][410],f[410][60],fact[410],ans;
bool mape[25][25];
int main(){
scanf("%d",&T);
c[0][0]=1;c[1][0]=c[1][1]=1;
for(int i=2;i<=405;++i){
for(int j=0;j<=i;++j){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
}
f[0][0]=1;
for(int i=1;i<=405;++i){
for(int j=1;j<=50&&j<=i;++j){
f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%p;
}
}
fact[0]=1;
for(int i=1;i<=405;++i){
fact[i]=(long long)i*fact[i-1]%p;
}
while(T--){
scanf("%d %d %d",&n,&m,&k);
s1=0,s2=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mape[i][j]=(i&1)^(j&1);
s1+=mape[i][j];
s2+=1^mape[i][j];
}
}
ans=0;
for(int i=1;i<=k;++i){
for(int j=0;j<=i;++j){
(ans+=(((((c[k][i]%p*c[i][j])%p*f[s1][j])%p*f[s2][i-j])%p*fact[j])%p*fact[i-j])%p)%=p;
}
}
printf("%lld
",ans%p);
}
return 0;
}
T3 10/10
题意
给出两个根两棵树，问让它们形态相同要添加几个节点。
这道题还没学，考试直接输2，10 pts
解析
树形动态规划。
如何计算两棵子树的距离值？计算两棵子树所有儿子之间互相的距离值，然后二分图最优匹配即可。
二分图最优匹配可以用网络流做，也可以KM。
对于二叉树的数据，直接枚举和哪个儿子匹配也可。
代码（以后来写）