CodeForces. Round 502

比賽連結：CodeForces Round #502
以下為我個人的解法，在優化上不一定做得很好。

Problem A

水題。對每筆資料進行Sorting，再用O(n)的方式找答案即可。
時間複雜度：$O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n[1001];
    int a, b, c, d, tmp;
    int e;
    cin >> e;
    for (int i = 0; i < e; i++) {
        cin >> a >> b >> c >> d;
        n[i] = a + b + c + d;
        if (!i)
            tmp = n[i];
    }
    sort(n, n + e, cmp);
    for (int i = 0; i < e; i++)
        if (n[i] == tmp) {
            cout << i + 1 << '\n';
            return 0;
        }
    return 0;
}

Problem B

這題可拆成四個狀態。

A == 1 && B == 1
A == 0 && B == 0
A == 1 && B == 0
A == 0 && B == 1

分別紀錄四種狀態，再用乘法解決即可。
要注意需使用long long int 64位元整數型態
時間複雜度：$O(n)$

#include <bits/stdc++.h>
using namespace std;

string a, b;
long long stat[4];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    cin >> a >> b;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) {
            if (a[i] == '1') //1 1
                stat[0]++;
            else
                stat[1]++; // 0 0
        }else {
            if (a[i] == '1') // 1 0
                stat[2]++;
            else
                stat[3]++; // 0 1
        }
    }
    long long int ans = 0;
    ans = stat[0] * stat[1];
    ans += stat[2] * stat[1];
    ans += stat[2] * stat[3];
    cout << ans << '\n';
    return 0;
}

Problem C

這題是比較偏向數學的題目，解釋起來有點麻煩，以下會列出前10個答案，應該可以推論出規律。
時間複雜度：$O(n)$

1
1 2
3 1 2
3 4 1 2
4 5 1 2 3
4 5 6 1 2 3
7 4 5 6 1 2 3
7 8 4 5 6 1 2 3
7 8 9 4 5 6 1 2 3
9 10 5 6 7 8 1 2 3 4

程式碼：

#include <bits/stdc++.h>
using namespace std;

int square[318];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, tmp;
    cin >> n;
    for (int i = 1; i < 318; i++) square[i] = i*i;
    int a = upper_bound(square, square + 318, n) - square;
    if (a && square[a - 1] == n) a--;
    int res = n % a;
    tmp = n - res;
    while (res--) {
        cout << n - res << ' ';
    }

    while (tmp > 0) {
        for (int i = a - 1; i >= 0; i--)
            cout << tmp - i << ' ';
        tmp -= a;
    }
    cout << '\n';
}

Problem D

這題首先要先注意到$ n \le 12$，所以0-1字串的組合數最多只有到$2^{12}$種。但是題目的查詢數目遠多於$2^{12}$，所以這裡要先考慮到的就是先建表及記憶化(DP)。 接下來，關於0-1字串的比對，可以想到Bitwise的方法，將0-1字串轉成二進位的數字，再用^去比對。 然後就開始用暴力搜尋，對每一種0-1字串組合去計算「價格」。
時間複雜度：$O(2^{2n})$

#include <bits/stdc++.h>
using namespace std;
int cnt[1 << 13];
int ans[1 << 13][101];
int cost[13];
int to2(long long a) {
    int mul = 1;
    int ans = 0;
    while (a) {
        ans += mul * (a & 1);
        a /= 10;
        mul *= 2;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    long long a, b;
    cin >> n >> m >> q;
    for (int i = n - 1; i >= 0; i--)
        cin >> cost[i];
    for (int i = 0; i < m; i++) {
        cin >> a;
        cnt[to2(a)]++;
    }
    int MAX = 1 << n;
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (!cnt[j])
                continue;
            int tmp = i ^ j;
            int sum = 0;
            for (int k = 0; k < n; k++) {
                if (!(tmp & (1 << k)))
                    sum += cost[k];
            }
            if (sum > 100)
                continue;
            ans[i][sum] += cnt[j];
        }
        for (int j = 1; j <= 100; j++)
            ans[i][j] += ans[i][j - 1];
    }
    while (q--) {
        cin >> a >> b;
        cout << ans[to2(a)][b] << '\n';
    }
    return 0;
}

以上就是我比賽時AC的題目。