Training-2016.08.08
这场比赛可以在这里找到2012-2013 ACM-ICPC, Central Europe Regional Contest (CERC 12)
打算补的题目：B,G(已补),K
这次训练的代码在这里 Training-2016.08.08
A题
总共20个城市，每次枚举破产的是谁， $ 2^{20} $ 更新剩余所有城市的sum，用mask存储状态，避免重复计算。
WA：行末空格，读错题意，理解错输出格式。
C题
写段代码打个表即可。
D题
考虑每个点i作为单独出现的点，则它可以使得左端点在(last[i] + 1, i), 右端点在(i, next[i] - 1)的子串都合法。
其中last[i]表示a[i]上次出现的位置，next[i]表示a[i]下一次出现的位置。
所以问题就转化成了给你二维平面上一些矩形，问是否将整个上三角区域全部覆盖。
我的问题在于：
1. 求面积并的姿势太丑了，HDU 1542 这个写法中change太繁了，考虑到我们并不需要区间查询，只考虑线段树的根的sum，所以不需要标记下传，而且，我们的-1和+1的位置是一一对应的，不需要考虑标记合并啥的。。。反正各种特殊，所以直接update就可以0.0
2. 加了特判：如果相邻两个元素相同，就不用判了，直接返回boring。
E题
最后这个串其实展开是一个树结构，叶子是真·字符串，其他节点都是代表字符串的组合。
我们可以在这棵树上贪心地考虑：先让左儿子尽可能多的匹配，再让右儿子匹配……一个重要的剪枝是：如果当前节点代表的字符串中不含当前要匹配的这个字母，就return，这样可以保证我们最多走到2000个叶子节点，再加上树高最高500，就可以在时限内出解了。
G题
问给定n个点，分别属于k种颜色，每次可以选取从L到R，高度不超过H的一个矩形区域，问包含颜色少于k的区域中，包含点数最多是多少。
容易发现我们可以对y排序，从下向上做（解决H的限制），那么L和R怎么搞呢？我们枚举顶部被哪个点卡住（不包含的颜色是谁），用set找到这个点左右出现的同色点的x坐标，就可以找到一个L和R，使得从L到R，从0到H的区域内不包含当前枚举的这个点的颜色，然后计数可以用树状数组维护。最后再把所有的无上界的L到R区间枚举一遍即可。
H题
签到题，模拟，飞镖打靶，每个区域有个得分，直接用int判距离就可以了。
J题
有n个任务，两个实验室，每个任务都只能在其中一个实验室做，一些任务必须要在另一些任务之前做，问最小的换实验室次数。
做法：跟拓扑序有关，开两个队列，每次把当前实验室中所有能做的都做了，再把所有度数为0的节点放进相应的队列中，注意这里可以继续做当前实验室中新加进来的任务，不能做了就切换，ans++
An undergraduate at Shanghai Jiao Tong University who studies CS.