Atcoder abc223

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
G(树,dp,换根dp)H(线性基)

G - Vertex Deletion

https://atcoder.jp/contests/abc223/tasks/abc223_g

N 点, 标号1到N, 的树

找有几个点满足, 删了它和它直接相连的边以后, 最大匹配个数 = 原图最大匹配个数

限制

N 2e5

2 s

1024 mb

我的思路

显然如果删了u以后最大匹配个数不变, 那么在原图中u所直接连的点,在删除以后的图中都被选了

否则的话, 其中一个和u可以让匹配数+1

并且这些和u直接相连的点在最大匹配中是必选, 也就是不存在方案让它不被选

又因为结构是树

假设断开u-v的连接

以v为根的连通块为根做树

v必选(和子节点匹配)的条件是,任何一个子树的根未被选

v不被选(不和子节点匹配,可能和父节点匹配)的条件是,所有子树的根被选

感觉像是换根dp

也就是求u作为根 f(u) 为不和子节点匹配的 u的个数

f(u) = !(f(v1) & f(v2) & f(v3))

为了减少枚举,可以变成 子点0的个数统计

f(u) = count(f(v) == 0) > 0

u 交换 v

u 的子节点里没有了v, 更新u

v 的子节点里没有了u, 更新v

顺序就dfs顺序就完了

好像就AC了

代码

https://atcoder.jp/contests/abc223/submissions/33887853

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
#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

vector<int>p2[200010];

int c[200010]; // count 0
int x(int u){ return c[u] > 0;} // 根据子节点0的个数 推断是否和子节点匹配

void dfs(int u,int f){
  for(auto v:p2[u]) if(v != f) {
    dfs(v,u);
    c[u] += !x(v);
  }
}

void swaproot(int u,int v){
  c[u] -= !x(v);
  c[v] += !x(u);
}

int dfs2(int u,int f){
  int r = !x(u);
  for(auto v:p2[u]) if(v != f) {
    swaproot(u,v);
    r += dfs2(v,u);
    swaproot(v,u);
  }
  return r;
}

int main(){
  int n = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    p2[u].pb(v);
    p2[v].pb(u);
  }
  dfs(1,0);
  printf("%d\n", dfs2(1,0));
  return 0;
}

H - Xor Query

https://atcoder.jp/contests/abc223/tasks/abc223_h

N个整数数组A[1…N]

做Q次询问, 每次询问[L..R]区间,是能选出一些数 使得它们的xor = Xi

不用给方案,只用输出Yes/No

范围

N 4e5

Q 2e5

Ai [1,2^60]

Xi [1,2^60]

3s

1024 mb

我的思路

无

题解

线性代数的一点基础知识

每个数字可以表示成60个维度的向量

xor = 每个维度和 %2

选一些数 xor = x

等同于 选一些数,做向量各维度和 % 2

对x的集合$X$, span(X)表示 集合中能构成所有xor的结果的集合

本身是在一个 2^{60} 的空间里

如果区间[L..R] 中能选出一些让xor的值 = X

那么 span({a[k..R]}) 能产生向量X, 其中k >= L

对于给定R

如果 span{a[k..R]} 不等于 span{a[k+1..R]}

那么说明 a[k] 是 a[k..R]的一个线性基

那么对L 来说, a{L..R} 的能生成的 只和中间这些满足 的k有关

那么枚举右端点, 维护的每次如果不增加基,更新掉最前面一个和它冲突的

这样每个右端点都记录了最近的一些到它的线性基的下标了

代码

https://atcoder.jp/contests/abc223/submissions/33888843

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
#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

#define N 400000

int n, m;
pair<ll,int> a[N+10][100]; // [区间右端点 i][pwr] = pwr对应修改bit的 距离最近的 {线性基,下标}

bool query(){
  int l = read();
  int r = read();
  ll x = read();
  rep(i,0,61) if ((x>>i)&1) { // x 的 i 位bit 是1
    auto [base,idx] = a[r][i];
    if (!base || idx < l) return false; // 找不到, 或者最近的修改 超出范围
    x ^= base;
  }
  return true;
}

int main() {
  int n = read();
  int q = read();
  rep(pos,1,n+1) {
    int i = pos;
    ll x = read();
    rep(pwr,0,61) a[pos][pwr] = a[pos-1][pwr];// 拷贝一份
    rep(pwr,0,61) if ( (x>>pwr) & 1) { // x 位是1 , 这里和query的 位顺序一致即可, 可以从小到大,也可以从大到小
      auto [base,idx] = a[pos][pwr];
      if (!base) { // 新增基
        a[pos][pwr] = {x,i}; // 基,下标
        break;
      } else if (i > idx) { // 换离pos更近的基
        swap(a[pos][pwr].first, x);
        swap(a[pos][pwr].second, i);
      }
      x ^= a[pos][pwr].first; // 把pwr位的1删掉, 变换基
    }
  }
  while (q--) printf("%s\n",query()?"Yes":"No");
  return 0;
}

总结

G

没啥难的

H

线性基的知识点

参考

官方题解