bwtree
我们可以设 \(dp_{i, 0/1}\) 表示当前考虑至哪个点,这个节点的子树内选了几个叶子节点
#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 5, INF = 1e9;int n, a[N], dp[N][2];vector<int> g[N];void dfs(int u, int f) {dp[u][0] = (a[u] == 1);dp[u][1] = (a[u] == 0);if ((g[u].size() == 1 && g[u][0] == f) || g[u].size() == 0) {return ;}for (auto v : g[u]) {if (v == f) {continue;}dfs(v, u);}int ans = 0, tot = 0, mini = INF;for (auto v : g[u]) {if (v == f) {continue;}if (dp[v][0] > dp[v][1]) {ans += dp[v][0];}else {ans += dp[v][1];tot += 1;}mini = min(mini, max(dp[v][0], dp[v][1]) - min(dp[v][0], dp[v][1]));}dp[u][tot % 2] += ans;dp[u][(tot + 1) % 2] += ans - mini;
}int main() {ios::sync_with_stdio(0);cin.tie(0);freopen("bwtree.in", "r", stdin);freopen("bwtree.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1, u, v; i < n; i++) {cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);cout << max(dp[1][0], dp[1][1]);return 0;
}
prison
一眼题,但是忘了 \(tarjan\) 如何写,答案就是强连通分块数量,连接不同强连通分量之间的边数
#include <bits/stdc++.h>using namespace std;#define int long longconst int N = 1e5 + 5;int n, m, dfn[N], cnt, ans, res[N], a[N], tot;bool vis[N];vector<int> g[N];stack<int> stk;void dfs(int u) {dfn[u] = ++cnt;res[u] = dfn[u];vis[u] = true;stk.push(u);for (auto v : g[u]) {if (!dfn[v]) {dfs(v);res[u] = min(res[u], res[v]);}else if (vis[v]) {res[u] = min(res[u], dfn[v]);}}if (res[u] == dfn[u]) {tot++;while (stk.top() != u) {a[stk.top()] = tot;vis[stk.top()] = false;stk.pop();}a[u] = tot;vis[u] = false;stk.pop();}
}signed main() {freopen("prison.in", "r", stdin);freopen("prison.out", "w", stdout);cin >> n >> m;for (int i = 1, opt, u, v; i <= m; i++) {cin >> opt >> u >> v;if (opt == 0) {g[u].push_back(v);g[v].push_back(u);}else {g[u].push_back(v);}}for (int i = 1; i <= n; i++) {if (!dfn[i]) {dfs(i);}}for (int i = 1; i <= n; i++) {for (auto v : g[i]) {ans += (a[v] != a[i]);}}cout << tot << " " << ans;return 0;
}
placement
我们来拆式子
\[a[i] \times i - b[i] \times (n - i + 1) \\
a[i] \times i - b[i] \times n + b[i] \times i - b[i]\\
(a[i] + b[i]) \times i - (n + 1) \times b[i]
\]
那么式子中的 \(b[i] \times (n + 1)\) 就是确定的了,所以我们只需要关心 \(a[i] + b[i]\),更具式子,显然我们要让 \(a[i] + b[i]\) 大的靠后放,那么我们想让答案最大的形式就已经确定了,我们只能交换 \(a[i] + b[i]\) 相等的数,此题完结
#include <bits/stdc++.h>using namespace std;#define int long longconst int N = 1e5 + 5, mod = 1e9 + 7;struct node {int a, b;
}x[N];int n, inv[N], ans = 1;bool cmp(node _x, node _y) {return _x.a + _x.b < _y.a + _y.b;
}signed main() {freopen("placement.in", "r", stdin);freopen("placement.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++) {cin >> x[i].a;}for (int i = 1; i <= n; i++) {cin >> x[i].b;}inv[1] = 1;for (int i = 2; i <= 100000; i++) {inv[i] = inv[i - 1] * i % mod;}sort(x + 1, x + n + 1, cmp);for (int i = 1; i <= n; i++) {if (x[i].a + x[i].b != x[i - 1].a + x[i - 1].b) {int p = i;while (p <= n && x[p].a + x[p].b == x[i].a + x[i].b) {p++;}ans = ans * inv[p - i] % mod;}}cout << ans;return 0;
}
hierarchy
我们可以维护一堆\(set\),表示职级为 \(a\) 的工资有哪些,\(set\) 为大根堆,我们还可以开一个线段树维护职级为 \([l, r]\) 的最大工资,然后我们在每次往下递归时每次从 \(set\)里删除掉,然后再在回溯时加上即可,然后我们在每次删掉是更新一下线段树
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 5;int t, n, a[N], b[N], maxia[N], maxib[N], c[N], p[N], cnt, tr[N * 4];vector<int> g[N];multiset<int, greater<int>> s[N];bool flag;void build(int i, int l, int r) {if (l == r) {if (!s[l].empty()) {tr[i] = *s[l].begin();}else tr[i] = 0;return ;}int mid = (l + r) >> 1;build(i * 2, l, mid);build(i * 2 + 1, mid + 1, r);tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
}void modify(int i, int l, int r, int p) {if (l == r) {if (!s[l].empty()) {tr[i] = *s[l].begin();}else tr[i] = 0;return ;}int mid = (l + r) >> 1;if (mid >= p) {modify(i * 2, l, mid, p);}else modify(i * 2 + 1, mid + 1, r, p);tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
}int query(int i, int l, int r, int x, int y) {if (x > y) {return 0;}if (l > y || r < x) {return 0;}if (l >= x && r <= y) {return tr[i];}int mid = (l + r) >> 1;return max(query(i * 2, l, mid, x, y), query(i * 2 + 1, mid + 1, r, x, y));
}void dfs(int u, int f) {for (auto v : g[u]) {if (v == f) {continue;}dfs(v, u);maxia[u] = max(maxia[v], maxia[u]);maxib[u] = max(maxib[v], maxib[u]);}if (maxia[u] > a[u] || maxib[u] > b[u]) {flag = false;}maxia[u] = a[u], maxib[u] = b[u];
}void dfs1(int u, int f) {s[a[u]].erase(s[a[u]].find(b[u]));modify(1, 1, cnt, a[u]);for (auto v : g[u]) {if (v == f) {continue;}dfs1(v, u);}int tmp = query(1, 1, cnt, a[u], cnt);if (tmp >= b[u]) {flag = false;}s[a[u]].insert(b[u]);modify(1, 1, cnt, a[u]);
}void Solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i];c[i] = a[i];g[i].clear();maxia[i] = 0, maxib[i] = 0;s[i].clear();}cnt = 0;sort(c + 1, c + n + 1);for (int i = 1; i <= n; i++) {if (c[i - 1] != c[i]) p[++cnt] = c[i];}for (int i = 1; i <= n; i++) {a[i] = lower_bound(p + 1, p + cnt + 1, a[i]) - p;s[a[i]].insert(b[i]);}build(1, 1, cnt);for (int i = 1, u, v; i < n; i++) {cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}flag = true;dfs(1, 0);dfs1(1, 0);if (!flag) {cout << "NO\n";}else cout << "YES\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> t;while (t--) {Solve();}return 0;
}
