Codeforces Round 792

發表於 更新於 分類於 ， 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这种数也这样拆

参考

官方