题面：https://www.cnblogs.com/Juve/articles/11390839.html
所有官方正解在我的文件里
A. 虎
算法1：我们发现非关键边与黑色边去掉以后,答案就是将所有度数为奇数的点作为路径的端点,所以记去掉非关键边与黑色边以后度数为奇数的点的个数为s,而一条路径有2个端点,所以答案就是$frac{s}{2}$。
注意映射
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 1000005
using namespace std;
int n,ans=0,du[MAXN],id[MAXN],tot=0;
signed main(){
scanf("%d",&n);
for(int i=2,x,y,z;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
if(z==0){
if(id[i]) id[x]=id[i];
else if(id[x]) id[i]=id[x];
else id[x]=id[i]=++tot;
}
if(y==0){
if(!id[i]) id[i]=++tot;
if(!id[x]) id[x]=++tot;
du[id[i]]++,du[id[x]]++;
}
}
for(int i=2;i<=tot;i++){
if(du[i]&1) ans++;
}
printf("%d
",(ans+1)/2);
return 0;
}
算法2：不妨设0号点为根,那么将i到j的路径取反等价于将0到i和0到j的路径取反,因此只要求出最少需要将多少条到根的路径取反,然后除以二上取整就是答案。用f[i]表示i的子树中所有边(包括 i 连向父亲的边)满足条件时的最少取反路径数,只要先对i的所有儿子的f值求和,然后判断i连向父亲的边是否满足条件,如果不满足再+1即可。
B：阴阳
放个代码就跑
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 1005
using namespace std;
const int mod=1e9+7;
int n,m,ans=0,sum_b[MAXN][MAXN],sum_w[MAXN][MAXN];
char ch[MAXN],app_b=0,app_w=0;
int work1(){
int f[MAXN][MAXN]={0},res=0;
f[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
if(sum_w[i][j]) break;
if(sum_b[i][m]-sum_b[i][j]) continue;
for(int k=0;k<=j;++k)
f[i][j]=(f[i][j]+f[i-1][k])%mod;
if(i==n) (res+=f[n][j])%=mod;
}
}
return res%mod;
}
int work2(){
int f[MAXN][MAXN]={0},res=0;
f[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
if(sum_b[i][j]) break;
if(sum_w[i][m]!=sum_w[i][j]) continue;
for(int k=0;k<=j;++k)
f[i][j]=(f[i][j]+f[i-1][k])%mod;
if(i==n) (res+=f[n][j])%=mod;
}
}
return res%mod;
}
int work3(){
int f[MAXN][MAXN]={0},res=0;
f[0][m]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
if(sum_w[i][j]) break;
if(sum_b[i][m]-sum_b[i][j]) continue;
for(int k=j;k<=m;++k)
f[i][j]=(f[i][j]+f[i-1][k])%mod;
if(i==n) (res+=f[n][j])%=mod;
}
}
return res%mod;
}
int work4(){
int f[MAXN][MAXN]={0},res=0;
f[0][m]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
if(sum_b[i][j]) break;
if(sum_w[i][m]-sum_w[i][j]) continue;
for(int k=j;k<=m;++k)
f[i][j]=(f[i][j]+f[i-1][k])%mod;
if(i==n) (res+=f[n][j])%=mod;
}
}
return res%mod;
}
int work5(){
int res=0;
for(int i=0;i<=n;++i){
bool flag=0;
for(int j=1;j<=i;++j)
if(sum_w[j][m]){
flag=1;break;
}
if(flag) break;
for(int j=i+1;j<=n;++j)
if(sum_b[j][m]){
flag=1;break;
}
if(flag) continue;
res++;
}
return res%mod;
}
int work6(){
int res=0;
for(int i=0;i<=n;++i){
bool flag=0;
for(int j=1;j<=i;++j)
if(sum_b[j][m]){
flag=1;break;
}
if(flag) break;
for(int j=i+1;j<=n;++j)
if(sum_w[j][m]){
flag=1;break;
}
if(flag) continue;
res++;
}
return res%mod;
}
int work7(){
int res=0;
for(int i=0;i<=m;++i){
bool flag=0;
for(int j=1;j<=n;++j){
if(sum_w[j][i]){
flag=1;
break;
}
if(sum_b[j][m]!=sum_b[j][i]){
flag=1;
break;
}
}
if(flag) continue;
res++;
}
return res%mod;
}
int work8(){
int res=0;
for(int i=0;i<=m;++i){
bool flag=0;
for(int j=1;j<=n;++j){
if(sum_b[j][i]){
flag=1;
break;
}
if(sum_w[j][m]!=sum_w[j][i]){
flag=1;
break;
}
}
if(flag) continue;
res++;
}
return res%mod;
}
signed main(){
//freopen("test.in","r",stdin);
//freopen("b1.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",ch+1);
for(int j=1;j<=m;j++){
sum_b[i][j]=sum_b[i][j-1];sum_w[i][j]=sum_w[i][j-1];
if(ch[j]=='B') sum_b[i][j]++,app_b=1;
if(ch[j]=='W') sum_w[i][j]++,app_w=1;
}
}
if(!app_b) ans++;
if(!app_w) ans++;
(ans+=work1())%=mod;
(ans+=work2())%=mod;
(ans+=work3())%=mod;
(ans+=work4())%=mod;
(ans-=work5())%=mod;
(ans-=work6())%=mod;
(ans-=work7())%=mod;
(ans-=work8())%=mod;
ans%=mod;
printf("%d
",ans);
return 0;
}