目录
A. 【2018普转提day22专题】下棋
小A和小B在下棋。
这张棋盘是\(n\times m\)的。每一个格子要么是黑色的，要么是白色的。两个人轮流进行操作。A先手。每一次可以选择一个黑色的格子，以这个格子为右下角，棋盘左上角为左上角，将这个矩阵的所有格子的颜色由黑变成白，由白变成黑。如果找不到一个黑色的格子，那么那个人就输了。
现在两个人都想让A赢，请问谁能赢呢。
输入格式
第一行一个整数\(T\),表示有\(T\)组数据。
每组数据第一行两个整数\(n，m\)，表示棋盘的大小。
接下来\(n\)行每行\(m\)个字符B（黑色）或者W（白色）。
输入格式
对于每组的每个询问，输出一行，如果A赢输出“szh”，B赢输出”pog”(不含引号)。
样例1
input
3
2 2
BW
WW
2 2
WW
WW
2 2
WB
BWoutput
szh
pog
pog限制与约定
对于\(20\%\)的数据，\(T=1\)
对于另外\(30\%\)的数据，\(n,m\le 3\)
对于另外\(10\%\)的数据，\(n=1\)
对于\(100\%\)的数据，\(T,n,m\le 100\)
时间限制：1 s
空间限制：512 MB
B. 【2018普转提day22专题】子矩阵
小A有一个\(n\times m\)的矩阵！
求他所有子矩阵的权值和的和。
输出答案对\(2^{32}\)取模的值。
输入格式
第一行两个整数\(n,m\)，表示矩阵的大小。
接下来\(n\)行，每行\(m\)个数表示\(a_{i,j}\)。
输入格式
输出一行表示该矩阵的价值。
样例1
input
2 3
2 3 3
6 6 6output
174限制与约定
对于\(10\%\)的数据\(n,m\le 10\)
对于另外\(20\%\)的数据\(n,m\le 100\)
对于另外\(20\%\)的数据\(n,m\le 1000\)
对于\(100\%\)的数据\(n\times m\le 1000000,0\le a_{i,j}\le 10^9\)
时间限制：1 s
空间限制：512 MB
C. 【2018普转提day22专题】砝码
小A手里有\(n\)个砝码。每个砝码有质量\(a_i\)。
定义这\(n\)个砝码的实用度为用这\(n\)个砝码的某个子集能表示出多少个不同的质量和。
现在，小A可以修改其中一个砝码的重量。现在，他想问修改那个砝码的重量后可以使得实用度最大呢？
如果有多组方案的话，输出编号最小的。
输入格式
第一行一个整数\(n\)。
接下来\(n\)行，每行一个\(a_i\)。
输入格式
一行一个整数表示编号。
样例1
input
4
1
4
5
5output
3限制与约定
对于\(30\%\)的数据，\(n\le 20\)
对于另外\(20\%\)的数据\(n\le 100,a_i\le 100\)
对于\(100\%\)的数据\(n\le 100,1\le a_i\le 7000\)。
时间限制：1 s
空间限制：512 MB
D. 【2018普转提day22专题】三元组
有一个序列\(A_i\)，\(A_i\in \{0,1,2\}\)。
每个值\(A_i\) 有一个权值\(P_i\)。如果两个值的权值\(P_i\) 和\(P_j\) 满足\(P_i\ge 2P_j\)，那么\(A_i, A_j\) 不能共存。
称\(A_i\) 的一个子序列的特征三元组为\((Sum_0, Sum_1, Sum_2)\)，其中\(Sum_p\) 为子序列中的\(A_i=p\)的个数。当然这里要求所有值可以共存。
求：\(A_i\) 的所有合法子序列的特征三元组的种类数目。
输入格式
第一行，一个整数\(N\)，代表序列内元素的数目。
以下\(N\) 行，每行两个整数\(A_i\),\(P_i\)，描述了一个元素
输入格式
一个整数，为特征三元组的种类数目。
样例1
input
3
0 2
1 3
2 4output
6样例2
限制与约定
对于\(20\%\)的数据，\(N\le 20\)。
对于\(40\%\)的数据，\(N\le 50\)。
对于\(60\%\)的数据，\(N\le 200\)。
对于\(80\%\)的数据，\(N\le 2000\)。
对于\(100\%\)的数据，\(1\le N\le 200000\)。
对于所有数据，保证：\(Ai\in \{0, 1, 2\}，0＜P_i\le 10^9\)。
时间限制：1 s
空间限制：512 MB