goto

A Salem and Sticks

水题，直接枚举即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,a[1005],mincost=1e9,ans;

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for (int i=0;i<=105;++i){
        int tmp=0;
        for (int j=1;j<=n;++j){
            tmp+=min({abs(a[j]-i),abs(a[j]-i-1),abs(a[j]-i+1)});
        }
        if (tmp<mincost) mincost=tmp,ans=i;
    }
    cout<<ans<<' '<<mincost<<endl;
    return 0;
}

B Zuhair and Strings

水题，枚举字母，然后更新答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k,ans;
char s[200005];

int main(){
    cin>>n>>k;
    scanf("%s",s+1);
    for (int i=0;i<26;++i){
        char tmp=i+'a';
        int j=1,last=1,tans=0;
        while (j<=n){
            if (s[j]!=tmp){
                j++;
                continue;
            }
            last=j;
            while (s[j]==tmp && j<=n){
                j++;
            }
            tans+=(j-last)/k;
        }
        ans=max(ans,tans);
    }
    cout<<ans<<endl;
    return 0;
}

C Ayoub and Lost Array

一个计数DP，F[i][j]表示前i为之和变为j的方案总数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,l,r,a[10];
long long f[200005][4],p=1e9+7;

void init(){
    int t1=(l/3),t2=(r/3);
    a[0]=a[1]=a[2]=t2-t1;
    a[0]++;
    t1*=3;
    t2*=3;
    for (int i=t1;i<=l-1;++i) a[i%3]--;
    for (int i=t2+1;i<=r;++i) a[i%3]++;
}

int main(){
    cin>>n>>l>>r;
    init();
    for (int i=0;i<=2;++i) f[1][i]=a[i]%p;
    for (int i=2;i<=n;++i){
        for (int j=0;j<=2;++j){
            for (int k=0;k<=2;++k){
                f[i][j]=((f[i-1][(j-k+3)%3]*a[k]%p)+f[i][j])%p;
            }
        }
    }
    cout<<f[n][0]<<endl;
    return 0;
}

D Kilani and the Game

一个多源BFS，注意每个点只需要进行一次扩展，因此队列中只需要保存上一次新拓展得到的点即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{
    int x,y;
}con[12][1000005];

struct sta{
    int x,y,step;
};

int n,m,p,a[15],f[1005][1005],cnt[15],last[15],last_last[15];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char s[1005];
queue <sta> q;

void bfs(int player){
    while (!q.empty()) q.pop();
    for (int i=last_last[player]+1;i<=last[player];++i){
        q.push({con[player][i].x,con[player][i].y,a[player]});
    }
    while (!q.empty()){
        sta tmp=q.front();
        q.pop();
        for (int i=0;i<=3;++i){
            int x=tmp.x+dx[i],y=tmp.y+dy[i];
            if (x>=1 && y>=1 && x<=n && y<=m && f[x][y]==0 && tmp.step>0){
                f[x][y]=player;
                cnt[player]++;
                con[player][cnt[player]]={x,y};
                q.push({x,y,tmp.step-1});
            }
        }
    }
}

void solve(){
    while (1){
        int y=0;
        for (int i=1;i<=p;++i) bfs(i);
        for (int i=1;i<=p;++i) last_last[i]=last[i];
        for (int i=1;i<=p;++i){
            if (last[i]!=cnt[i]) y=1;
            last[i]=cnt[i];
        }
        if (y==0) break;
    }
}

int main(){
    cin>>n>>m>>p;
    for (int i=1;i<=p;++i) scanf("%d",&a[i]);
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        for (int j=1;j<=m;++j){
            int tmp;
            if (s[j]=='.') tmp=0;
            else if(s[j]=='#') tmp=-1;
            else tmp=s[j]-'0';
            f[i][j]=tmp;
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            if (f[i][j]>0){
                cnt[f[i][j]]++;
                con[f[i][j]][cnt[f[i][j]]]={i,j};
            }
        }
    }
    for (int i=1;i<=p;++i) last[i]=cnt[i];
    solve();
    for (int i=1;i<=p;++i) cout<<cnt[i]<<' ';
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/96/