YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 3.2k 所需閱讀時間 ≈ 11 分鐘
F(双指针,滑窗,同值跳点,前缀最值)G(二分图匹配,数学)H(构造,分治,小值枚举,无代码)

F

题目

https://codeforces.com/contest/1684/problem/F

长n数组a

m个区间[l,r]

自己任选一个范围(与上面的区间无关),修改区间中所有值成任意值, 让上面区间每个区间都没有重复的数

问 你任选的区间最短长度

范围

n 2e5

m 2e5

ai 1e9

2s

256MB

题解

我的思路

ai和n不成比例,与具体值无关, 无脑离散化一下,把ai范围降低到n

对于一个区间[l,r], 如果覆盖了一侧,如[l0,r],那么其实很好求l0的最大值(因为要区间尽量小

只需要通过v2idx[v] = last index, 跳一跳就行了

那么其实可以得到 这些l0 中最小的l0, 记为 L, 同样可以得到最大的R

那么 答案一定是包含了[L,R]的

那么问题变成了, 如果就是给你一个区间,但是是部分覆盖如何做到最短, [l,r] 你要找 [l...[L..R]...r]

其中 [l..L-1][R+1..r] 不存在重复的数,还要[L,R]最短

方法

如果答案是[L,R] 也就是 任何给的线段[l,r]中,不存在相同值都不属于[L,R],

先让L = 1, 那么找r 跟上面说的一样, 找到max(min(ri))

然后,如果L左移1,R会如何变化

如果[L+1,R] 满足则就是R否则R只能增大, 甚至 L+1就无法合法了

注意到 如果有同样的l ,那么只用考虑r更大的即可

[L..R] => [L+1..?]

首先 如果 [lastpos[v[L]]...L] 被包含在某个区间中, 那么必定不可行, 之后更大的L也不可行了break掉

如果 大于R的 value = v[L]的 位置在p

且[L...p]在某个区间中, 那么必定[L+1..R]不合法

[L+1...p] 则是新的合法的

上面两个都需要的是查询 左端点在[0...pos] 中的给定线段, 右侧端点最大值

这个注意到是一次赋值,多次查询没有更改的,直接前缀最大值

代码

https://codeforces.com/contest/1684/submission/158651275

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
#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 emplace_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
const int N = 200000;
 
int f[N+10]; // 前缀最大值[前缀左端点] = 最大右侧端点
ll a[N+10];
vector<int> gist[N+10]; // gist[值] = vector<int> 下标
pii seg[N+10]; // 题目给的线段
ll mnl[N+10]; // mnl[ir] = 最小合法il => [il..ir]没有重复的数
bool s[N+10]; // 存在过的数
int n,m;
 
void solve() {
  // clear
  fill(f,f+n,-1);
  fill(gist,gist+n,vector<int>());
 
  n = read();
  m = read();
  rep(i,0,n) a[i] = read();
  // 离散一下
  vector<pii> sa ;
  rep(i,0,n) sa.push_back({a[i],i});
  sort(all(sa));
  rep(i,0,n) {
    auto [v,j] = sa[i];
    if(i == 0) a[j] = 0;
    else if(v == sa[i-1].first) a[j] = a[sa[i-1].second];
    else a[j] = a[sa[i-1].second] + 1;
  }
 
  rep(i,0,n) gist[a[i]].pb(i);
 
  rep(i,0,m){
    int l = read();
    int r = read();
    seg[i] = {--l,--r};
    f[l] = max(f[l], r);
  }
  rep(i,1,n) f[i] = max(f[i-1],f[i]);
  // 双指针 [il...ir] 没有重复的数
  // mnl[ir] = 合法的最小il
  int il = n;
  per(ir,0,n){
    while (il && !s[a[il - 1]]) s[a[--il]] = true;
    mnl[ir] = il;
    s[a[ir]] = false;
  }
 
  // mnr 为L = 1 时 R的最小值 , [R+1..n] 要么就是 本身合法线段要么就是 [R+1..r] 合法
  ll mnr = -1;
  rep(i,0,m){
    auto [l,r] = seg[i];
    if (mnl[r] <= l) continue; // 本身就合法 直接忽略
    mnr = max(mnr, mnl[r] - 1);
  }
  if (mnr == -1) {
    printf("0\n");
    return;
  }
  ll ans = mnr + 1;
  // L 每次 +1
  // [l..mnr] => [l+1..?]
  rep(l,0,n-1){
    // l 不是 a[l] 首次出现的位置
    if (gist[a[l]][0] != l) {
      // 上一个同样值的位置
      int pr = *(--lower_bound(all(gist[a[l]]), l));
      // 左端点小于等于 pr, 的最大右端点, 如果删除了 就会有区间包含[pr...l] 有两个a[l]
      // 再移动 就不可能了, 所以直接break
      if (f[pr] >= l) break;
    }
    // 下一个 为a[l] 的 且在某个区间中
    if (gist[a[l]].back() > mnr ) {
      int nxt = *upper_bound(all(gist[a[l]]), mnr);
      if (f[l] >= nxt) mnr = nxt;
    }
    assert(mnr > l);
    ans = min(ans, mnr - l);
  }
  printf("%lld\n",ans);
}
 
int main() {
  int t = read();
  while (t--) solve();
  return 0;
}

G

题目

https://codeforces.com/contest/1684/problem/G

t 是一个数组

考虑Euclid求gcd

1
2
3
4
5
6
7
8
9
10
11
12
function Euclid(a, b):
    if a < b:
        swap(a, b)

    if b == 0:
        return a

    r = reminder from dividing a by b
    if r > 0:
        append r to the back of t

    return Euclid(b, r)

p 是一个包含不超过m的正数对的数组

t 初始为空

然后 对p的所有 数对 运行上述算法

t然后被打乱了给你

你需要找一个 数组, len <= 2e4, 能产生 t, 或者判断它不可能存在

范围

len(t) 1e3

m 1e9

1 <= ti <= m

1s

256mb

题解

我的思路

其实就是 辗转相除(a,b), a>b 中间的所有非零余数

b > v, a >= b + v > 2v

所以如果有值不满足m > 2v 则直接不可能输出-1

否则直接无脑2v+1,v+1?, 但注意到2v+1,v+1,v,1 还会产生1, 也就是不行的

另外3v,2v,v 不会有额外产生,如果有多余的3v <= m 可以这样处理掉

所以只用考虑3v > m > 2v 的v值m/2 > v > m/3 (非整除)

a = 2v+i,b = v+i,v,i,... (i <= m-2v < v)

但怎么选i, 以及处理之后的余数,并没有任何想法

v的选择可以从大到小, 这样也可能消耗掉 一部分 m/2 > v > m/3

题解

一样 先把v的范围限定在了3v > m > 2v, 范围以外的和我想的一样的处理

m >= a=2v+i,b=v+i,v,i,...

也就是考虑到 2v + gcd(v,i) <= 2v+i <= m

也就是对于每个 v > m/3, 一定存在一个是它因数的x,且2v + x <= 2m

于是建立二分图

左边 > m/3, 右边 <= m/3

做二分图匹配即可

我的问题,在i 和 m/3大小判断错了, 其实 2v+i = a <= m和v > m/3 就可以得到i < m/3的

这样的话,v必然是靠小于等于m/3的消耗掉的,不如直接贪约数

有一说一,写起来其实会比F简单?

代码

https://codeforces.com/contest/1684/submission/158654516

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
#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 = 1000;
vector<int> g[N+10]; // g[二分图左端点] = vector<>右端点
int with[N+10]; // with[右端点] = 链接的来源左端点
int vis[N+10]; // 二分图每轮选左侧起始点时,是否访问到
ll a[N+10];

bool dfs(int v) {
  if (vis[v]) return false;
  vis[v] = 1;
  // 直接就有可选终点
  for (auto to : g[v]) {
    if (with[to] == -1) {
      with[to] = v;
      return true;
    }
  }
  // 递归走 v -> to0 -> with[to0] -> t1 -> with[t1] - ... -> took
  for (auto to : g[v]) {
    if (dfs(with[to])) {
      with[to] = v; // 更新指向
      return true;
    }
  }
  return false;
}

int main() {
  int n = read();
  int A = read();
  // 二分图
  vector<ll> l;
  vector<ll> r;

  rep(i,0,n) {
    a[i] = read();
    (3 * a[i] > A ? l : r).pb(a[i]);
  }
  // 建立边
  rep(i,0,l.size()) {
    rep(j,0,r.size()) {
      if (l[i] % r[j])continue;
      if(2 * l[i] + r[j] > A) continue;
      g[i].pb(j);
    }
  }
  // 二分图匹配
  fill(with,with+r.size(),-1);
  rep(i,0,l.size()) {
    fill(vis,vis+l.size(),0);
    if(!dfs(i)){
      // 未消耗掉所有 > m/3
      printf("-1\n");
      return 0;
    }
  }
  vector<pair<ll,ll>> ans;
  rep(j,0,r.size()) {
    if (with[j] == -1) {
      ans.pb({3 * r[j], 2 * r[j]}); // <= m/3 的 直接 `3v,2v => v`
    } else { // 2v+i,v+i => v,i
      ans.pb({2 * l[with[j]] + r[j], l[with[j]] + r[j]});
    }
  }
  printf("%d\n",(int)ans.size());
  for (auto [a,b]: ans) printf("%lld %lld\n",a,b);
  return 0;
}

H

题目

https://codeforces.com/contest/1684/problem/H

给0/1串s, 切分成任意多个不相交子串, 然后让这些子串表示的二进制值的和是2的幂次

范围

|s| 1e6

2s

256mb

题解

我的思路

如果1的个数是2的幂次, 那么直接全部拆碎就完了

不妨设一共有$w$个1,且 $2^k < w < 2^{k+1}$

除了最后一位1, 任何一个1 都可变成2的贡献,不论是通过 11还是10, 它对w的贡献就是+1

但是如果连续的两个1,至多有一个可以贡献2,

同样除了最后两位1, 任何一个1 都可变成4的贡献,通过1XX, 对w贡献是+3

但是如果连续的三个中出现的1,至多有一个可以贡献4,

所以 (w-2)/3 个1 可以变成贡献4, 于是可以多贡献 (w-2)

但值得注意的是, 之所以 (w-2)/3 一个是因为尾部, 一个是因为 连续的3个中出现1, 才会不能让所有的1贡献4, 下限是(w-2)/3

这样的话,也就是说 有部分的贡献的是2, 总可以补全到$>= 2^{k+1}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
100 = 4 (+3)
10,0 = 2 (+1)
1,0,0 = 1

101 = 5 (+3)
10,1 = 3 (+1)
1,0,1 = 2

110 = 6 (+4)
1,10 = 3 (+1)
11,0 = 3 (+1)
1,1,0 = 2

111 = 7 (+4)
11,1 = 4 (+1)
1,1,1 = 3

所以对于所有1开头的3位, 有的贡献可以+1,+3, 有的贡献可以+1,+4

2^{k+1}-1 >= w >= 2^k+1

所以 通过+3,+4 让w和 2^{k+1}的距离 在某个3元组能达到[1,3]之间, 剩下的[1,3]就靠+1补满

且, 注意到如果是靠不少+3达到的,那么剩余的长3的组一定还不少, 不会耗尽所有

所以w足够大时,必定可行

需要考虑w小的时候, 但多么小呢?

w = 1,2,4,8直接可行

w = 3 时, dst = 4. +1 必定可行

w = 5 时, dst = 8, 需要+3, (111)(110) 就是个不能用上面切割达到的

w = 6,7 时, dst = 8, 需要+2/+1, 必定两/一次+1可以达到

w = 9 时, dst = 16, 需要+7, (111)(111)(111) ,也是不能用上面切割达到

w = …

这块细节就不知道怎么搞, 也不知道大于多少以后w一定可以

方法

1,2,4,等2的幂次, 直接切碎

k = 3 可以用上面我说的方法

k = 5

如果1连续, 1111+1 = 10000

否则1之间存在0, 存在一个0,则101存在,多个0,则100存在. 101+1+1+1=1000, 100+1+1+1+1 = 1000

k > 5

solve(l,r,k,n) 函数表示把有k个1的[l..r]段切来和为n

这里目标n也是放在 2的log(2,k)向上取整幂次,

足够大的n, 考虑是按照k 来切开, 让它分别为 k/2向下取整和 k/2向上取整, 并且 让它们的和都是 n/2

solve(l,r,k,n) = solve(l,pos,k/2,n/2) and solve(pos+1,r,k-k/2,n/2)

然后界限来就是说 k = 6..11 时 如何搞

这里其实可以自己随便乱搞了,毕竟范围有限,目标明确

官方英文题解里有具体方法

这里方法上有一个要注意的是, 当 1的个数是 (2的幂次)+1 时, 它期望切割出来的2的(幂次-1)那一部分还是需要到

比如 17 = 16+1个1, 期望的结果是 2**5 = 32

17 = 8+9, 9的期望结果是16没问题, 但是8 也需要16 而不是得到8

但注意到这个问题集中在2的幂次上

所以再向下考虑4个1要得到8

考虑最左1开头的数:

111: 111+1=1000

110: 110+1+1 = 1000

101: 后面一个1贡献2,1个1贡献1, 101+10+1 = 1000

100: 后面一个1贡献2,两个1贡献1, 100+10+1+1 = 1000

都可以得到8

代码

鸽, 构造+枚举小值 是我太菜了

总结

F:

一个是 包含两个相同值,转化成包含两个相邻相同值,因为同样的值出现多次, 只用考虑相邻 v…v…v, 只用考虑[v…v]…v 或v…[v…v]

看起来没离散2e5个<1e9的map效率还行啊, 仅仅是查询的话

双指针 + 滑窗还是写不熟啊

G:

这里主要在i的范围判断错了,如果 i > m/3 那么 2v+i >= 2m/3 + m/3 = m, 我数学太菜了

H:

从小特例开始考虑算是有一定思路是对的, 但是要敢于分情况讨论

但是这个分治的确没想到,就算想到一半, 可能没想到让k/2向下和向上取整,都去等于 n/2

或者整体来说, 没想到 和可以拆成 和的一半 对应 1个数的一半

特别是这里敢于 2的幂次+1这种数也这样拆

参考

官方

發表於 更新於 分類於 Disqus： 文章字數： 200 所需閱讀時間 ≈ 1 分鐘

比赛总结

https://ac.nowcoder.com/acm/contest/34330/E

考虑存在一个点 其它点仅和它断边

注意sum n很大, 清理按m清理

代码

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<n;i++)

// n(完全图), n-1, <= n-2?
int p2[1000010];

ll n ;
ll m ;
vector<int>uv;

void w(){
  scanf("%lld %lld",&n,&m);
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u] ++ ;
    p2[v] ++ ;
    uv.push_back(u);
    uv.push_back(v);
  }
  // 完全图
  if(m == n*(n-1)/2){
    printf("0\n");
    return ;
  }
  if(m == n*(n-1)/2 - 1){ 
    printf("-1\n");
    return ;
  }
  // 连了4个点 -2
  // 连了3个点 -1
  // sum n 很大
  if(n*(n-1)/2 - m > n){
    printf("-2\n");
    return ;
  }
    rep(i,1,n+1){
      if(p2[i] == n-1 - (n*(n-1)/2 - m)){
        printf("-1\n");
        return ;
      }
    }
  printf("-2\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
      w();
      for(auto u:uv)p2[u] = 0;
      uv = {};
  }
  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
E(rmq 倍增)F(树上同值跳点,切割联通块大小)

E - Labyrinth Adventures

题目

https://codeforces.com/contest/1681/problem/E

n行n列的迷宫

1
2
3
4
5
55555
44445
33345
22345
12345

左下角第一层,然后它八临的第二层,再8临第三层

不同层之间有墙隔着,部分墙的位置有门, 每两层之间有恰好两个门, 一个是上下方向,一个是左右方向, 门是双向通的

q个询问两点之间最少的移动步数

范围

n 1e5

q 2e5

6s

512MB

题解

n很大显然无法建立图

但我们可以考虑如果是图会怎么做

首先如果没有任何阻挡,那么两点之间的曼哈顿距离为 走个直角, 因此如果两个同色,那么必然答案就是曼哈顿距离

那么就是考虑不同颜色

显然也不会 一个色不连续的走到,否则这段路径直接同色最短, 综上 如果 a < b , 那么a->b 的距离 = a->某个门-> a+1->某个门->a+2 ->某个门 -> ... -> b

再改改

位置pos -> 门(a,0) -> 门(b-1,0) -> 位置dst

位置pos -> 门(a,0) -> 门(b-1,1) -> 位置dst

位置pos -> 门(a,1) -> 门(b-1,0) -> 位置dst

位置pos -> 门(a,1) -> 门(b-1,1) -> 位置dst

如果我们能快速求两个门之间的最短距离就好了

直接考虑rmq的办法, 记录 (位置i,0/1号门, 2的幂次j距离, 0/1号门) 的最小距离

这样复杂度为$O(n \cdot log(n) )$ 的初始化和 $O( log(n))$ 的单次查询

代码

无

会的, 不想写了

F

题目

https://codeforces.com/contest/1681/problem/F

给到一个n个点的树, 边上有整数

记f(u,v) = 点u到点v简单路径上 只出现了一次的数字的个数

求对于所有u < v 的点对, f(u,v)的总和

边的值[1..n] 不需要自己离散化了

范围

n 5e5

6s

1024mb

题解

显然假设一条边上写的是 x

那么从贡献角度来讲, 它对答案的贡献是,左侧端点不再经过值为x边的点数 乘上 右侧端点不再经过值为x边的点数

问题呢, 如果我们通过叶子统计汇总,那么每个叶子上需要记录O(n)个值的出现次数, 那显然就n 方了

那么我们考虑对于一个d, 在dfs时,不要影响到其它的块的办法

任意选一个点作为根,先考虑 dfs过程中经过了两个边为d

分别是(u0,v0,d) 和 (u1,v1,d)

那么 (u1,v1) 的贡献 = 以v0为根的d断开的联通块大小 乘上 以v1为根的d断开的联通块大小

而 以v为根的d断开的联通块大小 = v为根的子树大小 - sum{最近的d断开的 以v1/v2/v3/v4… 为根的树的大小}

这样 辅助数组 记录深搜过程中 上一个同边对应的点即可, 空间就是O(n),

还有一个问题, 如果是 dfs中首次出现的呢

这里的方法是对于每一个d 假装树的根的父节点连出去的就是d,即可

代码

https://codeforces.com/contest/1681/submission/158413431

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const int N = 5e5;
int idx;
tuple<int,int,int> e[N*2 + 10]; // {u,v,d}
vector<pair<int,int> > u2vi[N+10]; // [u] = vector<{v,i}>
int loc[N*2+10]; // [d] = 深搜过程中 当前深搜链上 边为d的叶向端点
int lst[N*2+10]; // lst[v] = v作为叶节点父边为d , 通向根的链上,最近一个边为d的叶向节点 //上一个v'
int sz[N+10]; // 子树大小, 纯的树统计,不考虑边值
ll f[N*2+10]; // 考虑边值有效的树的大小
int n;
void dfs(int u, int fa) { // 点, 父节点
  sz[u] = 1; // 纯的子树大小
  for(auto [v,ei]: u2vi[u]){
    int d = get<2>(e[ei]);
    if (v == fa) continue;
    lst[v] = loc[d]; // 即帮助深搜恢复loc[d], 也自己记录了它到根的简单路径上最近的 边为d的叶向节点
    loc[d] = v; // 当前的深搜的链上 边为d的叶向端点
    dfs(v, u);
    loc[d] = lst[v]; // 恢复上一次的 loc[d]
    sz[u] += sz[v];
  }
  // 原理就很简单了 对于 u->v, 边为d 来说, 以v为根的连通块大小 = 它的子树大小 - sum{它子树中紧邻的边d的根为v' 的子树大小}
  f[u] += sz[u];
  f[lst[u]] -= sz[u];
}

int main() {
  cin >> n;
  rep(i,1,n){
    int u, v, d;
    scanf("%d %d %d",&u,&v,&d);
    e[i] = {u,v,d};
    u2vi[u].push_back({v,i});
    u2vi[v].push_back({u,i});
  }
  // 初始化f 和 loc
  rep(i,1,n+1){
    f[i + n] = n;
    loc[i] = i + n; // 初始化为每个值 对应虚拟节点为 value+n
  }
  dfs(1, -1);
  ll ans = 0;
  rep(i,2,n+1){
    ans += (f[i] * f[lst[i]]);
  }
  printf("%lld\n",ans);
  return 0;
}

总结

其实相当于线性数组的变性, 靠值来记录上一个同样值的位置, 不同的是线性可以直接坐标差得到中间的联通块, 而 树状可以dfs知道 到根最近的同样的值在哪, 而联通块的信息直接表示在根上

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 3k 所需閱讀時間 ≈ 10 分鐘
E(sosDP,子集和DP,动态规划,贡献统计),F(dp,bitmask,特殊表示,动归状态设计)

E

https://codeforces.com/contest/1679/problem/E

长度n,前17个小写字母组成的字符串s,其中有?表示t中任意字符

q次询问,每次给17个字母中的一个子集,问把?所有填子集的填法中,原串的回文子串个数和, 答案mod 998244353

范围

n 1e3

t 17

q 2e5

2s

256MB

我的思路

首先看到q 2e5, 和 t 17, 因为2^17 == 131072,其实可以变成求所有方案的答案

统计所有回文子串 的效率最好就是选取中心,再枚举长度

那么这个题也是这样做, 枚举中心向两边搜索

其中注意到的是,当选定中心后,如果对称位置上有一个问号一个确定字符,那么这个问号必定填这个字符

如果两个都是问号,那么自由度+1, 它

如果对称都填了但是不一样,那么到此结束

也就是n方可以统计 cnt[必要字符bitmask][自由度] = 次数

那么 每次询问bitmask 是 M 的话

ans[M] = sum { cnt[m 是M的子集][i = 0..] * size(M)^i }

那么问题来了, 朴素计算我必定超时, 但是我不知道如何dp, 看Codeforces的群里有人说sosdp

SOSDP 子集和DP

$F[mask] =\sum_{i \in mask}A[i]$

暴力枚举 $O(4^n)$

1
2
3
4
5
rep(mask,0,1 << N){
  rep(i,0,1 << N){ // 枚举 mask, 检测是否是它的子集
    if((i&mask) == i) F[mask] += A[i];
  }
}

枚举子集和$O(3^n)$

子集遍历

也可以dfs,当然dfs会多函数调用和堆栈 比如mask = 111, i依次为 111,110,101,100,011,010,001,000, 注意到的是mask中间穿插0对应的就是i对应位置穿插0,看起来就像每次-1

1
2
3
4
5
6
rep(mask,0,1 << N){
  F[mask] = A[0]; // 所有集合包含空集 空集合也作为停止条件
  for(int i = mask;i;i = (i-1)&mask){ // 这就是传说中的二进制枚举子集 ,
    F[mask] += A[i];
  }
}

SOSdp $O(n2^n)$

dp[mask][i] 表示 高位和mask一致, 低[0..i]位所有方案的和

dp[10110][2] = A[10000]+A[10010]+A[10100]+A[10110]

状态转移

第i位为0时,dp[mask][i] = dp[mask][i-1]

第i位为1时,dp[mask][i] = dp[mask][i-1] + dp[mask xor (1 << i)][i-1]

这样变成递推 或者记忆化搜索,可以 $O(n2^n)$ 完成

上面合并一下变成,dp[mask][i] = dp[mask][i-1] + (mask & (1 << i)?dp[mask xor (1 << i)][i-1]:0)

注意到i依赖于i-1还可以滚动数组降低空间

1
2
3
4
5
6
7
rep(mask,0,1<<N) f[mask] = A[mask];
rep(i,0,N){
  // 这里不需要从大到小, 因为dp[mask]已经初始化了,只会更新1 << i上为1的,而更新的来源是1 << i上不是1的
  rep(mask,0,1 << N){
    if(mask & (1 << i)) f[mask]+=f[mask ^ (1 << i)];
  }
}

题解

我的暴力的代码

1
2
3
4
5
6
7
8
ans[mask] = 0;
sz = bitcount(mask)
rep(qmark,0,501){ // 自由的问号个数
  ti = pow(sz,qmark)
  for(int i = mask;i;i = (i-1)&mask){
    ans[mask] += cnt[i][qmark] * ti
  }
}

这是$O(n 3^{|t|})$ 的复杂度 肯定过不了

通过sosdp降低到$O(n t 2^{|t|})$ 虽然降低了不少,但是依然过不了

这里dp 改一个方式设计, 变成贡献统计

先交换一下循环层级

1
2
3
4
5
6
7
ans[mask] = 0;
sz = bitcount(mask)
for(int i = mask;i;i = (i-1)&mask){
  rep(qmark,0,501){
    ans[mask] += cnt[i][qmark] * pow(sz,qmark)
  }
}

因为{i,qmark}中i是mask的子集,而{i,qmark}对mask 的贡献来讲 只与bitcount(mask) 有关,与mask 具体无关

1
2
3
4
5
6
7
8
9
10
11
12
13
rep(i,0,(1 << N)){
  rep(sz,1,17+1){
    rep(qmark,0,501){
      cost[i][sz] += cnt[i][qmark] * pow(sz,qmark);
    }
  }
}
ans[mask] = 0;
sz = bitcount(mask)
// sosdp 优化掉
for(int i = mask;i;i = (i-1)&mask){
  ans[mask] += cost[i][sz];
}

下面得到优化了, 但上面看起来复杂度并没有变好

但既然都说道贡献统计了,就去看贡献来源

在我们初始找回文时[i...j] 如果是一个回文,它的必须字符集为mask,自由度为qmark

那么

1
2
3
rep(sz,1,17+1){
  cost[mask][sz] += pow(sz,qmark);
}

这样 初始化就变成$O(|t| n^2)$

综上 $O(初始化幂次 |t|n + 初始化贡献 |t| n^2 + 初始化答案 |t|^2 2^{|t|} + 查询 |t|q )$

注意到 题目要统计 所有字符串个数,也就是说 同一个位置的回文串 在不同字符串中出现,要多次统计

所以

1
2
3
rep(sz,1,17+1){
  cost[mask][sz] += pow(sz,qmark) * pow(sz,total qmark - used qmark);
}

代码

https://codeforces.com/contest/1679/submission/158244316

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#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

const int t = 17;
char s[1010]; // 读入
char s2[2010]; // 插入井号简化搜索
int n;

ll p[t+10][1010]; // 幂次预处理
ll cost[(1<<t)+10][t+10]; // 具体的值
ll ans[(1<<t)+10][t+10]; // 由具体值的子集和的答案
char query[t+10];

int main(){
  rep(i,1,t+1){
    p[i][0] = 1;
    rep(pwr,1,1000+1){
      p[i][pwr] = p[i][pwr-1]*i%MOD;
    }
  }
  scanf("%d",&n);
  scanf("%s",s);
  int qtotal = 0;
  rep(i,0,n) qtotal += s[i] == '?';
  // 字符两两间插入井号方便处理奇偶
  s2[0] = s[0];
  rep(i,1,n){
    s2[i*2-1] = '#';
    s2[i*2] = s[i];
  }
  // 中心
  rep(c,0,n*2-1){
    int mask = 0;
    int qmark = 0;
    int qcnt = 0;
    rep(l,0,n*2-1){ // 长度
      int il = c-l;
      int ir = c+l;
      if(il < 0 || ir >= n*2-1)break;
      qcnt += s2[il] == '?';
      qcnt += il != ir && s2[ir] == '?';
      if(s2[il] == '#')continue; // 不贡献的
      if(s2[il] == s2[ir]){
        if(s2[il] == '?'){
          qmark++;
        }
      }else{ // 不等
        if(s2[il] == '?'){
          mask |= (1 << (s2[ir] - 'a'));
        }else if(s2[ir] == '?'){
          mask |= (1 << (s2[il] - 'a'));
        }else{ // 不同的字符
          break;
        }
      }
      // 贡献统计
      rep(sz,1,17+1){
        // 不同字符串 同一个位置回文串的贡献要多次统计 所以要乘上 其余位置是问号的所有放入方案 让此处的贡献倍数 sz**(qtotal - qcnt)
        (cost[mask][sz] += p[sz][qmark] * p[sz][qtotal - qcnt] % MOD )%=MOD;
      }
    }
  }
  // sosdp
  rep(sz,1,t+1){
    rep(mask,0,1 << t){
      ans[mask][sz] = cost[mask][sz];
    }
    rep(i,0,t){
      rep(mask,0,1 << t){
        if(mask & (1 << i)) (ans[mask][sz] += ans[mask ^ (1 << i)][sz])%=MOD;
      }
    }
  }
  // query
  int q; // 2e5
  scanf("%d",&q);
  while(q--){
    // string to mask
    scanf("%s",query);
    int sz = strlen(query);
    int mask = 0;
    rep(i,0,sz){
      mask |= (1<<(query[i]-'a'));
    }
    printf("%lld\n", ans[mask][sz]);
  }
  return 0;
}

总结

回文的奇偶处理,可以用两两间插入不会出现的字符,如井号,方便枚举中心

学了一手sosdp

看ssr的twitter说有快速zeta变换, 搜下来看转移方程似乎就是sosdp, https://zhuanlan.zhihu.com/p/33328788?ivk_sa=1024320u

顺便这里的dp转化过程中 通过贡献和来优化效率

参考

官方

F

https://codeforces.com/contest/1679/problem/F

$[0..10^n)$的所有n位整数,不足的补前导零

给m个 (ui,vi) 数对, (ui不等于vi)

x 表示成十进制的数字数组 [d1,d2,…,dn]

一次操作可以交换相邻的d, 但需要满足 这两个数的 (di,di+1)或(di+1,di) 出现在 (ui,vi)中

如果一个数x能够通过上述转换变成y,那么认为它们是相等的, x和x自身相等

问题$[0..10^n)$ 有多少个不同的数, 答案mod 998244353

范围

n 5e4

m 45

u,v [0,9]

3s

256MB

题解

我的思路

先提取一下有用没用的信息,首先m没啥用因为实际就是所有数对的上限

如果x 中有两个数字 c0,c1 但是这两个数字没有在d中出现过, 那么这两个数字的相对前后关系不会改变

换句话说,如果两个相等的 它们互相可以转化,那么它们一定属于某个集合,集合里两两可以转化, 而有限集合一定有最小的, 我们用每个集合中数值最小的来表示一整个集合

于是 这个最小值值可以表示成 [单调递增] [单调递增] [单调递增] , 每两个单调递增之间 的值是不在数对里的

所以如果我们可以得到[起始,结束,长度]的方案数就可以考虑转移方程了

f[i][j][len1] = sum{ f[i][k][len0] * inc[ < k][j][len1-len0] } + inc[i][j][len]

看似复杂度没法搞,而实际上连逻辑也不一定对 201, 它允许 (0,1),(2,1) 那么显然120和它相等且更小

题解

思路是类似的, 也是集合的代表元, 但是并不是靠单调递增划分

而是说[序列长度l] 在后面加上mask中的数,它不会被移动到前面

那么,d会移动到前面的条件就是,序列的尾部的一串数都大于d,且都可以和d交换

[x,d1,d2,d3,...,ds,y]

其中 x > y, 且 y 可以和x,d1,...,ds交换

dp[suff][mask] 表示, suff个digits, 且只有mask中的digit可以被移到最左

考虑长度为s 的一个具体的串 等价最小串 X=[d0,d1,d2,.....,ds]

它最长的前缀[d0,d1,d2,....dt] 包含的digits 两两可换, 我们把这样的digits变成mask, X 可以表示成贡献到 dp[s][mask] 中

那么现在如果左边放一个d, 变成X1 = [d,d0,d1,d2,...,ds]

一旦d和 mask 中某个值可换, 记为e, 且d > e

显然,因为mask中两两可换,所以X1 可以变成 [d,e,d0,d1,d2,...,ds], 然后交换e,d 得到 [e,d,d0,d1,d2,...,ds]

因为e < d ,所以 这个值比X1 小

即是X前面不能插入d, 如果 mask 中存在比d小,且和d相连的任何一个e

这样可选的d的范围就出来了, 这部分可以预处理

从X而非mask的角度来看,就是说插入了d以后,得到的值依然是 集合表示的最小值(代表元)

mask的变化

如果d可以放,那么X1 = [d,d0,d1,d2,...,ds], 显然,它的 最长两两可换前缀中有d, 且剩余的部分从mask 中取, 因为mask本身就是两两可换,所以只用考虑和d是否有边

所以新mask = d | mask 中和d有边的点

注意到mask 的意义是 mask 中的值两两可换, 又是X的最大前缀

所以这里其实会计算不少无效的mask, 但因为算次数,这些次数一定是0, 不影响答案

代码

https://codeforces.com/contest/1679/submission/158638333

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#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

namespace X{
  ll r(){ll r;scanf("%lld",&r);return r;} // read
  void add(ll &v0,ll &v1){(v0+=v1%MOD)%=MOD;} // add with MOD
};
using namespace X;

const int S = 10;

// mask 意义, mask中两两可换, 是X的最大前缀
// camp[mask0] = mask1, mask1任意一个bit 和 mask0 中的比它小的bit都没有链接
// 在 mask1中的digit 才能加入到 mask0
vector<int> camp(1<<S,(1<<S)-1);
bool conn[S][S]; // 连接状态
ll dp[2][1 << S];
int trans[1 << S][S]; // [mask][digit] = newmask,

int main() {
  int n = r();
  int m = r();
  rep(i,0,m) {
    int u = r();
    int v = r();
    conn[u][v] = conn[v][u] = 1;
  }
  // 计算 camp
  // O(S^2 * 2^S)
  rep(mask,0,1 << S){
    rep(c,0,S){ // c 在 mask 中
      if (!(mask & (1 << c))) continue;
      rep(j,c+1,S){ // j > c
        if (conn[c][j]) {
          camp[mask] &= ~(1 << j);
        }
      }
    }
  }
  // 计算trans
  // O(S^2 * 2^S)
  rep(mask,0,1 << S) {
    rep(c,0,S){
      trans[mask][c] = 1 << c;
      rep(j,0,S){
        // j 出现在mask 中, (c,j) 可以交换
        if ((mask & (1 << j)) && conn[c][j]) {// 和 mask 中存在相连
          trans[mask][c] |= 1 << j;
        }
      }
    }
  }
  // 滚动数组
  int cur = 0;
  dp[0][0] = 1;
  // O(n * S * 2^S)
  rep(i,0,n){
    // clear
    fill(dp[cur^1],dp[cur^1] + (1<<S),0);
    rep(mask,0,1<<S){
      if (dp[cur][mask] == 0) continue;
      rep(c,0,S){
        // 在camp[mask] 中的才能加
        if (!(camp[mask] & (1 << c))) continue;
        add(dp[cur ^ 1][trans[mask][c]] , dp[cur][mask]);
      }
    }
    cur ^= 1;
  }

  ll ans = 0;
  rep(mask,1,1<<S) add(ans,dp[cur][mask]);
  printf("%lld\n", ans);
}

总结

我的思路里关于 排序,代表元都有了, 这是好事,但是

其实这里一个核心 在于怎么把 最小值元素X,抽象的表示到一个dp的state中

这里给出的state的设计方案是最长两两可换的前缀的bitmask, 和长度来表示

换句话说如果有人告诉我怎么设计state,那么转移方程还是随便写的

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 950 所需閱讀時間 ≈ 3 分鐘
D(树的边与点,贡献统计,DP,特殊题目条件)

题目

https://atcoder.jp/contests/arc140/tasks/arc140_d

初始有 n 个点，给定一个长度为 n 的数组 ai，若 ai≠−1，则有无向边 (i,ai)，若 ai=−1，则点 i 可以连向 1∼n 任意点，求所有图的联通块个数之和

n 2e3

答案mod 998244353

题解

考虑G中一个联通分量

如果它有N点,N个边,那么它恰好有一个环

这关键就在题目的特殊性上,因为(i->ai),即每个点连出一条边,所以n个点组成的联通分量一定恰好N个边, 题目条件特点!

因此 题目变成统计环的 而不是统计联通分量

然后先考虑 非-1的部分已经构成的环, 这部分如果再和其它相连,那么额外连的部分一定不会再有环,是个树,所以其它和它连的部分一定不会再贡献,

所以在考虑-1构成环的话不会考虑已经初始有环的联通分量

对于目前剩余没有环的联通分量是树,把这些树标号从1到k,并且b[i]表示这些树的点的个数, 注意到它一定只有一条未连接的边

现在考虑一个环的构成, 一定是由一些树连成的

树1->树2->树3->树k->树1

我们不考虑没有参与到环中的其它树,即使它从联通分量角度连进来了, 我们之考虑对环的构成直接有贡献的树

那么 如果是由 k个构成的,每一个的树的出点是固定的,但是入点的选择是上一个树的点的个数, 而它们排成环的方案是(k-1)!

所以环的构成是$(k-1)! \times \prod_{i=1}^{k} B_{x_i}$

n 很小 n方 可以接受可以DP

说是分治计算$\prod_{i=1}^{K} (1 + B_ix)$可以做到 n log(n)

代码

https://atcoder.jp/contests/arc140/submissions/31923069

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#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

int n;
int a[2010];// 读入
int fa[2010]; // 并查集父节点
int sz[2010]; // 点个数
bool cir[2010]; // 是否有环

int getfa(int x){
  return x == fa[x]?x:(fa[x] = getfa(fa[x]));
}

void link(int u,int v){
  int fu = getfa(u);
  int fv = getfa(v);
  if(fu == fv){
    cir[fu] = true; // 有环
    return;
  }
  sz[fv] += sz[fu]; // 大小
  cir[fv] |= cir[fu]; // 环
  fa[fu] = fv;
}

ll mypow(ll v,int pwr){
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}
ll fac[2010] = {1}; // 阶乘

int main(){
  cin>>n;
  int freecnt = 0; // 自由度 -1 个数
  rep(i,1,n+1){
    fa[i] = i;
    sz[i] = 1;
    fac[i] = fac[i-1]*i%MOD;
    scanf("%d",a+i);
    freecnt += a[i] == -1;
  }
  rep(i,1,n+1){
    if(a[i] == -1)continue;
    link(i,a[i]);
  }
  vector<int> arr ;
  int circnt = 0;
  rep(i,1,n+1){
    if(fa[i] != i)continue; // 非联通块根
    if(cir[i]){ // 环
      circnt++;
      continue;
    }
    arr.push_back(sz[i]); // 树 有一个自由度
  }
  ll ans = circnt * mypow(n,freecnt) % MOD; // 本身就是环的贡献
  vector<ll> mulsum(n+10,0); // dp mulsum[树的个数] = sz乘积和
  mulsum[0] = 1;
  rep(i,0,(int)arr.size()){
    rep(k,0,i+1){
      // 注意前面一半只是 k+1个构成环的方案数, 对于环以外的 freecnt-k-1的自由度任意搭配 才是这些环对总答案的贡献值
      (ans += fac[k] * mulsum[k] % MOD * arr[i] % MOD * mypow(n,freecnt-k-1) % MOD)%=MOD;
    }
    per(k,0,i+1){
      (mulsum[k+1] += mulsum[k]*arr[i])%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

总结

我想了很久,都没有注意到题目条件特殊性带给联通分量的特殊性, 这还是不应该,应该加强这方面的反应

其实也算是树的知识没有警醒我, 边=点-1,那么就会反应到这里连通分量的边 <= 点 且 >= 点-1

参考

官方

0%