Training-2016.08.11
这场的题目在这里：2014 Asia AnShan Regional Contest
这场Training的代码在这里
计划补的题目：
计划加训的题目：
B题
CLJ跟妹子聊天，模拟聊天窗口的变化过程。
Trick：最后说Bye的时候先和top说，但是也要判是否跟top说过话，没说过话的话也是不用Bye的。
D题
给n个数，你可以炸掉其中的k个数，使剩下的数的方差×num最小。
贪心地考虑：按照x排序后最后剩下的一定是连续的一段，所以枚举是哪一段就可以了。
E题
签到题，DP一下。
3Y：
- 碰到了奇怪的Vim快捷键使得代码中的数字都加了1
- memset(false, 0, sizeof (0));
I题
签到题，模拟。
2Y：没开long long
J题
给一个N×N的棋盘，其中一些点已经被染黑，现在你可以将剩下的格子染成黑或白，问最大的白色正方形的边长为i(i∈0~n)的方案数分别是多少。
做法：DP套DP
假如我们知道了整个棋盘最终的染色方案，我们求其中最大的白色正方形可以用以下DP来做：
g[i][j] = min(g[i-1][j], g[i][j-1], g[i-1][j-1]) + 1;
这里g表示以(i,j)为右下角的最大的白正方形的边长。
我们发现g的计算只与以下两个条件有关：
1. 第i行的染色情况
2. 第i - 1行的g的DP值
所以我们可以在此基础上再设计一个DP来计算答案。
考虑f[i][j][mask]表示前i行，最大的白正方形边长为j，且最后一行的g值为mask的方案数。转移的时候，我们 $ 2 ^ n $ 枚举下一行的染色方案，那么从[i,j,mask]能转移到的新的mask可以通过上面的DP求出，而新的j只需要用原来的j与新的mask中的每个g值取max便可算出。
这个题虽然状态空间很大，但是实际可达的状态数并不是很多，所以可以使用map来存储f[i][j]，即用mask做key。但是在实践中我的姿势不知为何自带大常数，样例数据，谭上将的代码只需6s出解，我的就需要10~11s，最终靠队友吕正re了一个unordered_map才AC，hash表就是快啊0.0只跑了3s（还是在我常数巨大的情况下）
这个题特殊之处在于内层DP的值是作为外层DP的状态的，所以在找当前状态能转移到的目标状态的时候相当于再做一次DP，所以叫DP套DP？
感觉自己的DP姿势又丰富了一些……
An undergraduate at Shanghai Jiao Tong University who studies CS.