Codeforces Round 934 (Div. 1)

發表於 更新於 分類於 ， Disqus： 文章字數： 4.4k 所需閱讀時間 ≈ 15 分鐘
D1,D2(DP,容斥)E1,E2(二分,贪心)F(TODO)

https://codeforces.com/contest/1943

D1,D2 Counting Is Fun

如果数组 每次可以 选择连续长度大于1的区间 同时减去1,操作多次以后 所有值变为0,则该数组是好（good）数组

对于 长度n,值范围[0,k]的 $(1+k)^n$个数组有多少个是好数组 $\mod p$

n D1(400),D2(3000)

$\sum n^2$, D1(2e5),D2(1e7)

$k \le n$

$p\in[10^8,10^9]$ 是质数

3s

1024mb

我的思路

good的充要条件？

首先 两端 不大于a1

如果出现连续3个$a < b > c$

要$b-a\le c$ (b,c同时下降 直到b变为a)或$b-c\le a$ (a,b同时下降 直到b变为c)

都是$b\le a+c$

所以 如果good 一定满足 上面的 两端 和 单峰的条件

那么如果满足 两端 和 单峰条件

对于单峰从左到右, 下降，每个前面的不影响后面的，

因此 这个条件是充要

就dp吧

dp[i][x][y]= 前i-1个位置合法，第i-1个位置是x,后一个是y的方案数

从第二项开始

然后 ans = sum dp[n][>=x][x]

对于$x\le y$

dp[i+1][x][y] = sum dp[i][...][x]

对于$x > y$

dp[i+1][x][y] = (sum dp[i][t][x], x <= t+y )=sum dp[i][>=x-y][x]

所以

dp[i+1][x][y] = sum dp[i][>=x-y][x], 其中 dp[i][<0][x]=0

用 后缀和可以 均摊 O(1) 计算每个x,y

所以有一个 $n n^2$的方法，感觉能过D1, 然后D2 明显TLE

感觉就是需要再次优化效率，然而上面的似乎并不能nxn的矩阵的矩阵乘法

然而 并没有成功优化

题解

一样 先 证明 充要条件 $a_i \le a_{i-1}+a_{i+1}$

一样 dp(i,a[i-1]=x,a[i+1]=y) 需要n^4, 通过 前缀和/后缀和 降低到n^3

D2:

容斥！？！？！？！？！？

属性$x_i$ 表示 $a_i > a_{i-1}+a_{i+1}$， 对应bad

$ans = \sum (-1)^{属性个数} 指定属性对应方案数$

例如n=3

$ans=f([])-f([1])-f([2])-f([3])+f([1,2])+f([2,3])+f([3,1])-f([1,2,3])$

dp[i,vi,cnt]= 第i个是vi，前i个中 钦定了cnt个bad 的方案数（注意这里是钦定的不是实际的，也就是未钦定的位置可以bad也可以good）

注意到只需要(-1)^cnt 所以

dp[i,vi,cnt=0/1]= 第i个是vi，前i-1个中 钦定了cnt%2 个bad 的方案数

ans=sum (-1)^cnt dp[n+1,0,cnt]

那么讨论转移

  1. 第i-1位不钦定 bad,那么它随便选！

dp[i,vi,cnt=0/1]+=sum dp[i-1, all, cnt]

  1. 钦定i-1位产生贡献,

dp[i,vi,cnt=0/1]=sum dp[i-2,j,1-cnt] * (k-vi-j), j=0..(k-vi)

也就是 i-2位放j,i位放vi,那么第i-1位放 vi+j+1…k 一共 k-vi-j 个

$dp[i][j][t]=\sum_{x=0}^{k-j} dp[i-2][x]1-t$

$dp[i][j][t]=\sum_{x=0}^{k-j} dp[i-2][x]1-t-j\sum_{x=0}^{k-j} dp[i-2][x][1-t]$

令 $dp_1[i][j][t]=\sum_{x=0}^j dp[i][x][t]$

$dp_2[i][j][t]=\sum_{x=0}^j dp[i][x]t$

$dp[i][j][t]+=dp_2[i-2][k-j][1-t]-j\cdot dp_1[i-2][k-j][1-t]$

综上 $dp[i][j][t]=dp_1[i-1][k][t]+dp_2[i-2][k-j][1-t]-j\cdot dp_1[i-2][k-j][1-t]$

代码

https://codeforces.com/contest/1943/submission/254768467

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

int n;
ll dp[3010][3010][2]; // dp[i][j][c]=第i个是j,前0..i-1个中钦定bad个数mod 2=c的方案数
ll dp1[3010][3010][2]; // sum dp[i][0..j][c]
ll dp2[3010][3010][2]; // sum dp[i][0..j][c](k-j)
void w(){
  n = read();
  int k=read();
  int p=read();
  auto up=[&](int i){
    rep(c,0,2) {
      dp1[i][0][c] = dp[i][0][c];
      rep(v,1,k+1) dp1[i][v][c] = (dp1[i][v-1][c] + dp[i][v][c])%p;
      dp2[i][0][c] = dp[i][0][c]*(k-0)%p;
      rep(v,1,k+1) dp2[i][v][c] = (dp2[i][v-1][c] + dp[i][v][c]*(k-v)%p)%p;
    }
  };
  dp[0][0][0]=1;
  up(0);
  rep(v,0,k+1) dp[1][v][0]=1;
  up(1);

  rep(i,2,n+1+1) {
    rep(v,0,k+1) rep(c,0,2)  dp[i][v][c]=(dp1[i-1][k][c]+dp2[i-2][k-v][1-c]-v*dp1[i-2][k-v][1-c]%p+p)%p;
    up(i);
  }
  ll ans=(dp[n+1][0][0]-dp[n+1][0][1]+p)%p;
  printf("%lld\n",ans);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

E1,E2 MEX Game 2

t,m 范围在E1,E2不同

a[n],c=[]

alice先/bob后

alice选 一个a[i] 删除并加到c的末尾，希望mex(c)尽量大

bob 选择至多k个a中的数删除，希望mex(c)尽量小

m是最大值，给定0~m的出现次数fi

m E1(50，总共1000),E2(2e5,总共2e5)

t测试组数 E1(500),E2(1e5)

k 1e9

fi [1,1e9]

2s

256mb

我的思路

k=1时就是前面的A题了

其核心就是 在1次操作后， alice每次在bob操作后 选择未来可能最快被截断的且未选过的值

而这些要选的值是在所有开始之前，通过分析就定好了的

那么这里 k大了以后

需要做的如果类似的是， 确定最终要选的 [0...x] 那么bob只会删除 这里的值

而alice 要做的就是每次选择[0...x] 中出现次数最少的

那么 同样 如果有多个 <=k的，那么 如果首次不选最小的值 且 个数<=k的，那么最小的会被割断，

所以[0...x] 最多有一个 个数<=k

然而这个性质只是必要，还不充分

因为 k=1时每次只能删除1个

而 k>1时 可以删除多个

也就意味着 可以同时让多个从 >k变为<=k

例如 k = 2

1
2
3
4
5
6
7
012 值

333 个数
223, bob 删除1和2各1个

alice必定选0
然后bob切断1,

因此 如果bob可以一次 让 a<b都<=k, 那么对于>b的所有都不应该先选

问题是 如果 次数更多bob会如何操作 什么是充要条件呢？

另一个观察就是 我们要么选天然的，要么选bob操作过的

也就是 选bob操作过的相当于 变相的减少了 bob的前置操作次数

再另一个角度讲，就是 当我们认为最终能[0...x]

那么 操作次数剩余>=1次时 bob不能同时让[0...x] 中任意两个未被选的 <=k

因为 预置了alice的首次操作，每次变成bob先alice后，

那么 所有-=k,那么就是 >=2次时 什么情况能让 >=1次时 最小的两个未被选的和 <=k

不妨从小到大排列, 注意到 alice的操作 一定是选 未被选的个数最小的

1
2
3
4
5
6
7
8
9
10
11
a<=b<=c...
那么 操作后一定保持(因为 如果是 x<=y => x0>=y0 的话，可以颠倒x0,y0得到同样的结果)
a1<=b1<=c1<=... 然后 a1被alice删除掉选走

那么变成需要满足

a>=a1
b>=b1
c>=c1
a1<=b1<=c1
b1+c1<=k

然而这个条件 如何算呢

max(b+c-k,0) 也就是(b,c)一共至少需要删除的量

(b-a)+(c-a) 是 不动a时,(b,c)最多能删除的量

若 max(b+c-k,0) <= (b-a)+(c-a) 则可以在不动a的情况下 让 b1+c1<=k, 也就是不合法

所以 合法需要 max(b+c-k,0) > (b-a)+(c-a) 即 max(2a-k,2a-b-c) > 0

且 尽量少动a

1
2
a   b          c           (a+b > k 否则直接操作a+b即可)
?  (>=k-k/2)  (>=k-k/2)

感觉推不出来

然后就是m比较小的话，尝试二分答案

然后 alice的操作变成每次 找范围内 未删除最小的一组 取用并删除

而 bob的操作 变成每次 找最小的多个 保持其顺序不变的情况下，一共减去k，想办法让其中一个 <= 0

然后 一个猜想 是 操作的个数会非严格单调递减

并且首次操作以后 被操作的个数会趋于相等？

考虑 虽然 指定[0...x]的操作满足合法的单调性，但 只有在分界点上才可以“贪心”，所以并不能二分

也就是 如果长度 [0...t]都可以达到[0...t+1]不可达到，那么bob每次操作都是剩余的全长？

所以枚举 m, 找最小的m， 直接用 贪心（从最大的开始消除并且保持 大小顺序不变）？？？

题解

也是 如果要判断 [0...x] 是否合法，那么 bob和alice的操作 都是在这个范围内

和我上面一样的结论

alice 每次只需要拿 出现次数最少的未被选择的数

同样 bob的每次操作 不会改变 fi的大小顺序（所以相当于k次 把 值最大中index最小的-=1）

因此 如果再指定 bob成功变为0的 值钦定是v

那么 bob会在不影响 大小顺序的前提下尽可能的让v的个数变小，

数组 维持成 sort pair{个数,值}

1
2
3
4
for 猜测长度
	for 猜测bob消除的目标
		for 模拟 操作
			for 每次操作 数组变化

O(m^4) 感觉也能过 E1

也是 特殊的 考虑

如果 一个数组 是 x,x,…x,x+1,…,x+1形式的则称作flat的（也就是上面我想的 如果一直操作最大-1，都是在趋近于flat的

那么 这样的flat 可以表示成 （n=长度，s=总和） 的2元组

例子 a=[1,2,3,5,5],k=4

有alice的操作: $[1,2,3,5,5] \to [2,3,5,5] \to [2,3,3,3] \to [3,3,3] \to [1,2,2]\to \dots$

无alice的操作 $[1,2,3,5,5] \to [1,2,3,3,3] \to [1,1,2,2,2] \to \dots$

而$[1,2,2]$ 不是 $[1,1,2,2,2]$ 的后缀，且是首次发生

如果 对于数组来说 有alice的操作的数组 在第p轮操作后 首次 不是 无alice的操作的数组 的后缀

那么 有alice的 数组 $= flat(n-p,(\sum f[p+1\cdots n]) - pk)$

证明: n-p是显然的

显然 不论有没有alice操作，每次操作的范围都是 一个后缀，而这个后缀的长度是非严格单调递增的，

当 (无alice的 操作后缀长度) <= (当前有alice的 操作的后缀长度)时，显然 在有alice对应的后缀是同样的操作

换句话说，之所以不同，是因为 无alice的操作过程中 后缀长度 大于 有alice的长度

而 注意到操作长度内 一定是flat的！

所以 在操作之前 n-p+1 长度，且所有 前面操作 都是在[p...n]的后缀中做-k

而第p次 删掉第p个，最后一次在[p+1..n]中做-k

不是很懂为什么 题解??????这里直接 是 所有在[p+1..n]里-pk，感觉前置操作是可能操作p的啊，例如 反例子

1
2
3
4
5
6
7
`f=[1,5,5,5],k=3`

`[1,5,5,5]->[5,5,5]->[4,4,4]->[4,4]->[2,3]`

`[1,5,5,5]->[1,4,4,4]->[1,2,2,3]`

而 `[2,3]=(n=2,s=5) != (n-p=4-2,f3+f4-pk=5+5-2*3=4)`

感觉需要先判断 a[p] 和 (n-p+1,f[p...n]-(p-1)k)中首个元素的大小来判断 (p-1)次时 是否操作到了 p位置，

而不论 这两种情况中哪一种，都会变到一个 2元的状态 (n,s)

而对于给定$n$, s又是单调的，对于每个n可以计算最小的s

所以上面的应该不是找 首次不是后缀，而应该找首次操作后缀长度=总数组长度，这样的花 总长度是严格单调递减，而“累计后缀操作长度”是非严格单调递增的，之所以这里需要累计是因为

1
2
3
4
5
6
7
8
1 2 3 3 3 3 
如果 每次处理2个，那么
第一次
1 2 2 2 3 3 
第二次
1 2 2 2 2 2

会发现第一次是后4个，而第二次是后2个，变短了，所以这里需要看成第二次是从初始状态做了2k次减1的累计操作得到，所以第二次还是看错长度4的操作

注意到随着操作次数p的上升

f的后缀总长度在下降，后缀和在下降，-pk也在单调递减

类似E1,对于给定p

那么就是

  • f[i+1...sz]全变为f[i]的代价 < pk，也就是至少需要i或者更前
  • 且f[i...sz]全变为f[i-1]的代价 >= pk, 也就是不影响i-1时操作后面的能消除pk个

所以可以二分 次数p，找到 n-p > 操作长度 和 n-p <= 操作长度 的分界点 （这里把等号放右侧的好处是，分界点的值就是题解中的(n-p,sum f[p+1..n]-pk)）

那么对于$(n,s)$, 操作一次后是 $(n-1,s-\lfloor \frac{s}{n}\rfloor -k)$

显然好坏满足单调性，可以 找到 $s_{\min}(n)$ 让 它是好的, 预处理，二分倒推都行就行

综上 E2:

1
2
3
4
二分答案 ans
	for bob 目标攻破的位置
		二分变成 (n,s) 形式
			利用预计算的 n=>min s 判断s

或者 这里不要预计算，而是把所有(n,s) 统一从高到低计算，对于同样的n只保留最小的s

1
2
3
4
5
6
二分答案 ans
	ns_list = []
	for bob 目标攻破的位置
		ns_list.append(二分变成 (n,s) 形式)
	for ns_list 按n从大到小下降
		对于每个n 只保留最小的s

代码

E1

https://codeforces.com/contest/1943/submission/254840722

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
#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;}
void w() {
  ll n=read();
  ll k=read();
  vector <ll> f(n + 1);
  rep(i,0,n+1) f[i]=read();
  auto check = [&](ll x){ // [0..x-1] 都能选到
    vector<ll> b;
    rep(i,0,x) b.push_back(f[i]);
    sort(b.begin(), b.end());
    rep(fix,1,x) { // bob 能消除个数大小排序中第fix 大的
      deque <ll> c;
      rep(i,0,fix+1) c.push_back(b[i]);
      assert(c.size() >= 2);
      while (c.size() > 1){
        c.pop_front(); // alice 每次删除最小
        int sz = c.size();
        ll sti = 0;//[sti....sz) 是操作范围, 要么sti=0,要么[sti..sz)>=[sti-1](不被操作) 所以c[sti-1] != c[sti]
        ll sum = 0; // 后缀j个的和
        per(j,1,sz) {
          sum += c[j];
          if (sum - (c[j-1])*(sz-j) >= k){ // sum (c[j~sz) - c[j-1]) = (sum c[j~sz) ) - (sz-j)*c[j-1]
            sti = j; // [sti...sz)
            break;
          }
        }
        ll have = k;
        rep(j,sti+1,sz) { // c[sti+1..sz) = c[sti] 先把[sti+1..sz)和sti 相等
          have -= c[j]-c[sti];
          c[j] = c[sti];
        }
        assert(have >= 0);
        rep(j,sti,sz) { // [sti,sz) 分摊have个 = have/长度 向上取整
          ll rm=have/(sz-j)+!!(have%(sz-j));
          c[j] -= rm;
          have -= rm;
        }
        rep(j,0,sz-1) assert(c[j] <= c[j + 1]);
        if(c.back() <= 0) return false;
      }
    }
    return true;
  };
  ll l = 1, r = n + 2; // ans=l 可达, r 不可达
  while (r-l>1) {
    ll mid = (l+r)/2;
    (check(mid)?l:r)=mid;
  }
  printf("%lld\n",l);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

E2

https://codeforces.com/contest/1943/submission/254864648

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;
const ll INF=0x3f3f3f3f'3f3f3f3f;
#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;}

ll k;
ll f[200010];
ll n2s[200010]; // n2s[n=长度] = 总和
void chmin(ll&a,ll b){a=min(a,b);}

bool solve(vector<ll> v){
  sort(begin(v),end(v));
  rep(i,0,size(v)+1) n2s[i]=INF; // INF
  ll l=1; // 左端点 v[l..i]，同时也是次数
  ll sli=0; // sli= sum v[l..i]
  rep(i,1,size(v)){ // 枚举bob切割点, 那么也就是 需要 v[0..i] 变形成(n,s)的格式
    sli+=v[i];
    while (l<i && sli-(i-l+1)*v[l] >= l*k){ // 如果 [l..i] 无法全变成 v[l] 且还有剩余(需要操作到l)，那么l+=1
      sli-=v[l];
      l++;
    }
    assert(sli-l*k<INF);
    chmin(n2s[i-l+1],sli-l*k); // 记录(n,s)对，同一个n只保留最小的s
  }
  per(i,2,size(v)+1) chmin(n2s[i-1],n2s[i]-n2s[i]/i-k);
  return n2s[1]>0;
}

void w(){
  ll n=read();
  k=read();
  rep(i,0,n+1) f[i]=read();
  ll l=0,r=n+2;
  while(r-l>1){
    ll mid=(l+r)/2;
    (solve(vector<ll>(f,f+mid))?l:r)=mid;
  }
  printf("%lld\n",l);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

总结

官方题解

D1,D2: D1的范围自己搞定了，一直在想怎么优化 转移效率或者转移方程

我看洛谷有些人是真的直接在D1上优化

D2的评分2800

我在想 这里容斥究竟妙在哪里，感觉上妙在 bad 永不相邻，而good是相邻的，所以good的转移 需要看两位，而bad的转移只用看1位，从而有更小的状态设计，转移的部分都用到了 前缀后缀和的优化

E1（2900）,E2（3300）:

自己 分析出了

  • alice 每次拿最小
  • bob 操作不会改变 fi的大小顺序
  • 操作就是 从最大的做k次-1

感觉 E1 比 D2 简单（虽然评分更高），

这里 在处理时，是先指定alice的目标，排序个数，再指定bob按照个数的目标，虽然这里bob的目标可以让alice再有更优的操作，也就是继续缩减alice的目标，但不要这样增加的复杂程度，因为这里我们 外层循环判断是alice的目标能否达成，即bob的所有目标不能达成即可，也就是这里一旦把最优动态决策变成了 固定的简化操作以后，就不要再考虑“全局最优的问题”了

然后 都想到了flat的方向，但自己没有深入推导

  1. 操作的部分一定是flat
  2. 一定是[原数组前缀 的 后缀]+flat结构，接下来就是 二分切割点了

F: TODO