Codeforces Round 981 (Div. 3) （A~F）

Codeforces Round 981 (Div. 3)

A. Sakurako and Kosuke

思路

签到题，直接判断奇偶即可

code

void solve(){int n;cin >> n;if(n & 1) cout << "Kosuke" << endl;else cout << "Sakurako" << endl;return ;
}

B. Sakurako and Water

思路

考点：模拟

从头开始遍历，如果当前数 ＜ 0，则说明这个数需要进行增加操作，那就遍历这个数的对角线，找出最大值，将这个对角线都加上最大值即可
将这些最大值全部累加，最后输出即可

code

const int N=1000;
int a[N][N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){cin >> a[i][j];}int ans=0;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(a[i][j]<0){int k=min(n-i+1,n-j+1);int s=0; for(int z=0;z<k;++z){if(a[i+z][j+z]<0) s=max(s,abs(a[i+z][j+z]));}for(int z=0;z<k;++z){a[i+z][j+z]+=s;}ans+=s;}}cout << ans << endl;return ;
}

C. Sakurako’s Field Trip

思路

考点：模拟

暴力解法，我们只需要考虑每一项 $i$ 和它的镜像 $n-i+1$ 前后四项的值
如果这四个数有3个数的值相同，ans++，如果这四个数都相同，ans+=2

这时还需要考虑边界的问题，如果这个数为奇数并且遍历到中间这个数
那么我们就只需要考虑3个数，中间这个数和它前后这两个数

• 如果这三个数都相同，ans+=2
• 中间的数和前面的数相同或者中间的数和后面的数相同，ans++

如果这个数为偶数并且遍历到中间这两个数
那么我们只需要判断这两个数是否相同即可，相同ans++

讲起来有点复杂，实际上代码挺简单的

code

int a[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i) cin >> a[i];int ans=0;for(int i=1,j=n;i<j;++i,--j){map<int,int> m;m.clear();if(i+1<j-1){m[a[i]]++,m[a[i+1]]++,m[a[j]]++,m[a[j-1]]++;for(auto x : m){if(x.se==3) ans++;if(x.se==4) ans+=2;}}else if(i+1==j-1){int x=a[i],y=a[i+1],z=a[j];if(x==y){if(x==z) ans+=2;else ans+=1;}else{if(y==z) ans+=1;}}else{if(a[i]==a[j]) ans+=1;}}cout << ans << endl;return ;
}

D. Kousuke’s Assignment

思路

考点：前缀和

对于数组 $a$ ，先计算出它的前缀和，对于这个前缀和，我们维护当前 $i$ 的上一个下标
如果遇见相同的前缀和，查询该前缀和的上一个下标是否小于上一段线段的结束位置
如果小于则选择,更新该前缀和的上一个下标为 $i-1$

code

int a[N],sum[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i){cin >> a[i]; sum[i]=sum[i-1]+a[i];} int ans=0,mx=-1;map<int,int> m;m[0]=0;for(int i=1;i<=n;++i){if(m.count(sum[i])){if(m[sum[i]]>mx){ans++;mx=i-1;}}m[sum[i]]=i;}cout << ans << endl;return ;
}

E. Sakurako, Kosuke, and the Permutation

思路

我们可以将这题看成一个环， $i->p_i->p_{pi}->\cdot \cdot \cdot \cdot \cdot \cdot ->i$ 为一个循环节
我们需要将这个环拆分成若干个自环和环节数为2的环
如果这个环为自环，代表自己指向自己，如果这个环的环节为2，代表这个环里的两个数相互指向对面

把玩一下不难发现，替换 $p_{pi}=i$ 优于$p_i=i$ 的操作
因为进行$p_i=i$ 的替换只能保证一个数是准确的，让这个数形成自环
而进行$p_{pi}=i$ 不仅可以保证一个数是准确的，还有可能会形成环节为2的环

因此我们只需要考虑$p_{pi}=i$ 的操作即可，用map存储环，每次进行替换操作维护map即可

code

int a[N];
void solve(){int n;cin >> n;map<int,int> m;for(int i=1;i<=n;++i){cin >> a[i];m[a[i]]=i;} int ans=0;for(int i=1;i<=n;++i){if(a[i]!=i && a[a[i]]!=i){int s=m[i];int t=a[i]; swap(a[s],a[t]);m[a[s]]=s;m[a[t]]=t;ans++;}}cout << ans << endl;return ;
}

F. Kosuke’s Sloth

思路

斐波那契数列在模 $k$ 意义下有周期性（皮萨诺周期）,且这个周期 $<=6k$
暴力枚举求出周期$r$,则第 $n$ 个数的下标为 $rn$

code

int f[N];
void solve(){int n,k;cin >> n >> k;f[1]=1,f[2]=1;if(k==1){cout << n%mod << endl;return ;}int ans=0;for(int i=3;i<=6e5+5;++i){f[i]=(f[i-1]+f[i-2])%k;if(f[i]%k==0){ans=i;break;}}cout << ((n%mod)*(ans%mod))%mod << endl;return ;
}