ICPC2017北京
A - Domains
回来自己写写吧
B - K-Dimensional Foil
不懂线代
C - Graph
给定一个$N$个点$M$条边的无向图，现在$Q$次询问编号为$[L,R]$的点构成的子图中联通的点对数。$N,M\leq50000,Q\leq100000$。
考虑按点度数分块，将连续一段度数不超过$\sqrt{n}$的点分为一段，若一个点度数大于$\sqrt{n}$单独分段。每个询问由中间一大段整段和两边的散点组成，那么对中间一大段整段相同的一起处理。先枚举整段的左端，然后往右扫，也就是在并查集上加边，当扫到端点时处理询问。对于一个询问，最多修改$\sqrt{n}$个点，那么将这些点抠出，建出一个新的虚并查集，在虚并查集上加边更新答案即可。这样大并查集要做$O(\sqrt{n})$遍，每次$O(n)$；询问有$Q$个，每次$O(\sqrt{n})$，于是总复杂度$O(n\sqrt{n}+Q\sqrt{n})$。
D - Chinese Checkers
给你一个六角跳棋，让你模拟其操作
直接建坐标系模拟即可，难度不大。
E - Cats and Fish
按吃的速度排序暴力处理
F - Secret Poems
不是我的题
G - Liaoning Ship's Voyage
不是我的题，可以写一下
H - Puzzle Game
给定一个$n*m$的矩阵，其中每个数的大小为$a_{i,j}$，可以将其中一个数修改为$P$，使得最大的子矩阵的值最小。$n,m\leq150$。
考虑枚举修改每一个数$a_{i,j}$，那么只要预处理出第$1~i-1$行，第$i+1~n$行，第$1~j-1$列，第$j+1~n$列的最大子矩阵，并求出包含$a_{i,j}$的最大子矩阵即可。
这几个问题的处理方法是类似的，例如处理行的，可以枚举上端点和下端点，那么就变成了一列数上的问题。那么记一下前缀和后缀的最小值，正反各做一遍就可以得到包含某一列的最大值，然后再将这个答案通过DP更新到每一行上就可以得到包含$a_{i,j}$的最大子矩阵。所有的操作时间复杂度都是$O(n^3)$。
I - Colored Nodes
被坑死了
J - Pangu and Stones
石子合并，不过每次可以合并$[L,R]$颗石子，$n\leq100$
一样地DP就好了，枚举合并多少颗石子，时间复杂度$O(n^4)$。
评论 (0)
