CF tracker

Edu List

https://codeforces.com/contest/1716

E. Swap and Maximum Block

给一个长度 2^n 的数组a, 值范围是[1~2^n]

q个询问,

每个询问, 给k, for i = [1..2^n-2^k], 如果该轮询问没有交换过a[i],则交换swap(a[i],a[i+2^k])

操作后, 输出最大的连续区间的和

范围

n 18

a[i] \in [-1e9,1e9]

q 2e5

4s

512mb

我的思路

很显然 就是一个满完全二叉树

而操作k 就是从下向上第k层左右交换,(第k-1层每个点交换左右儿子)

问题是如何维护最大值, 或者如何算最大值

考虑直接算,

f(l..r) = max(f(l..mid),f(mid+1..r),maxr(l..mid) + maxl(mid+1..r))

maxr(l…r) = max(suffix(l…r))

maxl(l…r) = max(prefix(l…r))

但问题是 交换会让比 n-k层更低的 都会影响

感觉可能的方向, 就是 暴力从下向上, 枚举所有

似乎 就 层数的个数 和层数的方案数的乘积都是2^n, 这样就是n 2^n???

CF tracker

Edu List

https://codeforces.com/contest/1721

F. Matching Reduction

给2分图, 左侧n1个点, 右侧n2个点, m条边

2种询问

第一种, 删除最少的点, 让最大匹配的值 正好少1, 输出具体选点方案, 剩余的匹配边的index和

第二种, (只会紧跟着第一种, 输出实际的匹配方案)

注意的是,在输出询问的结果前是无法读下一个的, 你需要fflush 输出后才能读下一个询问

范围

n1,n2 [1,2e5]

m 2e5

q 2e5

8s

512mb

强制在线

我的思路

极端一点, 不妨设每次都有1和2的询问, 就变成了如何维护二分图的匹配了

有点想到 abc215 的霍尔定理(左侧n点,右侧m点, 最大匹配为n的充分必要条件, 左侧的任意k个点集子集,连右侧点的个数都>=k)

所以如果 当前的匹配 刚好一侧点=匹配个数, 那么这一侧就随便删除一个点就行, 并且还满足这一侧的点=匹配数

问题来到 当匹配数 < 左侧点, 右侧点 时如何处理

1
2
3
4

1 -> 4
2 -> 4
3 -> 5
3 -> 6

比如这个就是两侧都是3个点,但是最大匹配只是2, 看上去, 删除3或者4都能让个数-1

再变化

1
2
3
4
5
6

1 -> 4
2 -> 4
3 -> 5
3 -> 6
7 -> 8
7 -> 9

不论删除3还是7 都可以让匹配数-1, 但是 都不会让匹配数 = 一侧点数

主要感觉霍尔定理还是和完美匹配挂钩

考虑直接匹配, 得到一个方案, 如果删除的点不在匹配中, 那么一定对个数无影响

所以至少需要删除一个匹配中的点

虽然匹配过程有顺序, 但是因为点是可以乱序, 所以考虑如果让最后一个失配 会怎么样

1. 删除左侧点,

那么 左侧且在它前面的未匹配点不会影响,因为没匹配它时也未找到方案(在匈牙利算法中一个匹配成功的点会一直在匹配中)

左侧未匹配在它之后的可能会有影响, 设它是 u0 -> v0, 而后面的是u1 能通过某条路径(不一定直接,可能和前面的点走反边)和v0 匹配, 而u0 可以匹配某个当前右侧未匹配的 v, 那么这种情况 会有更大匹配, 而当前就是最大匹配矛盾,

所以如果有u1有路径和v0 匹配则 u0 一定没有额外可匹配的点,(这种情况删除v0即可, 空出来的u0不会被任何匹配)

否则所有u1都没有路径到v0, (这种情况删除u0即可,空出来的v0不会被任何匹配,其实左右交换是有对称性的)

综上得到, 每次只需要删除一个点(左右中一个和另一侧 未配点没有匹配关系的)

how 找

好处是上面的方案 所有匹配都没有变化, 只是减少, 而不会交换匹配的点

那么不如先跑一遍最大匹配, 然后枚举点和边, 计算每个点和未匹配的点有边的个数(O(E+V))

丢进set< pair<个数,点id>>维护

然后删除时更新一下set, 每条边更新一次, O(E log E)

然后随便set维护一下匹配方案

似乎就没了?

但是想了个反例

1
2
3
4

1-1
2-1
2-2
3-2

然后当前是1-1和2-2, 注意到右侧2没有未匹配点和它相连, 所以如果删除它匹配的左侧1, 并不能让个数下降

所以需要 找到的是一侧匹配的点 有, 一侧没有的这种去删除, 否则 所有的点都没有额外连接点了(就可以任意一个)

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 能预判吗??

并不会

CF tracker

Edu List

https://codeforces.com/contest/1739

F. Keyboard Design

n个字符串 si, 价值ci

包含的字符都是 ‘a’~’l’ (前12个), 保证每个字符串中相邻字符不同

求 价值最大的 字符串价值集合 满足:

可以制作一个'a'~'l'出现且只出现一次的字符串t, 使得集合中所有字符串si中相邻的字符,在t上也相邻

范围

n 1000

sum |si| 2000

ci [1,1e5]

4s

1024mb

我的思路

2000 这数字有点假, 因为既然是前12个, 真的有用的配对是 11+10+9+..+1 = 12 * 11/2 = 66个

但是 66 个去做bitmask就不现实了,

12个字符,有11个连接,所以这66个中最多同时11个, 更直接就是 12!=479001600, 但是太大了

12如果是bitmask, 但似乎表示不了什么意义, 即使连成链, 不只是两头有意义, 中间的连接方式也会影响

所以其实是 n = 1000

然后每个字符串提供一个 <= 11 的连接方案(66种候选), 如果超过11一定不可能

然后 选一个集合, 使得连接方案的并 依然<= 11, 且没有任何字符连了3个, 也不构成环

样例1

1
2
3
4

3
7 abacaba
10 cba
4 db

就可以变形成

1
2
3
4

3
2 a-b a-c
2 a-b b-c
1 b-d

一个想法是, 从排列来讲是12!, 上面看到是4e8, 但是如果仅仅说连接方式, 一个连接方式 对应两个排列, 所以还是有2e8

难道真的要 暴力搜索+剪枝吗??

这个ci, 1e5 到大不小的,算和的话能有1e8, 没啥想法

想钦定一个 si被选, 但这样的 感觉还没钦定连接好, 但钦定连接就是枚举

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的则可以忽略

不会啊,干