Codeforces Round #533 (Div. 2)（ABCD）-蒲公英云

Codeforces Round #533 (Div. 2)（ABCD）

A. Salem and Sticks（暴力）

题意：给你n个棒子，长度分别为ai，让你找到一个长度x，使得n个棒子的长度都变为x+1或者x-1或者x的花费最小，花费为abs(ai-b);

解：因为n只有1000，棒子最长也只有100；所以在1-100内暴力就行了；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int a[maxn];
int b[maxn],n,c[maxn];
int gao(int ans){
    int sum=0;
    for(int i=1;i<=n;i++){
        if(a[i]==ans+1||a[i]==ans||a[i]==ans-1)continue;
        sum+=abs(ans-a[i])-1;
    }
    return sum;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int flag=0,sum1=0,sum2=0,sum3=0,minn=inf;
    for(int i=1;i<=n;i++){
        if(a[i]==a[i-1])
            continue;
        sum1=gao(a[i]);
        sum2=gao(a[i]-1);
        sum3=gao(a[i]+1);
        minn=min(minn,min(sum1,min(sum2,sum3)));
        if(minn==sum1){
            flag=a[i];
        }
        else if(minn==sum2){
            flag=a[i]-1;
        }
        else if(minn==sum3){
            flag=a[i]+1;
        }
    }
    cout<<flag<<' '<<minn<<endl;
    return 0;
}

B. Zuhair and Strings

题意：给你一个字符串s，问你有多少个长度为k的连续相同的字符字串；

解：统计每个字母长度为k的字串用num记录，然后跑一遍num找出最大值；刚开始忘了处理结尾的字符导致wa了两罚；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
int num[30];
int main(){
    ios::sync_with_stdio(false);
    string s;
    int n,k;
    cin>>n>>k;
    cin>>s;
    int cnt=1;
    for(int i=1;i<n;i++){
        if(s[i]==s[i-1]){
            cnt++;
        }
        else{
            if(cnt/k)num[s[i-1]-'a']+=cnt/k;
            cnt=1;
        }
    }
    if(cnt/k)num[s[n-1]-'a']+=cnt/k;
    int ans=0;
    for(int i=0;i<26;i++){
        ans=max(ans,num[i]);
    }
    cout<<ans<<endl;
    return 0;
}

C. Ayoub and Lost Array（DP）

题意：问区间[L,R]内n个数之和%3==0有多少组，数字可以重复使用；

解：刚开始想用多重集排列来做，先求出总的，然后再减去%3==1 %3==2的个数，算了半天发现走不通；

然后观摩了别人的做法，dp

先算一下L-R内%3分别等于0，1，2的个数

用前缀的思想，L-R内%3==0的有R/3-(L-1)/3；那么1和2分别就是(R+2)/3-(L+1)/3 (R+1)/3-(L)/3 (这个可以用a%3=0然后再推一下)

dp[i][0,1,2] i表示选择 i 个时的情况%3==0/1/2的分别有几种

然后dp[i][0]=dp[i-1][0]*a+dp[i-1][1]*c+dp[i-1][2]*b;

其他两个也跟上面差不多；

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
typedef  long long ll;
ll dp[maxn][3];
int main(){
    ll n,l,r;
    cin>>n>>l>>r;
    ll a=r/3-(l-1)/3;
    ll b=(r+2)/3-(l+1)/3;
    ll c=(r+1)/3-l/3;
    dp[1][0]=a,dp[1][1]=b,dp[1][2]=c;
    for(int i=2;i<=n;i++){
        dp[i][0]=(dp[i-1][0]*a%mod+dp[i-1][1]*c%mod+dp[i-1][2]*b%mod)%mod;
        dp[i][1]=(dp[i-1][1]*a%mod+dp[i-1][0]*b%mod+dp[i-1][2]*c%mod)%mod;
        dp[i][2]=(dp[i-1][2]*a%mod+dp[i-1][0]*c%mod+dp[i-1][1]*b%mod)%mod;
    }
    cout<<dp[n][0]%mod<<endl;
    return 0;
}

D. Kilani and the Game（感觉比c简单）（BFS）

题意：给你n*m的图，有p个人，每个人的扩展速度为si，然后#不能扩展，每轮每个人只能扩展一次，直到扩展到不能扩展为止，问每个人的领域是多少

解：每轮每个人跑si次BFS，每次跑完的点再用一个queue来存，然后跑完当前所有的，再把暂存的放到原本的队列中

没做到完美的剪枝导致T了2发；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
int n,m,p;
char s[maxn];
ll ans[maxn];
bool vis[maxn][maxn];
ll sp[maxn];
int cnt=0;
int dx[4]={
     0,1,-1,0};
int dy[4]={
     1,0,0,-1};
queue<pair<int,int>>que[maxn],t;
void bfs(int st){
    int o=sp[st];
    int tot=0;
    while(tot<o){
        int xx=cnt;
        while(!que[st].empty()){
            pair<int,int>u=que[st].front();que[st].pop();
            int x=u.first;
            int y=u.second;
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx<0||ny<0||nx>=n||ny>=m||vis[nx][ny])continue;
                vis[nx][ny]=true;
                t.push(make_pair(nx,ny));
                ans[st]++;
                cnt++;
            }
        }
    if(xx==cnt)return;//剪枝（这个很重要）
        if(cnt>=n*m)return;
        while(!t.empty()){
            pair<int,int>u=t.front();
            t.pop();
            que[st].push(u);
        }
        tot++;
        if(o==tot)return;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for(int i=1;i<=p;i++){
        cin>>sp[i];
    }
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<m;j++){
            if(s[j]=='#'){
                vis[i][j]=true;
                cnt++;
            }
            else if(s[j]>='0'&&s[j]<='9'){
                vis[i][j]=true;
                ans[s[j]-'0']++;
                que[s[j]-'0'].push(make_pair(i,j));
                cnt++;
            }
        }
    }
    while(cnt<n*m){
        int xx=cnt;
        for(int i=1;i<=p;i++){
            bfs(i);
        }
        if(cnt==xx)break;//剪枝
    }
    for(int i=1;i<=p;i++){
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}