「CometOJ」2019国庆欢乐赛

Link

A

只有三种情况，讨论即可

B

一个小贪心

sort (A + 1, A + 5 + 1);
for (int i = 1; i <= 5; ++i) ans1 += A[i];
for (int i = 1; i < 5; ++i) ans2 += A[i];
cout << min (ans1 / 2, ans2) << endl;

C

随便数点

D

当$n \le 10^5$时，可以枚举做了$Q$张试卷，剩下的题按时间从小到大做

$n$更大时，直观的想法是猜答案关于$Q$单峰。但实际上函数会有一部分是平的（斜率为$0$），无法三分

于是考虑和$m$相关的做法：暴力做法在枚举做完$Q$张试卷后，剩下的题按顺序做到第$P$种。考虑枚举这个$P$，在枚举出$P$后，合法的$Q$是一段区间$[Q_l, Q_r]$，并且答案在$[Q_l, Q_r]$上单调（可以感性理解）

因此只需要对于每个$P$，计算$Q_l, Q_r$处的答案即可

E

对$n$奇偶分情况讨论，$O(1)$直接计算答案

F

先把原题的$a_i$都除10，最后再乘回来

若不允许超速，那么每个点会有一个速度上限$lim_i$。它们之间相互限制，即$lim_i = \min \{a_i,lim_{i - 1} + 1, lim_{i + 1}+ 1\}$。然而限制关系不会互相影响（即不会从左边限制到右边，再又限制回左边），所以可以从前后分别扫一次更新$lim$值

允许超速的话，相当于把某个$a_i$设成$\infty$. 显然只有$lim_i = a_i$的$i$才可能超速

对于每个关键点暴力重新算一遍$lim$是$O(n^2)$的，注意到算当前关键点的答案时，上一个关键点之前和下一个关键点之后的$lim$是不会变的，所以每次只需要处理到前后第一个关键点位置即可，均摊复杂度$O(n)$

G

[后缀自动机] [字符串]

建SAM，每个节点存在原串中最前的位置。查询时暴力匹配，用$\ge c$的边更新答案

H

[拓扑排序] [博弈]

sol from xcy

设二元组$(x,y)$表示当前要进行操作的人持有$x$, 不进行操作的人持有$y$. 则必胜点为$(x,0)\ (x\in[1,n-1])$. $(x,y)$可转移到$(y,(x+y)\ mod\ n),(y,xy\ mod\ n)$.

如果是DAG, 可以直接确定每个点为必胜点还是必败点. 但会有环.

如果不考虑环边, 一个点为必胜点, 则加上环边它仍为必胜点, 因为走到那个点的人会往必胜的那条边走. 而如果为必败点, 走到那个点的人不希望自己输, 于是会走到环上, 而无论环长为奇数还是偶数, 都可以无限地走下去, 故为平局.

因为有环所以才存在平局，否则每个点的状态都是确定的！

故可以从$(x,0)$开始反推. 如果当前点为必败点, 则连向它的点为必胜点. 如果当前点为必胜点, 则先不管连向它的点. 等到有两个必胜点同时被一个点连向时, 该点就是必败点(除$(x, 0)$外每个点出度都为$2$). 最后没有被扩展到的点一定为平局.

注意环上的必败点不能被扩展到, 只要在环上连向的点是必胜点, 另一条边连向的也是必胜点, 它就可以被确定为必败点. 而平局点也不一定在环上, 因为可能出现一个点连向环上的平局点的情况, 此时该点也是平局点.