2021中國大學生程式設計競賽（CCPC）- 網絡選拔賽

1001 - Cut The Wire

補題連結

x x x是偶數時:

x > = n + 1 x >= n + 1 x>=n+1 & & \&\& && x 2 < = n \frac{x}{2} <= n 2x​<=n

⇒ ⇒ ⇒ n + 1 < = x < = 2 n n+1 <= x <= 2n n+1<=x<=2n

是以區間大小為 2 n − ( n + 1 ) + 1 = n 2n - (n + 1) + 1 = n 2n−(n+1)+1=n

可以确定 2 n 2n 2n 一定是偶數，

是以在 [ n + 1 , 2 n ] [n+1, 2n] [n+1,2n] 區間内偶數的個數為 ⌈ n 2 ⌉ ⌈\frac{n}{2}⌉ ⌈2n​⌉

可以表示為 s u m 1 = sum1 = sum1= n + 1 2 \frac{n+1}{2} 2n+1​

x x x 是奇數時:

x < = n x <= n x<=n & & \&\& && 3 x + 1 > = n + 1 3x + 1 >= n + 1 3x+1>=n+1

⇒ ⇒ ⇒ n 3 < = x < = n \frac{n}{3} <= x <= n 3n​<=x<=n

是以區間的大小為 n − ⌈ n 3 ⌉ + 1 n - ⌈\frac{n}{3}⌉ + 1 n−⌈3n​⌉+1 = = = ⌊ 2 n 3 ⌋ + 1 ⌊\frac{2n}{3}⌋ + 1 ⌊32n​⌋+1

如果 n n n 是奇數并且區間大小是奇數

如: 3 , 4 , 5 , 6 , 7 3, 4, 5, 6, 7 3,4,5,6,7

此時區間内滿足是奇數的個數有 區間大小 s u m 2 = s i z e / 2 + 1 sum2 = size / 2 + 1 sum2=size/2+1 個

而其他情況( n n n是奇數和區間大小 s i z e size size是奇數不同時滿足)

如: 3 , 4 , 5 , 6 3, 4, 5, 6 3,4,5,6 或者 4 , 5 , 6 4, 5, 6 4,5,6 或者 4 , 5 , 6 , 7 4, 5, 6, 7 4,5,6,7

此時區間内滿足是奇數的個數有 區間大小 s u m 2 = s i z e / 2 sum2 = size / 2 sum2=size/2 個

最後輸出 s u m 1 + s u m 2 sum1 + sum2 sum1+sum2 即可 ~

#include <iostream>

using namespace std;

typedef long long ll;

int main(){

    int t, n;
    scanf("%d", &t);
    ll res;
    while (t--){

        scanf("%d", &n);

        ll sum1 = (n + 1) / 2;
        ll sum2 = (n * 2 / 3 + 1);

        if(sum2 % 2 && n % 2){
            sum2 = sum2 / 2 + 1;
        }else{
            sum2 = sum2 / 2;
        }

        res = sum1 + sum2;

        printf("%lld\n", res);
    }

    return 0;
}
           

1009 - Command Sequence

補題連結

用 m a p map map 記錄經過每一點的次數，如果經過次數 x > 1 x > 1 x>1，則這個點對答案的貢獻為 x ∗ ( x − 1 ) / 2 x * (x - 1) / 2 x∗(x−1)/2

（在紙上畫一下就知道了 ~）

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

unordered_map<ll, ll> mp;

ll row, col, res;

char s[N];

int main(){

    ll t, n;
    scanf("%lld", &t);

    while (t--){

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

        row = 0, col = 0, res = 0;
        mp[0] = 1;

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

            switch (s[i]){

                case 'U':
                    col++; break;
                case 'D':
                    col--; break;
                case 'R':
                    row++; break;
                case 'L':
                    row--; break;
            }

            ll pos = row * N + col;

            mp[pos]++;
        }

        for(auto p: mp){
            ll x = p.second;
            res += x * (x - 1) / 2;
        }

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

        mp.clear();
    }

    return 0;
}
           

1006 - Power Sum

可以發現任何相鄰 4 4 4 項 平 方 數 平方數 平方數 取 1001 1001 1001 即 + − −   + + - - ~+ +−− + 的結果都為 4 4 4，比如 16 − 25 − 36 + 49 = 4 16 - 25 - 36 + 49 = 4 16−25−36+49=4 而 1 = 1 1 = 1 1=1， 2 = − 1 − 4 − 9 + 16 2 = -1 - 4 - 9 + 16 2=−1−4−9+16， 3 = − 1 + 4 3 = -1 + 4 3=−1+4，這樣湊出來 ⌊ n 4 ⌋ ⌊\frac{n}{4}⌋ ⌊4n​⌋ 個 1001 1001 1001， n   %   4 n ~ \% ~ 4 n % 4 的值用最前面的項湊就行了 !

#include <iostream>

using namespace std;

int main(){

    int t;

    cin >> t;

    while (t--){

        int n;

        cin >> n;

        if(n % 4 == 0) cout << n << endl;
        else if(n % 4 == 1) cout << n << "\n" << "1";
        else if(n % 4 == 2) cout << n + 2 << "\n" << "0001";
        else if (n % 4 == 3) cout << n - 1 << "\n" << "01";

        for (int i = 1; i <= n / 4; ++i) {
            cout << "1001";
        }
        cout << endl;
    }

    return 0;
}
           

1007 - Function