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

痛定思痛。 2023-06-03 13:52 26阅读 0赞

A. Salem and Sticks（暴力）

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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了两罚；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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发；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
    }

转载于:https://www.cnblogs.com/lin1874/p/11371003.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/3ed0594ac3ee4ce69655aa061a586c81.png