Chonu

Posted on Edited on In , Valine:

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与其下一个数（就是当前数与其遍历过的上一个数）相同的时候选择交换，可以证明这样操作对答案的增益一定是非负的

证明如下

  1. 如果a[i]==a[n-i+1]，操作无影响

  2. 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";
}

Posted on In , Valine:

A - Profitable Interest Rate

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
    int a,b;cin>>a>>b;
    if(a>=b){
        cout<<a<<"\n";
    }else{
        int k=2*a-b;
        if(k>0){
            cout<<k<<"\n";
        }else{
            cout<<0<<"\n";
        }
    }            
}

B - Buying Lemonade

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
   int n,k;cin>>n>>k;
   vector<int>a(n);
   for(int i=0;i<n;i++) cin>>a[i];
   sort(a.begin(),a.end());
   int sum=0,ans=0,mn=0;
   for(int i=0;i<n;i++){
      a[i]-=mn;
      if(sum+a[i]*(n-i)<k){
         sum+=a[i]*(n-i);
         mn+=a[i];ans+=a[i]*(n-i);
      }else{
         ans+=k-sum;
         break;
      }  
      ans++; 
   }     
   cout<<ans<<"\n";       
}

C - Concatenation of Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
    int n;cin>>n;
    vector<array<int,3>>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1];
        a[i][2]=a[i][0]+a[i][1];
    }     
    sort(a.begin(),a.end(),[&](auto l,auto r){
        if(l[2]!=r[2])return l[2]<r[2]; 
        else return min(l[0],l[1])<min(r[0],r[1]);
    });
    for(int i=0;i<n;i++){
        cout<<a[i][0]<<" "<<a[i][1]<<" ";
    }
    cout<<"\n";
}

D - Skipping

只有答题才能得分，所以跳题相当于花费a[i]从位置i转移到b[i]

答题就是花费0从i转移到i-1

最终答案就是所有能遍历到的位置上的a[i]-cost[i]

b[i]小于等于i时选择跳过是不明智的，因为此时在到达b[i]的过程中通过答题到b[i]能获得的分数一定更大

i 到 j 有两种方法，第一种是 j=b[i]，直接从 i 跳到 j ；第二种是 i<j<b[i] ，从 i 跳到 b[i] 再向左答题到 j，两种方法的花费都是a[i]，

所以我们遍历所有位置，每次取能到当前位置且花费最小，转移到当前位置求每个能遍历到的位置的最小花费

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
void solve(){
   int n;cin>>n;
   vector<pair<int,int>>a(n+1);
   for(int i=1;i<=n;i++) cin>>a[i].first;
   for(int i=1;i<=n;i++) cin>>a[i].second;
   priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
   pq.push({a[1].first,a[1].second});
   vector<int>dp(n+1,1e18);
   dp[1]=0;
   for(int i=2;i<=n;i++){
      while(pq.size()&&pq.top().second<i){
         pq.pop();
      }
      if(pq.empty()){
         break;
      }
      dp[i]=pq.top().first;   
      if(a[i].second>i){
         pq.push({dp[i]+a[i].first,a[i].second});
      }
   }  
   int sum=0,ans=0;          
   for(int i=1;i<=n;i++){
      sum+=a[i].first;
      ans=max(ans,sum-dp[i]);
   }
   cout<<ans<<"\n";
}