noip2021 训练 2 做题记录

CF1100E Andrew and Taxi

Description

Luogu传送门

给定一个有向图，改变其中某些边的方向，它将成为一个有向无环图。

现在求一个改变边方向的方案，使得所选边边权的最大值最小。

Solution

题目要求最大值最小，明显的二分。

所以我们二分一下边权，然后连大于等于当前二分值的边，利用拓扑排序判断有无环，更新 \(l\)，\(r\) 即可。

算出最大边权之后，我们考虑如何确定边的方向。还是拓扑，从拓扑序小的点向拓扑序大的点连边即可。

CF632F Magic Matrix

Descrip

Luogu传送门

Solution

\[sto\ neeko哥哥\ orz \]

首先转化一下题意：（前两条就不说了），对于 \((i, j)\)，第 \(i\) 行和第 \(j\) 行中，不能存在一列 \(k\) 使得 \(max(a_{i,k}, a_{j,k}) < a_{i,j}\)（感觉好像和没说一样）。

我们对于输入的矩阵中的权值从小到大排个序，然后依次插入矩阵，插入矩阵的权值为 1。

因此，假设枚举到了权值 \(v\)，若 \(a_{i,j}\) 为 1，表示 \(val_{i,j} < v\)。

若 \((i,j)\) 合法，那么第 \(i\) 行和第 \(j\) 行按位与的值不能出现 1，如果出现 1 就输出 NOT MAGIC。

把每一行用 \(bitset\) 维护一下，时间复杂度 \(O(\frac{n^3}{w})\)。

CF1131F Asya And Kittens

Description

Luogu传送门

Solution

水题一道。

并查集维护一下，相邻的联通快强行连边即可。

不知道为什么是紫的 。

CF949C Data Center Maintenance

Description

Luogu传送门

首先吐槽一下谜之题意，这里放上自己的翻译:

给出 \(n\) 个数据中心，\(m\) 份资料。要把 \(m\) 份资料放到其中的两个数据中心备份，需要保证任意时刻都可以至少在一个数据中心进行备份。定义一天有 \(h\) 个小时，每个数据中心在一天内有一小时维护时间 \(u_i\)（\(0 \leq u_i < h\)），在这一小时内该数据中心无法进行备份。

由于某种原因，需要把一些数据中心的维护时间向后推迟 1 小时（一个数据中心的维护时间的向后推迟可能导致有的资料无法在任意时刻进行备份且若 \(u_i = h - 1\) 那么推迟后 \(u_i = 0\)），请你求出最少需要向后推迟多少个数据中心，并把这些数据中心的编号输出出来。

注意：输入的 \(u_{c_1} \ne u_{c_2}\)，意味着刚开始时任意资料都可以在任意时间进行备份。

Solution

通过观察样例可以发现，不管你初始时是否合法都必须有向后推迟的数据中心，即至少一个。

所以题目就是要求我们选择一个点 +1，并将因此而被迫推迟的点都推迟 1，然后计算最少推迟多少个点。

那么我们如何找到哪些点是被迫推迟的呢？

对于一组条件 \(x\) 和 \(y\)：

• 若 \({a_x + 1}\equiv{a_y} \pmod {h}\)，我们就从 \(x\) 向 \(y\) 建一条边。

• 若 \({a_y + 1}\equiv{a_x} \pmod {h}\)，我们就从 \(y\) 向 \(x\) 建一条边。

然后就形成了一张 \(DAG\)，考虑到在一个环里的点，不管选哪一个整个环都会被选，所以可以 \(Tarjan\) 缩点。

然后不难发现，若选择出度不为 0 的点，那么它指向的那个点也会被迫选上，这明显不如只选被指向的点优。

所以我们只用找出度为 0 的点中的 \(siz\) 最小的点即可。

最后附上详细版博客

CF343D Water Tree

Description

Luogu传送门

Solution

树链剖分板子的弱化版，不多说了，顺便推销一波自己的博客 []。

CF85E Guard Towers

Description

Luogu传送门

Solution

水黑。

二分+二分图

显然二分一下曼哈顿距离，然后利用二分图染色判断该距离是否合法。

具体来说，大于当前二分值的点要放到不同的集合，小于等于二分值的点可以放到相同集合，如果两个点不能放到相同集合却已经在相同集合时，不合法。

染色过程中记录一下联通块个数为 \(cnt\)，观察到（样例 1）左部点和右部点可以互换，所以对于一个联通块有两种方案，且由于同一个联通块中的左右部点交换不影响其他联通块，所以方案数为 \(2^{cnt}\)。

CF711D Directed Roads

Description

Luogu传送门

题意也有一点问题，刚开始输入的是有向边。

Solution

看到 \(n\) 个点 \(n\) 条边，显然的基环树（可能是基环树森林），所以我们对于环上的点和非环上的点分别处理。

假设一共有 \(cnt\) 个环，每个环上有 \(d_i\) 个点，我们来分类讨论一下：

• 对于环上的点，我们发现只有两种情况会产生环，即

  • \(1 \rightarrow 2 \rightarrow 3 \rightarrow ··· \rightarrow d_i - 1 \rightarrow d_i \rightarrow 1\)
  • \(d_i \rightarrow d_i - 1 \rightarrow ··· \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow d_i\)

  所以我们用总情况数减去 \(2\)即可。方案数：

  \[ans = \prod\limits_{i = 1}^{cnt}{(2^{d_i} - 2)} \]

• 对于非环上的点，我们发现不论朝哪个方向连，都不会影响是否会产生环，所以方案数为 \(2^{非环上点的个数}\)：

  \[ans = 2^{n - \sum\limits_{i = 1}^{cnt}d_i} \]

至此，我们就讨论完了（事实上还是很简单的），总结一下：

\[ans = \prod\limits_{i = 1}^{cnt}{(2^{d_i} - 2)} \times 2^{n - \sum\limits_{i = 1}^{cnt}d_i} \]

那么如何找环呢？我这里写了个 Tarjan 缩点，大小大于 2 的强连通分量就是环（感觉用牛刀杀鸡了……不管了）。

CF17E Palisection

Description

Luogu传送门

Solution

非常有意思的一道题。

看到回文子串，首先想到的 manacher 算法。emm……但是写了 manacher 之后怎么做呢？

我们发现，求相交的回文子串非常麻烦，所以直接一波正难则反，用总的回文子串数减去不相交的。

接下来考虑如何求不相交的回文子串。

我们开两个数组 \(f_i\)，\(g_i\)。\(f_i\) 表示以 \(i\) 为开头的回文串有多少个，\(g_i\) 表示以 \(i\) 为结尾的回文串有多少个。

看到标签里的\(\color{blue}{前缀和}\)，我们给 \(g_i\) 做个前缀和存到 \(sum_i\) 里，那么 \(sum_i\) 就表示结尾是 \(i\) 及以前的点的回文子串有多少个， 我们发现不相交的回文子串个数就是:

\[res = \sum\limits_{i = 1}^{n}{sum_i \times f_{i + 1}} \]

用总数减去即可。

那么 \(f_i\) 和 \(g_i\) 怎么求呢？

我们发现标签里的 \(\color{blue}{差分}\) 还没有用到标签真是好用。考虑用差分。

我们已经使用 manacher 算法求出了每个点作为回文串的中心时最长的回文半径是多少，设为 \(p_i\)（\(p_i\) 是原字符串扩展后的新串的回文半径，长度就是原串的回文串的长度，如果不懂的话可以去学一下 manacher，这里不再赘述）。

我们发现，一个半径 \(p_i\) 会形成许多回文串，分别是：

\[i - p_i + 1\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + p_i - 1 \]

\[i - p_i + 2\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + p_i - 2 \]

\[i - p_i + 3\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + p_i - 3 \]

\[· \]

\[· \]

\[i - 1\ \ \ \ \sim\ \ \ \ i\ \ \ \ \sim\ \ \ \ i + 1 \]

\[i \]

也就是说，我们要对 \(f_{i - p_i + 1} \sim f_i\) 都 +1，同样的，对\(g_i \sim g_{i + p_i - 1}\) 也都 +1。

这时我们就可以用差分来解决了，即 \(f_{i - p_i + 1}++\)，\(f_{i + 1}--\)，同时对 \(g_{i}++\)，\(g_{i + p_i}--\)。

最后循环一遍统计答案就可以啦，需要注意的是，现在我们已经把原本的字符串扩展过了，所以循环的增幅为 2。

CF40E Number Table

Description

Luogu传送门

Solution

简单计数。

我们首先考虑填一个空的矩阵有多少种方案数。

对于 1 ~ \(n - 1\) 行，我们先把最后一个数单独取出来一个数，剩下前 \(m - 1\) 个数随便填，最后一个数可以让这一行的乘积变成 -1。

同理，不管前 \(n - 1\) 行怎么填，最后一行总能让每一列的乘积变为 -1。

所以总方案数就是：

\[ans = 2^{(n - 1)(m - 1)} \]

下面我们来考虑一下这道题。

首先可以判一波无解，先把结论放在这里：\(n\)，\(m\) 奇偶性不同时，无解。

证明：

每一行，每一列乘积都为 -1，我们可以把这些 -1 乘在一起，即\((-1)^{n + m}\)，再考虑一下这些数乘起来的本质是什么，是不是矩阵中每一个点的平方的乘积呢？是的。也就是说，乘积必为正数，就是 1。但当 \(n\)，\(m\) 奇偶数性不同时，乘积是 -1，矛盾。

证毕.

我们继续来分析，观察到最后一句话：\(0 \leq k < max(n, m)\)

这有什么用呢？

我们假设 \(n > m\)，上面的条件就变为了 \(k < n\)，也就是说，不论你怎么填，必定有一行是空的（一个数都没有）。

我们发现，这样就有上面简化版题目的性质了，即，我们可以不考虑列了。

这时我们也可以套用上面的解法了，\(O(n)\) 枚举每一行，\(ans = ans \times 2^{m - cnt_i - 1}\)，\(cnt_i\) 是第 \(i\) 行 1 的个数，减去 1 是因为要空出来一个数来使这一行的乘积为 -1。

注意：这里也要判一下无解，当有一行全部被填满且乘积为 1 时，无解（显然）。