Atcoder abc298

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
G(枚举)Ex(树,DP,LCA)

https://atcoder.jp/contests/abc298/tasks

G - Strawberry War

H行W列

有s[i][j]个草莓

每次切割，把一个剩余块横向或纵向切成两块

t次切割后，让 一块最多草莓 - 一块最少草莓 尽量小

h,w [1,6]

s[i,j] [0,10^16]

6s

1024mb

我的思路

dp[l,r,t,b,t] = set<pair<min,max> >

因为min越大 max可能也会增大，所以min max应该 成对

这样状态数比较大

注意到状态合并

左侧[min,max] =>

若右侧 l >= min, 取 min(max,右侧r)

若左侧 r <= max, 取 max(min,右侧l)

否则 l < min and max < r 则是 [l,r]

但这样也很大

题解

可能的矩形个数为$\frac{H(H+1)W(W+1)}{4}$

把这些矩形中的 个数 列出$a_1,a_2,\cdots,a_x$

对于$i=1,2,\cdots,X$, 计算 min(max(M)), 其中所有块都$\ge a_i$

dp[minx][maxx][miny][maxy][m] =, 对应矩形切成m块的 min(max(个数))

X是 $O(H^2W^2)$

DP是$O(H^2W^2T)$ 个状态, 状态转移$O((H+W)T)$

可以暴力过………

代码

https://atcoder.jp/contests/abc298/submissions/42058278

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=7; // 1-index
const ll INF=0x3f3f3f3f'3f3f3f3f;
ll a[N][N];
ll cal(int l,int r,int t,int b){
  return a[r][b]-a[r][t-1]-a[l-1][b]+a[l-1][t-1];
};

int main() {
  int H=read();
  int W=read();
  int k=read();
  rep(i,1,H+1)rep(j,1,W+1) a[i][j]=read();
  rep(i,1,H+1)rep(j,1,W+1) a[i][j]+=a[i-1][j];
  rep(i,1,H+1)rep(j,1,W+1) a[i][j]+=a[i][j-1];
  ll ans=INF;
  rep(l,1,H+1)rep(r,l,H+1)rep(t,1,W+1)rep(b,t,W+1){
    auto dp=vector(N,vector(N,vector(N,vector(N,vector<ll>(k+1,-1)))));
    ll mn=cal(l,r,t,b);
    auto dfs=[&](int l,int r,int t,int b,int T,auto&fn)->ll{
      ll &ret=dp[l][r][t][b][T];
      if(~ret) return ret;
      ret=INF;
      if((r-l+1)*(b-t+1)<=T or cal(l,r,t,b)<mn*(T+1))return ret;
      if(!T) return ret=cal(l,r,t,b);
      rep(i,l,r)rep(j,0,T)ret=min(ret,max(
            fn(l  ,i,t,b,j    ,fn),
            fn(i+1,r,t,b,T-1-j,fn)));
      rep(i,t,b)rep(j,0,T)ret=min(ret,max(
            fn(l,r,t  ,i,j    ,fn),
            fn(l,r,i+1,b,T-1-j,fn)));
      return ret;
    };
    ans=min(ans,dfs(1,H,1,W,k,dfs)-mn);
  }
  printf("%lld",ans);
  return 0;
}

Ex Sum of Min of Length

n点树, d(u,v)为u..v距离

q个询问:li,ri

$\sum_{j=1}^{N} min(d(j,L_i),d(j,R_i))$

n,q 2e5

3s

1024mb

我的思路

首先树不变化

每次询问，相当于，树上所有点 到 给定 两点最近距离的和

...u.......v...

3部分，u..v链上的点和链上点衍生的树, u..v链以外的点

首先有lca 容易计算出公共祖先和 距离的中点

对于子树向点到u的距离和可以dp[u] = (sum dp[v]) + sz[u]-1算出来

对于父向的直接算似乎不好算，但是可以换根dp算所有点到u的距离和

因此 对于u…v链以外的点 的距离贡献和就很好算了 = 到u/到v 所有贡献和减去一个分支的距离贡献和

当u,v只有一个中点(否则是两个中点)时，不妨全部是连u

于是可以变成...u...midu-midv...v...

ans = all(u) + all(v) - (midv右子树->u) - (midu左子树->u)

而(midv右子树->u) = midv右子树 贡献和 + 个数 * d(u,midv)

所以似乎就没了?

代码

https://atcoder.jp/contests/abc298/submissions/42059400

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
#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);)
ll read(){ll r;scanf("%lld",&r);return r;}

vector<int> g[200010];
int n;
int d[200010];
int sz[200010]; // 子树大小
ll s[200010]; // 子树到u距离贡献
ll a[200010]; // 所有点到u距离贡献
const int PWR=22;
int fa[200010][PWR];
void dfs(int u,int f,int dep){
  sz[u]=1;
  d[u]=dep;
  fa[u][0]=f;
  rep(pwr,1,PWR) fa[u][pwr]=fa[fa[u][pwr-1]][pwr-1];
  for(auto v:g[u]) if(v!=f){
    dfs(v,u,dep+1);
    sz[u]+=sz[v];
    s[u]+=s[v]+sz[v];
  }
}

void dfs1(int u,int f,ll ans){
  a[u] = ans;
  for(auto v:g[u]) if(v!=f) dfs1(v,u, ans + (n-sz[v]) - (sz[v]));
  // printf("node[%d] = {sz=%d,s=%lld,fa=%d,d=%d,a=%lld}\n",u,sz[u],s[u],fa[u][0],d[u],a[u]);
}

int stepup(int u,int s){
  per(pwr,0,PWR) if(s >= (1<<pwr)){
    u=fa[u][pwr];
    s-=(1<<pwr);
  }
  return u;
}

int lca(int u,int v){
  if(d[u] > d[v]){
    u=stepup(u,d[u]-d[v]);
  }else if(d[v] > d[u]){
    v=stepup(v,d[v]-d[u]);
  }
  int du=d[u];
  int dv=d[v];
  assert(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];
}

pair<ll,ll> usubv(int u,int v){ // u,v相邻 u的所有贡献减去v的分支, {长度贡献,点数}
  if(d[u] < d[v]){ // u父
    return {a[u] - (s[v]+sz[v]), n-sz[v]};
  }else{ // v父
    return {s[u],sz[u]};
  }
  assert(false);
}

ll dis(int u,int v){
  int r=lca(u,v);
  return (d[u]-d[r])+(d[v]-d[r]);
}

ll query(int u,int v){
  if(u==v) return a[u];
  // u != v
  int r=lca(u,v);
  int l=dis(u,v);
  int midu;
  int midv;
  if(d[u] == d[v]){
    midu = r;
    midv = stepup(v,l/2-1);
  }else if(d[u] > d[v]){
    midu = stepup(u,l/2);
    midv = stepup(u,l/2+1);
  }else { // d[v] > d[u]
    midu = stepup(v,l/2+1);
    midv = stepup(v,l/2);
  }

  ll ans =0;
  // ...u...midu-midv...v...
  {
    auto [c,cnt] = usubv(midv,midu);
    ans += a[u] - (c + cnt*dis(u,midv)); // u - midv子树
  }
  {
    auto [c,cnt] = usubv(midu,midv);
    ans += a[v] - (c + cnt*dis(v,midu)); // v - midu子树
  }
  return ans;
}

int main(){
  n=read();
  rep(i,1,n) {
    int u=read();
    int v=read();
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1,1,0);
  dfs1(1,1,s[1]);
  int q=read();
  while(q--){
    int u=read();
    int v=read();
    printf("%lld\n",query(u,v));
  }
  return 0;
}

总结

G

数据范围小了，反而设计状态更难了，这题都是橙色，也有做过这种枚举下届去dp上界的，这里更需要敢去枚举

dp其实大方向也是对的，问题就是这里 min/max没有局部性就只有大量状态，局部性就需要枚举min或者max, 而这个其实说白了就是枚举，但菜啊

Ex

这Ex没难度啊，感觉G光是赶去逼复杂度就比Ex难啊

参考

官方题解