Codeforces Round #533 (Div. 2) 1113解题报告A/B/C/D

题意：求一个数t 求对于每个数改变到差值在1以内输出t以及最小的花费（总和花费）

题解：枚举t 直接差值不在1以内的求差值绝对值+1 其余的不算



#include <bits/stdc++.h>
#define maxn  1000+5
#define INF 0x3f3f3f3f
using namespace std;
int a[maxn];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int ans,ansd=INF;
    for(int t=0;t<=120;t++){
        int tmp=0;
        for(int i=0;i<n;i++){
            tmp+=abs(t-a[i]);
            if(abs(t-a[i])>0)tmp--;
        }
        if(tmp<=ansd){
            ansd=tmp;
            ans=t;
        }
    }
    cout<<ans<<" "<<ansd<<endl;
    return 0;
}

题意：求每个字母最长的子串

题解：枚举字母求最长子串

#include <bits/stdc++.h>
#define maxn  1000+5
#define INF 0x3f3f3f3f
using namespace std;
int a[maxn];
int main(){
    int n,k;
    string s;
    cin>>n>>k>>s;
    int tmp=1,ans=0,anst=0;
    for(int i=0;i<26;i++){
        ans=0;tmp=0;
        for(int j=0;j<n;j++){
            if(s[j]==i+'a')
                tmp++;
            else tmp=0;
            if(tmp>=k){
                tmp=0;
                ans++;
            }
        }
        anst=max(ans,anst);
    }
    cout<<anst<<endl;
    return 0;
}

题意：给你序列长度和序列每个元素的范围让你求出多少个序列的总和能被3整除

题解：乍看是排列组合，实则是递推dp哒，你就随便看看，我就随便写写（实则是菜）

递推方程i 是前i个元素 j是前n个元素剩下的余数

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int n,l,r;
long long mod0,mod1,mod2,f[200100][3];//记得开long long
int main()
{
    cin>>n>>l>>r;
    mod0=(r-l+1)/3; mod1=(r-l+1)/3,mod2=(r-l+1)/3;
    for(int i=0;i<(r-l+1)%3;i++){
        if((l+i)%3==0)
            mod0++;
        if((l+i)%3==1)
            mod1++;
        if((l+i)%3==2)
            mod2++;
    }
    f[0][0]=1;
    for (int i=1;i<=n;i++){
        f[i][0]=(f[i-1][0]*mod0)%mod+(f[i-1][1]*mod2)%mod+(f[i-1][2]*mod1)%mod;
        f[i][0]%=mod;
        f[i][1]=(f[i-1][1]*mod0)%mod+(f[i-1][2]*mod2)%mod+(f[i-1][0]*mod1)%mod;
        f[i][1]%=mod;
        f[i][2]=(f[i-1][0]*mod2)%mod+(f[i-1][1]*mod1)%mod+(f[i-1][2]*mod0)%mod;
        f[i][2]%=mod;
    }
    cout<<f[n][0]<<endl;
    return 0;
}

题意：从每个数字开始，每次周围方格扩散一次，最后不能扩散为止，输出最后每个数字占多少格

题解：用队列直接模拟，这个写法还是比较具有技巧性的

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000+5
int n,m,p;
int vis[maxn][maxn],pi[maxn],ans[maxn];
char mp[maxn][maxn];
struct node {
    int x,y,i;
};
queue<node>q[maxn];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int bfs(int s){
    int sum=q[s].size();
    queue<node>tmp;
    for(int i=0;i<sum;i++){
        tmp.push(q[s].front());
        q[s].pop();
    }
    while(!tmp.empty()){
        node now=tmp.front();
        tmp.pop();
        for(int i=0;i<4;i++){
            node next;
            next.x=now.x+dx[i],next.y=now.y+dy[i],next.i=now.i;
            if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]!='#'&&vis[next.x][next.y]==0){
                    vis[next.x][next.y]=now.i;
                    q[s].push(next);
            }
        }
    }
    return q[s].size();
}
int main()
{
    node tmp;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=p;i++){
        scanf("%d",&pi[i]);
        if(pi[i]>1000)pi[i]=1000;
    }
    for(int i=0;i<n;i++){
        scanf("%s",mp[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mp[i][j]>'0'&&mp[i][j]<='9'){
                node now;
                vis[i][j]=mp[i][j]-'0';
                now.x=i,now.y=j,now.i=mp[i][j]-'0';
                q[now.i].push(now);
            }
        }
    }
    int flag;
    while(1){
        flag=0;
        for(int i=1;i<=p;i++){
            for(int j=1;j<=pi[i];j++){
                if(bfs(i))flag=1;
                else break;
            }
        }
        if(!flag)break;
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]!=0){
                ans[vis[i][j]]++;
            }
        }
    }
    for(int i=1;i<=p;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}