Codeforces Global Round 19

签到

#include 
using namespace std;
const int N = 1e4 + 10;
int a[N], b[N];
int main() {
    int t;
    cin >> t;
    while (t -- ) {
        int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    bool ok = 0;
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i ++ )
        if (b[i] != a[i]) ok = 1;
	    if (ok) puts("YES");
	    else puts("NO");
    }
    return 0;
}

显然，把所有的 a i a_i ai​ 都分开答案最佳，只有当 a i a_i ai​ 等于 0 0 0 时，收益是 1 1 1
这题要是把题干中的 c c c 去掉就有意思了

#include 
using namespace std;
int a[110];
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) 
            scanf("%d", &a[i]);
        int ans = 0;
        for (int i = 1; i <= n; i ++ )
            ans += i * (n - i + 1) * (1 + (a[i] == 0));
        cout << ans << endl;
    }
    return 0;
}

签到

#include 
using namespace std;
const int N = 1e5 + 10;
int a[N], sum[N];
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) 
            scanf("%d", &a[i]);
        if (n == 3 && a[2] % 2 == 1) {
            puts("-1");
            continue;
        } 
        bool ok = 1;
        for (int i = 2; i < n; i ++ )
            if (a[i] != 1) ok = 0;
        if (ok) {
            puts("-1");
            continue;
        }
        LL ans = 0;
        for (int i = 2; i < n; i ++ )
            ans += (a[i] + 1) / 2;
        printf("%lldn", ans);
    }
    return 0;
}

看到平方猜到均值不等式，那展开式子看，推出 ∑ i = 0 n a i 2 ∗ ( n − 2 ) + ∑ i = 0 n b i 2 ∗ ( n − 2 ) + s u m a 2 + s u m b 2 sum_{i=0}^{n} a_i ^ 2* (n - 2) + sum_{i=0}^{n} b_i ^ 2* (n - 2) + sum_a ^ 2 + sum_b ^2 i=0∑n​ai2​∗(n−2)+i=0∑n​bi2​∗(n−2)+suma2​+sumb2​
题目转化成求 s u m a 2 + s u m b 2 sum_a ^ 2 + sum_b ^ 2 suma2​+sumb2​ 的最小值，那么这就是均值不等式，也就是让 s u m a sum_a suma​ 和 s u m b sum_b sumb​ 的差越小越好。看到 n n n 的范围，显然，这是一个 01 01 01 背包
背包状态： i i i 表示走到第 i i i 个 a i a_i ai​， j j j 表示前 i i i 个 a i a_i ai​ 的和， d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 个 s u m a sum_a suma​ 和 s u m b sum_b sumb​ 的差
背包转移：见代码

#include 
using namespace std;
int a[110], b[110];
int dp[110][10010];
int work(int a, int b) {
    return a * a + b * b;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n;
        scanf("%d", &n);
        LL sum = 0;
        for (int i = 1; i <= n; i ++ ) {
            scanf("%d", a + i);
            sum += a[i];
        }
        for (int i = 1; i <= n; i ++ ) {
            scanf("%d", b + i);
            sum += b[i];
        }
        for (int i = 0; i <= n; i ++ )
            for (int j = 0; j < 10010; j ++ ) {
                dp[i][j] = INF;
            }
        dp[0][0] = 0;
        for (int i = 0; i < n; i ++ ) {
            for (int j = 0; j < 10010; j ++ ) {
                if (j >= a[i + 1] && abs(dp[i + 1][j]) > abs(dp[i][j - a[i + 1]] + a[i + 1] - b[i + 1])) {
                    dp[i + 1][j] = dp[i][j - a[i + 1]] + a[i + 1] - b[i + 1];
                }
                if (j >= b[i + 1] && abs(dp[i + 1][j]) > abs(dp[i][j - b[i + 1]] + b[i + 1] - a[i + 1])) {
                    dp[i + 1][j] = dp[i][j - b[i + 1]] + b[i + 1] - a[i + 1];
                }
            }
        }
        int ans = INF, pos = 0;
        for (int j = 0; j < 10010; j ++ )
            if (abs(dp[n][j]) < ans) {
                ans = abs(dp[n][j]);
                pos = j;
            }
        LL res = 0;
        for (int i = 1; i <= n; i ++ )
            res += work(a[i], b[i]) * (n - 2);
        res += pos * pos + (sum - pos) * (sum - pos);
        cout << res << endl;
    }
    return 0;
}

大模拟

#include 
using namespace std;
#define PB push_back
typedef long long LL;
typedef pair PII;
typedef vector VI;
unordered_map cnt;
set bad;
VI flag;
unordered_map v;
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        cnt.clear();
        bad.clear();
        flag.clear();
        v.clear();
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) {
            int a;
            scanf("%d", &a);
            cnt[a] ++;
        }
        for (int i = 1; i <= m; i ++ ) {
            int x, y;
            scanf("%d%d", &x, &y);
            bad.insert(minmax(x, y));
        }
        for (auto [x, num] : cnt) {
            if (v[num].empty()) flag.PB(num);
            v[num].PB(x);
        }
        for (auto t : flag)
            sort(v[t].begin(), v[t].end(), greater());
        LL ans = 0;
        for (auto i : flag) {
            for (auto j : flag) {
                if (i == j) {
                    for (auto x : v[i])
                        for (auto y : v[j]) {
                            if (x == y) break;
                            if (!bad.count(minmax(x, y))) {
                                ans = max(ans, 1ll * (i + i) * (x + y));
                                break;
                            }
                        }
                    break;
                }
                for (auto x : v[i]) {
                    for (auto y : v[j]) {
                        if (!bad.count(minmax(x, y))) {
                            ans = max(ans, 1ll * (i + j) * (x + y));
                                break;
                        }
                    }
                    if (!bad.count(minmax(x, v[j][0]))) break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

树形 d p dp dp