CCPC Online 2025 游寄
赛时
随机 roll 题，先 roll 到 \(K\) 然后没看懂，又 roll 到 \(E\)
谁家好人上来就把两道签到题就 roll 完了（）
和队友讨论了一下 \(E\)，发现很简单，队友推了个式子过了
回头一看，发现自己上来先把两个签到 roll 到了
然后转头告诉队友说 \(G\) 会了，我先写 \(G\)
写了一会发现不对，分块的话怎么优化都是 \(O(n\sqrt{n}\log n)\) 的，交了一发 \(TLE\)，先换题了
队友在看 \(K\)，给我讲了一下题意和思路，根据队友发现的规律，大胆猜测倒序就是最优解，交了一发过了
然后和队友交换题目，我看 \(A\) 队友重构 \(G\)
过了不久，我推了个式子，验算了一下是对的，果断换下队友开写
第一发少考虑情况，第二发过了
又过了一会，队友的 \(G\) 重构完事了，交了两发都 \(T\) 了，同时我在看 \(C\)，发现这个就是超级钢琴，简单想了一想细节会了
跟队友说你先别调了我写，然后第一发多测不清空 \(WA\)，害得又花了 \(20min\) 写了拍子和对拍，过了
然后剩下 \(40min\)，两人对着代码瞪了半天，发现队友写的复杂度是错的
请输入文本
然后紧急想新做法，最后 \(20min\) 的时候想到根号分治，思路会了但是写完只剩下 \(5min\)，调了半天没过
寄
题解&补题
E
E题意
两个人打比赛，采用 \(n\) 局 \(\frac{n + 1}{2}\) 胜（\(n\) 是奇数）制，现在已知打了 \(m\) 局分出胜负，问至少看多少局能够知道赢家
E题解
假设 \(A\) 赢了，那么他赢得次数是 \(a=\frac{n+1}{2}\)，而 \(B\) 赢的次数是 \(b=m-a\) 次
设 \(c=a-b\)，那么安排前 \(b\times 2\) 场，双方各赢一半，是猜不出谁最后赢的
只有再看一局才能确定谁赢
最终答案是 \(b\times 2 + 1\)
K
K题意
定义一个长为 \(n\) 的排列的权值是，将这个排列循环位移 \(n\) 次，每位移一次都计算其置换环的数量，将数量累加起来就是这个排列的权值
现在给定 \(n\le 10^3\)，要你构造一个排列，使其权值最大。给出构造方案
K题解
诈骗题
手玩发现，倒序的答案是最大的，每次的数量都是 \(\frac{n}{2}\)（大 \(1\) 或小 \(1\)）
A
A题意
给你一个 \((n+1)\times (m+1)\) 的矩形（\((0,0)\to (n, m)\)）
你要对其中的每一个整点，求以这个整点为一个顶点，其他顶点也是整点的正方形数目，要求正方形必须完全被矩形包含，边长不必是整数
A题解
考虑枚举另一个相邻的顶点，不妨设这个顶点是 \((a+x,b+y)\)，这里强制 \(x>0,y\ge 0\)（其他象限只需旋转整个图形即可），另一条以 \((a,b)\) 为顶点的边为这条边逆时针旋转 \(90\degree\)
然后其他两个点的坐标都可以求 \((a-y,b+x),(a+x-y,b+x+y)\)
然后唯一的限制就是这四个点都在矩形内（这里将 \((a,b)\) 平移到 \((0,0)\) 处）
发现对于 \(x, y\) 产生若干限制：
- 对 \((x, y)\): \(x\le n,y\le m\)
- 对 \((x+y,x-y)\): \(x+y\le m\)
- 对 \((-y,x)\): \(x\le m,y\le a\)
建立一个 \(x,y\) 的平面直角坐标系，发现限制变成了一条斜率 \(k=-1\) 的 \(x+y\le m\) 的直线和两条垂直于坐标轴的直线，求一下里面的面积就好
C
C题意
现在有 \(n\) 个点，有一个常数 \(k\)，每个点有一个权值 \(t_i\)
在两个点之间连线的代价是 \((t_i+t_j)\mod k\)
问你将所有点连成一个连通块的最小代价
C题解
超级钢琴+启发式合并
首先先排序
然后考虑，对于一个点 \(i\)，他最优的链接方案就是，在数轴上依次排开所有点，然后找到 \(k-t_i\) 这个位置放一个指针，一直向后推直到有一个点，那么连接这个点就是最优的（如果右面没有点就从 \(0\) 开始向右推）
考虑和超级钢琴一样的做法，每一个点都找一个最优的链接点，然后扔进堆里边
每次找一个最低的代价联边，然后给这个点再找一个次优的点扔进堆里面
如果当前堆顶的一对点已经在一个连通块里就推到下一个
但是只是这样的话，每个点最多（其实是必然）向后推 \(n\) 次，最后复杂度变成 \(n^2\) 没法接受
考虑到每次操作最浪费时间的就是有很多同连通块的次优点必须走一遍才知道同连通块
不难想到，在数轴上将相邻同连通块的并到一起，遇到的时候直接跳过去
启发式合并一下，每次将小的合到大的上面，然后周围有同连通块就并到一起
做完了
G
G题意
给你一个长度为 \(n\le 10^5\) 的数列 \(A\)，每次给出询问 \((q\le 10^5)\) 形如 \(val(x,y)\)，需要回答满足 \(1\le i < j\le n,A_i=x,A_j=y\) 的 \((i, j)\) 的数量
G题解
红温题
分块怎么优化都是带一个 \(log\) 过不去
考虑根号分治，将同颜色数量 \(\ge B\) 的称为大颜色，其余称为小颜色
对于大颜色，提前处理一个数组 \(pre_{i, j}\) 表示从 \(1-j\) 中，颜色为 \(i\) 的数量。
- 对于大颜色与大颜色的查询可以提前预处理，查询是 \(O(1)\) 的，预处理总共 \(O(n\sqrt n)\)
- 对于小颜色与小颜色，直接归并排序时计算满足条件的方案即可，查询复杂度线性 \(O(\sqrt{n})\)，不需要预处理
- 对于大颜色对小颜色，直接对每一个小颜色位置累加 \(pre\) 值即可，查询也是线性的
- 对于小颜色对大颜色，考虑到有等式 \(sum_x\times sum_y=val(x,y)+val(y,x)\)，先按照 \(3\) 的方法直接求，然后用等式转化一下就好
做完了
先补到这