Educational Codeforces Round 135

發表於 更新於 分類於 ， Disqus： 文章字數： 3.8k 所需閱讀時間 ≈ 13 分鐘
F(二分图)G(子集,bitmask,DP)

CF tracker

Edu List

https://codeforces.com/contest/1728

F. Fishermen

n个钓鱼人

第i个获得大小a[i]的鱼

他们选一个报告的顺序, 报告鱼的大小b[i], 但是可能虚报

第一个报告的 诚实报告

其它人报告的 是最小的b[i]=a[p[i]]的倍数 且 大于 前一个报告值

1
2
3
1 2 3 2 2 8 3
按顺序报 变成
1 2 3 4 4 8 9

对于所有报告顺序, 让所有报告的 sum b[i] 最小

输出sum b[i]的最小值即可

范围

n 1000

ai [1,1e6]

6s

512mb

我的思路

如果两两不同, 那么从小到大就好了, 因为b[i] >= a[i], 这是所有都取a[i] 是最小值

如果 两个相同, 那么至少一个要虚报, 那么至少 2a[i]

如果 三个相同, 那么=> a[i], 2a[i], 3a[i]

但不只是让它们不同就完了, 因为翻倍后依然可能相同

1
2 2 2 3 3
1
2 4 6 3 6

这两个6还要处理

但是一个6是变8, 一个是变9

显然 如果a 有重复n次, 那么 a,2a,…,na 一定都有的,不会中间空着, 否则把更大的来填补可以让它更小

感觉上 当倍增的时候遇到相同的, 那就让小的去增加,

但实际上

1
2
3
4
2 2 2 2 3 3
变成
2 4 6 8
3 6

如果是 2的6去变化, 那么要变成16, 不如3的6变成9

而变化, 因为上面说了不会中间空着, 那就是每次找 最大的倍数去变

这样靠差值最小来变化的贪心, 似乎是对的吗???? 但我证明不了

然后 如果这样搞, 运算量

1
600 个1, 300个2 这样大量重叠

似乎也就O(2n)?

写了下, 不出所料 样例都没过

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++)
ll read(){ll r;scanf("%lld",&r);return r;} // read
int main(){
  int n=read();
  map<ll,vector<pair<ll,int> > > v2tv; // {倍数, 原值}
  rep(i,0,n){
    int a=read();
    v2tv[a].push_back({1,a});
  }
  map<ll,ll> v2mxt; // v 到最大倍数
  ll ans=0;
  while(v2tv.size()){
    auto [k,arr]=*v2tv.begin();
    v2tv.erase(v2tv.begin());
    auto keep=arr[0];
    rep(i,1,size(arr)){
      auto [kt,kv] = keep; // keep {t,v}
      auto [nt,nv] = arr[i]; // new {t,v}
      if(!v2mxt.count(kv)) v2mxt[kv]=1; // kt 一定是1
      if(!v2mxt.count(nv)) v2mxt[nv]=1; // nt 一定是1

      ll nkt=v2mxt[kv]+1;
      ll nnt=v2mxt[nv]+1;
      if(nkt*kv < nnt*nv){ // 用keep
        v2mxt[kv]=nkt;
        v2tv[nkt*kv].push_back({nkt,kv});
        keep=arr[i];
      }else{ // 用 arr[i]
        v2mxt[nv]=nnt;
        v2tv[nnt*nv].push_back({nnt,nv});
      }
    }
    printf("%d -> %lld\n",keep.second,keep.first*keep.second);
    ans+=k;
  }
  printf("%lld\n",ans);
  return 0;
}
1
2
3
4
5
6
7
8
1 -> 1
2 -> 2
3 -> 3
2 -> 4
3 -> 6
8 -> 8
2 -> 10
34

问题就在6的地方是动2还是动3, 动2是先到8再到10, 这个8 能预判吗??

并不会

题解

b是可能的 的答案 的充要条件 是 b[i] 是 a[i] 倍数, 且b[i] 两两不同

bi <= n * a[i], 因为 每个=a[i]数之所以要乘法, 就是为了必让和其它数碰撞,那么 不妨设其它数变化固定了, 那么最多占了 n-其它的个数 个位置, 所以剩下的位置 不小于 =a[i]的个数, 所以显然b[i] <= n*a[i]

然后构建二分图???!!!

左侧 a[i] 右侧 (1~n) a[i]

然后是二分图 带权匹配, 还要权最小

但是最小费用流 跑 1e6 点, 1e6边的图 并不可行

按照右侧点从小到大排序

然后把左右交换!!!!, 用b 去配a, 而不是a去配b

这样就是从小到大去配, 而且配了的, 即使交叉也是保持配了的

如果配失败了, 不需要清空vis ,可以优化O(n^4) 到 O(n^3)

代码

https://codeforces.com/contest/1728/submission/189159290

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

ll a[1010];
int r2l[1010]; // [右侧点] => 已经配对的左侧点, 0表示未配对
vector<bool> vis;
vector<int> e[1000010];
bool f(int u) { //
  for(int x:e[u]) if(!vis[x]) {
    vis[x]=true;
    if(!r2l[x] || f(r2l[x])) return r2l[x]=u;
  }
  return false;
}
int main() {
  vector<ll> val;
  int n=read();
  vis.assign(n+1,false); // 1-index
  rep(i,1,n+1){
    a[i]=read();
    rep(p,1,n+1) val.push_back(p*a[i]);
  }
  sort(val.begin(),val.end()); // 排序去重
  val.erase(unique(val.begin(),val.end()),val.end());
  int m=val.size(); // **左**侧点个数, 用值去配a,而不是a去配b
  rep(i,1,n+1) rep(p,1,n+1){
    int x=lower_bound(val.begin(),val.end(),a[i]*p)-val.begin()+1; // 1-index
    e[x].push_back(i);
  }
  int cnt=0;
  ll res=0;
  rep(i,1,m+1) if(f(i)) {
    res+=val[i-1];
    if(++cnt==n) break; // 最多就是n个匹配
    fill(begin(vis),end(vis),false); // 成功才清除vis,失败vis过的点都是无法找到的,不需要清空下次还能减少判断
  }
  printf("%lld\n",res);
  return 0;
}

G. Illumination

线段[0,d]内,有n灯, m个点关键点

对于每个灯, 可以选择它的 power \in [0,d], 点x上i的灯, 可以照亮 [x-power[i], x+power[i]]

一个合法 power 方案, 要每个关键点至少被一个灯照亮

q个询问, 每个询问独立,

  • 如果 在 qi 位置 增加一个灯, 问添加后所有灯的所有合法power的方案数 mod 998244353

范围

d [4,3e5]

n [1,2e5]

m [1,16]

q 5e5

8s

512mb

我的思路

m有点小, 但如果bitmask 再乘上n又有点大了

这样每次独立的增加一个, 感觉上有点像区间维护 中间插东西, 需要线段树一类的去维护

这q 5e5 感觉乱给的, 毕竟d才3e5, 不过都是3e5的量级 也差不多

如果不是插入一次性给的点, 怎么算

dp[i][j] = 前i个点, 成功覆盖小于 pos[i] 的 关键点 超出距离为j的 方案数

这样 状态 是 O(n * d) 太大了, 还要转移就更不行了

dp[i][j] = , 第i个关键点 左侧覆盖它 且index 最大的点是j, 且比i小的关键点全被覆盖的方案数

感觉上信息不足, 超出的距离也有意义 需要记录, 而且还可以从右侧覆盖

直接按照m个点切割成 m+1段区间

计算 区间i内的点, 向左覆盖到最小的 关键点

count[区间i][向左覆盖到最小的关键点][向右覆盖到最大的关键点] = 方案数

然后就可以

dp[前i个区间中的点][向左][向右] = 方案数

ans = dp[m+1][1][m]

两个问题 count 如何计算, dp如何转移

dp[i][l][r] = sum dp[i-1][l0][r0] * count[i][l1][r1] 满足 (min(l0,l1) = l, max(r0,r1) = r)

似乎好像 就是 [16x16] 的转移, 那么就是 其实就是 矩阵乘法+线段树维护? 但256^3 再 乘上q(5e5)实在有点大

这q甚至似乎 256 * 256 都接受不了

这个q显然可以离线按照顺序算

所以在离线的加持下问题变成3段(或2段)

左[l][r] , 当前[l][r], 右[l][r]

要求它们组合情况下 [1][m] 的值

其实问题回到 上面提出还未解决的问题, count怎么算

再仔细一想, 其实不用切割,

每个点可以表示成 [不覆盖关键点 的方案数, 覆盖1个的方案数….,覆盖16个的方案数]

最多17个状态

而实际上 变成这个状态后, 与实际的点在哪里 就属于冗余信息了.

那么就是 state[l][r] x point[17个状态] => new state[l][r]

要做~7e5次这个运算, 因为5e5(3e5)次都是单独的, 所以n(2e5)次是批量还是单独 似乎对量级都影响不大了

感觉表达式一写,它就是一种二维的什么卷积??

c[i][j] = sum a[i0][j0] * b[i1][j1] , (i,j) = (min(i0,i1),max(j0,j1))

统计一点

i0=i,j0=j,i1>=i, j1<=j

i0=i,j0<j,i1>=i, j1==j

i0>i,j0=j,i1==i, j1<=j

i0>i,j0<j,i1==i, j1==j

配上二维前缀和, 可以优化到16 * 16, 似乎就能过了, 256*7*10**5= 179200000

但实际上是不对的, 当两个不重叠的 [l,r] 合并 并不是 min, max

而还是 bitmask

f[bitmask] = 方案数

f[bitmask] * 新点 => newf[bitmask]

这就不一样了, 需要得到初始的f[bitmask]

和 f[bitmask] * 新点 的 [1<<m-1] 的单点值即可

单点 最多17种非0 bitmask, 但是17 * (1<<m-1) * q 也接受不了

所以问题在于, 如何批量计算初始的f[bitmask]

和 单点如何快速计算 [1<<m-1] 的值

看起来前面是 c[i] = sum a[i0]*b[i1], i=i0|i1的卷积问题

但即使 能够 线性(比log还小)得到, 2**16*2*10**5= 13107200000, 似乎也不太能做

而最后的 单点计算反而简单一些, 如果前面算好了, 可以把bitmask 转换成 [左侧连续1的最右][右侧连续1的最左]

再累和,去预处理 [左侧连续1 >= i][ 右侧连续1 <= j]的个数

这样 单点的p 加入, 枚举17种 都是O(1)的了

所以如果能快速算出前面的f[bitmask]这个题就AC了

题解

也是先考虑静态

但它不是考虑的插入计算, 而是考虑 所有 - 无效的方案, 然后无效的方案用容斥算

容斥就很显然, 灯的照亮半径被左右 指定 无效的关键点限制最大长度, 所以 算完后 ans=ways[mask]*(-1)^popcount(mask)

而且容斥, 正好和我上面切割的想法一样, 因为 当指定相邻 i 和j不被照亮时, 它们中间的 对 ways贡献的倍数就是固定的

所以容斥 先计算 count[i][j] = , i和j之间的方案数, 复杂度为 (<= m左关键点 * m右关键点 * n之间的点), 是可以接受的

然后再转成 dp[前缀mask] = 方案数, 来帮助计算 ways[mask] = O(mask * m) 也是可以接受的,

O(m) 每个询问??

1
2
3
4
11 3 2
1 4 11
2 7
...
1
2
3
4
11
   0 1 2 3 4 5 6 7 8 9 10 11
L    x     x               x
P      x         x

这里通过 pways[mask] = 钦定mask时 一个点的方案 * 距离 和 pways[mask 更大一个点] * 1/距离来实现

比如 对于灯L=11 和 mask=10,

ways[10] = pways[10] * pways[11]

而关键点P=7时, 它对 11的贡献是 *4, 而对于10的贡献是*1/4

关键点P=2对10的贡献是*9,对11的贡献是*2, 所以 ways[10]=18

1
2
3
4
ways[00]=1 // 这个会被替换掉
ways[10]=18
ways[01]=72
ways[11]=8

ans=sum ways[mask] * (-1)^popcount(mask)

ans=sum (\prod f(mask,l[i])) * (-1)^popcount(mask)

ans=sum (\prod f(mask,l[0..n-1])) * f(mask,x) * (-1)^popcount(mask)

所以需要 预计算 让f(mask,x) == d 的所有mask对应的 sum (\prod f(mask,l[0..n-1])) * (-1)^popcount(mask)

这样 一个灯x的和最近点j距离d的贡献, mask = 是msk[x][j]含j的子集 且 不是msk[x][j]不含j的子集

所以 按照accways[mask]=sum ways[mask] * (-1)^popcount(mask) 即可

转换加权类和

1
2
3
4
accways[00]=1728
accways[01]=1710
accways[10]=1656
accways[11]=1646

这样 ans = sum d[x][j] * (accways[mask[x][j]] - accways[mask[x][j] - (1<<j)]) , j=0..m-1

代码

https://codeforces.com/contest/1728/submission/189262201

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int 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;} // read

ll binpow(ll a, ll p){
  ll r = 1;
  while (p){
    if (p & 1) (r*=a)%=MOD;
    (a*=a)%=MOD;
    p/=2;
  }
  return r;
}

int c[1<<16];
int main() {
  int D=read();
  int n=read();
  int m=read();
  vector<int> inv(D+1,1); // [i]=1/i
  rep(i,2, D+1) inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;

  vector<int> b(n);
  rep(i,0, n) b[i]=read();

  vector<int> a(m);
  rep(i,0, m) a[i]=read();
  sort(a.begin(), a.end());
  a.resize(unique(begin(a),end(a))-begin(a));
  m=a.size();
  rep(i,1,1<<m) c[i]=c[i&(i-1)]+1;
  int all = (1 << m) - 1;
  vector<ll> pways(1 << m, 1); // f[mask] = 钦定mask不被覆盖 的方案数
  rep(i,0,m) rep(j,0,n){ // b[j] 最近的不被覆盖的
    int d = abs(b[j] - a[i]);
    int mask; // 不被b[j] 覆盖的点的mask: 1...10...01...1
    if (b[j] > a[i]){ // [a[i]=b[j]-d...b[j]...b[j]+d]
      int r = lower_bound(a.begin(), a.end(), b[j] + d) - a.begin();
      mask = all ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);// [0...i]...[r...m-1], 会左右同时包含等于
    } else {           // [b[j]-d...b[j]...b[j]+d=a[i]]
      int l = lower_bound(a.begin(), a.end(), b[j] - d) - a.begin();
      mask = all ^ ((1 << i) - 1) ^ ((1 << l) - 1);// [0...l-1]...[i..m-1] 左侧不会包含等于, 右侧包含等于,如样例3
    }
    (pways[mask] *=d)%=MOD; // 记录的达到这个状态的钦定下,有[0~d-1]种方案
    (pways[mask-(1<<i)] *=inv[d])%=MOD;// 对相对小的取逆,保证每个点所乘的串只会有刚好mask的贡献,可能在第一种情况失去意义,但是如果把(d看成带左右优先级的话, 依然保有意义)
  }
  // ways[mask] = \prod pways[包含mask的]
  vector<ll> ways = pways; // f[mask] = 钦定mask不被覆盖 的方案数
  rep(i,0,m)per(mask,0,all+1)if((mask>>i)&1)(ways[mask-(1<<i)]*=ways[mask])%=MOD;// 从大到小, 变成 ways[mask] = `>= mask`的方案数, 这样就是 钦定[mask] = 方案数, 除了mask==0
  ways[0] = binpow(D+1, n);

  vector<ll> accways = ways; // accways[mask] = sum ways[submask \subset mask] * (-1)^c[submask];
  rep(mask,0, 1 << m) (accways[mask] *= (c[mask]&1) ? -1 : 1)%=MOD; // 乘上 -1幂次的权
  rep(i,0, m) rep(mask,0, 1 << m) if (!((mask>>i) & 1)) (accways[mask|(1 << i)]+=accways[mask])%=MOD; // 从小到大

  int q=read();
  while(q--){
    int x=read();
    ll ans = binpow(D+1, n+1); // 所有方案
    rep(i,0,m){
      int d = abs(x - a[i]);
      int mask;
      if (x > a[i]){
        int r = lower_bound(a.begin(), a.end(), x + d) - a.begin();
        mask = all ^ ((1 << r) - 1) ^ ((1 << (i + 1)) - 1);// [0...i]...[r...m-1], 会左右同时包含等于
      } else{
        int l = lower_bound(a.begin(), a.end(), x - d) - a.begin();
        mask = all ^ ((1 << i) - 1) ^ ((1 << l) - 1);// [0...l-1]...[i..m-1] 左侧不会包含等于, 右侧包含等于
      }
      (ans += d*(accways[mask]-accways[mask-(1<<i)])%MOD)%=MOD;
    }
    printf("%lld\n", (ans+MOD)%MOD);
  }
  return 0;
}

总结

这F全场9人过, G全场48人过

F

光是b[i] <= n * a[i] 就没想到, 所以也完全没往二分图去想, 不过感觉 a->b 配对的 似乎就是 网络流和二分图相关的, 要建立联系

然后这个把值反过来 和 二分图匹配时的性质, 来保证最小性 也是学到了, 有点意思!!!

G

思路流程还是感觉比较传统了, 都是先考虑静态, 再考虑插入

这里 的 乘d 和 d的相反数, 感觉逻辑懂了, 但是没有很悟, 感觉还是很神奇, 因为我自己想的时候, 总想到 一个精确的[d0~d1]之间

感觉是 ways[mask] = f(点1) * f(点2) *...

然后f(点1) = p(短距离=大mask) * p(短距离的逆=相对小mask) * ... * p(正好距离=mask), 题解里的(sum-over-subsets (well, product-over-subsets in this case :)))

以及这里 关于相等的经典处理, 就是按照额外顺序来让它们全部都不等

然后这里反复的子集集合的变化, 虽然都可以证明, 但还是很不熟悉

参考

官方