| Rank | Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 5/113 | 5/11 | O | O | Ø | O | Ø | Ø | Ø | O | Ø | O | . |
O: 当场通过
Ø: 赛后通过
.: 尚未通过
A Knight
solved by ch
ch's solution
B Tree
solved by chelly
chelly's solution
两次树DP即可，第二次树DP的时候可以用前缀和/后缀和优化把复杂度降低到O(n)
C Two Graphs
upsolved by chelly
chelly's solution
先只考虑只有一个图的情况
每个连通块是树或者环套树等价于对于每个无向边都能定向到一个连接点，使得每个点的入度至多为1
于是我们可以在二分图的左边放上点，右边放上边，对于边e(a,b)，点a和点b都向边e连边，那么问题就是个最大权匹配
现在考虑两个图的情况，将表示边的节点拆成两个，对于第一个图中的边e(a,b)，第一个图中的点a和点b向e1连边，对于第二个图中的边e(c,d)，e2向第二个图中的c和d连边，然后e1向e2连边，这些边的cap都是1，只有e1向e2连边的cost是该条边的权值，其它的cost都是0
那么从最左端到最右端的一条流就是表示一种合法的指派，于是问题就转化成了最大费用可行流
D Shopping
solved by chelly
chelly's solution
贪心即可，优先把价格大的降成半价
E Trophies
unsolved
从大到小插入，计算以当前插入的数字为min，对答案的贡献
F Palindrome
upsolved by chelly
chelly's solution
回文中心在s串的情况和回文中心在t串情况类似，我们不妨只考虑回文中心在s串的情况
我们考虑一个回文串去除在s中的回文后缀之后，一定有在s中剩余的前缀和在t中剩余的后缀是对称的，即把t串反过来，这两个小字符串是完全一样的
考虑建出s串和反向t串的广义后缀自动机，考虑同样的一个子串对答案的贡献
设一个后缀自动机节点是u，那么对答案的贡献就是(maxlen[u]-minlen[u]+1)endpos1[u]endpos2[u]*num[u]
num[u]表示以u点里面的子串，在s中有多少个紧跟在后面的回文串，这个东西可以马拉车预处理出来，在自动机上更新
G Stones
upsolved by ch
ch's solution
打sg表找规律
H Travel
solved by chelly
chelly's solution
容易发现把树分成连通块等价于删边，答案就是(inom {n-1} {m-1} * (m-1)!)
I Metropolis
upsolved by chelly
chelly's solution
以所有关键点为源点求解最短路，并记录下每个点是由哪个关键点到达的，我们称其为该点的颜色
考虑从某个关键点u走到另外一个关键点v的最短路径，一定存在路径上的边(a,b)使得连接的两个点a和b颜色不同
并且如果v是从u出发走到的最近关键点，那么该路径上一定只有两种颜色
于是我们可以枚举原图中的每条两个端点颜色不同的边，用它来更新答案
J Graph Coloring I
solved by chelly
chelly's solution
dfs黑白染色即可
K Graph Coloring II
unsolved
Replay
本场由chelly、ch、Feynman1999线下打的。
开场chelly签了一个贪心题，然后ch和Feynman跟榜想A，想了一段时间想不出。chelly后来思考出了B题的解法，上去码码码，成功拿下一血。之后chelly跟榜顺利切了H和J。ch和Feynman一直在思考A题的做法，终于之后ch乱搞搞过了A。之后就基本处于挂机状态了……