Atcoder abc329

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(dp)

https://atcoder.jp/contests/abc329

G -  Delivery on Tree

n点，二叉树，根1

m 球, 每个球有 初始点 和 目标点

1个篮子 初始空，位置在1, 最大容量k

每次可以 移动篮子， 装入在起始位置的球，放出在目标位置的球，不能超过最大容量

最终篮子还要回到点1

问 有多少种路径方案方案，经过每条边恰好2次 mod 998244353，且所有球被移动到了目标位置

n 1e4

m 2e5

k 1e3

3s

1024mb

我的思路

2个关键性质：二叉树，所有边恰好走2次

对于一个二叉树的一个有分叉节点来说

如果有左侧向右侧的移动，那么 左侧先于右侧访问

如果有右侧向左侧的移动，那么 右侧先于左侧访问

如果同时有则方案为0

由上 我们可以知道一些 节点的左右的访问先后顺序

那么剩下的就是 点到祖先节点的移动，和祖先到后代的移动

对于 跨 lca的移动来说 可以拆分成 u->lca(u,v) 和 lca(u,v)->v

O(m log n) 可以完成

问题变成n点，2m条 下向上和上向下的 移动限制， 和部分节点有先后顺序的限制的合法方案数

一个问题是移动能否拆成单位距离1的移动？

注意到从上向下的时候 当遇到起始时，且边向内有目标点时，一定要拿起，而遇到放下时，优先放下更优，

而从下向上时， 离开的时候 拿起更优，而到终点时一定要放下

所以 把所有路径可以拆分成 很多单位距离为1的路径，并且同样的贪心规则向下的一定拿起，向上的第二次遇到拿起，能放下就放下，并且在限制了 左右先后以后 对于跨lca的需要注意的是，拿起时 是进入lca(u,v)->v方向的对应边的时候，而不是首次，而对于分叉的其实一样

所以稍微改一下，是进入边 和 离开边产生增加 和减少，不再放在点上

通过树上前缀和 可以 O(m+n)完成

所以变成n个点 有向但双向边，每个边有一个 进入增加，和离开减少，保持 <=k 的方案数

k 1e3 不算大

想法是dp[u][l/r] = map<inc,cnt> 是走这一侧合法的 增量集合? 能做吗？

AC倒是AC了就是写得有点久

代码

https://atcoder.jp/contests/abc329/submissions/50023645

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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);)
ll read(){ll r;scanf("%lld",&r);return r;}
struct state{
public:
  int v;
  int ip; // in +
  int im; // in -
  int op; // out +
  int om; // out -
  bool first;
  state(int v){
    this->v=v;
    this->ip=0;
    this->im=0;
    this->op=0;
    this->om=0;
    this->first=false;
  }
};
vector<state> g[10010]; // g[u] = {v, 进+,出-,返回+，返回-,first}
const int PWR=15;
const int N=10000;
int d[N+10];
int fa[N+10][PWR];

int up(int u,int step){
  per(pwr,0,PWR) if(step & (1<<pwr)) u = fa[u][pwr];
  return u;
}

int lca(int u,int v){
  assert(u!=v);
  int du = d[u];
  int dv = d[v];
  if(du < dv) v=up(v,dv-du);
  else        u=up(u,du-dv);
  if(u==v)return u;
  per(pwr,0,PWR) if(fa[u][pwr]!=fa[v][pwr]) {
    u=fa[u][pwr];
    v=fa[v][pwr];
  }
  return fa[u][0];
}

void add(int u,int v) {
  int uv = lca(u,v);
  if(uv == u) { // 上到下 u->v
    g[u][(up(v,d[v]-d[u]-1) == g[u][0].v) ? 0 : 1].ip += 1; // v在u的左/右分支
    int fv=fa[v][0];
    g[fv][(v == g[fv][0].v) ? 0 : 1].im += 1; // v在fa[v]的左右分支
  } else if(uv == v) { // 下到上
    int fu=fa[u][0];
    g[fu][(u == g[fu][0].v) ? 0 : 1].op += 1; // v在fa[v]的左右分支
    g[v][(up(u,d[u]-d[v]-1) == g[v][0].v) ? 0 : 1].om += 1; // v在u的左/右分支
  } else { // 跨uv
    g[uv][(up(u,d[u]-d[uv]-1) == g[uv][0].v)?0:1].first = true; // u在左/右侧
    add(u,uv);
    add(uv,v);
  }
}
int k;
using ret_state = tuple<int,map<int,mint>>;
ret_state solve(int u) { // {out, map{max,cnt}} , 无方案时 map为空map
  if(g[u].size() == 0) { // 单点
    map<int,mint> ret;
    ret[0]=1;
    return {0,ret};
  }
  auto trans=[&](const state&s)->ret_state{
    auto [v,ip,im,op,om,fir] = s;
    auto [o,res] = solve(v);
    map<int,mint> calc;
    for(auto [mx,cnt]:res) {
      int newmx = max({ip,mx+ip-im,ip-im+o+op});
      if(newmx <= k) calc[newmx] += cnt;
    }
    return {ip-im+o+op-om,calc};
  };
  auto link=[&](const ret_state&s0,const ret_state&s1)->ret_state { // 先s0,再s1
    auto [o_0,res_0] = s0;
    auto [o_1,res_1] = s1;
    mint tot0 = 0;
    for(auto [v,c]:res_0) tot0+=c;
    mint tot1 = 0;
    for(auto [v,c]:res_1) tot1+=c;
    map<int,mint>ret;
    auto itr0=res_0.end();
    auto itr1=res_1.end();
    while(itr0 != res_0.begin() and itr1 != res_1.begin()){
      auto [mx0,c0] =*prev(itr0);
      auto [mx1,c1] =*prev(itr1);
      if(mx0 <= mx1+o_0){ // 左边的全部被右边覆盖
        if(mx1+o_0 <= k) ret[mx1+o_0] += tot0*c1;
        tot1 -= c1;
        itr1 =prev(itr1);
      }else{ // 右边的全被左边max覆盖
        ret[mx0] += c0*tot1;
        tot0 -= c0;
        itr0 = prev(itr0);
      }
    }
    return {o_0+o_1,ret};
  };
  auto [o_l,res_l] = trans(g[u][0]);
  if(g[u].size() == 1) { // 优化长链子?和重儿子?
    return {o_l,res_l};
  }else { //
    auto [o_r,res_r] = trans(g[u][1]);
    if(g[u][0].first and g[u][1].first) {
      return {0,{}}; // 无方案
    }else if(g[u][0].first){
      return link({o_l,res_l},{o_r,res_r});
    }else if(g[u][1].first){
      return link({o_r,res_r},{o_l,res_l});
    }else{
      auto [o_lr,res_lr] = link({o_l,res_l},{o_r,res_r});
      auto [o_rl,res_rl] = link({o_r,res_r},{o_l,res_l});
      map<int,mint> ret;
      for(auto [v,cnt]:res_lr) ret[v]+=cnt;
      for(auto [v,cnt]:res_rl) ret[v]+=cnt;
      return {o_lr,ret};
    }
  }
}

int main(){
  int n=read();
  int m=read();
  k=read();
  rep(i,2,n+1) {
    int x=read();
    g[x].push_back(state(i));
    fa[i][0] = x;
  }
  fa[1][0]=1;
  rep(u,2,n+1) d[u] = d[fa[u][0]]+1;
  rep(i,1,PWR) rep(u,1,n+1) fa[u][i] = fa[fa[u][i-1]][i-1];
  rep(i,0,m) {
    int s=read();
    int t=read();
    add(s,t);
  }
  auto [o,cnt] = solve(1);
  assert(o==0);
  mint ans = 0;
  for(auto [mx,c]:cnt) ans+=c;
  printf("%d\n",ans.val());
  return 0;
}

总结

我不知道这个题目难度在哪，但写起来是真的久，难道是实现上的耗时是它的主要难度？

然后官方std竟然只用了120行？？？？

我看排行榜 maspy ssrs都花了很长时间

这种dp设计感觉挺直接的吧， 然后熟悉c++的lambda以后，基本重复代码越來越少，同时也降低了出错的频率，