[USACO21JAN] 金组 Dance Mooves
zyc2003
·
·
题解
题目链接 : [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
现在我说 : 如果把每一个位置看做一个**点** , 点 $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)$ 的算法还能慢 ?)
```cpp
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;
}
```