Atcoder abc246

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
G(博弈论,树形DP,二分)Ex(DP,线段树,矩阵)

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

G - Game on Tree 3

n点,1为根的树

除了根,点i上面还有值Ai

棋子初始在1

  1. 乙 选一个非根点,修改值Ai = 0
  2. 甲 把棋子移动到当前所在的一个子节点上, 随时可以结束游戏

移动到叶子后结束

分数=结束游戏时棋子所在位置的值

甲要让分尽量大, 乙要让分尽量小

求分

范围

n 2e5

ai 1e9

6s

1024mb

我的思路

一眼感觉树上dp, 因为乙要让分尽量小, 所以每次乙一定操作的是当前所在的剩余树上的点

但感觉不一定操作最近的

比如

1
2
3
         0
   1         1 
100 100     100

那么,最大答案是1, 乙第一次移动的是左边某个叶子的100, 因为如果不是这样, 那么甲向左走,可以得到>=100 > 1

没啥想法对于局部性, dp[i][j] = 点i为根的树已经删了j个点后剩余能得到的最大值, 但转移和范围 感觉都没想法

题解

如果能判断 T能否得分 >= X, 那么就可以二分

(我有想过这样二分, 但是感觉上, 判大于 我的思路也和直接算的思路一样, 没有啥额外想法)

对于给定X, 考虑把树上 $\ge X$染黑, $< X$染白,

  1. 如果走到黑色,则甲胜利
  2. 乙把一个黑涂白
  3. 甲移动一次

然后证明, 和总和是等价的

???, 下面这样最大不是101吗?

1
2
   1         1
100  100 100   100

艹 我读错题目了, 分数=最后停留位置的分数,不是和, 甲可以在中途结束游戏

那么 其实这个二分+染色就显然了

然后就树上DP

dp[u] = 以u为根, 最少需要预先删除的点的个数, 能让乙赢!

所以乙胜利的条件就是dp[1] = 0

假设k 有k个子节点v1,v2,…,vk

推dp[u] 和子节点dp[vi]的关系

显然 dp[u] = max(0, sum(dp[vi]) - 1) + color[u]

首先u是黑色,则一定要删除

然后如果有多于1个子节点预删除的个数不满足,那么这次处理后,一定有一个不满足的路径去走, 所以至多有一个子树的预删除少1个,

然后就没了

代码

https://atcoder.jp/contests/abc246/submissions/35075031

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
#include<bits/stdc++.h>
#define rep(i,a,n)for(int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
const int N=2e5;
int a[N+10];
std::vector<int>g[N+10];
int dfs(int u,int fa,int x){
  int s=0;
  for(auto v:g[u])if(v!=fa)s+=dfs(v,u,x);
  return std::max(s-1,0)+(a[u]>=x);
}
int main(){
  int n=read();
  rep(i,1,n)a[i]=read();
  rep(_,1,n){
    int u=read()-1;//0-index
    int v=read()-1;
    g[u ].push_back(v);
    g[v].push_back(u);
  }
  int l=0,r=1000000001; // l Takahashi win, r lose
  while(r-l>1){
    int mid=(l+r)/2;
    (dfs(0,-1,mid)?l:r)=mid;
  }
  printf("%d\n",l);
  return 0;
}

Ex - 01? Queries

长N的01字符串S, 包含?

Q个询问,

  1. 赋值 S[xi] = ci
  2. S能形成的非连续子序列的种数,(所有?独立的考虑替换成0或1), mod 998244353

范围

n,q 1e5

ci, 0,1,?

6s

1024mb

我的思路

显然不考虑动态变化

先考虑如果一个给定的s,如何计算

如果? 有k个,那么长k的所有串都能得到, 但是这样和0,1不好组合

从dp角度

dp[i][0/1] 表示 以i结尾,且s[i]==0/1的方案数

注意去重, 任意一个字符串能表示, 如果它结尾是1, 那么它的被统计次数应该被记录在当前最后一个1出现的位置, 如果结尾是0,也是被统计在最后一个0出现的位置, 所以

ans = dp[最后一个1][1] + dp[最后一个0][0]

转移dp[i][1] = ???

题解

还是先考虑固定的字符串

f[i][0/1] 表示前i个, 结尾是0/1的子序列数量, ans = f[n][1]+f[n][0]

s[i] != 1 : f[i][0] = f[i-1][0] + (f[i-1][1]+1)

s[i] == 1 : f[i][0] = f[i-1][0]

s[i] != 0:f[i][1] = f[i-1][1] + (f[i-1][0]+1)

s[i] == 0:f[i][1] = f[i-1][1]

1 时的0转移,和0时的1转移很好解释, 因为不会产生新的对应结尾的

但是0时的0转移没有那么显然

比如100

dp[1][1] = 1, 有1

dp[1][0] = 2 有10,0

dp[2][0] = 2 + (1+1) = 4, 有0,00,10,100,

问题在于, 那些 前i个不能产生,但是拼上0以后可以产生的字符串

考虑计数: 前i个产生字符串,再拼接上一个0 , = (dp[i][0]+dp[i][1])+1, 这个1表示空字符串拼上0

去掉已经出现的dp[i][0] 个

剩下的就是没有出现过的,((dp[i][0]+dp[i][1])+1 - dp[i][0]) = (dp[i][1]+1)

得证

因此问题变成 线性转移, 啊不就是矩阵

(dp[i][0] & dp[i][1] & 1) * 转移矩阵

不就是区间查询,区间修改,

线段树之类维护一下就好了

代码

https://atcoder.jp/contests/abc246/submissions/35076203

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r

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

template<class T>
T mul(const T&a,const T&b){
  T r = vector(a.size(),vector<mint>(b[0].size(),0));
  rep(i,0,a.size())rep(j,0,b[0].size())rep(k,0,a[0].size()) r[i][j]+=a[i][k]*b[k][j];
  return r;
}

const int N = 1e5;
vector<vector<mint> > t[N*4+10];
char s[N+10];
int c2i[256];
vector<vector<mint> > m[3] = {
  { // 0
    {1,0,0},
    {1,1,0},
    {1,0,1}
  },{ // 1
    {1,1,0},
    {0,1,0},
    {0,1,1}
  },{ // ?
    {1,1,0},
    {1,1,0},
    {1,1,1}
  }
};

vector<vector<mint>> build(int o,int l, int r) {
  if (l == r) return t[o] = m[c2i[(int)s[l]]];
  return t[o] = mul(build(SEG_L_CHILD),build(SEG_R_CHILD));
}

vector<vector<mint>> update(int o, int l, int r, int x, char c) {
  if (l == r) return t[o] = m[c2i[(int)c]];
  if (x <= mid) return t[o] = mul(update(SEG_L_CHILD,x,c),t[SEG_R]);
  else return t[o] = mul(t[SEG_L],update(SEG_R_CHILD,x,c));
}

int main() {
  vector<vector<mint>> pre = {{0,0,1}};
  vector<vector<mint>> suf = {{1},{1},{0}};
  c2i[(int)'0'] = 0;
  c2i[(int)'1'] = 1;
  c2i[(int)'?'] = 2;
  int n = read();
  int q = read();
  scanf("%s",s);
  build(SEG_ROOT);
  while (q--) {
    int x = read()-1;
    char ch[3];
    scanf("%s",ch);
    printf("%d\n",mul(mul(pre,update(SEG_ROOT,x,ch[0])),suf)[0][0].val());
  }
  return 0;
}

总结

G

读错题了

但这样的话二分变黑白就很明显了, 然后就是树形dp, 但这个状态我是没想到的

Ex

我的dp还是 菜,完全不会, 这个递推表达式把我看楞了, 就是不知道怎么计算非重复的部分的个数

反而后面线段树+矩阵倒是很熟了

参考

官方题解