XXII Open Cup named after E.V. Pankratiev, Grand Prix of IMO

Contest link: XXII Open Cup named after E.V. Pankratiev, Grand Prix of IMO。

M. Math

题意：给你一个长度为 \(n\) 的数组 \(a\)，求有多少对 \((i,j)\) 满足 \(a_i^2+a_j\) 是完全平方数。\(1\le n,a_i\le 10^6\)。

根据 \(a\) 统计出 \(cnt\) 数据，然后直接暴力枚举值即可。

A. AND

题意：给定一个大小为 \(n\) 的集合 \(S\)，你需要构造一个长度为 \(m\le 5\cdot n\) 的序列 \(a\)，使得 \(\{x|x=\operatorname{AND}_{l\le i\le r}a_i\}=S\)。\(1\le n\le 10^5\)。

求出所有数的 \(\operatorname{AND}\)，如果不存在于 \(S\) 中则必然无解，否则每两个数的中间插入一个所有数的 \(\operatorname{AND}\) 即可。

B. Bruteforce

题意：给定 \(w,k\)，维护一个长度为 \(n\) 的数组 \(a\)，令 \(b\) 为 \(a\) sort 后的数组，每次询问求 \(\sum \lfloor\dfrac{b_i\cdot i^k}{w}\rfloor\)，需要支持 \(a\) 数组单点修改。\(1\le n,q\le 10^5,1\le w,k\le 5\)。

容易用平衡树维护不下取整的和，也容易维护 \(\bmod w\) 为每个值的个数，减一下就算完了，复杂度 \(O(n(w^2+k^2)\log n)\)。

E. Eulerian?

题意：交互。有一张简单图，每次询问可以查询一个点集的导出子图有多少条边，你需要判断这张图是否存在欧拉回路。\(3\le n\le 10^4\)，询问次数 \(\le 60\)。

每次问两个互补的点集，可以求出两个点集间有多少条边，如果是奇数条，那么过去就回不来了，直接随机 \(30\) 次即可。

F. Fancy Formulas

题意：给定质数 \(p\)，每次可将 \((a,b)\) 在模意义下变为 \((2a,b-a)\) 或 \((a-b,2b)\)，\(q\) 组询问，每次给定 \(a,b,c,d\)，问 \((a,b)\) 变为 \((c,d)\) 至少要操作几次，保证 \((a+b),(c+d)\not\equiv0\pmod p\)。\(q\le 10^5\)。

首先发现每次操作和 \(\bmod p\) 是不变的，如果 \(a+b\not\equiv c+d\pmod p\) 则必然无解，否则将 \(a,b,c,d\) 同时除去 \((a+b)\bmod p\)，那么 \(b,d\) 就无关紧要了，相当于每次操作 \(a\to 2a\) 或 \(a\to 2a-1\)，问你最少多少次变成 \(c\)。

容易发现操作次数不超过 \(\log p\)，所以直接枚举答案后 check 即可，复杂度 \(O(q\log p)\)。

H. Hamiltonian

题意：给定 \(k\)，构造一张 \(n\le 20\) 个点 \(m\) 条边的简单无向图，使得其存在恰好 \(k\) 个无序点对 \((u,v)\)，\(u\) 与 \(v\) 间存在哈密顿路径。\(1\le k\le 60\)。

首先对于 \(k\le 2\) 的情况直接输出样例即可。

对于 \(3\le k\le 20\) 的情况，直接构造一个 \(k\) 个点的环即可。

对于 \(21\le k\le 60\) 的情况，先构造一个 \(x\) 个点的完全图，然后再在外面挂一个 \(y\ge 3\) 个点的耳朵，此时的答案是 \(\frac{x(x-1)}{2}+2(x-2)+y\)，打表发现 \(x+y\le 20\) 的情况下能够取到所有的 \(21\le k\le 60\)。

G. Glory Graph

题意：给你一个 \(n\) 个点的完全图，每条边为红色或黄色，定义 \(X\) 为边数比 \(1:5\) 的四元组，\(Y\) 为边数为 \(3:3\) 的四元组，你需要求出 \(X-Y\)。\(4\le n\le 2000\)。

贺一张图：

然后直接用 bitset 计算即可，复杂度 \(O(\frac{n^3}{\omega})\)。

D. Deleting

题意：给定 \(cost(l,r)\) 表示将 \(l\) 和 \(r\) 同时删除的代价。你需要将所有 \(n\) 个数删除，每次只能删除相邻的两个数，定义一种删除方案的代价是所有使用的 \(cost\) 的最大值。你需要求出最小的操作代价。\(2\le n\le 4000\)。

容易列出 \(n^3\) 的区间 dp，一种朴素的想法是二分答案后，然后用 bitset 优化 dp，卡一下常 \(O(\frac{n^3\log n}{\omega})\) 直接过了。

另一种方式是发现有效的 dp 状态数是 \(O(n^2)\) 的，如果能快速找到所有更新的 dp 状态位置，那么就能解决问题了。

当我们将一个 \(f_{l,r}\) 设为 true 后，其实可以直接将 \(f_{l}\) 取反后与 \(f_{r+1}\) 取交，\(f_{r}\) 取反后与 \(f_{l-1}\) 取交，这样所有为 \(1\) 的位置就是新的要更新 dp 值的位置。复杂度优化为 \(O(\frac{n^3}{\omega})\)，可以轻松通过。

L. Little LCS

题意：给你两个长度为 \(2n+1\) 的字符串 \(S\) 与 \(T\)，仅包含字符 \(\text{A,B,C,?}\)，保证相邻的两个字符不同。你需要将所有的 \(\text{?}\) 替换成 \(\text{A,B,C}\) 中的一个，使得 \(S\) 与 \(T\) 的最长公共子序列长度为 \(n\)。

将 \(S\) 与 \(T\) 中的字符相邻两个分成一组，发现每个对应的组至少有一个字符是相同的，因此 LCS 的下界是 \(n\)。

打个表发现一个非常申币的事情：合法的 \((S,T)\) 只有如下的两种之一：

• \(S=\text{ABAB}\dots\text{BABA}\)，\(T\) 的奇数为全部为 \(\text{C}\)，剩下的任意。
• \(S\) 和 \(T\) 的所有偶数位都是 \(\text{A}\)，然后存在一个 \(x\)，其中 \(S\) 的前 \(x\) 个是 \(\text{B}\)，后面是 \(\text{C}\)，\(T\) 的前 \(x\) 个是 \(\text{C}\)，后面是 \(\text{B}\)。

直接按照这两类计算即可，复杂度 \(O(n)\)。

J. Joke

题意：你有两个排列 \(p,q\)，你要将 \(1\sim 2n\) 这些数填到排列上，使得每个排列上填的数的相对大小与 \(p,q\) 相同。通过填上的数对应的大小关系生成 \(01\) 序列 \(s\)，定义 \(f(p,q)\) 为生成的 \(s\) 的个数。现在 \(p\) 给定，\(q\) 的一部分位置未确定，问 \(q\) 的所有不同填发中的 \(f(p,q)\) 之和。\(1\le n\le 100\)。

首先考虑 \(f(\{1,2,3,\dots,n\},q)\)。先钦定 \(s\)，这个 \(s\) 合法判定可以将固定的大小关系小的向大的连边，使得不存在环。容易发现如果存在环，则必然存在四元环。

接下来每次考虑 \(q\) 最大的那个位置：

• 如果这个位置的 \(s=0\)，那么这个点没有出度，因此不可能在这个点上出现四元环，可以直接忽略。
• 如果这个位置的 \(s=1\)，那么这个位置右边的所有位置的 \(s\) 都必须为 \(1\)。

因此可以考虑抽象为如下过程：每次删除序列的最大值，或删除最大值及其右边的所有值，问有多少种选法。容易发现这个方案数等价于 \(q\) 的上升子序列个数。

容易发现 \((p_i,q_i)\) 的位置关系是无关的，所以按照 \(p\) 从 \(1\sim n\) 排序，这样 \(p\) 就无关了。

接下来考虑 dp，令 \(f_{i,j}\) 表示考虑了前 \(i\) 个位置，递增序列上出现了 \(j\) 个未确定的值的递增序列个数。

转移时直接枚举前一个位置，与这个区间内选了多少个未确定的值即可转移，复杂度 \(O(n^4)\)。

I. Intellectual Implementation

题意：给定平面上的 \(n\) 个正交矩形，顶点是整点，不同矩形的横纵坐标不同。问你有多少个三元组 \((x,y,z)\)，满足 \(x,y,z\) 三个矩形两两无交。\(1\le n\le 2\times 10^5\)。

考虑容斥，需要计算的是两个矩形有交的对数与三个矩形有交的对数，首先可以考虑在每个交的右下角进行计算，可以直接容斥计算。

考虑扫描线，需要维护的东西形如一个数组 \(a\)，你需要求出的是 \(\sum\binom{a_i}{2}\) 与 \(\sum\binom{a_i}{3}\)，需要支持的是区间加与全局查询。

考虑用线段树维护，其中根据组合数的意义， \(\sum\binom{a_i+x}{k}=\sum\sum_{t=0}^k\binom{a_i}{t}\cdot\binom{x}{k-t}\)，因此可以直接维护，复杂度一个 \(\log\)，有点难写，先鸽了。