第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（南京） CDH

C
Klee in Solitary Confinement
思维题

先预处理出每个数的个数，若k为0，直接输出最大的个数。若不为0，对于每个数，对自己x贡献-1，并且当贡献≤0时，重新置0，意味着不对前面的数+k。然后对x+k贡献+1,并更新最大值，最后输出最大值即可
Code
#include <cstdio> #include <algorithm> #define py 2000000 using namespace std;
int n, k, dp[4000010], ans, sum[4000010], a[4000010]; int main() { //
freopen("_in.txt", "r", stdin); scanf("%d%d", &n, &k); int x; for (int i = 1; i
<= n; i++) { scanf("%d", &a[i]); sum[a[i] + py]++; ans = max(ans, sum[a[i] + py]
); } if(k==0) { printf("%d\n",ans); return 0; } for (int i = 1; i <= n; i++) { x
= a[i]; dp[x + py]--; if (dp[x + py] < 0) dp[x + py] = 0; dp[x + py + k]++; ans
= max(ans, sum[x + py + k] + dp[x + py + k]); } printf("%d\n", ans); return 0; }
D
Paimon Sorting
因为对于序列的每一个数都要询问一次，且该数后面的数对结果没有影响，故考虑插入法

如果插入的数小于当前最大值，则直到最后一轮之前该数都不会对结果有贡献，最后一轮的贡献则为前面比它大的数的个数（去重后），这里用两个树状数组维护。

如果相等，则始终不会产生贡献。

如果插入的数大于当前最大值，经过手模，观察出为2+当前最大值第二次出现后的数的个数。
Code
#include <bits/stdc++.h> #define DEBUG freopen("_in.txt", "r", stdin); //
#define DEBUG freopen("_in.txt", "r", stdin), freopen("_out.txt", "w", stdout);
typedef long long ll; using namespace std; const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll maxn = 2e5 + 10; const ll maxm = 2e7 + 10; const ll mod = 1e9 + 7;
const double pi = acos(-1); const double eps = 1e-8; ll T, n; ll c1[maxn], vis[
maxn],c2[maxn]; ll lowbit(ll i) { return i & (-i); } void update1(ll x) { for (
ll i= x; i <= n; i += lowbit(i)) { c1[i]++; } } ll query1(ll x) { ll ans = 0;
for (ll i = x; i; i -= lowbit(i)) { ans += c1[i]; } return ans; } void update2(
ll x) { for (ll i = x; i <= n; i += lowbit(i)) { c2[i]++; } } ll query2(ll x) {
ll ans= 0; for (ll i = x; i; i -= lowbit(i)) { ans += c2[i]; } return ans; } int
main() { // DEBUG; scanf("%lld", &T); while (T--) { scanf("%lld", &n); for (ll i
= 1; i <= n; i++) { c1[i] = 0; c2[i] = 0; vis[i]=0; } ll v; scanf("%lld", &v);
ll maxx= v, cnt1 = 1, cnt2 = 0, ans = 0, cnt3 = 0; update1(v); vis[v] = 1;
printf("%lld", ans); for (ll i = 2; i <= n; i++) { ll v; scanf("%lld", &v); if (
v< maxx) { ans += i - query1(v)-1-(cnt3 - query2(v)); printf(" %lld", ans); if (
cnt1>= 2) { cnt2++; } } else if (v == maxx) { printf(" %lld", ans); cnt1++; if (
cnt1>= 2) { cnt2++; } } else { ans += 2; ans += cnt2; printf(" %lld", ans); cnt1
= 1; cnt2 = 0; maxx = v; } if(vis[v]) { cnt3++; update2(v); } update1(v); vis[v]
= 1; } printf("\n"); } return 0; }
H
Crystalfly
树上DP，dp[i][2],表示点i的子树所贡献的最大值，dp[i][0]，该点的直连子节点的dp[i][2]的和，对于一个点
1、存在1个3s子节点，则为一个1s点并且损失其全部直连子节点+1个3s子节点
2、存在1个以上3s子节点，则为一个1s点或3s子节点并且损失其全部直连子节点+1个3s子节点
3、不存在3s子节点，则优先选择其中点权最大的子节点
Code
#include <cstdio> #include <algorithm> using namespace std; long long T, n, val
[100010], t[100010], head[100010], k, fa[100010], dp[100010][3]; struct edge {
long long to, next; } ed[200010]; void adde(long long u, long long v) { ed[++k].
to= v; ed[k].next = head[u]; head[u] = k; } void dfs(long long u) { long long
sum_dp0= 0; long long max_i = 0; long long max_it3 = 0; long long max_02 = -
0x3f3f3f3f3f3f3f3f; long long temp = 0; long long lans = 0; for (long long i =
head[u]; i; i = ed[i].next) { long long v = ed[i].to; if (v == fa[u]) continue;
fa[v] = u; dfs(v); sum_dp0 += dp[v][0]; max_i = max(max_i, val[v]); if (t[v] ==
3) { if (max_it3 <= val[v]) { max_it3 = val[v]; temp = v; } } } for (long long i
= head[u]; i; i = ed[i].next) { long long v = ed[i].to; if (v == fa[u]) continue
; if (v == temp) continue; max_02 = max(max_02, dp[v][2] - dp[v][0] + val[v]); }
lans= max_it3 + max_02;//第一种情况 max_it3 = 0; for (long long i = head[u]; i; i =
ed[i].next) { long long v = ed[i].to; if (v == fa[u]) continue; if (v == temp)
continue; if (t[v] == 3) max_it3 = max(max_it3, val[v]); } lans = max(lans,
max_it3+ dp[temp][2] - dp[temp][0] + val[temp]);//第二种情况 dp[u][0] = max(sum_dp0 +
max_i, sum_dp0 + lans);//第三种情况 dp[u][2] = sum_dp0; return; } int main() { scanf
("%lld", &T); while (T--) { scanf("%lld", &n); k = 0; for (int i = 1; i <= n; i
++) { head[i] = 0; fa[i] = 0; dp[i][0] = 0; dp[i][2] = 0; } for (long long i = 1
; i <= n; i++) scanf("%lld", &val[i]); for (long long i = 1; i <= n; i++) scanf(
"%lld", &t[i]); for (long long i = 1; i <= n - 1; i++) { long long u, v; scanf(
"%lld%lld", &u, &v); adde(u, v); adde(v, u); } dfs(1); printf("%lld\n", dp[1][0]
+ val[1]); } return 0; }

• « 上一篇：用Python画圣诞树
• » 下一篇：RSA算法的C语言实现