Atcoder abc219

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
F(排序,分组)G(根号分类,分类)H(区间DP,问题转化)

F - Cleaning Robot

https://atcoder.jp/contests/abc219/tasks/abc219_f

给序列 从点(0,0) 出发,上下左右走n个点,

重复序列k次, 问经过次数>=1的点有几个

限制

n 2e5

k 1e12

2s

1024mb

我的思路

可以看成 一个图形, 每次平移固定向量, k次,问覆盖的图形面积

似乎脑补可得: 每次计算增量, 如果增量不变, 则往后都是这个增量

但不知道如何判断 达到了最小增量

如果是这个形状, s -> e

1
2
3
4
5
xxx
x
x
e
sxx

那么下一次增量是5, 下下次增量也是5, 但是 这不是最小增量, 最小是3

所以可能要变成去计算每个点首次不产生贡献的时刻, 而不产生贡献,也就是沿着 e -> s 的向量方向如果存在点

所以考虑对点归类, 能够通过向量 e -> s 到达的 归类

然后比较时刻和所有点的首次不产生贡献的时间即可

不产生时刻 = 同类别最近的方向向量 / 向量

好像就过了

代码

https://atcoder.jp/contests/abc219/submissions/33772772

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
75
76
77
78
79
80
81
82
#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 per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

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

char s[200010];
int ch[256];

int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};

vector<pair<pair<ll,ll>,ll> > pos;

int main(){
  ch[(int)'L'] = 0;
  ch[(int)'R'] = 1;
  ch[(int)'U'] = 2;
  ch[(int)'D'] = 3;
  scanf("%s",s);
  int n = strlen(s);
  ll k = read();

  ll dx = 0;
  ll dy = 0;
  vector<pair<ll,ll> > vis = {{dx,dy}};
  rep(i,0,n){
    dx += di[ch[(int)s[i]]];
    dy += dj[ch[(int)s[i]]];
    vis.push_back({dx, dy});
  }
  if(dx < 0){ // 保证在 (-pi/2,pi/2]
    dx = -dx;
    dy = -dy;
  }else if(dx == 0 && dy < 0){ // <- bug dx == 0
    dy = -dy;
  }

  sort(vis.begin(),vis.end());
  rep(i,0,vis.size()) if(i == 0 || vis[i] != vis[i-1]){
    auto [x,y] = vis[i];
    ll t = 0;
    if(dx != 0){ // dx >= 0
      t = x/dx;
      x -= t * dx;
      y -= t * dy;
      if(x < 0){
        t --;
        x += dx;
        y += dy;
      }
    }else if(dy != 0){ // dx == 0, dy >= 0
      t = y/dy;
      y -= t * dy;
      if(y < 0){
        t --;
        y += dy;
      }
    }
    pos.push_back({ { x , y } , t}); // 没空格 hexo 炸了
  }
  sort(pos.begin(),pos.end());
  ll ans = 0;
  if(dx == 0 && dy == 0){
    ans = pos.size();
  }else{
    rep(i,0,pos.size()){
      if(i == 0 || pos[i].first != pos[i-1].first){
        ans += k;
      }else{
        ans += min(k, pos[i].second - pos[i-1].second);
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}

G - Propagation

https://atcoder.jp/contests/abc219/tasks/abc219_g

n个点,m跳边的图, 点i上写的i

q次操作

每次让点xi 上的值扩散给它的所有相邻节点

输出最终每个点上的值

范围

n 2e5

m 2e5

q 2e5

无重边 自环

2s

1024mb

我的思路

直接模拟? 如果出现2层菊花形状 每次一个外层染进来,中心扩散, 那么可能就是QN的量级

那么思路方向一个如何批量 或者 lazy的表示

另一个就是有没有可能倒着做

如果把做为修改中心的, 作为点, 按时间顺序和依赖关系 可以建立树(森林), 但不太知道怎么去建

题解

分度处理

对于度小于 $\sqrt{m}$, 直接修改周围的点, 而对于 $\ge \sqrt{m}$的度的点, 在点上标识

对于查询, 可以查询所有, 相当于边访问2次

而每次 处理前, 需要遍历一次周围度大于等于$\sqrt{m}$ 的

复杂度分析

修改就不用说了显然

而就每次获取最新状态时, 因为要遍历相邻的所有度$\sqrt{m}$

那么假设有$w$个, 那么即使边来自它们之间 $\frac{w \sqrt{m}}{2} leq m$, 即$w \leq {2\sqrt{m}}$, 说明也是$O(\sqrt{m})$ 级别的访问

中间复杂度$O(q\sqrt{m})$, 最后查询复杂度$O(n\sqrt{m})$

代码

https://atcoder.jp/contests/abc219/submissions/33773300

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
#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 per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

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

vector<int>p2[200010];
vector<int>pl[200010]; // linked large
bool large[200010]; // is large
pair<int,int> distr[200010]; // [u] = {value, time}

int a[200010]; // value
int t[200010]; // time

int getV(int u){
  int val = a[u];
  int ti = t[u];
  for(auto v:pl[u]) if(distr[v].second > ti) tie(val,ti) = distr[v];
  return val;
}

int main(){
  int n = read();
  ll m = read();
  int q = read();
  rep(i,0,m){
    int u = read();
    int v = read();
    p2[u].pb(v);
    p2[v].pb(u);
  }
  iota(a+1,a+n+1,1);
  rep(i,1,n+1) large[i] = (ll)p2[i].size() * (ll)p2[i].size() > m;
  rep(u,1,n+1){
    for(auto v:p2[u]){
      if(large[v]) pl[u].push_back(v);
    }
  }
  rep(ti,1,q+1){
    int u = read();
    int val = getV(u);
    a[u] = val;
    t[u] = ti;
    if(large[u]){
      distr[u] = {val, ti};
    }else{
      for(auto v:p2[u]){
        a[v] = val;
        t[v] = ti;
      }
    }
  }
  rep(i,1,n+1) printf("%d ",getV(i));
  return 0;
}

H - Candles

https://atcoder.jp/contests/abc219/tasks/abc219_h

N 个蜡烛, 第i个在Xi, 长度Ai

每分钟, 点燃的蜡烛长度-1, 直到 = 0, 而没点燃的不变化

初始在0,每分钟可以移动+1/-1, 如果当前位置有任何蜡烛,可以扑灭(不耗时)

求所有蜡烛长度剩余和的最大值

范围

N 300

xi [-1e9,1e9]

Ai [1,1e9]

我的思路

第一感觉是, 向左走 然后一直向右, 或者向右然后一直向左, 找这个折反点

问题是,会不会出现 左右左的情况?

例如-1上有10个, 2上有10个, -4 上1个, 都足够的长

那么 0 -> -1 -> 2 -> -4 的损失是21 * 1 + 11 * 3 + 1 * 6, 是最小的

这样证否了贪心折返

注意到N很小

甚至能接受 n^3, 考虑dp

dp[i..j][0] = [i,j] 区间内全部熄灭(烧完), 停在i 的 {最大长度, 时间}

问题是, 这种状态设计下, 最大长度和时间是有一致性吗?

题解

也是说, 仅从访问来看

如果已经访问过的区间是[X_i,X_j] 那么下一次 一定是[X_{i-1},X_j] 或[X_i,X_{j+1}]

修改一下问题

  1. 蜡烛可以负数长度
  2. 你可以在起始时移除一些蜡烛

显然新答案不会比原答案更大,而如果有一个答案的方案你照着走,然后把是会是负数的在一开始就移除,那么也可以达到这个原答案的最大值

那么

  1. 初始 分 = 0
  2. 计数 C 去 [0,N] 之间的一个值, 相当于剩余的蜡烛个数,但是不知道具体是哪C个蜡烛
  3. Hi等于对应蜡烛的高度
  4. 每次移动坐标变化1, 分数 -= C
  5. 对于走到一个未访问过的点, 且C > 0, 可以选择 C-=1, 分 += Hi

求最大分

显然最优解和答案是一样的

// 咦 我怎么看到上凸函数的影子

然后就可以dp了

dp[i][j][flag][k] = 已获的最大分数, $[X_i,X_j]$ 已经访问,$flag = 0$ 在$X_i$,$flag = 1$ 在$X_j$, $k$ 是剩余的要去熄灭的蜡烛个数

那么转移方程, 走到$X_i$

dp[i][j][0][k] = max(dp[i+1][j][0/1][k] - 距离 * k, dp[i+1][j][0/1][k+1] - 距离 * (k+1) + H[i])

转移方程, 走到$X_j$

dp[i][j][1][k] = max(dp[i][j-1][0/1][k] - 距离 * k, dp[i][j-1][0/1][k+1] - 距离 * (k+1) + H[i])

最后答案就是dp[0][n-1][0/1][0]

代码

https://atcoder.jp/contests/abc219/submissions/33780170

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
#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 per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

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

const int N = 300;

ll dp[N+10][N+10][2][N+10];
pair<int,int> ph[N+10]; // pos height 起点 {0,0}
const ll INF = 0x3f3f3f3f3f3f3f3f;

void setMax(ll &v0,ll v1){ if(v1 > v0) v0 = v1; }

int main(){
  int n = read();
  rep(i,1,n+1){
    auto p = read();
    auto h = read();
    ph[i] = {p,h};
  }
  sort(ph,ph+n+1);
  int ci = -1; // center i 起始点
  rep(i,0,n+1){
    if(ph[i] == make_pair(0,0)){
      ci = i;
      break;
    }
  }
  rep(i,0,n+1) rep(j,0,n+1) rep(f,0,2) rep(c,0,n+1) dp[i][j][f][c] = -INF;
  rep(f,0,2) rep(c,0,n+1) dp[ci][ci][f][c] = 0;
  per(i,0,ci+1) rep(j,ci,n+1) {
    //dp[i][j][0][k]=max(dp[i+1][j][0/1][k]-距离*k,dp[i+1][j][0/1][k+1]-距离*(k+1)+H[i])`
    //dp[i][j][1][k]=max(dp[i][j-1][0/1][k]-距离*k,dp[i][j-1][0/1][k+1]-距离*(k+1)+H[i])`
    if(i == j) continue;
    rep(c,0,n+1) rep(f,0,2) {
      if(i < ci) {
        auto [x,h] = ph[i];
        const ll pos[] = {i+1, j};
        ll &res = dp[i][j][0][c];
        setMax(res, dp[pos[0]][pos[1]][f][c] - (ph[pos[f]].first - x) * c);
        if(c < n) setMax(res, dp[pos[0]][pos[1]][f][c+1] - (ph[pos[f]].first - x) * (c+1) + h);
      }
      if(j > ci){
        auto [x,h] = ph[j];
        const ll pos[] = {i, j-1};
        ll &res = dp[i][j][1][c];
        setMax(res, dp[pos[0]][pos[1]][f][c] - (x - ph[pos[f]].first) * c);
        if(c < n) setMax(res, dp[pos[0]][pos[1]][f][c+1] - (x - ph[pos[f]].first) * (c+1) + h);
      }
    }
  }
  printf("%lld\n", max(dp[0][n][0][0], dp[0][n][1][0]));
  return 0;
}

总结

F

一眼题

G

分类处理, 根号分治

做了不少分类的,又忘了分类

H

一个是题目转化去掉限制的技巧不会啊, 如果直接是转化后的题面, 那我还是会区间DP的, 但这个转化感觉遇到多了学一学转化

其实就是这里每分钟下降 燃烧着的个数, 会因为=0而难以维护, 通过支持负数 和可预先移除来让每分钟下降易于维护, 同时保持新的最大答案 = 原答案

n^3和dp的感知还是没有问题, 虽然在没有前面转化的情况下用处不大

参考

官方题解