Atcoder abc218

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
G(DP,树,multiset)H(王钦石二分,Alien Trick)

G - Game on Tree 2

https://atcoder.jp/contests/abc218/tasks/abc218_g

n点, 树, 点i上有数字Ai

初始 棋子在点1, 交替玩, 每次移动到未访问过的相邻点, 直到无法移动为止

先手 希望最大化访问过的中位数, 后手希望最小化中位数

如果他们都最优方案, 求这个中位数

限制

N 1e5

Ai [2,1e9]

我的思路

既然是树, 相当于1作为根, 走到叶节点结束, 路径上的中位数就是结果

换句话说, 每个叶节点 可以存储结果

如果能够算出每个从根到叶的结果, 那么简单的根据深度树上dp就完了(根 同的2倍深度 选最大, 根%2不同深度选最小)

想到的是相当于从中间剖开,那么dfs维护一个大根堆,一个小根堆,让它们元素个数差最多是1即可

代码

https://atcoder.jp/contests/abc218/submissions/33755229

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int A[100010];
vector<int> e[100010];

template<typename T> using maxSet = multiset<T, greater<T>>;
template<typename T> using minSet = multiset<T>;

int mid[100010];

template<typename T>
void balance(maxSet<T> &small,minSet<T> &large){
  while(large.size() > small.size()){
    small.insert(*large.begin());
    large.erase(large.begin());
  }
  while(small.size() >= large.size() + 2){
    large.insert(*small.begin());
    small.erase(small.begin());
  }
}

template<typename T>
int dfs(int u,int f,maxSet<T> &small,minSet<T> &large, int dep){
  // 插入
  if(small.size() == 0 || *small.begin() >= A[u]){
    small.insert(A[u]);
  }else{
    large.insert(A[u]);
  }
  balance(small,large);

  int res = 0;
  if(u != 1 && e[u].size() == 1){ // leaf
    res = (small.size() == large.size()) ? (*small.begin() + *large.begin())/2 : *small.begin();
  }else{
    vector<int> vals;
    for(auto v:e[u]) if(v != f) vals.push_back(dfs(v,u,small,large,dep^1));
    res = (dep==0)? *max_element(vals.begin(),vals.end()) : *min_element(vals.begin(),vals.end());
  }
  // 删除
  auto sptr = small.find(A[u]);
  if(sptr != small.end()){
    small.erase(sptr);
  }else{
    auto lptr = large.find(A[u]);
    assert(lptr != large.end());
    large.erase(lptr);
  }
  balance(small,large);
  return res;
}

int main(){
  int n = read();
  rep(i,1,n+1) A[i] = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  maxSet<int> small ; // 前一半
  minSet<int> large ;
  printf("%d\n",dfs(1,1,small,large,0));
  return 0;
}

H - Red and Blue Lamps

https://atcoder.jp/contests/abc218/tasks/abc218_h

N个灯, 你需要让R个红色,N-R个蓝色

如果 i 和 i+1 不同色 则有Ai的贡献

求最大的贡献

范围

N 2e5

R [1,N-1]

Ai [1,1e9]

2s

1024mb

我的思路

显然有个n^2的dp

dp[i][j][c] = 前i个有j个红色,第i个颜色为c,的最大贡献

dp[i][j][red] = max(dp[i-1][j-1][red] , dp[i-1][j-1][blue] + A[i])

dp[i][j][blue] = max(dp[i-1][j][red] +A[i], dp[i-1][j][blue])

但肯定超时

题解

如果红色比蓝色多, 则交换颜色数量

那么尽量多的两两不同,显然红色不相邻

那么把 A[i]+A[i+1] 看作整体

构造B[i] = A[i]+A[i+1] 数组

变成在B中选r个不相邻的元素使得总价值最大, 类似的dp[i][j][0/1] = 前i个,选了j个,第i个是否选的最大值

dp[i][j][1] = dp[i-1][j-1][0] + B[i]

dp[i][j][0] = max(dp[i-1][j][1],dp[i-1][j][0])

复杂度依然不能接受

但是有简单的性质: 可以王钦石二分

王钦石二分

  1. 当可选的越多(虽然题目要你求具体的), 那么总收益越大(单增)
  2. 当选的越多, 增量非严格递减凹函数(上凸)
  3. 不限制个数,容器得到最优方案

反过来, 如果我们指定一个最大收益, 那么可以快速算出需要可选的最少数量

如果变成二维图,是凹(上凸)函数,

方法是二分斜率, 对斜率找和凹函数的切点(切线)

而显然切线在y轴截距最大, f(x) = g(x) - k x, 原函数g(x), 截距函数f(x)

问题变成 给k, 找最大f(x), 而 g(x) - k x 从另一个角度看, 就是每个值-k 以后选x, 对于x没有限制时, 容易求的话,那就容易得到f(x) 和 x

求的话因为干掉了一个记录当前有多少个的限制, 从而可以简单dp

然后…. 我被卡double /long double 了

现实是,本身斜率就是 每次增量, 答案不会有小数,而切点对切线斜率也是单调影响, 所以,全整数就行了

代码

https://atcoder.jp/contests/abc218/submissions/33768310

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
ll a[200010];

pair<ll,int> f(ll v){ // f(斜率) => {最大截距, 横坐标(选的个数)}
  auto dp = vector(n,vector(2,pair<ll,int>{0,0})); // dp[i][第i个 选/不选] = {最大截距,个数}
  rep(i,1,n){
    auto [y0, c0] = dp[i-1][0];
    dp[i][1] = {y0 + (a[i-1] - v), c0 + 1}; // 当前选, 则上一个不选
    dp[i][0] = max(dp[i-1][0],dp[i-1][1]); // 当前不选, 则上一个可选可不选
  }
  return max(dp[n-1][0],dp[n-1][1]);
}

int main(){
  n = read();
  int x = read();
  x = min(x, n-x);
  rep(i,0,n-1) a[i] = read(); // [0..n-2]
  rep(i,0,n-1) a[i] += a[i+1]; // [0..n-2], 看成多了末尾多了一个0, 对最大值无影响
  ll L = 0, R = 3000'000'000; // 斜率
  // 二分, 这里可能 有多个点 让同一个斜率最大, 保证 斜率R < x <= 斜率L 即可, 注意到这这里可能 f(R).pos < f(L).pos < x, 但f(L).pos 只是斜率L上的任意一点 但只要x 斜率不大于 L即可
  while(L + 1 < R) (f((L+R)/2).second < x ? R : L) = mid;
  printf("%lld\n", f(L).first + x * L);
}

总结

G

没啥难的

H

感觉有的时候还是有点 PE的味道,偏数学一点

这里涉及 王钦石二分, 也是凸(凹)函数和二分相关的知识

然后这里double还不行,得long double

参考

官方题解

王钦石二分