A. Sakurako and Kosuke

思路：

赛时读完题就去写了一个循环去模拟两者操作并记录次数，游戏结束时奇数次操作为先手win，偶数次操作为后手win，后来发现每次操作只会向目标方向移动一格，所以如果到n格，n为奇数时，为先手者到n格，后手win，反之先手win

Solved：

void solve()
{
	int n;cin>>n;
	int x=1;
	int p=0;
	int cnt=0;
	for(int i=1;i<=10000;i++){
		if(p<-n||p>n){
			break;
		}
		if(i&1){
			p+=x;
		}else{
			p-=x;
		}
		cnt++;
		x+=2;
	}
	if(cnt&1){
		cout<<"Sakurako"<<endl;
	}else{
		cout<<"Kosuke"<<endl;
	}
}

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

B. Sakurako and Water

思路：

赛时读题发现只需要记录每个主对角线上最小的那个数即可，发现数据较小，直接暴力枚举了每个点及其对角线上的所有点

Solved：

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++){
			int mi=0;
			for(int k=0;k<=n;k++){
				int x=i+k,y=j+k;
				if(x>n||y>n){
					break;
				}
				if(a[x][y]<mi){
					mi=a[x][y];//只要最小的
				}
				if(a[x][y]<0){//负数改为0
					a[x][y]=0;
				}
			}
			ans+=labs(mi);
		}
	}
	cout<<ans<<endl;
}

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++){//上三角主对角线 
		int mi=0;
		for(int j=0;j<=n;j++){
			int x=1+j,y=i+j;
			if(x>n||y>n){
				break;
			}
			mi=min(mi,a[x][y]);
		}
		ans+=labs(mi);
	}
	for(int i=2;i<=n;i++){//ctrl+v下三角 
		int mi=0;
		for(int j=0;j<=n;j++){
			int x=i+j,y=1+j;
			if(x>n||y>n){
				break;
			}
			mi=min(mi,a[x][y]);
		}
		ans+=labs(mi);
	}
	cout<<ans<<endl;
}

C. Sakurako’s Field Trip

思路：

赛时读题后想到一种暴力做法，分别枚举出本体和镜像对于左右邻居交换与不交换产生的影响，如果交换前影响 大于 交换后，就应该换，但是会出现严重的边界问题

例如：4 3 3 3 1 2 1 4 1

不论从左枚举还是从右枚举，在 3 3 3 这组数中，明显应该交换中间的3，一次就可以解决，但是如果顺序枚举左右，就会导致左边或者右边的3先进行交换

解决办法：

对于只有2或3个数，发现无论怎么交换，都无法改变他们的邻居

对于4或5个数，发现交换1，5和交换2，4他们对应的单边邻居依然是相同的

1 2 3 4 5

交换(2 , 4)，1的邻居为4

交换(1 , 5)，1的邻居依然为4

那么继续推，对于6或7个数单边邻居依然如此，所以只用考虑一边，递推至另一边，所有的情况就考虑完全了

Solved：

void solve()
{
	int n;cin>>n;
	a[n+1]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int lmid=n/2,rmid=n/2+1;//1 2 3 4 根据分析，从1，4分别开始定义l，r
	if(n%2==1){//1 2 3 4 5 ， 根据分析，从1，5开始
		lmid=n/2,rmid=n/2+2;
	} 	
	for(int i=lmid-1,j=rmid+1;i>=1;){
		int lst1=0,rst1=0;//交换前状态
		int lst2=0,rst2=0;//交换后状态
		if(a[i]==a[i+1]){//只考虑单边邻居
			lst1++;
		}
		if(a[j]==a[j-1]){
			rst1++;
		}
		if(a[i]==a[j-1]){
			lst2++;
		}
		if(a[j]==a[i+1]){
			rst2++;
		}	
		if(lst1+rst1>lst2+rst2){//交换状态后更优则交换
				swap(a[i],a[j]);
		}
		i--;
		j++;
	}
	int ans=0;		
	for(int i=1;i<=n;i++){//记录结果
		if(a[i]==a[i+1]){
			ans++;
		}
	}
	cout<<ans<<endl;
	return ;
}

D. Kousuke’s Assignment

思路：

对于本题来说，可以先考虑一种局部最优解情况

1 0 -1 ，肯定是选择0单独作为一段为最优，如果选择了1 0 -1，将可能会少计算一段，所以完美线段长度越短越好

例如-1 1 0 -1 1 ，此时，应该选-1 1和0 和-1 1为最优

递推到全局会发现，只要出现某一段为0，就应该将该段最小化并记录，顺序遍历即为答案

Solved：

void solve()
{
	map<int,int> mp;
	int n;cin>>n;
	int sum=0,ans=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		sum+=x;
		if(sum==0){
            //如果有一段sum=0，出现了完美段，记录ans，重置所有判断条件
			mp.clear();
			ans++;
			sum=0;
			continue;
		}
		if(mp[sum]>0){
            //如果在一段中sum出现了两次，就有可能在这之间+0或者加上了一对相反数如1，-1，出现了完美段，记录ans，重置所有判断条件
			mp.clear();
			ans++;
			sum=0;
			continue;
		}
		mp[sum]++;//记录此时段总和
	}
	cout<<ans<<endl;
}

E. Sakurako, Kosuke, and the Permutation

思路：

看题解有大佬给了一个置换环知识点

对于本题来说，理解一下题意会发现每个位置上最优只会存在两种状态

• 自己与自己形成一个环 Pi = i
• 自己与另一个位置形成一个环（2） P[ Pi ] = i P[ i ] = Pi 也就是说i ， j形成一个环满足p[ i ] = j , p[ j ] = i

通过以上推断，就可以明显看出，如果满足题意，该位置可以不换，否则，应先满足第二个条件

过程中应先将每个位置的a[i]与i连接一条边，以确保在二条件更换中快速确定位置

Solved：

void solve(){
	int n;cin>>n;
	map<int,int> mp;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]=i;
        //例如，1号位置为3，那么应将1号位对应的mp[1]=3,将1号位和3号位连一条边
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==i||a[a[i]]==i){
			continue;
		}else{
            //不满足题意时，优先二条件更换
			int s=mp[i];//取出对应a[i]满足条件的点
			int t=a[i];//取出a[a[i]]
			swap(a[s],a[t]);//将a[a[i]]和a[mp[i]]交换满足二条件
			swap(mp[a[s]],mp[a[t]]);//同时交换两数在a[]中对应位置，此时a[i]号位与1号位成二元环，最优
			ans++;//记录
		}
	}
	cout<<ans<<endl;
}

F. Kosuke’s Sloth

思路：

斐波那契数列有一个性质，如果第i项是k的倍数，那么第ni项也是k的倍数

该题可以通过打表斐波那契数列找到第一个k的倍数，对应*n就是第n项

但是数据范围可能很大，需要把握好取模条件

Solved：

void solve(){
	int n,k;cin>>n>>k;
	f[1]=1;
	if(f[1]%k==0){
		cout<<n%mod<<endl;
		return ;
	}
	f[2]=1;
	int ans=0;
	for(int i=3;i<=10000000;i++){
		f[i]=(f[i-1]+f[i-2])%k;//f[i-1]+f[i-2]可能会非常大,所以在相加过程中对k取模判断
		if(f[i]%k==0){
			ans=i;
			break;	
		}
	}
	cout<<((n%mod)*(ans%mod))%mod<<endl;
}