果然昨天和别人合照丢的脸今天都加进RP里了
T3是用了dp快速幂（？？？），T1，T2考试的时候把想法都写注释了。
T1：
#include<cstdio> using namespace std; const int maxn=1e6+7; int n; int f[maxn]; int head[maxn]; int nx[maxn<<1]; int to[maxn<<1]; int tp[maxn<<1],cnt; inline void add(int a,int b,int c){ nx[++cnt]=head[a]; head[a]=cnt; to[cnt]=b; tp[cnt]=c; } void init(){ scanf("%d",&n); for(int i=2;i<=n;++i){ int x,y,z; scanf("%d%d%d",&f[i],&x,&y); z=y?(x?2:1):0;//must not,must,no lim add(i,f[i],z); add(f[i],i,z); } } int dp[maxn]; bool g[maxn]; void dfs(int x){ bool leaf=1; for(int i=head[x];i;i=nx[i]){ int t=to[i]; if(t!=f[x]) dfs(t),leaf=0; } if(leaf) return; int cntt=0; for(int i=head[x];i;i=nx[i]){ int son=to[i]; if(son==f[x]) continue; dp[x]+=dp[son]; if(tp[i]==1||(!tp[i]&&g[son])){ dp[x]-=g[son]; ++cntt; } } dp[x]+=(cntt+1)>>1; g[x]=cntt&1; } int main(){ init(); dfs(1); printf("%d ",dp[1]); return 0; } /* 边只有三种，必须翻，可以翻，不能翻 是否存在需要翻转不能翻转的边的情况 不会，因为还要把它翻回去，不如两边分开翻 所以遇到不能翻，直接截断翻转链。 dp[n]表示仅考虑一棵子树内的最少翻转次数。 g[n]表示子树是否需要一条从根引出的翻转链。 先把儿子的dp都加上 必须翻的边 减去儿子的g，记录下来作贡献 不能翻的边 不管 可以翻的边 如果儿子有g，当成必须翻的边处理，否则不管 运用了一个贪心的想法，如果可以尽量把问题拖到父亲解决，代价不会更高 */
T2：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=1e3+7; const int mod=1e9+7; int n,m,ans; bool have_w,have_b; char ch[maxn]; short map[maxn][maxn]; void init(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i){ scanf("%s",ch+1); for(int j=1;j<=m;++j){ if(ch[j]=='W') map[i][j]=1,have_w=1; if(ch[j]=='B') map[i][j]=2,have_b=1; } } } short tmp[maxn][maxn]; void rotate(){ for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) tmp[i][j]=map[i][j]; swap(n,m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) map[i][j]=tmp[j][n-i+1]; } int dp[2][maxn],high[maxn],low[maxn]; void DP(){ for(int i=1;i<=m;++i){ high[i]=n;low[i]=0; for(int j=1;j<=n;++j){ if(map[j][i]==1) low[i]=max(low[i],n-j+1); if(map[j][i]==2) high[i]=min(high[i],n-j); } } for(int j=n;j;--j) dp[0][j]=1; dp[0][0]=0; for(int i=1;i<=m;++i){ bool u=i&1; memset(dp[u],0,sizeof(dp[u])); for(int j=low[i];j<=high[i];++j) dp[u][j]=dp[u^1][j]; for(int j=n;~j;--j) (dp[u][j]+=dp[u][j+1])%=mod; } (ans+=dp[m&1][0]-dp[m&1][n])%=mod; } //保证了dp求出的有高度相等，但是没有全选/全不选 //减去高度相等时多算出的贡献，每种都多算了一次 //高于或等于最高的1,低于最低的2时，可以高度相等。 int pos[3][4]; void uniq(){ pos[1][0]=pos[2][0]=n+1; pos[1][2]=pos[2][2]=m+1; pos[1][1]=pos[1][3]=pos[2][1]=pos[2][3]=0; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ for(int k=1;k<=2;++k) if(map[i][j]==k){ pos[k][0]=min(pos[k][0],i); pos[k][1]=max(pos[k][1],i); pos[k][2]=min(pos[k][2],j); pos[k][3]=max(pos[k][3],j); } } } //have_w&&have_b 包括了0和m ans-=max(pos[2][0]-pos[1][1],0); ans-=max(pos[1][0]-pos[2][1],0); ans-=max(pos[2][2]-pos[1][3],0); ans-=max(pos[1][2]-pos[2][3],0); //减了404m,应为101m if(!have_w&&!have_b) ans+=10; //减了202m,应为10或1m if(have_w&&!have_b) ans+=5; if(!have_w&&have_b) ans+=5; ans%=mod; (ans+=mod)%=mod; } int main(){ init(); uniq(); DP(); rotate(); DP(); rotate(); DP(); rotate(); DP(); printf("%d ",ans); return 0; } /* 对于每一行和每一列，要么清一色，要么各占半壁江山，没有夹在中间的情况 所以在整张图上阴阳的分布是各占据一个直角 把阳的直角放在左下角 把区域看成数轴上柱子的高度，则柱子高度单调不增 强制为阳就是最低高度，强制为阴就是最高高度 然后把图旋转90度，dp4次 貌似高度全都相等的情况要特殊考虑 */
T3：
#include<cstdio> using namespace std; int main(){ puts("0"); return 0; }