[数据结构与算法]Codeforces Round #774 (Div. 2) A-D

A. Square Counting

思路

签到

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t -- ) {
        LL n, s;
        cin >> n >> s;
        cout << s / n / n << endl;
    }
    return 0;
}

B. Quality vs Quantity

思路

签到

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
LL sum[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t -- ) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; i ++ ) 
            sum[i] = sum[i - 1] + a[i];
        bool ok = 0;
        for (int i = 1; i < (n + 1) / 2; i ++ ) {
            if (sum[n] - sum[n - i] > sum[i + 1]) {
                ok = 1;
                break;
            }
        }
        if (ok) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

C. Factorials and Powers of Two

思路

借鉴状态压缩，枚举阶乘数的选择，剩下的用二进制表示，复杂度 $O(2^{12}?logn)$

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long LL;
typedef vector<LL> VI;
VI res;
LL n;
void init() {
    LL ans = 2;
    for (int i = 3; i <= 150; i ++ ) {
        if (ans * i > 1e12) break;
        ans = ans * i;
        res.PB(ans);
    }
    sort(res.begin(), res.end());
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    init();
    while (t -- ) {
        cin >> n;
        int ans = INF;
        for (int i = 0; i < (1 << 12); i ++ ) {
            int j = i;
            int cnt = 0;
            int num = 0;
            LL sum = 0;
            while (j) {
                if (j & 1) {
                    sum += res[cnt];
                    num ++;
                }
                cnt ++;
                j >>= 1;
            }
            cnt = 0;
            sum = n - sum;
            if (sum < 0) continue;
            while (sum) {
                if (sum & 1) cnt ++;
                sum >>= 1;
            }
            ans = min(ans, cnt + num);
        }
        cout << ans << endl;
    }
    return 0;
}

D. Weight the Tree

思路

树形 $dp$，有点像染色，当时甚至想二分图来着，结果是树形 $dp$
我觉得这题主要想到是 $dp$ 就好做了
状态

• $dp0[i]$ : 存储以 $i$ 这个点为根的子树最多的 $goodvertices$ 点数量，且 $i$ 这个点不是 $goodvertices$
• $dp1[i]$ : 存储以 $i$ 这个点为根的子树最多的 $goodvertices$ 点数量，且 $i$ 这个点是 $goodvertices$
• $dq0[i]$ : 存储以 $i$ 这个点为根的子树最小的 $sumofweights$ ，且 $i$ 这个点不是 $goodvertices$
• $dq1[i]$ : 存储以 $i$ 这个点为根的子树最小的 $sumofweights$ ，且 $i$ 这个点是 $goodvertices$

如果点 $i$ 是 $goodvertices$，那么与他相连的点 $j$ 只能不是 $goodvertices$，如果点 $i$ 不是 $goodvertices$，那么与他相连的点 $j$ 可以是也可以不是 $goodvertices$

如果 $n==2$ 的话，不存在相邻两个点只能有一个是 $goodvertices$的问题，两个点都是 $goodvertices$

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef vector<int> VI;
const int N = 2e5 + 10;
VI edg[N];
int dp0[N], dq0[N], dp1[N], dq1[N];
int w[N];
void dfs(int u, int fa) {
    dp0[u] = 0, dq0[u] = 1, dp1[u] = 1, dq1[u] = edg[u].size();
    for (auto j : edg[u]) {
        if (j == fa) continue;
        dfs(j, u);
        dp1[u] += dp0[j], dq1[u] += dq0[j];
        if (dp0[j] > dp1[j] || (dp0[j] == dp1[j] && dq0[j] < dq1[j])) {
            dp0[u] += dp0[j], dq0[u] += dq0[j];
        } else {
            dp0[u] += dp1[j], dq0[u] += dq1[j];
        }
    }
}
void dfs2(int u, int fa, int op) {
    if (op == 1) w[u] = edg[u].size();
    else w[u] = 1;
    for (auto j : edg[u]) {
        if (j == fa) continue;
        if (op) dfs2(j, u, 0);
        else {
            if (dp0[j] > dp1[j] || (dp0[j] == dp1[j] && dq0[j] < dq1[j])) {
                dfs2(j, u, 0);
            } else {
                dfs2(j, u, 1);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) edg[i].clear();
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        cin >> a >> b;
        edg[a].PB(b), edg[b].PB(a);
    }
    if (n == 2) {
        cout << "2 2\n1 1\n";
        return 0;
    }
    dfs(1, -1);
    if (dp0[1] > dp1[1] || (dp0[1] == dp1[1] && dq0[1] < dq1[1])) {
        cout << dp0[1] << ' ' << dq0[1] << endl;
        dfs2(1, -1, 0);
    } else {
        cout << dp1[1] << ' ' << dq1[1] << endl;
        dfs2(1, -1, 1);
    }
    for (int i = 1; i <= n; i ++ )
        cout << w[i] << ' ';
    cout << endl;
	return 0;
}