Codeforces 1354E:Graph Coloring – 题解

主要思路

这个题还是比较简单的。

发现在生成树上放一个 \(2\) 之后,剩下与该点距离为偶数的点都已经确定了。所以对于一个连通块而言,被染成 \(2\) 的方式只有两种。

那么我们可以对这些连通块做一个背包,然后来判断是否有 \(n_2\) 的染色方案。

剩下的点随便染色即可。

继续阅读Codeforces 1354E:Graph Coloring – 题解

LibreOJ#3049. 「十二省联考 2019」字符串问题 – 题解

主要思路

这个题读完之后大概能知道是要建一个反串的 SAM,然后通过倍增定位 \(A, B\) 串然后加边,找最长路即可。

但是发现直接这样做,碰到 \(|A| < |B|\) 的时候会 GG,因为可能会出现在同一个节点上。这个时候我们就通过长度进行排序,给被重复的节点多做几个影子节点即可。

继续阅读LibreOJ#3049. 「十二省联考 2019」字符串问题 – 题解

P3245:[HNOI2016]大数 – 题解

主要思路

佛了。

让 \(p\) 跟 \(10\) 取个 \(\gcd\)。如果互质的话就是数数列 \(a_i = \text{从 i 到 n 表示的数字} \bmod p\) 区间里的同色对数,用莫队搞即可;如果是 \(2\) 那就把 \(0, 2, 4, 6, 8\) 这些尾数染颜色然后数同色对数,这个可以 \(\Theta(n)\),如果是 \(5\) 那就把 \(0, 5\) 染色即可。

继续阅读P3245:[HNOI2016]大数 – 题解

Codeforces 739E:Gosha is hunting – 题解

主要思路

一眼可以看出一个 \(\Theta(n^3)\) 的 DP。其实用双带权二分就可以用 \(\Theta(n \log^2 n)\) 的时间搞了,但是我没写这个写法。

考虑一下被选择时的贡献。\(p_a, p_b\) 是单元贡献,考虑同时被选的贡献 \(1 – (1 – p_a)(1 – p_b) = p_a + p_b – p_a p_b\)。所以我们可以考虑最大费用最大流,来算这个式子。

需要注意的是,我们需要保证每一次代价都是正的,因为我们其实并不需要最大流,而只是相对的最大费用。

继续阅读Codeforces 739E:Gosha is hunting – 题解