Educational Codeforces Round 59 (Rated for Div. 2)(ABCD)

港控/mmm° 2023-06-03 13:53 86阅读 0赞

A. Digits Sequence Dividing

题意：给你一个数字串，只包含1-9，让你至少分成两段，使得每一段的数字大于前一段的数字；

解：对n特判，如果n为2，那么比较一下两个数字大小，如果n>2，那么就可以直接分成两部分，第一部分1个数字，剩下都为第二部分；

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

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+10;
    const int mod=998244353;
    ll ans[maxn];
    int main(){
        int T;
        cin>>T;
        while(T--){
            int n;
            string s;
            cin>>n>>s;
            if(n==2){
                if(s[0]<s[1]){
                    cout<<"YES"<<endl;
                    cout<<"2"<<endl;
                    cout<<s[0]<<' '<<s[1]<<endl;
                }
                else cout<<"NO"<<endl;
            }
            else {
                cout<<"YES"<<endl;
                cout<<"2"<<endl;
                cout<<s[0]<<' ';
                for(int i=1;i<n;i++)cout<<s[i];
                cout<<endl;
            }
     
        }
     
     
        return 0;
    }

B. Digital root

题意:给你一个S(x)，让你求第k个x；S(5)=5,S(38)=S(3+8=11)=S(1+1=2)=2;

比如从5 1 有:1 10 19 28 37 46 发现规律：m+（n-1）\*9

解：写几个推下公式就蒙过去了

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

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+10;
     
    int main(){
        int T;
        cin>>T;
        while(T--){
            ll n,m;
            cin>>n>>m;
            cout<<9LL*(n-1)+1LL*m<<endl;
        }
     
        return 0;
    }

C. Brutality

题意：一个字符串，26个字母，每个位置的字母都有一个价值，连续字母出现不能超过k次，如果超过的需要删除掉，问你能获得的最大价值是多少；

解：暴力咯，把连续相同的字母放在优先队列里面，然后不连续之后从队列里面拿出k个，其他的都不要。

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

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=2e5+10;
    ll a[maxn];
    priority_queue<int>que;
    int main(){
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        string s;
        cin>>s;
        que.push(a[0]);
        ll ans=0LL;
        for(int i=1;i<n;i++){
            if(s[i]==s[i-1]){
                que.push(a[i]);
            }
            else{
                int cnt=0;
                while(!que.empty()){
                    if(cnt>=m)break;
                    ans+=que.top();que.pop();
                    cnt++;
                }
                while(!que.empty())que.pop();
                que.push(a[i]);
            }
        }
        int cnt=0;
        while(!que.empty()){
            if(cnt>=m)break;
            ans+=que.top();que.pop();
            cnt++;
        }
        while(!que.empty())que.pop();
        cout<<ans<<endl;
     
     
     
     
     
        return 0;
    }

D. Compression

题意：（自己做的时候还看不懂题意）看了下题解，原来是求把矩阵A能分成最大的矩阵B，满足矩阵B的长度能够被A的长度整除，

且A种B的规格的块要么满足都为1，要么满足都为0才行；

解：把二维前缀和先预处理一下，然后再去枚举n到1矩阵的规格，利用二维前缀和可以快速判断是否满足条件；

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

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=5300;
    int a[maxn][maxn],pre[maxn][maxn];
    string s;
    int n;
    bool check(int x){
        for(int i=0;i<n;i+=x){
            for(int j=0;j<n;j+=x){
                int now=pre[i+x][j+x]+pre[i][j]-pre[i+x][j]-pre[i][j+x];
                if(now!=0&&x*x!=now){
                    return false;
                }
            }
        }
        return true;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>s;
            for(int j=0;j<n/4;j++){
                int x=0;
                if(s[j]>='A'&&s[j]<='Z')
                    x=10+s[j]-'A';
                else x=s[j]-'0';
                a[i][4*j+3]=x>>0&1;
                a[i][4*j+2]=x>>1&1;
                a[i][4*j+1]=x>>2&1;
                a[i][4*j+0]=x>>3&1;
            }
        }
        /*for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<a[i][j]<<' ';
            }
            cout<<endl;
        }*/
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                pre[i+1][j+1]=pre[i][j+1]+pre[i+1][j]-pre[i][j]+a[i][j];
            }
        }
        for(int i=n;i>=1;i--){
            if(n%i==0){
                if(check(i)){
                    cout<<i<<endl;
                    return 0;
                }
            }
        }
     
     
        return 0;
    }

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

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