codeforces|Codeforces Round #774 (Div. 2) A-D codeforces|算法

A. Square Counting 思路签到

#include 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 思路 【codeforces|Codeforces Round #774 (Div. 2) A-D】签到

#include 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 ? l o g n ) O(2 ^ {12} * log n) O(212?logn)

#include using namespace std; #define PB push_back typedef long long LL; typedef vector 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 思路树形d p dp dp，有点像染色，当时甚至想二分图来着，结果是树形d p dp dp
我觉得这题主要想到是d p dp dp 就好做了
状态

d p 0 [ i ] dp0[i] dp0[i] : 存储以i i i 这个点为根的子树最多的g o o dv e r t i c e s good　vertices good　vertices 点数量，且i i i 这个点不是g o o dv e r t i c e s good　vertices good　vertices
d p 1 [ i ] dp1[i] dp1[i] : 存储以i i i 这个点为根的子树最多的g o o dv e r t i c e s good　vertices good　vertices 点数量，且i i i 这个点是g o o dv e r t i c e s good　vertices good　vertices
d q 0 [ i ] dq0[i] dq0[i] : 存储以i i i 这个点为根的子树最小的s u mo fw e i g h t s sum　of　weights sum　of　weights ，且i i i 这个点不是g o o dv e r t i c e s good　vertices good　vertices
d q 1 [ i ] dq1[i] dq1[i] : 存储以i i i 这个点为根的子树最小的s u mo fw e i g h t s sum　of　weights sum　of　weights ，且i i i 这个点是g o o dv e r t i c e s good　vertices good　vertices

如果点i i i 是g o o dv e r t i c e s good　vertices good　vertices，那么与他相连的点j j j 只能不是g o o dv e r t i c e s good　vertices good　vertices，如果点i i i 不是g o o dv e r t i c e s good　vertices good　vertices，那么与他相连的点j j j 可以是也可以不是g o o dv e r t i c e s good　vertices good　vertices
如果n = = 2 n == 2 n==2 的话，不存在相邻两个点只能有一个是g o o dv e r t i c e s good　vertices good　vertices的问题，两个点都是g o o dv e r t i c e s good　vertices good　vertices

#include using namespace std; #define PB push_back typedef vector 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; }