duel records
感觉最近不 duel
就完全没法集中精力做题。。。我才不会告诉你我写这东西也是因为不想做题。
初始 rating：\(\color{orange}{2368}\)。
#1 CF1438C Engineer Artem (*2000)
\({\color{red}\texttt{Lose}},{\color{orange}{}^{2368}}\searrow\color{orange}{}_{2240}\)。
对面那哥们 3min 秒了，我脑子没转过弯来。
其实是唐题，你直接黑白染色，黑点变奇数白点变偶数就完了。
#2 CF698C LRU (*2400)
\({\color{green}\texttt{Win}},{\color{orange}{}_{2240}}\nearrow\color{orange}{}^{2264}\)。
匹配到了 lbw 大神。
直接考虑倒序操作，一个东西进去就不动了。
那么直接状压哪些东西已经进去了，然后 dp 计算其概率，进到 \(k\) 个就统计贡献即可。
注意如果没东西能进（剩下的概率全是 \(0\)）也要返回。因为这个 corner case
挂了 3 发
#3 CF350E Wrong Floyd (*2200)
\({\color{green}\texttt{Win}},{\color{orange}{}_{2264}}\nearrow\color{orange}{}^{2284}\)。（eps 的优势）
考的是你有没有很好地理解 Floyd。
首先那 \(k\) 个点本身是没用的，直接按 \(1\sim k\) 做然后对应过去就行了。
\(k=n\) 显然是对的。下设 \(k<n\)。
考虑 Floyd 算法，做完 \(k\) 轮本质上是计算了以 \(1\sim k\) 为中转点时的距离。
先钦定两个点使它们的距离挂掉。注意到 \(\le k\) 的点会使对它进行的那一轮无效，所以不妨选择 \(1,2\)。
显然 \(1,2\) 间不能有边。
吗德不会讲了，反正边数上界是 \(m\le\frac{n(n-1)}2-k+1\)，构造是 \(2\sim n\) 连完全图，\(1\) 向 \((k+1)\sim n\) 连边。小于上界随便删点边即可。
#4 CF1059E Split the Tree (*2400)
\({\color{red}\texttt{Lose}},{\color{orange}{}^{2284}}\searrow\color{orange}{}_{2191}\)。（比对面晚 eps 分钟交，结果还挂了好几发。）
唐题，咋想了半天写了半天。
实际上一个点被盖多次也可以把一些链缩回去来达到恰好一次。所以可以当每个点至少覆盖一次。
注意到如果一个点为一条链的下端点，那上端点肯定越往上越优。这个上端点直接倍增啥的算下就行了。
然后易证从下往上贪就是对的。（一个点没被它的子树盖住就必须从它往上盖）
#5 CF1628D2 Game on Sum (Hard Version) (*2400)
\({\color{green}\texttt{Win}},{\color{orange}{}_{2191}}\nearrow\color{orange}{}^{2204}\)。
对面好像是个题解管理……？还跟我互关了……？上一场的对手还凑热闹来交这题了……？
首先 \(k\) 没用，单纯乘了个系数。可以当 \(k=1\) 做。
考虑 dp，\(dp_{n,m}\) 表示 \(n,m\) 的答案。
不难写出转移
\[dp_{n,m}=\max_{0\le x\le 1}\min\{dp_{n-1,m-1}+x,dp_{n-1,m}-x\}\]
（其中 \(x\) 是实数，如果 \(m<0\) 或 \(m>n\) 就是 \(+\infty\)。）
然后就能过 easy ver 了。
考虑优化，不难发现 \(dp_{n,0}=0,dp_{n,n}=n\)。
然后看转移式：如果 \(dp_{n-1,m}-dp_{n-1,m-1}\le 2\)，那么显然有 \(dp_{n,m}=\dfrac12(dp_{n-1,m}+dp_{n-1,m-1})\)。
然后这个条件是成立的，证明留作习题。
那么考虑计算每个 \((i,i)\) 对答案的贡献（实际上还有 \((i,0)\) 的，但是因为是 \(0\) 可以忽略掉）。
那么转化成：\((i,j)\) 可以走到 \((i-1,j)\) 或 \((i-1,j-1)\)，求 \((n,m)\) 首次走到 \(x=y\) 的位置是 \((i,i)\) 的方案数。
这玩意显然就是一堆组合数，贡献就乘一个 \(2\) 的负几次方就行。时间复杂度 \(\Theta(n)\)。