Educational Codeforces Round 137

發表於 更新於 分類於 ， Disqus： 文章字數： 4.2k 所需閱讀時間 ≈ 14 分鐘
D(随机)E(DP)F(数学,贡献统计)G(fib,DP)

https://codeforces.com/contest/1743

D. Problem with random tests

给你长 n的0/1

问它的两个子串(连续)的 bit or 的最大为多少

范围

n 1e6

4s

512mb

随机生成数据 不支持 hack

我的思路

首先一个肯定是原串,为了最高位1

那么剩下的一定是从最前连续1里面开始的

1
2
3
4
11100001....
3个1 len1=3
   4个0 len0=4
       ....

那么为了尽量高位填1, 如果len1 <= len0, 那就是都从第一个1开始,长度差为len1

1
2
3
11110001.....
len1=4
    len0=3

但如果len1 > len0

那么可以选的 有从头开始,和从偏移一个开始, 这两个都会or掉第一节的0, 但是后面的情况是未知的

看着禁止hack 似乎需要上string hash的意思?

如果暴力找就是 候选的开头在

1
2
11111110001....
xxxxx 这些位置都是候选

然后对于原串, 找每个0的位置, 反过来在候选中找是否为1, 不为1则剔除候选,

这样感觉要n^2

有点想后缀数组排序, 但问题是, 这里只有原串为0的对应位置需要是1(参与比较), 而原串已经是1的则可以忽略

不会啊,干

题解

取的两个一定是s前缀, 因为不是前缀变成前缀不会更差, 所以如果有最有解不是前缀,它门有等价的前缀方案

然后一样的,其中一个是s(为了最高位的i)

问题就是 s 和 s的前缀的计算, O(n^2)

然后就是 因为保证了随机性,所以就是上面的 候选+检查有0的位置, 暴力就完了, XD

随机题目暴力过?????? 随机完全不会 XD

E. FTL

2个武器, 每个伤害pi(瞬发),充能时间ti

敌人 血h, 护甲s

h<=0则死亡

每次 单独用武器, 则 h -= pi-s

同时用两个武器 则 h -= p1+p2-s

问最短时间击杀敌人

范围

pi,h,s [1,5000]

s < pi

ti [1,1e12]

4s

512mb

我的思路

这 5000就像是n^2的感觉, 但我完全没想到这个方向能怎么做状态

一个暴力一点的就是

map[h] = vector{时间, cooldown1,cooldown2}

这样每次 转移下一个状态, 可以单独等1, 单独等2, 和等两个一起用

但实际上 cooldown 如果不想等的话, 等待更长的不会优于 等两个一起用

所以是 等待短的 或 等待长的一起用, 延伸是两倍状态

再观察到, 每次转移后, 一定两个中一个的cooldown == 0

所以

map[h,cd1==0] = {time,cd2}

map[h,cd2==0] = {time,cd1}

map[h,cd1==0]={t,cd2} 为例, 考虑具体转移

单独用第一个

当cd2 >= t1时, map[h-(p1-s),cd1==0] = {t+t1,cd2-t1}

当cd2 < t1时, map[h-(p1-s),cd2==0] = {t+cd2,t1-cd2}

等待第二个好一起用, 不妨设(t1<=t2)

map[h-(p1+p2-s), t1==0] = {t+t1,t2-t1}

那么问题来了, 可能出现 h相同cd1==0的情况, 右侧出现 timeA > timeB 但是 cd2A < cd2B 的情况吗, 感觉右侧只记录 最小时间总不是太对?

如果硬做, 这个状态数量是 2^5000, 因为h严格单调递减

而且可能这种密铺, h=501, s=1, p1=101,t1=2,p2=101,t2=3

1
2
3
4
5
1 2 3 4 5 6
x x|x x|x x|
   100 100
y y y|y y y|
     100   201

题解

在任何适合3种选择, 单独1,单独2, 等一起

题解 说它们没想到 有效的 greedy和bruteforce

尝试dp, 也是显然t 范围1e12 肯定不是state 的键值

直接尝试 dp[damage] = time 也并不能建立关系(跟我想用剩余血量是一样的, 并不能

dp[damage] = 最小的时间,造成damage, 且最后一次伤害是同时用两个造成的, (这个且是我太菜了,想不出)

dp[0] = 0

那么就是考虑 相邻的同时用两次, 中间就都是单独用,那么单独用就是尽可能用更多了,

T0 -> T1 能造成的伤害 为 (p1+p2-s) + (T1-T0-t1)/t1 * (p1-s) + (T1-T0-t2)/t2 * (p2-s)

似乎不太行

反过来, damage层面考虑, 那么时间一定是 t1/t2 的倍数, 如果都不是就还有留白时间,就不是最短了

所以 分别考虑1号刚好和2号刚好

比如1号刚好c次(包含最后一次)

时间就是 T = c * t1 >= t2

所以有 damage = (p1+p2-s) + (c-1) * (p1-s) + (c * t1 / t2 - 1) * (p2-s)

反过来 1号刚好c次

damage = (p1+p2-s) + (c-1) * (p2-s) + (c * t2 / t1 - 1) * (p1-s)

这样 for damage: for c 就是 O(n^2) 了 可AC

F. Intersection and Union

n个 连续整数集合S_i = [li,ri]

然后集合就有 并,交 以及 \oplus 运算 = 出现且仅出现在一个中的元素集合

对于所有这三种操作构成的序列op, 求 $\sum_{op} |((S_1 op_1 S_2) op_2 S_3) \cdots op_{n-1} S_n |$, ||表示size

mod 998244353

范围

n 3e5

li ,ri , [0,3e5]

5s

512mb

我的思路

连续集合的交和并还很好, 有依然连续的性质, 但是这个 \oplus 就很搞

但实际上 并不需要实际的结果, 只需要个数和

那么就是 贡献统计

考虑 点v 是否在结果中,如果在就贡献1

f(n,v,true/false) = 前n个的所有操作 v是否在结果中 的方案数

注意到 f(n,v,true) + f(n,v,false) = 3^{n-1}

那么考虑计算f(n,v,true)

如果 S_n 中有v, 那么

对于 并, 3^{n-2}

对于 交, f(n-1,v,true)

对于 \oplus, f(n-1,v,false)

所以 v 的次数为 2 3^{n-2}

如果 S_n 中没有v, 那么

对于 并, f(n-1,v,true)

对于 交, 0

对于 \oplus, f(n-1,v,true)

所以 v 的次数 为 2f(n-1,v,true)

综上

1
2
3
4
5
6
7
f(n,v,true) =
  v in S_n : 2 3^{n-2}
  v not in S_n : 2 f(n-1,v,true)

f(1,v,true) =
  v in S_n : 1
  v not in S_n : 0

所以就是倒着来 找 首个包含v的S

怎么找呢 set维护连续线段

S_n 的[li..ri] 贡献 为 2 3^{n-2} * 个数

那么 未找到覆盖的就是 [0..li-1] [ri+1..3e5], 这个线段直接 set<pair<int,int>> 去维护

然后 S_{n-1} , 这就是找 为覆盖中和 [l_{n-1},r_{n-1}] 重叠的

贡献就是 2^2 3^{n-3} * 个数

就没了

代码

https://codeforces.com/contest/1743/submission/188929257

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

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

pair<int,int> lr[300010];
ll p2[300010]={1};
ll p3[300010]={1};

// lr0 - lr1, return {count, remain lr}
pair<int,vector<pair<int,int> > >cut(pair<int,int>lr0,pair<int,int>lr1){
  vector<pair<int,int>> ret;
  auto [l0,r0]=lr0;
  auto [l1,r1]=lr1;
  int cl=max(l0,l1);
  int cr=min(r0,r1);
  if(cl > l0) ret.push_back({l0,min(r0,cl-1)});
  if(cr < r0) ret.push_back({max(l0,cr+1),r0});
  return {max(0,cr-cl+1), ret};
}

int main(){
  int n=read();
  rep(i,1,n) p3[i]=p3[i-1]*3%MOD;
  rep(i,1,n) p2[i]=p2[i-1]*2%MOD;
  rep(i,0,n) lr[i]={read(),read()};
  set<pair<int,int> > s; // 未覆盖线段
  s.insert({0,300000});
  ll ans=0;
  per(i,0,n){
    auto [l,r]=lr[i];
    auto ptr=s.lower_bound({l,-1});
    vector<pair<int,int>> rm;
    vector<pair<int,int>> add;
    if(ptr != s.begin()) ptr=prev(ptr);
    ll c=0;
    while(ptr!=s.end() and ptr->first <= r){
      rm.push_back(*ptr);
      auto [cnt, remain] = cut(*ptr,{l,r});
      c+=cnt;
      for(auto o:remain) add.push_back(o);
      ptr=next(ptr);
    }
    for(auto o:rm) s.erase(o);
    for(auto o:add) s.insert(o);
    if(c) {
      if(i) (ans+=c*p2[n-i]%MOD*p3[i-1]%MOD)%=MOD;
      else (ans+=c*p2[n-(i+1)]%MOD*p3[(i+1)-1]%MOD)%=MOD;
    }
  }

  printf("%lld\n",ans);
  return 0;
}

G. Antifibonacci Cut

fib 字符串, 就是f[0]=”0”, f[1]=”1” f[i] = f[i-1]+f[i-2] 拼接

例如 0,1,10,101,10110,

g(s) = 把字符串切割成多个均不是 fib 字符串的 切割方案数

给你n个字符串 si

求 g(s1), g(s1+s2), g(s1+s2+s3), … 答案mod 998244353

范围

n 3e3

|si| 1e3

12s

4mb !!!!!!!!!!!!!!!!!!!!!!!!

我的思路

这个memory 很异常, int32 = 32/8 = 4bytes, 4mb = 1m int32, 你甚至不能把这些字符串拼起来? 但 似乎用位表示就可以?3e6/32 < 1m

抛开空间, 如何算呢?

g(s) = \sum (g(s[0..i]) * [s[i+1..] is not fib]) = (\sum g(s[0..i])) - (\sum g(s[0..i]) and s[i+1..] is fib)

一个就是前缀和, 一个就是特别要判断的

而要判断的 根据fib的性质来说, 长度成幂次增长 , 所以 真正要比对的个数不多, 总长度? 也是O(n)吗? 因为上面构成可以看到, f[i-2]是f[i]的后缀, 所以 奇偶可以分开, 如果已经不是f[i-2] 了那肯定不是f[i], 所以直接暴力判断 是每次O(len), 那么总的会达到 O( (n|si|)^2), 这样暴力都不行

那么再看转移 如果一段[l..r]是f[i-2], 那么其实要判断再向前[l’…r] 是不是f[i],只需要知道 前面一段[l’..l-1]是不是 f[i-1], 所以每次遍历只是log级别了, 时间问题就解决了

如果是一般的空间限制,这个题目已经AC了, 但这题还有空间问题

所以 其实可以维护一个叫 isfib[i][lvl], 然而打表 fib

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
0 1
1 1
2 2
3 3
4 5
5 8
6 13
7 21
8 34
9 55
10 89
11 144
12 233
13 377
14 610
15 987
16 1597
17 2584
18 4181
19 6765
20 10946
21 17711
22 28657
23 46368
24 75025
25 121393
26 196418
27 317811
28 514229
29 832040
30 1346269
31 2178309

发现要超过3e6 也会达到lvl\in [0,31], 这样空间上还有问题, 一个是 isfib[i][lvl] 要3e6 * 32bit 都不够, 就更不要说还要存g了

那至少isfib 要想办法优化掉

同样的 刚刚观察到 fib[n-2]是fib[n] 的后缀, 那么不如改成 maxfib[i][odd/even] = 最大fib, 注意到最大的<=31, 所以需要4个bit, odd和even合起来就是 1byte, 这样3e6 byte 可存下, 但是距离4mb 很接近几乎存不下其它的东西了

这个g 我是真不知道了 how存

题解

一样也是先想到

dp[i] = sum(dp[..i-1]) - sum(dp[j], s[j…i] is fib-str)

同样两个问题也是dp存不下,和 需要快速判断 s[j..i] 是不是fib-str

维护 (j,dp[j]) 列表 且 s[j..i] 是fib-str

显然 f[i-1] 是 f[i] 的前缀 (除了f[0])

因此 s[j…i] 是 fib[MAX] 的前缀,

那么当增加一个 字符 时, 检查哪些(j,dpi) 不是前缀(不一定要是fib-str, 只需要是一个长fib-str前缀就行), 来移除非法的j

  1. 生成 3e6 的fib-str
  2. 或者用 prefix来指向 fib-str

(j,dp[j]) 的大小 是log n的!!!???

显然的是 i向前的 fib-str个数是 log 的, 但是 向前是fib-str 前缀的怎么也是log 的啊???

proof

想一个无限(足够)长的 fib-str

1
2
3
4
5
fib-str:          1011010110110...
s      :  xxxxxxxxxxxxxxxxxx
                  j........i
                     j1
                         j2

不妨设 j 是最前的 是前缀的, j1 是j后面第一个, 那么一定存在一个 j2到j1距离 = j1到j距离, (相当于字符串自己递归)

这样看起来 n/len 的和, 的样子

那就是这个 len 是有说法的?

其实就是 要证明

fib-str 的 fib-str[0..i]的后缀 是 fib-str的前缀的个数是log i级别的

1
2
3
4
fib-str: xxxxxxxxxxx|yyyyyyy
        [0.............i]
        "f[n-1]....."
        "f[n]..............."

如果能证明 y 之前只有首个x合法就 能证明是log级别的了

归纳法

先 f[n-1] 中(也就是上面一串x) 后缀是前缀的全在 它最后的f[n-3]里, 且是 某个后缀f的起始位置

1
2
3
4
fib-str:  xxxxx xxx|yyyyy
          yyyyy|zzz|yyyyy
          j           i
                j1....i

那么要证明的就是 f[n-3]/f[n-5]/f[n-7]/... +'1' 不是 f[n] 的前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
fn = 101 10
     101 10
       j+1

fn = 10110 101
        j  1 是前缀
        j  10 不是前缀

fn = 10110101 10110
          j   1 是前缀
          j   10 是前缀
          j   101 是前缀
          j   1011 不是前缀

似乎并不行,

突然想到一个证明, XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 证明有问题

// —-
//
// 因为fib-str不是周期串(proof, 不妨设 fib-str[i] 是最短的有子周期的字符串, 那么这个周期串同时是它的前缀也就是 fib-str[0..i-1] 的前缀, 周期串也是后缀, 也是 i-2,i-4的后缀, 可以找到一个更短但是前缀后缀重叠的, 也是周期串,最小性不满足)
//
// // ............................................ // [ ][ ][ ][ ][ ]... // j : xxxxxyyyxxxxx // j-1: xxxxx //
//
// 或者在某个 [len(fib-str[j-1], len(fib-str[j])/2) 之间
//
// 但注意2倍周期 也同时是前后缀, 而两倍周期一定重叠, 所以又是可以找到更小的周期串, 和最小性冲突
//
// —
//
// 所以 如果fib-str[0…i]
//
//
// // fib: xxxxxxxx|yyyyy // [0..........i] // j.......i // k //
//
// 所以 j的位置 一定在 xxxxx一半以后, 否则 [j…k] 也是 xxxxx的前缀, 而单独看xxxxxxx 就会是周期序列, 而fib-str自身不是
//
// // [j....i] = xxxxxxxx|yyyyy - (> len(x)/2) //
//
// 所以两次以后就变成 比y更短的子问题
//
// 所以是log级别的!!!!!
//

1
2
3
4
5
6
7
8
0
1
10
101
10110
10110110
1011011010110
101101101011010110110

官方题解代码给了个很神奇的编码方式, 但是有点绕, 我给它再简化了一下

总的来说就是 fibstr[i] 就是编码值 末位 取反, 然后i -> i+1 的话 编码每次 +1, 但是一旦末尾相邻1则进位

1
2
3
4
5
6
7
8
9
10
1 -> 1  :                    1 fib 1
0 -> 2  :                   10 fib 2
1 -> 4  :   11         ->  100 fib 3
1 -> 5  :                  101     4
0 -> 8  :  110         -> 1000 fib 5
1 -> 9  :                 1001     6
0 -> 10 :                 1010     7
1 -> 16 : 1011 -> 1100 ->10000 fib 8
1 -> 17 :                10001     9
0 -> 18 :                10010     10

感觉可以倒着想一下, 先令code[fib[i]] = 2^i 也是所有 fib 映射到2的幂次

code[1]=1,code[2]=2,code[3]=4,code[5]=8,code[8]=16,code[13]=32

那么它们之间的就用 fib的映射的 和来表示

众所周知, 一个数只能唯一拆解成fib的和(不同时含相邻)

所以上面这种末尾连续11就仅为 其实就是 相当于 不同时含相邻的限制

因此 上面比如 18 = 10010 => fib[2]+fib[5] = 2+8 = 10

所以这个神奇的过程, 可以说是newcode = idx2code(code2idx(code) + 1) 的简化版

至于末位和x是取反, 就是因为这种运算关系下, 就如拼接一样,8=5+3 所以 [1..3]的末位 = [6..8]的末位

// 可能官方题解看起来更复杂, 是为了0位表示f[0]而不是f[1]

代码

https://codeforces.com/contest/1743/submission/189036902

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
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}


bool go(int& a, int x) {
  auto last_bit=[](int v){return v-(v&(v-1));};
  if(a%2 != 1-x) return false; // 低位和x相反, seqn[fib[i]]= (1<<i)
  // newa = idx2code(code2idx(a)+1)
  for(a+=1;a&(2*last_bit(a));a+=last_bit(a)) ; // ...11 00..00 -> ... 100 00..00, 末尾连续的1,要合并向上
  return true;
}

char s[1010];
int main() {
  int q=read();
  vector<pair<int, int>> w; // { cost, code[fib idx] }
  int last = 1; // 上一次答案
  int sum = 1; // 前缀和
  while(q--){
    scanf("%s",s);
    int sz=strlen(s);
    rep(i,0,sz){
      int c = s[i]-'0';
      int ndp = (sum-last)%MOD; // 切割最后一个char
      vector<pair<int, int>> neww;
      for(auto [cost, seqn]:w) if(go(seqn, c)) neww.push_back({cost, seqn}); // 这里go()更新了seqn
      w = neww;
      for(auto [cost, seqn]:w) if(!(seqn&(seqn-1))) (ndp -= cost)%=MOD; // fib在编码后都是2的幂次
      if(c == 1) w.push_back({last, 1}); // code[fib[1]=1]=1
      (sum += (last=ndp))%=MOD;
      assert(w.size() <= 60);
    }
    printf("%d\n",(last+MOD)%MOD);
  }
  return 0;
}

总结

D 也炸了, 对随机类的完全没感觉, 好家伙题解告诉我, 就是因为保证了随机性,就直接暴力检查就没了

E 估计出题人也觉得状态dp没那么难吧

这状态设计? 是我太菜, 感觉还是那个 dp[i] 除了i本身,还要附带一个特定的时刻, 比如有些就是i必须选中啊, i必须是某一段的结尾啊什么, 这里跟i没关系, 但是跟 其中的状态同时挂钩了

看到5000能想n^2 和与damage/health 作为state还是好的, 就是 以后要多思考 如何再增加一个且

F 感觉对我来说比E简单, 直接推一推,就出来了

啊,题解咋又是线段树又是矩阵的?????? 干了, 看了jiangly,noimi,rainboy,dreamoon都写的线段树,physics0523似乎跟我的一样, 好家伙我还真不知道线段树怎么搞

哦 我会了, 正着推 转移就是矩阵+线段树, 所以倒着搞就会特别简单

G

虽然也观察到了 f[n-1] 是 f[n]的前缀, 但是没想到怎么去用它

我感觉这个题目最关键的是说,有效的j开始的前缀列表 是log级别, 观察到这个剩下的就没啥了

然后这个编码还是有神奇

参考

官方