TheForces Round #24 (DIV3-Forces)11.1

TheForces Round #24 (DIV3-Forces)

A - Banis and Cards

思路：不大于n的m的倍数的和

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n,m;cin>>n>>m;
    int c=n/m;
    cout<<c*(c+1)/2*m<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B - Left or Right Shift

思路：要求字典序最小，找出所有字符变成a需要的最少次数，若当前k不够，直接往前转变是最优的；若当前k多出，可通过前后转变又变回a，只需判断当前k的奇偶

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n,k;cin>>n>>k;
    string s;cin>>s;
    string ans;
    for(int i=0;i<n;++i){
        int l=s[i]-'a',r=26-l;
        int x=min(min(l,r),k);
        char c;
        if(min(l,r)<=k)c='a';
        else c=s[i]-x;
        k-=x;
        ans.push_back(c);
        if(i==n-1&&k%2)ans.back()++;
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C - Yet Another ÷2 or +1 Problem

思路：暴力枚举操作，若当前字符全相等直接输出即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n,k;cin>>n>>k;
    string s;cin>>s;
    for(int i=0;i<k;++i)s.push_back(' ');
    int l=0,r=n-1,len=n;
    while(k>0){
        bool p=true;
        while(r-l>1&&s[l]==s[r]) {
            if (r > 0 && s[r] != s[r - 1])p = false;
            l++, r--;
        }
        if(s[l]==s[r]){
            if(p){
                for(int i=0;i<len;++i)cout<<s[i];
                for(int i=0;i<k;++i)cout<<s[len-1];cout<<'\n';
                return ;
            }
//            if(k>1){
//                r=len/2-1;
//                l=0;
//                k-=2;
//                len/=2;
//            }else{
//                for(int i=0;i<len;++i){
//                    cout<<s[i];
//                }cout<<s[len-1]<<'\n';
//                return ;
//            }
            s[len]=s[len-1];
            r=len,l=0;
            len++,k--;
        }else{
            r=len/2-1;
            l=0;
            k--;
            len/=2;
        }
//        cout<<l<<' '<<r<<'\n';
    }
    for(int i=0;i<len;++i)cout<<s[i];cout<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D - Sum and Difference

思路：可以发现最小的和为2l+2，要求所有和不一样，可以通过+3、-2构造出和每次加一；即构造方案为l+2、l、l+3、l+1、l+4、l+2...

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e6+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n,l,r;cin>>n>>l>>r;
    vector<int>ans;
    int now=l;
    if(now+2<=r)ans.push_back(now+2);
    ans.push_back(l);
    while(now+3<=r){
        ans.push_back(now+=3);
        ans.push_back(now-=2);
        if(ans.size()>=n)break;
    }
    if(ans.size()>=n){
        for(int i=0;i<n;++i)cout<<ans[i]<<' ';cout<<'\n';
    }else cout<<"-1\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}

E - L-shaped Dominoes

思路：dp啦，dp[i][j][k]维护前i列且第i列的a对应j、b对应k的状态，可以发现jk一共有四种情况00、01、10、11，维护每种状态即可啦

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e6+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int n;cin>>n;
    vector<vector<vector<int>>>f(n+5,vector<vector<int>>(2,vector<int>(2,0)));
    vector<int>a(n+5),b(n+5);
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>b[i];
//    f[1][1][0]=a[1],f[1][0][1]=b[1],f[1][1][1]=a[1]+b[1];
    for(int i=2;i<=n;++i){
        int s=max(max(f[i-1][0][0],f[i-1][1][1]),max(f[i-1][1][0],f[i-1][0][1]));
        if(i>2)f[i][0][0]=max(f[i][0][0],s);
        f[i][1][0]=max(f[i][1][0],f[i-1][0][0]+a[i-1]+b[i-1]+a[i]);
        f[i][0][1]=max(f[i][0][1],f[i-1][0][0]+a[i-1]+b[i-1]+b[i]);
        f[i][1][1]=max(f[i][1][1],max(max(f[i-1][1][0],f[i-1][0][0])+b[i-1],max(f[i-1][0][1],f[i-1][0][0])+a[i-1])+a[i]+b[i]);
    }
    cout<<max(max(f[n][0][0],f[n][1][1]),max(f[n][1][0],f[n][0][1]))<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}