20231027 NOIP#25 总结
时间安排
7:40~8:10
看题 \(A\) 一眼切，\(B,C,D,E\) 都不会。
8:10~8:30
写 \(A\)，但这个题坑真多。
8:30~8:50
写 \(C\)，这个好像是原题。
8:50~9:50
写 \(B\)，带些许数学的模拟，有点难写。
9:50~10:35
写 \(E\) 的前两档，但第二档做法假了。
10:35~11:30
反应了半天 \(D\)，终于会了。
11:30~11:50
罚坐中。
总结反思
- 暴力要打满，简单题也是要会的
题解
A.简单 DP
遇到限制特殊处理即可。
B.模拟
一圈一圈的考虑，竖列直接数学统计，横行维护区间加，最后不足一圈的暴力做。
C.KMP
作业原题，\(KMP\) 板子，每当匹配成功就删去 \(|T|\) 个，继承前一个的值继续匹配。
D.结论题
要么删去一个度数为奇数的点，要么删去两个相邻的度数为偶数的点。
E.~
首先要发现操作肯定是存在循环的，并且经过 \(k\) 次操作后每个位置到达的地方也是固定的。
所以先进行 \(k\) 次操作，而后将每个点操作前后的位置连边，这必然会构成一个简单环森林，那么每个点会在对应的环上走 \(\lfloor\frac{m}{k}\rfloor\) 的距离。
若走完了整个环，则环上每个点的答案就是整个环包含的所有点，否则就是对应路径所包含的点，这个可以通过双指针快速维护每个点。
但还会有不足 \(k\) 的余数 \(m\bmod k\) 次操作，这个直接暴力即可。
全程利用桶动态维护经过的点集，复杂度是 \(O(k+n)\)
代码
//显然不是我的代码
#include<bits/stdc++.h>
#define MAXN 200010
#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define iter vector<pii>::iterator
using namespace std;
int n,K,m,vis[MAXN],ans[MAXN];
vector<pii>s[MAXN];
int cnt[MAXN],res;
int pos[MAXN],p[MAXN];
int q[MAXN],l,r;
void add(int x,int ti){
for(iter it=s[x].begin();it!=s[x].end();it++){
if(it->fi>ti)return;
cnt[it->se]++;if(cnt[it->se]==1)res++;
}
}
void del(int x,int ti){
for(iter it=s[x].begin();it!=s[x].end();it++){
if(it->fi>ti)return;
cnt[it->se]--;if(!cnt[it->se])res--;
}
}
signed main(){
scanf("%lld%lld%lld",&n,&K,&m);
for(int i=1;i<=n;i++)pos[i]=i,s[i].pb(mp(0,i));
for(int i=1;i<=K;i++){
int a,b;scanf("%lld%lld",&a,&b);
s[pos[a]].pb(mp(i,b));s[pos[b]].pb(mp(i,a));
swap(pos[a],pos[b]);
}
for(int i=1;i<=n;i++)p[pos[i]]=i;
int t=m/K,w=m%K;
for(int i=1;i<=n;i++){
if(vis[i])continue;l=1,r=0;bool fl=0;
for(int u=i,tim=1;tim<=t;u=p[u],tim++){
if(u==i&&tim!=1){fl=1;break;}
add(u,K);q[++r]=u;
}
if(fl){
ans[i]=res;vis[i]=1;del(i,K);
for(int u=p[i];u!=i;u=p[u])
ans[u]=ans[i],del(u,K),vis[u]=1;
continue;
}p[0]=i;
for(int u=i,tim=1;u!=i||tim==1;u=p[u],tim++){
int nxt=p[q[r]];add(nxt,w);
ans[u]=res;del(nxt,w);
add(nxt,K);del(u,K);
l++;q[++r]=nxt;vis[u]=1;
}
for(int j=l;j<=r;j++)del(q[j],K);
}
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}