training-2016.08.16
题目在这里Andrew Stankevich Contest 34
代码在这里Our code
B题
题意：定义反回文数为：反着读和正着读的时候，没有一位是相同的。给一个x，问大于x的最小的反回文数是多少。(x <= 10^100 )
做法：发现反回文数的长度一定为偶数，所以当x为奇数的时候直接输出100…000111…110即可（即首尾为1、0，中间前一半为0，后一半为1）
当x为偶数的时候，如果出现冲突，显然改后一半比修改前一半要优，所以先将x+1，再从中间往两边开始贪心。如果到某一位不合法了，则将其+1，右边的数全部置为0，如果+1时出现进位，则退回去重新做（如果这时整个串长度变成奇数则用第一种方法处理）
E题
题意：n个人，每个人有一个编号，你每次可以喊：编号总和为sum的number个人过来。要求不能产生歧义，问前n-1个人已经编好号以后，第n个人的编号最小是多少？（递归的）
爆枚，打表，找规律。
F题：
题意：n×m的棋盘，每个格子有一枚硬币，正面朝上或反面朝上（废话），两个人轮流翻硬币，每次选一个正面朝上的(i,j)将其翻转，再选一个i’ < i, j’ < j, 翻转(i’,j),(i,j’),(i’,j’)这三个位置上的硬币(i’和j’可以为0，当某一个坐标为0时忽略这个位置)
做法：猜测每个硬币是独立的，每个硬币翻过去以后再将另外的三个位置翻过来，就相当于在那三个位置再放一枚石子（模2意义），所以就跟取石子一样了……吧……
SG[x][y] = mex(SG[i][y] ^ SG[x][j] ^ SG[i][j])
然后跑一遍就可以了……
I题
题意：给一棵树，问最少加多少条边，可以使得原图存在一条哈密顿回路。
考虑加的边最少，也就是让树上保留的边最多，且满足每个点的度数小于等于2。
- dp[x][0]表示从x的父亲连向x的边删掉，x子树中最少删边数。
- dp[x][1]表示从x的父亲连向x的边保留，x子树中最少删边数。
- 转移的时候，如果x连向父亲的边保留，则儿子中最多有一个保留连向父亲的边。否则最多可以有两个。
An undergraduate at Shanghai Jiao Tong University who studies CS.