11.13
挂分场。
t1
神秘淀粉质。
不想改了，反正noip不考（题解说的）。
赛时写了2h发现想假了，当场😡。
t2
简单构造。
但是挂分了。
每个球跳的次数求假了（不是这也能假）。
然后就挂了。
code
www
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> ans;signed main()
{freopen("atom.in", "r", stdin);freopen("atom.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> n;int k = n - 1;if (k & 1)m = (1 + (k >> 1)) * (k >> 1) + (k / 2 + 1);elsem = (1 + (k >> 1)) * (k >> 1);cout << m << "\n";int cnt = 0, d = 1, tot, sum, lim = 1;int SUM = 0;for (int i = 1; i <= m; ++i){ans.clear();tot = 0, sum = 0;// if (i == m)// cout << "d=" << d << "\n";if (cnt)sum += cnt, ans.emplace_back(cnt), ++tot;while (sum < k - d)sum += d, ans.emplace_back(d), ++tot;if (sum + d == k)ans.emplace_back(d), ++tot;cout << tot << ' ';for (auto y : ans)cout << y << ' ';cout << "\n";++cnt;if (cnt == lim){++d, cnt = 0;lim = (d > (k >> 1) ? k - d + 1 : d);// cout << "d=" << d << " lim=" << lim << "\n";}}// cout << SUM << "\n";return 0;
}
t3
树形dp(换根可以省)
dp一下回来的和不回来的。
注意是奇数减一还是偶数减一。
细节挺多，看代码吧。
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{int res = 0;char ch = getchar_unlocked();while (ch < '0')ch = getchar_unlocked();while (ch >= '0' && ch <= '9'){res = (res << 3) + (res << 1) + (ch ^ 48);ch = getchar_unlocked();}return res;
}const int maxn = 1e6 + 10;
int T, n;
int tot, to[maxn << 1], nxt[maxn << 1], h[maxn], val[maxn << 1];
inline void adde(int x, int y, int z)
{to[++tot] = y;nxt[tot] = h[x];h[x] = tot;val[tot] = z;
}int dp[maxn][2], sec[maxn], ans; // 0 no back / 1 go back
int fa[maxn];inline void dfs(int x, int f)
{for (int i = h[x]; i; i = nxt[i]){int y = to[i];if (y == f)continue;dfs(y, x);if (val[i] > 1)dp[x][1] += dp[y][1] + val[i] - (val[i] & 1);}for (int i = h[x]; i; i = nxt[i]){int y = to[i];if (y == f)continue;if (dp[x][1] - (val[i] > 1 ? dp[y][1] + val[i] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[y][0], dp[y][1]) >= dp[x][0]){sec[x] = dp[x][0];dp[x][0] = dp[x][1] - (val[i] > 1 ? dp[y][1] + val[i] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[y][0], dp[y][1]);fa[x] = y;}else if (sec[x] < dp[x][1] - (val[i] > 1 ? dp[y][1] + val[i] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[y][0], dp[y][1])){sec[x] = dp[x][1] - (val[i] > 1 ? dp[y][1] + val[i] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[y][0], dp[y][1]);}}
}inline void dfs1(int x, int f)
{ans = max(ans, max(dp[x][0], dp[x][1]));int reco0 = dp[x][0], reco1 = dp[x][1];for (int i = h[x]; i; i = nxt[i]){int y = to[i];if (y == f)continue;dp[x][0] = reco0, dp[x][1] = reco1;if (fa[x] == y){dp[x][0] = max(sec[x] - (val[i] > 1 ? val[i] + dp[y][1] - (val[i] & 1) : 0), dp[x][1] - max(dp[y][0], dp[y][1]) - val[i] + (val[i] & 1));}else{dp[x][0] = dp[x][0] - ((val[i] > 1 ? dp[y][1] + val[i] - (val[i] & 1) : 0));}if (val[i] > 1){dp[y][0] += dp[x][1] - dp[y][1];int tmp = dp[y][1];dp[y][1] = dp[x][1];dp[x][1] -= tmp + val[i] - (val[i] & 1);}if (dp[y][0] <= dp[y][1] - (val[i] > 1 ? val[i] + dp[x][1] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[x][1], dp[x][0])){sec[y] = dp[y][0];dp[y][0] = dp[y][1] - (val[i] > 1 ? val[i] + dp[x][1] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[x][1], dp[x][0]);fa[y] = x;}else if (sec[y] < dp[y][1] - (val[i] > 1 ? val[i] + dp[x][1] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[x][1], dp[x][0]))sec[y] = dp[y][1] - (val[i] > 1 ? val[i] + dp[x][1] - (val[i] & 1) : 0) + val[i] - (!(val[i] & 1)) + max(dp[x][1], dp[x][0]);dfs1(y, x);}
}signed main()
{freopen("plan.in", "r", stdin);freopen("plan.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cin >> T;while (T--){cin >> n;tot = 0;for (int i = 1; i <= n; i++)fa[i] = sec[i] = dp[i][0] = dp[i][1] = h[i] = 0;for (int i = 1, u, v, w; i < n; i++)cin >> u >> v >> w, adde(u, v, w), adde(v, u, w);dfs(1, 0);ans = 0;dfs1(1, 0);cout << ans << '\n';}return 0;
}
t4
不做简单题。
发现好像只要t1投入大量时间且得到分数不高就坠机了，之后的题满脑子都是暴力，根本无法有效思考。