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 ;
}