【cf比赛练习记录】Codeforces Round #579 (Div. 3)

思考之后再看题解，是与别人灵魂之间的沟通与碰撞

题意给出n个数，问它们向左或者向右是否都能成一个环。比如样例5是从1开始向左绕了一圈 [3, 2, 1, 5, 4] 变成 [1, 2, 3, 4, 5];

思路我的方法是差分，假如成立，相邻两个数的差的绝对值要么是1要么是n-1。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

using namespace std;

int q, n;

int num[202];

int sum[202];

int main()

{

    cin >> q;

    while(q--){

        cin >> n;

        memset(sum, 0, sizeof(sum));

        for(int i = 0; i < n; i++) cin >> num[i];

        bool can = true;

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

            if(i==0){

                sum[i] = num[i] - num[n-1];

            }

            else {

                sum[i] = num[i] - num[i-1];

            }

            if(abs(sum[i]) != 1 && abs(sum[i]) != n-1) can = false;

        }

        if(can) cout << "YES\n";

        else cout << "NO\n";

    }

    return 0;

}

B. Equal Rectangles

题意给出n个矩形，问所给出的4n条木棒所组成的矩形的面积是否都相等。

分析要使面积都相等，则要取中间值。先排个序，然后小的与大的在一起，从两头往中间靠拢。简单的实现。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

using namespace std;

int q, n;

int num[402];

int cnt[10004];

int main()

{

    cin >> q;

    while(q--){

        cin >> n;

        bool can = true;

        memset(cnt, 0, sizeof(cnt));

        for(int i = 0; i < 4*n; i++) {

            cin >> num[i];

            cnt[num[i]]++;

        }

        sort(num, num + 4*n);

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

            if(cnt[i]&1 == 1){ // 不清楚是否会有奇数边，所以遍历了一遍

                can = false;

                break;

            }

        }

        if(can){

            int sq = num[0] * num[4*n - 1]; // 两头

            int l = 2, r = 4*n - 3;

            for( ; l <= r; ){

                if(num[l] * num[r] != sq){

                    can = false;

                    break;

                }

                l += 2; r -= 2;

            }

        }

        if(can) cout << "YES\n";

        else cout << "NO\n";

    }

    return 0;

}

C. Common Divisors

题意求n个数的公约数的个数。

分析先求最大公约数（gcd），然后求这个最大公约数的约数（花样找质数），注意long long。

小插曲 因为我审题不认真，导致看漏了 Output 里的 "the number of..."，结果卡了很久quq。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b){

    if(b == 0) return a;

    else return gcd(b, a%b);

}

int n;

LL num[400005];

int main()

{

    scanf("%d", &n);

    for(int i = 0; i < n; i++) scanf("%I64d", &num[i]);

    LL ans = gcd(num[0], num[1]);

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

        ans = gcd(ans, num[i]);

    }

    LL cnt = 0;

    for(LL i = 1; i*i <= ans; i++){

        if(i*i == ans) cnt += 1;

        else if(ans%i == 0) cnt += 2;

    }

    printf("%I64d\n", cnt);

    return 0;

}

补题 D1. Remove the Substring (easy version)

题意 t是s的子串，问最长可以删去s的连续子串后，仍保持t是s的子串。

分析注意，“the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". ”。然后因为数据小，可以暴力枚举被删子串的起点与终点。

参考博客

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

using namespace std;

string s, t;

int ans;

int main()

{

    cin >> s >> t;

    for(int i = 0; i < s.size(); i++){ // 被删子串起点

        for(int j = i; j < s.size(); j++){ // 被删子串终点

            int tt = 0;

            // 判断删后的子串是否仍满足条件------------

            for(int k = 0; k < s.size(); k++){

                if(k == i){ // 遇到被删的起点立即跳到被删的终点

                    k = j;

                    continue;

                }

                if(s[k] == t[tt]){

                    tt++;

                    if(tt == t.size()){

                        break;

                    }

                }

            }

            // -----------------------------------------

            if(tt == t.size()) ans = max(ans, j-i+1);

        }

    }

    cout << ans << endl;

    return 0;

}

补题 D2. Remove the Substring (hard version)

题意与D1一样，只是数据更大，不能暴力。

分析字符串的配对。经过D1的练手发现，可删去的最长连续子序列分别在t子序列的前、中、尾三个部分。思维有点像尺取法，请配合代码食用。

参考博客

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

string s, t;

int pla[200005];

int main()

{

    cin >> s >> t;

    int j = 0, k = 1;

    pla[0] = -1;    // 有趣的操作

    for(int i = 0; i < s.size(); i++){

        if(j < t.size() && s[i] == t[j]){

            pla[k++] = i;   // 记录第一个子串的位置

            j++;

        }

    }

    for(int i = 0; i < k; i++){

        printf("i:%d pla[]:%d\n", i, pla[i]);

    } cout << endl;

    int ans = 0;

    for(int i = s.size() - 1, j = 0; i >= 0; i--){

        ans = max(ans, i - pla[t.size() - j]);

        printf("i:%d j:%d pla[]:%d i-pla[]:%d\n", i, j, pla[t.size() - j], i - pla[t.size() - j]);

        if(j < t.size() && s[i] == t[t.size() - j - 1]){    // 把t子串的末尾依次往前找

            j++;    // 请耐心思考一下

        }

    }

    cout << ans << endl;

    return 0;

}

补题 E.Boxers

题意在n个数里，可以对任意数+1或者-1或者不变，但是1不能变成0。问经过处理后的n个数里有多少个不同的数字。

分析利用桶排，都往下取，因为1不能减为0.（思考一下，非常简单）

小插曲 我又看错题意了quq

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

using namespace std;

int n;

int a[1500004];

int main()

{

    int num;

    cin >> n;

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

        cin >> num;

        a[num]++;

    }

    int ans = 0;

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

        if(a[i-1]){

            ans++;

        }

        else if(a[i]){

            ans++;

            a[i]--; // 减1往下取，因为减1的数没有

        }

        else if(a[i+1]){

            ans++;

            a[i+1]--; // 同理

        }

    }

    cout << ans << endl;

    return 0;

}

补题 F1. Complete the Projects (easy version)

题意处理n个事件，每次处理时r必须不能小于\(a_i\)，处理完后r的值会加上\(b_i\)的值（\(b_i\)可以是负数），问是否能处理完n个事件，处理完时r不能小于0。

分析典型的贪心题目，需要排序。

当 \(b \geq 0\) 时，取a小的；
当 \(b \leq 0\) 时，取 a+b 大的。

证明请看参考博客

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

#include<string>

#include<stack>

using namespace std;

struct node{

    int a, b;

}pro[102];

int n, r;

node one[102];

node two[102];

bool cmp1(node a, node b){

    return a.a < b.a;

}

bool cmp2(node a, node b){

    return a.a+a.b > b.a+b.b;

}

int main()

{

    cin >> n >> r;

    int num, d, cnt1 = 0, cnt2 = 0;

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

        cin >> num >> d;

        node e; e.a = num; e.b = d;

        if(d >= 0){

            one[cnt1++] = e;

        }

        else {

            two[cnt2++] = e;

        }

    }

    sort(one, one + cnt1, cmp1);

    sort(two, two + cnt2, cmp2);

//    cout << endl;

//    for(int i = 0; i < cnt1; i++){

//        cout << one[i].a << " " << one[i].b << endl;

//    } cout << endl;

//

//    for(int i = 0; i < cnt2; i++){

//        cout << two[i].a << " " << two[i].b << endl;

//    } cout << endl;

    bool can = true;

    for(int i = 0; i < cnt1; i++){

        if(r < one[i].a){

            can = false;

            break;

        }

        else r += one[i].b;

    }

    for(int i = 0; i < cnt2; i++){

        if(r < two[i].a){

            can = false;

            break;

        }

        else r += two[i].b;

    }

    if(r < 0) can = false;

    if(can) cout << "YES\n";

    else cout << "NO\n";

    return 0;

}

巴特西

【cf比赛练习记录】Codeforces Round #579 (Div. 3)

最新文章

热门文章