[CSP 2024 J & COGS 4052] 接龙

  注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题却受到伤害！！！）

 引入

  有 \(n\) 个人，每个人手里有一个数字序列（词库）。玩一个接龙游戏：

- 第 \(1\) 轮：可以从任意一个人的序列中，选一个长度在 \([2, k]\) 之间的连续子序列，且子序列的第一个数必须是 \(1\)

- 第 \(2\) 轮及以后：选的子序列的第一个数，必须等于上一轮子序列的最后一个数，且不能连续两轮用同一个人的序列

有 \(q\) 个询问，每个询问给两个数 \(r\) 和 \(c\)，问能否恰好用 \(r\) 轮接龙，让最后一轮的最后一个数字是 \(c\)

分析

  这道题如果直接模拟，复杂度会非常高。需要一种高效的方法来判断“可行性”。

正解采用动态规划加滑动窗口的思路：

  状态定义：\(dp[r][x]\) 表示能否在 \(r\) 轮内，以数字 \(x\) 作为结尾

- \(dp[r][x] = -1\)：不可行

- \(dp[r][x] = i\)：可行，且最后一轮是由第 \(i\) 个人完成的

- \(dp[r][x] = 0\)：可行，且有多个人都能完成（用于后续判断）

  状态转移：从 \(dp[r-1][y]\) 到 \(dp[r][x]\)

- 如果存在某个人 \(i\)，他的序列中有以 \(y\) 开头、长度在 \([2,k]\) 内的子序列，且以 \(x\) 结尾

- 且 \(dp[r-1][y]\) 不是由 \(i\) 完成的（不能连续两轮用同一个人）

- 那么 \(dp[r][x]\) 就是可行的

  优化方法：

- 用滑动窗口在每个序列中快速找到所有可能的（开头，结尾）对

- 用 \(cnt\) 记录当前正在构建的子序列长度

后记

 1. 为什么 \(cnt\) 这样工作？

当遇到一个可以作为开头的数字时，我们允许它后面最多接 \(k-1\) 个数。\(cnt\) 就是“还能接几个数”的计数器。每遍历一个数，如果 \(cnt>0\)，说明当前数可以作为某个子序列的结尾，然后 \(cnt\) 减一。

 2. \(dp[r][x]\) 的三个值含义

- \(-1\)：不可行

- \(i\)：可行，且最后一轮是第 \(i\) 个人完成的（唯一）

- \(0\)：可行，但有多个人都能完成（用于判断不能连续两轮同一个人）

 3. 为什么最后要取 \(tot\) 的最大值？

因为数字的范围可能很大（\(10^9\)），但实际出现的数字有限。只开 \(tot+2\) 的数组，避免内存过大。

 复杂度分析

轮数 \(\leq 100\)，总序列长度 \(\leq 2\times 10^5\)，总复杂度 \(O(100 \times \text{总长度})\)，可以接受。

 注意事项

1. 读入要用 \(ios::sync\_with\_stdio(0);cin.tie(0);\) 加速

2. 文件输入输出不要忘：\(freopen\)

3. dp 数组要用 vector 动态分配，避免内存过大

更新日志：

2026.3.20 创建题解

[Nescafé 18&COGS 1045] 七夕祭 题目解析

    注意到本题在洛谷是一道蓝题。所以：论如何在比赛中场切蓝题？（注意，这里没有任何一个人因为没做过交互题而在某比赛中遇到蓝题却受到伤害！！！）

  引入

       你有一个 \(N \times M\) 的矩形网格，其中 \(T\) 个格点是“感兴趣的”。你可以交换相邻的格点（左右相邻或上下相邻，且每行/列的首尾也算相邻，即环形）。目标是用最少的交换次数，同时满足两个条件：

1. 行均等：每一行感兴趣的格点数相同。

2. 列均等：每一列感兴趣的格点数相同。

这是一个典型的环形均分问题。核心思想是：行列独立，可以分别求解。

分析

第 1 步：数据统计与可行性预判

统计行和：设第 \(i\) 行有 \(R_i\) 个感兴趣的格点，则 \(\sum_{i=1}^{N} R_i = T\)。

统计列和：设第 \(j\) 列有 \(C_j\) 个感兴趣的格点，则 \(\sum_{j=1}^{M} C_j = T\)。

 预判可行性：

行方向可行的条件是 \(T\) 能被 \(N\) 整除。此时每行的目标数为 \(\text{avg}_R = \frac{T}{N}\)。

列方向可行的条件是 \(T\) 能被 \(M\) 整除。此时每列的目标数为 \(\text{avg}_C = \frac{T}{M}\)。

第 2 步：将行/列问题转化为一维环形均分问题

以行方向为例，我们得到了一个环形排列的数列 \([R_1, R_2, ..., R_N]\)，需要通过相邻交换（环形），使每个数都变成目标值 \(\text{avg}_R\)。这本质上是一个货物搬运问题。

转化：

我们定义一个“偏差”数组 \(A_i = R_i - \text{avg}_R\)。问题变成了：通过相邻搬运，使所有 \(A_i\) 变为 0。最终答案是所有搬运的“工作量”之和。

第 3 步：求解一维环形均分问题（数学推导）

设从第 \(i\) 个位置搬运到第 \(i+1\) 个位置的货物量为 \(x_i\)（可正可负，正表示向右搬，负表示向左搬）。那么，对于每个位置，经过搬运后，其偏差应该被消除：\(A_i + x_{i-1} - x_i = 0\)

其中 \(x_0\) 表示从第 \(N\) 个位置到第 \(1\) 个位置的搬运量（因为是环形）。整理得：\(x_i = A_i + x_{i-1}\)

这是一个递推关系。令 \(x_0 = k\)，则可以推出：

\(x_1 = A_1 + k\)

\(x_2 = A_2 + x_1 = A_1 + A_2 + k\)

\(x_3 = A_1 + A_2 + A_3 + k\)

...

 \(x_i = S_i + k\)

其中 \(S_i = \sum_{j=1}^{i} A_j\) 是前 \(i\) 个偏差的前缀和（注意，这里的 \(A_j\) 已经减去平均值，所以整个数列的总和为0，即 \(S_N = 0\)）。

我们的目标是最小化总运输量 \(\sum_{i=1}^{N} |x_i| = \sum_{i=1}^{N} |S_i + k|\)。

问题的几何意义：我们需要找到一个实数 \(k\)，使得数轴上的一系列点 \([-S_1, -S_2, ..., -S_N]\) 到点 \(k\) 的距离之和最小。

数学结论：使距离和最小的点 \(k\) 是这些点坐标的中位数。

第4步：计算最小交换次数

1.  根据第 2 步得到偏差数组 \(A_i\)。

2.  计算其前缀和 \(S_i = A_1 + A_2 + ... + A_i\)，得到一个长度为 \(N\) 的数组 \([S_1, S_2, ..., S_N]\)。

3.  对这个前缀和数组进行排序，找到它的中位数 \(m\)。

4.  最小交换次数即为 \(\sum_{i=1}^{N} |S_i - m|\)。

Ps：这个计算出的次数，实际上是“货物搬运的总量”。因为每次交换（相邻位置）只能搬运“1个单位”的货物，所以这个总量就等于最少的交换次数。

列方向的处理方法与行方向完全相同，只是将 \(N\) 换成 \(M\)，将 \(R_i\) 换成 \(C_j\)。

最终答案

1. 如果两个方向都可行，输出 both 和行与列次数之和。

2. 如果只有行可行，输出 row 和行的次数。

3. 如果只有列可行，输出 column 和列的次数。

4. 如果都不可行，输出 impossible。

代码如下

#include<bits/stdc++.h>
#define MAXN 100010
#define ll long long
using namespace std;

ll n1,m,t;
ll r[MAXN],c[MAXN],s[MAXN];

ll calc(ll n,ll a[],ll ta)
{
	for(int i=1;i<=n;++i) s[i]=s[i-1]+(a[i]-ta);
	sort(s+1,s+n+1);
	ll mid=s[(n+1)/2];
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=abs(s[i]-mid);
	return ans;
}

int main()
{
	freopen("tanabata.in","r",stdin);
	freopen("tanabata.out","w",stdout);
	cin>>n1>>m>>t;
	memset(r,0,sizeof(r));
	memset(c,0,sizeof(c));
	for(int i=1;i<=t;++i)
	{
		int x,y;
		cin>>x>>y;
		r[x]++; c[y]++;
	}
	bool okr=!(t%n1),okc=!(t%m);
	if(okr&&okc)
	{
		ll rans=calc(n1,r,t/n1);
		ll cans=calc(m,c,t/m);
		cout<<"both "<<rans+cans<<endl;
	}
	else if(okr)
	{
		ll rans=calc(n1,r,t/n1);
		cout<<"row "<<rans<<endl;
	}
	else if(okc)
	{
		ll cans=calc(m,c,t/m);
		cout<<"column "<<cans<<endl;
	}
	else cout<<"impossible"<<endl;
	return 0;
}

更新日志：

2026.3.14 创建题解

2026.3.16 格式修改

场上被这道题送走了。

直接做显然是很困难的，不过根据期望的性质，我们可以把答案的贡献拆到每一个子树上，具体的，对于一个大小为 $siz_x$ 的子树 $x$，若 $(x,fa_x)$ 成为重边的概率为 $P$，则这个子树对答案的贡献为 $(1-P)siz_x$。

接下来就是求出 $P=\frac{l_i}{\sum_{j=1}^k l_j}$ 了，显然我们可以在树上做 dp，并分别记录 $f_{i,j}$ 表示 $i$ 下有一条长度为 $j$ 重链的概率，$g_{i,j}$ 表示 $i$ 所有儿子重链长度之和为 $j$ 的概率。

$g_{i,j}$ 的转移是一个树上背包状物，不断让 $g,f$ 卷积即可，根据经典结论，树上背包的时间复杂度由每个点对贡献得来，复杂度为 $O(n^2)$。

$f_{i,j}$ 的计算和 $P$ 的计算是一体的，考虑 $x$ 的重链从他的儿子 $y$ 继承。枚举重链长度 $i$，则 $f_{x,i+1}\gets \sum_{j}f_{y,i}\times h_{x,j}\times \frac{i}{i+j}$，其中 $h_{x,j}$ 表示 $g_{x,j}$ 在不考虑 $y$ 这个儿子的情况下的背包数组。

$f_{i,j}$ 的计算可以通过预处理所有儿子实际上的长链之和，用树上背包的方法做到 $O(n^2)$，逆元直接预处理 $1\sim n$ 的即可。问题在于如何快速求 $h$。

方法一：记录 $v_1,v_2,\dots,v_k$ 的前缀背包和后缀背包，求 $h$ 只需要暴力卷积前后缀即可，复杂度为 $O(n^3)$。

方法二：考虑优化上面的过程，用 NTT 算法做卷积，时间复杂度为 $O(n^2\log n)$。

方法三：考虑分治算法，设分治到区间 $[l,r]$ 表示不考虑区间 $[l,r]$ 内所有元素时的 $h$，如果要分治处理 $[l,mid]$ 就将 $[mid+1,r]$ 的信息加到 $h$ 上，再丢到 $[l,mid]$ 处理，$[mid+1,r]$ 同样如此，常数较小，时间复杂度为 $O(n^2\log n)$。

方法四：上述三种算法都将除法变成乘法处理，考虑直接用除法，用 $g_x$ 除去 $f_y$。对于两个多项式 $F,G$（$F$ 为 $G$ 的倍数），他们的次数分别是 $l_1,l_2$（$l_1>l_2$），则 $\frac{F}{G}$ 的次数为 $l_1-l_2$，可以模拟竖式除法的过程，暴力除法的时间复杂度为 $l_2(l_1-l_2)$。不难发现，这个形式也及其类似树上背包的时间复杂度分析（每个点对会贡献一次），所以直接暴力除就可以了，每次只需要对 $f_y$ 的最高次项求逆元即可。时间复杂度为 $O(n^2)$。

此时，就解决了这道题目的所有问题，做到了 $O(n^2)$ 的时间复杂度。官方数据疑似放了很多 $O(n^3),O(n^2\log n)$ 的解法过去（后者几乎全过了）。

一、思路

首先对于公式我们可以注意到：

$t=(s_l \space \text{and}\space s_{l+1} \space \text{and } \cdots \text{ and } s_r) \text{ xor } (\text{not }(s_l \text{ or } s_{l+1} \text{ or } \cdots \text{ or } s_r))$

$\forall k \space (1 \leq k \leq m)$ 如果要对答案有贡献就要使 $s$ 的第 $k$ 列的第 $l$ 行到第 $r$ 行都是相同的数

 为什么呢

 如果当前第 $k$ 列对答案的贡献为 $0$

那么显而易见 $xor$ 前后两个式子都必须全为 $1$ 或全是 $0$，考虑全为 $0$ 的情况，对于前一个式子可能 $l \sim r$ 行全是 $0$ 或两种数都有，思考一下就能发现只有当两种数都有的时候才会使答案的贡献为 $0$。

再考虑一下如果前后两个式子全为 $1$，那么对于前一个式子就必须使 $l \sim r$ 行都为 $1$，但显然不可以的，所以就不再考虑。

综上所述如果想让当前第 $k$ 列对答案的贡献为 $1$ 那么 $l \sim r$ 每一个数都为同一种（$0$ 或 $1$）

二、实现

第一关

想必如果理解了以上思路，就很容易想到前缀和（似乎可以用树状数组（doge）），具体怎么实现也很简单根据题目数据会发现一个很奇妙的东西 $nm \leq 1e7$ 这意味着如果我们在主函数中直接定义并初始化时间复杂度是 $O(nm)$ 的！这样便可以建立数组而不超时了。

接下来定义数组 $sum_i,_j$ 表示第 $j$ 列，$1 \sim i$ 的行的前缀和，那么查询时只需要判断 $sum_{l -1},_j \space - \space sum_r,_j$ 是否全为 $0$ 或全为 $1$ 就行了

第二关

还有第二关，发现 $k$ 最大为 $2 * 10^6$ 这是很大的，意味着我们的查询 $l,r$ 完全有可能重复！所以我们可以用 hash 来优化一下（当然一些别的优化，例如：循环节优化 也可以），将每一个 $l,r$ 都变为 $1$ 个 $n$ 进制数，具体为 $l * n + r$，将转化后的数扔进 $map$（当然要用 $unordered \space map$ 优化），每次看 $l,r$ 是否重复即可

第二种实现

即二分做法，我会用另外一篇题解讲述。

一、 初始思路（第一反应）

• 直觉解法：

[线段覆盖模板]

二、 优化过程

• 思路：

首先我们会发现$2$个性质：
1:小A可以到达的点一定是连续的包含x的线段

2:此题即为求解小A可以到达的最大的线段中包含的关键车站




如何求解最大线段？

设最左端点为$1$,最右端点$r$

向左，发现到点i时，设$a_{i}$为以点$i$为终点的轨道中起点的编号最小值。用$a_{i}$更新$l$

向右同理

• 复杂度： 时间O($n$), 空间O($n$)

应该是最快的，现在是最优解