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 long
const 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 long
const 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;
}