ICPC2017北京

orz hhw posted @ 2017年11月23日 08:57 in 做题记录 with tags ACM 解题报告 , 129 阅读

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)$。