P6867 [COCI2019-2020#5] Politicari——模拟+找规律

P6867 [COCI2019-2020#5] Politicari

题目描述

有 n 个人互相批评。

另提供矩阵 A。

规则如下：

第一次，第 1 个人批评第 2 个人。

如果第 i−1次为第 u个人批评第 v 个人，

那么第 iii 次为第 v 个人批评第 Av,u​ 个人。

求第 kkk 次是谁进行批评（注意：不是被批评）。

输入格式

第一行：两个正整数，n 和k。

以下 n 行：矩阵 A。矩阵的主对角线（就是从左上到右下的那条对角线）全是 0，其他部分由从 1到 n的正整数组成。

输出格式

一行：你的答案。

输入输出样例
输入 #1

2 4
0 2
1 0

输出 #1

2

输入 #2

3 7
0 3 2
3 0 3
2 1 0

输出 #2

1

输入 #3

4 7
0 4 3 2
4 0 4 1
2 1 0 1
3 2 3 0

输出 #3

3

说明/提示

数据范围 对于 35pts35 pts35pts 的数据，保证 1≤k≤10^5。
对于所有的数据，2≤n≤500且 1≤k≤10^18

思路：

这是一道模拟+找规律的题目，其中，k的范围是1~10^18，是个非常大的数，直接模拟一定会超时，所以，要找规律；
通过举例发现这些数的出现存在一些规律，即会循环出现，所以我们主要就是找循环的区间（并且要注意循环可能不是从开始就有）；

主要步骤如下：
① 定义 r 数组记录每次的批评者与被批评者，v数组标记找过的位置
②输入数据；
③通过 v 数组先找再次出现循环的地方（即循环体结束的地方），并记录下来；
④通过 r 数组从开始比较，找出循环体开始的地方；
⑤最后计算k

题解

#include<bits/stdc++.h>
using namespace std;
int n,f[505][505],v[505][505],r[100010][3],cnt = 1;//r数组记录每次的批评者与被批评者，v数组标记找过的位置
long long k;
int main(){
cin >> n >> k;
//① 
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> f[i][j];
//②
int a = 1,b = 2,c;
r[1][1] = 1;r[1][2] = 2;
v[1][2] = 1;
for(int i=1;;i++){
c = f[b][a];
a = b;
b = c;
r[++cnt][1] = a;
r[cnt][2] = b;
if(v[a][b]==1){
break;
}
else {
v[a][b] = 1;
}
}
int ii;//ii记录循环前无规律的那一部分
for(int i=1;i<cnt;i++){
if(r[i][1]==a&&r[i][2]==b){
cnt -= i;
ii = i-1;
break;
}
}
int ans;
if(k-ii<0){
ans = r[cnt][1];
}
else {
k -= ii;
k %= cnt;
if(k==0) ans = r[ii+cnt][1];//注意 
else ans = r[ii+k][1];
}
cout << ans << endl;
return 0;
}

其中，注意最后对k进行计算时，k-ii后，注意如果k%=cnt后，k=0,则ans=r[ii+cnt][1];

if(k-ii<0){
ans = r[cnt][1];
}
else {
k -= ii;
k %= cnt;
if(k==0) ans = r[ii+cnt][1];//注意 
else ans = r[ii+k][1];
}

最后

以上就是舒心奇异果为你收集整理的P6867 [COCI2019-2020#5] Politicari——模拟+找规律的全部内容，希望文章能够帮你解决P6867 [COCI2019-2020#5] Politicari——模拟+找规律所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。