D. Pair of Topics
题解
将不等式变下形:(a_i + a_j > b_i + b_j)等价于(a_i - b_i > b_j - a_j)
令(c[i] = a_i - b_i, d[j] = b[j] - a[j]),问题转化为对于每一个(c),有多少个(d)小于它。将(d)排序,然后二分查找即可。
注意去重和(a[i] > b[i])的情况
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
long long ans = 0;
for (int i = 1; i <= n; ++i) {
cin >> b[i];
c[i] = a[i] - b[i];
if (c[i] > 0) ans--;
b[i] = b[i] - a[i];
}
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++i) {
ans += lower_bound(b + 1, b + n + 1, c[i]) - (b + 1);
}
cout << ans / 2 << endl;
return 0;
}
E. Sleeping Schedule
题目:https://codeforces.com/contest/1324/problem/E
决定多练练DP,orz
题解
对于每次碎觉,可以选择提前睡或者不提前睡
令 (dp[i][j]:=) 睡觉次数为(i),提前睡了(j)次的 (good) (sleeping) (times) (很自然的定义,有木有),(sum[i] = sum_{j = 1}^{i}a_i),有:
- (dp[i][j]) = (max(dp[i - 1][j]), (dp[i - 1][j - 1]) + check((sum - j) \% h, l, r))
注意边界!
只需要知道提前睡了几次,不用记录是哪几次提前睡的(%%%出题人)。因为模运算可以合并
/*cf给出代码一向都很nice,用vector初始化二维数组是真的方便*/
inline bool check(int x, int l, int r) {
return (l <= x && x <= r);
}
void Solve() {
int n, h, l, r;
cin >> n >> h >> l >> r;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<vector<int> > dp(n + 1, vector<int>(n + 1, -INF));
dp[0][0] = 0;
int sum = 0;
for (int i = 1; i <= n; ++i) {
sum += a[i];
dp[i][0] = dp[i - 1][0] + check(sum % h, l, r);
for (int j = 1; j < i; ++j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + check((sum - j) % h, l, r);
dp[i][i] = dp[i - 1][i - 1] + check((sum - i) % h, l, r);
}
cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
}
F. Maximum White Subtree
一棵树(无根)有(n)个节点,每个节点都被染色(黑色 or 白色)
对于每个节点,找一个包含该节点的连通块,使得连通块中白色节点的个数与黑色节点个数的差值最大,既(Cnt_{white} -Cnt_{black})最大
题解
题目中(subtree)指的是包含节点(u)的连通块。
假如这是一颗有根树,对于每个节点,只考虑求: 以该节点为根的子树的(max(Cnt_w - cnt_b))。那么自底向上(dp)统计即可:
令(dp[u]:=cnt_w - cnt_b),则(dp[parent_u] = dp[parent_u] + (dp[u] > 0 ? dp[u] : 0))
显然,这样只正确求出了根节点的答案。对于除根以外的节点,都没有考虑(parent_u)对节点(u)的贡献。
令(ans[u]:=)节点(u)的完整答案,则(ans[root] =dp[root])。假设我们已经求得了(ans[parent_u]),怎么求(ans[u])呢?仔细观察一下,发现:
- (dp[u] leq 0),意味着(u)对(parent_u)没有贡献
- (ans[parent_u] leq 0),则 (ans[u] = dp[u])
- (ans[parent_u] > 0),则 (ans[u] = ans[parent_u] + dp[u])
- (dp[u] > 0)
- (ans[parent_u] leq dp[u]),则 (ans[u] = dp[u])
- (ans[parent_u] > 0),则 (ans[u] = ans[parent_u])
整理一下,然后(code)
int n, cnt;
int dp[MAXN], ans[MAXN], head[MAXN];
struct edge { int to, next; } e[MAXN * 2];
void Inite() {
cnt = 0;
memset(head, -1, sizeof(head));
}
void add_edge(int u, int v) {
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
void DFS_down_to_top(int u, int p) {
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (p == v) continue;
DFS_down_to_top(v, u);
dp[u] += (dp[v] > 0 ? dp[v] : 0);
}
}
void DFS_top_to_down(int u, int p) {
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (p == v) continue;
if (dp[v] <= 0) {
if (ans[u] <= 0) ans[v] = dp[v];
else ans[v] = dp[v] + ans[u];
}
else {
if (ans[u] <= dp[v]) ans[v] = dp[v];
else ans[v] = ans[u];
}
DFS_top_to_down(v, u);
}
}
int main() {
Inite();
cin >> n;
for (int i = 1, u; i <= n; ++i) {
cin >> u;
dp[i] = (u == 1 ? 1 : -1);
}
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
DFS_down_to_top(1, -1);
ans[1] = dp[1];
DFS_top_to_down(1, -1);
for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
cout << endl;
return 0;
}