Codeforces Edu Round 59 A-D

A. Digits Sequence Dividing

注意特殊情况，在\(n = 2\)时除非\(str[1] >= str[2]\)，否则可以把第一个数划分下来，剩下的数直接当成一组，一定满足条件。

#include <cstdio>

#include <iostream>

#include <string>

using namespace std;

const int N = 310;

int n;

char s[N];

int main(){

    int T; scanf("%d", &T);

    while(T--){

        scanf("%d%s", &n, s + 1);

        if(n == 2){

            if(s[1] >= s[2]) puts("NO");

            else printf("YES\n2\n%c  %c\n", s[1], s[2]);

        }else{

            printf("YES\n2\n%c ", s[1]);

            for(int i = 2; i <= n; i++) putchar(s[i]);

            puts("");

        }

    }

    return 0;

}

B. Digital root

通过打表找规律发现的…看了题解，证明还是很NB的...

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long LL;

int main(){

    int T; scanf("%d", &T);

    while(T--){

        LL k, x; scanf("%lld%lld", &k, &x);

        printf("%lld\n", (k - 1) * 9 + x);

    }

    return 0;

}

C. Brutality

用堆维护连续子段最大和即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long LL;

const int N = 200010;

int n, k, a[N];

LL ans = 0;

char s[N];

priority_queue<int, vector<int>, greater<int> > q;

int main(){

    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; i++) scanf("%d", a + i);

    scanf("%s", s + 1);

    for(int i = 1; i <= n; i++){

        if(s[i] != s[i - 1]){

            while(!q.empty()) ans += q.top(), q.pop();

            q.push(a[i]);

        }else{

            q.push(a[i]);

        }

        while(q.size() > k) q.pop();

    }

    while(!q.empty()) ans += q.top(), q.pop();

    printf("%lld\n", ans);

    return 0;

}

D. Compression

实质上是把这图压缩到最小的点阵图，用\(bitset\)优化复杂度，暴力水过。

#include <cstdio>

#include <iostream>

#include <bitset>

using namespace std;

const int N = 5210;

bitset<N> a[N];

int n;

//密集恐惧症

int main(){

    ios::sync_with_stdio(false);

    cin >> n;

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= n; j += 4){

            char x; cin >> x;

          	//16进制转2进制

            if(x == '1') a[i][j + 3] = 1;

            else if(x == '2') a[i][j + 2] = 1;

            else if(x == '3') a[i][j + 2] = a[i][j + 3] = 1;

            else if(x == '4') a[i][j + 1] = 1;

            else if(x == '5') a[i][j + 1] = a[i][j + 3] = 1;

            else if(x == '6') a[i][j + 2] = a[i][j + 3] = 1;

            else if(x == '7') a[i][j + 1] = a[i][j + 2] = a[i][j + 3] = 1;

            else if(x == '8') a[i][j] = 1;

            else if(x == '9') a[i][j] = a[i][j + 3] = 1;

            else if(x == 'A') a[i][j] = a[i][j + 2] = 1;

            else if(x == 'B') a[i][j] = a[i][j + 2] = a[i][j + 3] = 1;

            else if(x == 'C') a[i][j] = a[i][j + 1] = 1;

            else if(x == 'D') a[i][j] = a[i][j + 1] = a[i][j + 3] = 1;

            else if(x == 'E') a[i][j] = a[i][j + 1] = a[i][j + 2] = 1;

            else if(x == 'F') a[i][j] = a[i][j + 1] = a[i][j + 2] = a[i][j + 3] = 1;

        }

    }

    for(int x = n; x >= 2; x--){

        if(n % x) continue;

        bool ep = true;

        for(int i = 1; i <= n; i += x){

            for(int j = i + 1; j < i + x; j++){

                ep = ep && (a[j] == a[i]);

                if(!ep) break;

            }

            if(!ep) break;

            for(int j = 1; j <= n; j += x){

                for(int k = j + 1; k < j + x; k++){

                    ep = ep && (a[i][k] == a[i][k - 1]);

                    if(!ep) break;

                }

                if(!ep) break;

            }

            if(!ep) break;

        }

        if(ep) { cout << x; return 0; }

    }

    cout << 1;

    return 0;

}

巴特西

Codeforces Edu Round 59 A-D

A. Digits Sequence Dividing

B. Digital root

C. Brutality

D. Compression

最新文章

热门文章