自动搬运

查看原文

来自洛谷，原作者为

	zyc2003 El Psy Congroo

搬运于2025-08-24 22:28:32，当前版本为作者最后更新于2021-01-30 15:40:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接 : [USACO21JAN] Dance Mooves G

前置知识

推荐先写出银组的本题的弱化版 : [USACO21JAN] Dance Mooves : Silver , 这样对理解本题会有更大帮助 . 或者你也可以选择直接看本篇题解 .

总体思路

这里不再简述题意 , 因为题面比较清晰明了 .

当进行完一轮置换 , 也就是 $K$ 个交换之后 , 我们设 $\mathrm{next}_i$ 是执行完一轮置换之后 , 第 $i$ 头奶牛会到达的位置 . 就拿样例来说 , 原来的奶牛序列是 :

$$1,2,3,4,5,6$$

那么经过 $K=4$ 次的交换后 , 序列变成 :

$$2,3,4,5,1,6$$

$1$ 号奶牛去到了位置 $5$ , $2$ 号奶牛去到了位置 $1$ ... 等等 .

现在我说 : 如果把每一个位置看做一个点 , 点 $i$ 向 $\mathrm{next}_i$ 连边 , 那么我们会得到一堆简单环构成的森林 . 对于样例来说 , 我们形成了两个环 :

证明也很简单 . 我们知道 , 在一轮置换之后 , $i$ 位置上的奶牛一定到达了 $\mathrm{next}_i$ 位置 , 而必然存在另一个位置 $j$ , 一轮置换后到达了 $\mathrm{next}_j=i$ 位置 . 理由是 $i$ 位置不可能是没有奶牛的 , 所以 $j$ 的存在性显然 .

至于 $\mathrm{next}_i=i$ 的情况 , 那就显然是一个自环 . 此时不可能存在 $j\neq i$ , 使得 $\mathrm{next}_j=i$ .

这也就是说 , 这 $n$ 个结点的入度和出度均为 $1$ , 且一共 $n$ 条边 . 那么就形成了一堆简单环构成的森林 . 现在 , 我们就把序列问题转化到了图上 .

我们知道 , 如果没有 $M$ 的限制 , 而是可以无限走 : 那么一个环上的点最终都可以彼此到达 . 这也是本题测试点 $6-10$ 的情况 , 或者说是银组本题弱化版的情况 . 那么在这种情况下 , 我们开 $n$ 个 $\rm vector$ , 令 $\mathrm{pass}_i$ 表示 $i$ 在一轮置换中 , 一共经过了哪些位置 , 比如还是样例中 , $\mathrm{pass}_1=\{1,2,3,4,5\}$ .

对于一个环上的所有点 , 由于是无限置换 , 所以它们能到达的位置集合必然相同 . 只需要对每一个环上每一个点的 $\mathrm{pass}_i$ 进行遍历 , 位置集合大小即为这一个环的答案 . 由于一个 $\mathrm{pass}_i$ 只会被统计 $1$ 次 , 而 $\mathrm{pass}_i$ 的总大小约为 $2K$ , 所以统计答案的时间复杂度为 $\mathcal O(K)$ 的 .

那么现在回到有限制的情况 . 我们知道 , 在 $M$ 分钟内 , 我们进行了 :

$$\mathrm{times}=\lfloor\frac{M}{K} \rfloor$$

轮置换 , 进行完这 $\mathrm{times}$ 轮置换后 , 又按照操作序列执行了 :

$$\mathrm{rest\_opt}=M-\mathrm{times}*K$$

次交换 (注意 , $K$ 次交换称为一次置换)

那么对于大小 $\leq \rm times$ 的环而言 , 这 $\rm times$ 次置换已经足以让一个点跑回自己 : 这个环的上所有点的答案还是像刚才讨论的无限置换一样 .

那么大小 $> \rm times$ 的环呢 ? 观察环上的一个点 $x$ , 经过 $\rm times$ 轮置换后 , 它会到达的点是确定的 , 设为 $y$ . 而还要再从 $y$ 位置出发 , 又经过了 $\rm rest\_opt$ 次交换 . 在这个过程中经过的位置集合 , 就是点 $x$ 的答案 .

所以我们现在需要另外 $n$ 个 $\rm vector$ , 来统计剩下的 $\rm rest\_opt$ 次交换中 , 每一个点经过了哪些位置 . 不妨使用 $\mathrm{rest}_i$ 表示剩下的 $\rm rest\_opt$ 次交换中 , 点 $i$ 经过的位置 .

那么这样 , 可以 $\mathcal O(NK)$ 地求出每一个点的答案 . 不过这样有什么用 ? 还不如打暴力来得快 ...

别急 , 有一个很显然的优化方法 . 考虑已经求出了某个环上 $x$ 点的答案 , 那么对于他所指向的点 $\mathrm{next}_x$ , $\mathrm{next}_x$相比 $x$ 而言 , 不会遍历 $\mathrm{pass}_x$ , 以及 $\mathrm{rest}_y$ . (这里 $y$ 的意思和上面讨论时相同 , $x$ 虽然置换到了 $y$ , 但是并不能再从 $y$ 开始进行完整的一轮置换) . 但是 , 他多遍历了 $\mathrm{pass_y}$ , 和 $\mathrm{rest}_{\mathrm{next}_y}$ .

所以我们破环成链 ,复制一遍增添在末尾 , 使用双指针移动 , 并且用一个桶 $\mathrm {buf}$ 记录每个位置的经过次数 , 从 $0$ 变成 $1$ 时答案增加 , 从 $1$ 变成 $0$ 时答案减少 . 这样就可以显然 $\mathcal O(K)$ 地统计答案 , 因为一个 $\mathrm {pass}_i$ 只会被加入贡献一次 , 消除贡献一次 . $\mathrm{rest}_i$ 同理 .

注意细节

由于本题题目较难 , 作者水平有限只能提供总体思路 , 实现细节方面只能提供一些参考 . 如下 :

$1.$ 我在计算完 $\mathrm{pass}_i$ 集合后 , 会弹出最后一个元素 . 因为最后一个元素就是 $\mathrm{next}_i$ , 在扫描 $\mathrm {pass}_{i}$ 和 $\mathrm{pass}_{\mathrm{next}_i}$ 时 , 可能会导致 $\mathrm{next}_i$ 被重复统计 . 所以需要弹出 . (没有被交换过的位置除外 , 不用弹出) (不弹出也没事 , 只是不严谨 , 不会影响计数)

$2.$ 记得消除贡献要消除完整 , 从一个环里出来后 , 要把桶清空 . 不要使用 $\rm memset$ , 可能会超时呢 . (实际上好像没有超时 ? 但是不推荐这样做 .)

$3.$ 特别注意 $\mathrm{times}=0$ 的情况 . 此时一轮置换都无法完成 . 我在代码中是使用 $\rm l \leq r$ 特判(因为如果为 $0$ , 必然出现双指针移动时时刻 $\rm l > r$)

$4.$ 注意 $M\leq 10^{18}$ , 一些变量需要使用 $\rm long \ long$ 存储 .

代码部分

代码只有关键部分的注释 , 不推荐仔细浏览 (因为实现细节还是自己调为好) . 头文件 , 快读 , 快写就不放上来了 .

跑得挺快的 , 总时间 $1s$ 左右 . (废话 , $\mathcal O(N+K)$ 的算法还能慢 ?)

int n;LL times,m,k;
int A[N],B[N],pos[N],nxt[N];
vector <int> pass[N],rest[N];
vector <int> cir[N];int cnt,len[N];bool vis[N];
int ans[N];
int buf[N],sum;

void GetCir(int x) {
	int to=x;
	do {
		vis[to]=1;
		cir[cnt].push_back(to);
		to=nxt[to];
	} while(to != x);
	len[cnt]=cir[cnt].size();
}
void Solve(int now) {
	if((LL)len[now] <= times) {
		//Add Contribution
		for(int i=0;i<len[now];++i) {
			int x=cir[now][i];
			for(int j=0;j<pass[x].size();++j) {
				int y=pass[x][j];
				buf[y] == 0 ? sum++,buf[y]++ : buf[y]++;
			}
		}
		for(int i=0;i<len[now];++i) {
			int x=cir[now][i];
			ans[x]=sum;
		}
		//Delete contribution
		for(int i=0;i<len[now];++i) {
			int x=cir[now][i];
			for(int j=0;j<pass[x].size();++j) {
				int y=pass[x][j];
				buf[y]=0;
			}
		}
		sum=0;
		return ;
	}
	for(int i=0;i<len[now]-1;++i)
		cir[now].push_back(cir[now][i]);
	//Previous Treatment , Add Contribution : l -> r
	int l=0,r=times-1;
	for(int i=l;i<=r;++i) {
		int x=cir[now][i];
		for(int j=0;j<pass[x].size();++j) {
			int y=pass[x][j];
			buf[y] == 0 ? sum++,buf[y]++ : buf[y]++;
		}
	}
	for(int i=0;i<rest[cir[now][r+1]].size();++i) {
		int y=rest[cir[now][r+1]][i];
		buf[y] == 0 ? sum++,buf[y]++ : buf[y]++;
	}
	ans[cir[now][l]]=sum;
	//Now Let's Get Each Answer
	while(l < len[now]-1) {
		int x=cir[now][l];
		if(l <= r) {
			for(int i=0;i<pass[x].size();++i) {
				int y=pass[x][i];
				buf[y] == 1 ? sum--,buf[y]-- : buf[y]--;
			}
		}
		x=cir[now][r+1];
		for(int i=0;i<rest[x].size();++i) {
			int y=rest[x][i];
			buf[y] == 1 ? sum--,buf[y]-- : buf[y]--;
		}
		++l,++r;
		x=cir[now][r];
		if(l <= r) {
			for(int i=0;i<pass[x].size();++i) {
				int y=pass[x][i];
				buf[y] == 0 ? sum++,buf[y]++ : buf[y]++;
			}
		}
		x=cir[now][r+1];
		for(int i=0;i<rest[x].size();++i) {
			int y=rest[x][i];
			buf[y] == 0 ? sum++,buf[y]++ : buf[y]++;
		}
		ans[cir[now][l]]=sum;
	}
	//Remember to Delete Contribution
	for(int i=l;i<=r;++i) {
		int x=cir[now][i];
		for(int j=0;j<pass[x].size();++j) {
			int y=pass[x][j];
			buf[y]=0;
		}
	}
	for(int i=0;i<rest[cir[now][r+1]].size();++i) {
		int y=rest[cir[now][r+1]][i];
		buf[y]=0;
	}
	memset(buf,0,sizeof buf);
	sum=0;
}

int main() {
	n=read(),k=read(),m=read();times=m/k;
	for(int i=1;i<=k;++i) 
		A[i]=read(),B[i]=read();
	for(int i=1;i<=n;++i)
		pass[i].push_back(i),rest[i].push_back(i),pos[i]=i;
	for(LL i=1;i<=k;++i) {
		pass[pos[A[i]]].push_back(B[i]),
		pass[pos[B[i]]].push_back(A[i]);
		if(i <= m-k*times)
			rest[pos[A[i]]].push_back(B[i]),
			rest[pos[B[i]]].push_back(A[i]);
		swap(pos[A[i]],pos[B[i]]);
	}
	for(int i=1;i<=n;++i) {
		nxt[pos[i]]=i;
		if(pass[i].size() != 1)
			pass[i].pop_back();
	}
	for(int i=1;i<=n;++i)
		if(!vis[i])	++cnt,GetCir(i);
	for(int i=1;i<=cnt;++i)
		Solve(i);
	for(int i=1;i<=n;++i)
		Writes(ans[i]);
	return 0;
}