team2012-D3-1C
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
=== 0013 ===
{{{
cost[x][y][t], 1<=x<=n, 1<=y<=m, 0<=t<=3
表示第4k+t时刻经过点(x, y)时的代价
对于每一个defender，四个方向处理一下就行，注意这个cost是叠加的。
最后做一次bfs即可，注意结果要用一个pair<cost, time>来处理
}}}
=== 0014 ===
{{{
二分答案然后two-set
第i对：对应节点i*2和i*2+1
构图之后，求一次强连通分支，判断是否存在X和~X在用一个联通分块的情况
}}}
{{{
Components(n * 2);
for (int i = 0; i < n; i++) {
if (id[i*2] == id[i*2+1]) return false;
}
}}}
=== 0015 ===
{{{
一颗有n个节点的树上染c种颜色的方案数是：c*pow(c-1,n-1)
加上任意一条边之后，整个图存在唯一的环，用lca可以求出环的长度k
不妨设：对于长度为k的环，其上的染色方案数为f(k)
f(0)=c,f(1)=0,
f(n)=(c-2)*f(n-1)+(c-1)*f(n-2), n>1
剩下的n-k个节点，染色方案数是：pow(c-1,n-k)
}}}
=== 0016 ===
奇偶性
{{{
int s[2] = {0};
for (int i = 0; i < l; i++) {
for (int j = 0; j < w; j++) {
for (int k = 0; k < h; k++) {
scanf("%d", &a[i][j][k]);
s[(i+j+k) % 2] += a[i][j][k];
}
}
}
if (s[0] == s[1]) printf("Yes\n");
else printf("No\n");
}}}
=== 0017 ===
{{{
分8段处理，对于每一段：
不妨设开头的值为（a,b），那么以后的状态有四种：
(a,b), (a,非b), (非a,b), (非a,非b)
转移矩阵为：
}}}
{{{
mat[0][0] = mat[0][1] = mat[0][2] = mat[1][3] = mat[2][3] = 1;
mat[0][3] = mat[1][2] = mat[2][1] = mat[3][0] = 0;
mat[1][0] = mat[1][1] = mat[3][2] = (q-1+MOD)%MOD;
mat[2][0] = mat[2][2] = mat[3][1] = (p-1+MOD)%MOD;
mat[3][3] = (p + q - 3 + MOD) % MOD;
}}}
然后做一次快速幂乘，最后特判处理即可
=== 0018 ===
{{{
枚举所有的牌，判断加上该牌之后，是否符合要求。
判断：
首先枚举眼，然后判断剩下的牌是否可以每3张一组，牌相同或者成为一个顺
判断方法：只需贪心即可，从最小的牌开始，如果>=3张，就让其中的3张分为一组，否则i,i+1,i+2成为一个顺
如果i+1,i+2的数目不够，return false
}}}0013
{{{
cost[x][y][t], 1<=x<=n, 1<=y<=m, 0<=t<=3
表示第4k+t时刻经过点(x, y)时的代价
对于每一个defender，四个方向处理一下就行，注意这个cost是叠加的。
最后做一次bfs即可，注意结果要用一个pair
}}}
0014
{{{
二分答案然后two-set
第i对：对应节点i*2和i*2+1
构图之后，求一次强连通分支，判断是否存在X和~X在用一个联通分块的情况
}}}
{{{
Components(n * 2);
for (int i = 0; i < n; i++) {
if (id[i*2] == id[i*2+1]) return false;
}
}}}
0015
{{{
一颗有n个节点的树上染c种颜色的方案数是：c*pow(c-1,n-1)
加上任意一条边之后，整个图存在唯一的环，用lca可以求出环的长度k
不妨设：对于长度为k的环，其上的染色方案数为f(k)
f(0)=c,f(1)=0,
f(n)=(c-2)*f(n-1)+(c-1)*f(n-2), n>1
剩下的n-k个节点，染色方案数是：pow(c-1,n-k)
}}}
0016
奇偶性
{{{
int s[2] = {0};
for (int i = 0; i < l; i++) {
for (int j = 0; j < w; j++) {
for (int k = 0; k < h; k++) {
scanf("%d", &a[i][j][k]);
s[(i+j+k) % 2] += a[i][j][k];
}
}
}
if (s[0] == s[1]) printf("Yes\n");
else printf("No\n");
}}}
0017
{{{
分8段处理，对于每一段：
不妨设开头的值为（a,b），那么以后的状态有四种：
(a,b), (a,非b), (非a,b), (非a,非b)
转移矩阵为：
}}}
{{{
mat[0][0] = mat[0][1] = mat[0][2] = mat[1][3] = mat[2][3] = 1;
mat[0][3] = mat[1][2] = mat[2][1] = mat[3][0] = 0;
mat[1][0] = mat[1][1] = mat[3][2] = (q-1+MOD)%MOD;
mat[2][0] = mat[2][2] = mat[3][1] = (p-1+MOD)%MOD;
mat[3][3] = (p + q - 3 + MOD) % MOD;
}}}
然后做一次快速幂乘，最后特判处理即可
0018
{{{
枚举所有的牌，判断加上该牌之后，是否符合要求。
判断：
首先枚举眼，然后判断剩下的牌是否可以每3张一组，牌相同或者成为一个顺
判断方法：只需贪心即可，从最小的牌开始，如果>=3张，就让其中的3张分为一组，否则i,i+1,i+2成为一个顺
如果i+1,i+2的数目不够，return false
}}}