题解 P6867 【[COCI2019-2020#5] Politicari】

### 题目大意 给出一个矩阵$A$，按指定规则进行$k$次批评后求第$k$次**进行批评**的人。 ### 分析 首先想到可以模拟出每次批评的过程，但是看到数据范围： $1\le k\le 10^8$……嘶…… 于是**纯模拟必爆**~~（它SPFA了）~~ 发现如果按照题目中根据矩阵指示的方式进行批评，会有**环**的出现，即在进行数次批评后会回到之前的某次批评过程，可以想到利用这一点减少模拟次数。 批评的过程可以用一个一维数组（代码中为$ans$）进行存储，$ans_i$代表第$i$次**进行批评**的人，根据题目中描写的批评过程，可知第$i-1$次批评为$ans_{i-1}$对$ans_i$（当前进行批评的人）的批评。同时，我们还需要用一个函数来计算循环节开始的时间。 分析结束，上代码！（更多细节请看注释~） ### Code 对了……  ```cpp #include<bits/stdc++.h> #define ll long long #define db double using namespace std; const int INF=0x3f3f3f3f; ll n,k,T,st;//1<=k<=10^18，十年OI一场空，不开long long___~ ll a[501][501]; ll ans[500001]; bool v[501][501];//v[i][j]记录第i个人是否批评过第j个人。 void get_st(ll v,ll u)//找循环起点 { for(ll i=1;i<T;i++) if(ans[i]==v&&ans[i+1]==u){ st=i; return; } } void find(ll now,ll cnt) { ans[cnt]=now; ll t=a[now][ans[cnt-1]]; if(cnt==k){//小优化，如果已经找到了第k次批评，直接输出 printf("%d",now); T=0; return; } if(v[now][t]){ T=cnt; get_st(now,t); return; } v[now][t]=1; find(t,cnt+1); } int main() { scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]); memset(v,0,sizeof(v)); ans[1]=1; v[1][2]=1;//第一次批评为1批评2 find(2,2); if(!T) return 0; T-=st; k-=st; printf("%lld",ans[k%T+st]); return 0; } ``` 完结撒fa~