A - Sakurako and Kosuke
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void solve(){
int n;cin>>n;
int m=1,cnt=0;
for(int i=1;;i++){
if(i&1){
cnt-=(2*i-1);
}else{
cnt+=(2*i-1);
}
if(abs(cnt)<=n){
continue;
}else{
m=i;
break;
}
}
cout<<(m&1?"Kosuke":"Sakurako")<<"\n";
}
|
B - Sakurako and Water
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void solve(){
int n;cin>>n;
vector<vector<int>>g(n+1,vector<int>(n+1));
map<int,vector<int>>mp;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
if(g[i][j]<0){
mp[i-j].push_back(abs(g[i][j]));
}
}
}
int ans=0;
for(auto &[x,y]:mp){
sort(y.begin(),y.end(),greater<int>());
ans+=y[0];
}
cout<<ans<<"\n";
}
|
C - Sakurako’s Field Trip
C这个题有一点说法，其实想明白什么时候换就可以
从左到n/2的位置每次考虑是否交换当前位置，当i这个位置与i-1的数相同的时候或者n-i+1与其下一个数（就是当前数与其遍历过的上一个数）相同的时候选择交换，可以证明这样操作对答案的增益一定是非负的
证明如下
如果a[i]==a[n-i+1]，操作无影响
a[i]!=a[n-i+1]，
设交换之前点i对答案的增益为 ans=(a[i]==a[i-1]+a[i]==a[i+1]+a[n-i+1]==a[n-i]+a[n-i+1]==a[n-i+2])
交换之后点i对答案的增益为 ans1=(a[n-i+1]==a[i-1]+a[n-i+1]==a[i+1]+a[i]==a[n-i]+a[i]==a[n-i+2])
最坏情况就是
a[i]==a[i-1]&&a[i]!=a[i+1]&&a[n-i+1]!=a[n-i]&&a[n-i+1]!=a[n-i+2]
a[n-i+1]==a[i+1]&&a[i]==a[n-i]&&a[i]==a[n-i+2]
这样的话，交换之后答案多2，但是这种情况下在下一次交换过程中会被重新满足条件执行交换
综上，一直执行交换，最后求答案即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve(){
int n;cin>>n;
vector<int>a(n+10,0),cnt(n+1,0);
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0;
for(int i=1;i<=(n+1)/2;i++){
if(a[i]==a[i-1]||a[n-i+1]==a[n-i+2]){
swap(a[i],a[n-i+1]);
}
}
for(int i=1;i<=n-1;i++){
if(a[i]==a[i+1]) ans++;
}
cout<<ans<<"\n";
}
|
D - Kousuke’s Assignment
没啥说的，遇到0就断开一定是最优的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| void solve(){
int n;cin>>n;
vector<int>a(n+1),pre(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
int ans=0,lst=0;
map<int,int>mp;
for(int i=1;i<=n;i++){
if(a[i]==0){
lst=i;ans++;
continue;
}
int d=pre[i]-pre[lst];
if(d==0){
if(lst<i){
ans++;
lst=max(i,lst);
}
}else if(mp.count(d)){
if(lst<mp[d]){
ans++;
lst=max(i,lst);
}
}
mp[d]=i;
}
cout<<ans<<'\n';
}
|
E - Sakurako, Kosuke, and the Permutation
每次交换完之后就保证当前位置不再交换,这样顺序从1到n就是最小交换次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve(){
int n;cin>>n;
vector<int>a(n+1),pos(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]==i) continue;
if(pos[i]==a[i]&&a[a[i]]==i) continue;
swap(a[pos[i]],a[a[i]]);
swap(pos[a[pos[i]]],pos[a[a[i]]]);
ans++;
}
cout<<ans<<"\n";
}
|
F - Kosuke’s Sloth
递推数列具有模周期性，找到第一个循环节中的下标再乘n即可
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve(){
int n,k;cin>>n>>k;
f[1]=f[2]=1;
int pos=0;
for(int i=1;;i++){
if(i>=3) f[i]=(f[i-1]+f[i-2])%k;
if(f[i]%k==0){
pos=i;
break;
}
}
cout<<(pos%mod)*(n%mod)%mod<<"\n";
}
|