Codeforces Round 800

發表於 更新於 分類於 ， Disqus： 文章字數： 4.1k 所需閱讀時間 ≈ 14 分鐘
C(反向dijkstra)D(DP,数学,贡献)E(标记,延后处理,贪心,树状数组)F(0/1串,数学)

D

https://codeforces.com/contest/1693/problem/D

给你一个排列

问多少个子区间 可以表示成 增序列和减序列合成的, 称作Decinc

范围

n 2e5

2s

512MB

题解

我的思路

如果是判断一个是否合法

考虑

inc[i] 表示i在增序列, 减序列的最大值

dec[i] 表示i在减序列, 增序列的最小值

然后dp一下O(n) 就做了

然后这里考虑有没有办法转移

因为如果[i..j] 是decinc的,那么它的所有子区间也是

考虑有没有办法dp然后做转移, 发现并没有办法转移

题解

AmShZ

一样的, 但是说是可以证明均摊更新是常数倍?

对于给定i, 找最大的j, 使得 j < i, a[j] > a[j+1]

注意到a[j],a[j+1] 不会都在增序列里,必定一个在减序列里

情况1 a[j+1] 在增序列的话 => a[j] 在减序列

情况2 a[j+1] 在减序列

且因为它是最大的j, 所以a[j] > a[j+1], 且a[j+1] < a[j+2] < a[j+3] < ... < a[i]

inc[i] = a[j](情况1) or a[j+1](情况2) or 0

而对于inc[i]初始化是是inf, 而对于a[j+1]..a[i]这一段都是inf

所以每个位置的值只会有4种情况

dec对称关系同理

换句话说

l从大到小,

每轮从小到大, 如果更新才会去算下一个位置, 否则提前退出

这里还有一点是就是 运算时,当给定l的时候, dp[i]仅依赖于dp[i-1]和a[i], 所以说如果dp[i]没有更新,则i以后的也不会更新, 所以更新的一定是连续的区间

所以sum 遍历 = sum 更新次数 = sum变化次数 = O(n)

Koosha_Mv

一个由升序和降序列合成的序列,当且仅当它不含 3412 也不含 2143

显然包含则不满足

怎么证明不满足一定包含这样的呢

回到dp的过程, 如果刚好在i不满足,

那么, 如果 a[i-1] < a[i], (a[i-1] > a[i] 对称同理

显然a[i-1] 在增序列不合法, (如果a[i-1] 在增序列有合法方案,那么把a[i]放到增序列即可

a[i-1]在减序列, 且 增序列最小值 > a[i]

所以 存在a[j] > a[i] > a[i-1], j < i-1

所以原序列是由

增序列 ..... a[j] 和 减序列.... a[i-1]合成的

因为a[j] 是满足的最小的a[j]

也就是, a[j] 不能放进减序列里(如果可以则能得到更小的增序列值

那么 不妨设下标 w(可能不存在) < j < k ,且 a[k] 在减序列中, a[w] 在减数列中

那么a[j] < a[k] (j k i-1 i => 3 4 1 2) 或 a[j] > a[w](a[j] 左侧至少一个

考虑把a[j]左侧分成三部分讨论, 大于a[j]的, a[i]到a[j]之间的, 小于a[i]的

如果a[i]到a[j]之间存在(3 4 1 2)`, 否则完全不存在, 且 小于a[i] 至少一个

如果大于a[j]的存在,则一定全属于减序列

如果小于a[i]的有不只1个, 那么一旦有其中两个递减 => (? ? j i) => (2 1 4 3) 即它的对称状态

小于a[i]的一定是升序列

总上可以重组 升序列a[j] 左侧,小于a[i], 包含a[w] .... a[j], 降序列a[j]左侧大于a[j]...a[j]右侧原减序列

注意到这样重组以后, a[j] 可以被放入减序列, 而增序列最小值将不再是a[j]

性质充要得证

如何实现

注意到3412和2143是对称的,所以a[i] = n+1-a[i] ,再跑一次3412就行

那么如何计算3412

考虑计算的结果是对于当前位置i作为3,min_r[i]表示最近的2让3412出现

给定3以后,4要是最近的,如果有2,那么1是离2最近的

所以先预处理每个位置后面和它最近的比它大的,以及每个位置前面最近的比它小的的位置

但是记录并不是[3]->4, [2] -> 1

考虑反着来4-> array{3}, 1->array{2}

为什么要这么样做呢,因为除了大小关系还有顺序,1 需要在4的右侧

那么我们倒着遍历4的位置

我们可以用fenwick记录i右侧, (1,2) 存在的[值]->2的坐标

这样我们对于每个3, 去fenwick上查, 值 < 3的值中存在的最大坐标, 就算出答案了

代码

https://codeforces.com/contest/1693/submission/160996027

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
#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 = 2e5 + 10;

int n;
int a[N]; // 数组
int inc0[N]; // a[i] 在增数组时, 减数组的最大值
int dec0[N]; // a[i] 在减数组时, 增数组的最小值
int f[N]; // f[i] = 该轮次的计算中,当前点i到 以l为起点的终点 的距离
ll ans;

void udec0(int i){
  if (n >= i){
    // 就硬算
    int inc1 = max( (dec0[i - 1] < a[i]?a[i - 1]:0), (a[i - 1] < a[i] ? inc0[i - 1]: 0));
    int dec1 = min( (a[i] < inc0[i - 1]?a[i - 1]:n+1), (a[i] < a[i - 1] ? dec0[i - 1]: n+1));
    if (!(inc1 == inc0[i] && dec1 == dec0[i])){ // 更新的一定是连续的区间, sum(遍历) = sum(更新) = sum(变化)
      inc0[i] = inc1;
      dec0[i] = dec1;
      f[i] = 0; // 结束点 距离为0
      if (dec1 <= n || inc1) udec0(i+1);
    }
  }
  f[i - 1] = f[i] + 1; // 到结束点距离+1
}

int main(){
  n = read();
  rep(i,1,n+1) a[i] = read();
  per(i,1,n+1) { // 倒序l
    inc0[i] = n + 1;
    dec0[i] = 0;
    udec0(i + 1);
    ans += f[i];
  }
  printf("%lld\n", ans);
  return 0;
}

3412,2143的

https://codeforces.com/contest/1693/submission/161132167

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
#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 = 2e5 + 10;


int INF = 0x3f3f3f3f;

// 前缀最小值fenwick
struct Fenwick {
  const int n;
  vector<int> a;
  Fenwick(int n) : n(n), a(n, INF) {}
  // 支持 [0..n) 更新最大值
  void setMin(int x, int v) {
    for (int i = x + 1; i <= n; i += i & -i) a[i - 1] = min(a[i - 1], v);
  }
  // 获得 [0,x) 最大值
  int get(int x) {
    int ans = INF;
    for (int i = x; i > 0; i -= i & -i) ans = min(ans, a[i - 1]);
    return ans;
  }
};


int n;
int a[N]; // 数组
int min_r[N];
ll ans;
stack <int> sk;
vector <int> vec[2][N];

// 如果指定3和2的位置,所以你需要的是3后面最近的4, 和2前面最近的1
void find_3412(){
  Fenwick f(n+10); // 下标是值, 前缀表示小于某个值的出现的最小坐标
  rep(i,0,2) fill(vec[i]+1,vec[i]+n+1,vector<int>());

  // vec[0][i] = vector<int> {j,...}, 表示 j 前面最近的比j小的是i, sk中保留单增的值对应的下标
  sk = {};
  rep(i,1,n+1) {
    while (!sk.empty() && a[i] < a[sk.top()]) sk.pop();
    if (!sk.empty()) vec[0][sk.top()].push_back(i);
    sk.push(i);
  }
  // 倒着做一边, sk中保持值单调递减, vec[1][i] = {j...} , j后面最近的比a[j]大的是a[i]
  sk = {};
  per(i,1,n+1) {
    while (!sk.empty() && a[sk.top()] < a[i]) sk.pop();
    if (!sk.empty()) vec[1][sk.top()].push_back(i);
    sk.push(i);
  }
  // 倒着做
  per(i,1,n+1){
    // f在遍历过程中,存的是(1,2) 的下标都>=i, 然后[2的值] = 位置
    // i=>1, ind=>2
    for (auto ind : vec[0][i]) f.setMin(a[ind], ind); // (i,ind) 构成增序列
    // 这次就是 i=>4, ind => 3, 因为如果确定了3,那么4就最近最好, 所以查询的是(1,2)位置在(以后,且值小于3的,结束位置的最小值),
    // 这里遍历过程之所以i=>4 而不是3,主要因为 保证(1,2)在当前位置右侧
    for (auto ind : vec[1][i]) min_r[ind] = min(min_r[ind], f.get(a[ind]));
    // 得到的是min_r[3的位置] = 最近的2的位置能构成3 4 1 2
    // 在反转过程中 min_r 直接取min,而f是清空
  }
}

int main(){
  n = read();
  INF = n+1;
  rep(i,1,n+1) a[i] = read();
  fill(min_r, min_r + n + 2, INF);
  find_3412();
  rep(i,1,n+1) a[i] = n + 1 - a[i]; // 做对称, 因为对称不影响答案, 而3412和2143是对称的
  find_3412();
  per(i,1,n+1) {
    min_r[i] = min(min_r[i], min_r[i + 1]);
    ans += min_r[i] - i;
  }
  printf("%lld\n", ans);
  return 0;
}

E

题目

https://codeforces.com/contest/1693/problem/E

n+2 长度数组a

首尾元素值为0

最小操作次数让 所有值 = 0

每次操作可以任选以下一种

  1. 最左的最大值=它的左侧的最大值
  2. 最右的最大值=它的右侧的最大值

范围

n 2e5

2s

256mb

题解

我的思路

值挺友好,给你的是[0,n]的范围,(就算很大也可以手动离散

没思路了

ecnerwala

官方的代码实在太长了

ecnerwala 有个超短的代码

https://codeforces.com/contest/1693/submission/160890042

有点延后判断, 贪心选最小值的意味

1
2
3
4
5
6
7
8
9
10
11
12
0 1 4 2 4 0 2 0
. . . . . . . . // 初始
. . ? . ? . . . // 最大的标记为?, 贡献 +2, 意义是第一轮处理2个

. . . x x x x . // 准备处理2的也就是x覆盖区间的, 把区间左侧问号标成 <(表示这个?位置的值比当前小,和左侧的最值相等, 右侧标成 > (同理
. . < . ? . . . // 标记
. . < ? ? . ? . // 对2处理, 贡献 +3

. . ? > > . > . // 同理对于1, 但注意到 1右侧的 < 会变成? 因为
. ? ? > > . > . // 贡献+2

// 0 不需要处理

总贡献是2+3+2 = 7

样例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 1 3 5 4 2 0
. . . . . . .

. . . ? . . . // +1

. . . < . . . // 
. . . < ? . . // +1

. . . ? > . . //
. . ? ? > . . // +2

. . < < ? . . //
. . < < ? ? . // +2

. . ? ? > > . //
. ? ? ? . . . // +3

1+1+2+2+3 = 9

再补充一个例子 1 2 3

1
2
3
4
5
6
7
8
9
10
0 1 2 3 0
. . . . .

. . . ? . // +1

. . . > . // 
. . ? > . // +1

. . > > . // 
. ? > > . // +1

1+1+1 = 3

总的来说, 每轮最大值,确定覆盖区间

区间左侧:

1
2
? 变 <
> 变?

区间内部

1
2
< 变 ?
> 变 ?

区间右侧

1
2
? 变 >
< 变 ?

最后最大值的所有点都是? , 统计?个数即可

实现

并不需要真的像上面思路那样维护4种 . , ? , > , <的状态

发现其实只需要统计?的个数

那么?个数有多少呢

区间内,所有大于它的都变成了问号, 所以区间内就是大于它的个数

区间左侧, 可能有 >,?,<

但 注意到一旦出现 > ,说明上一轮 > 的左侧有?, 如果出现 < 说明上一轮右侧有 ?

引理, 每轮结束后 除开.的情况,剩下的一定是 < ? > 形状的

归纳法可证明

因此, 你需要统计的是

  1. 相交关系
1
2
3
4
5
    ?   ?      // 上一轮结果
<  [l...r] >   // 上一轮结果
     [l...r]   // 本轮
      ?   ?    // 本轮
   < [l...r]>  // 结果
  1. 非相交关系
1
2
3
4
5
    ?   ?                 // 上一轮结果
<  [l...r] >              // 上一轮结果
                [l...r]   // 本轮
                 ?   ?    // 本轮
        < [l      ...r]>  // 结果

有

1
2
newl = min(l, lastr)
newr = max(r, lastl)

区间统计点 = 前缀差 = 树状数组维护

代码

ecnerwaia https://codeforces.com/contest/1693/submission/160890042

基于修改+注释+自己格式+bit改为fenwick: https://codeforces.com/contest/1693/submission/161139663

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
#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;} // read
 
int main() {
  int n = read();
  vector<vector<int> > idxs(n+1); // [值] = 下标数组
  rep(i,1,n+1) idxs[read()].push_back(i);
 
  vector<int> fenwick(n); // 树状数组, 大于等于当前的点记为1
 
  ll ans = 0;
  int lo = 1, hi = n + 1; // 左闭右开, [lo,hi)
  per(v, 1, n+1) { // 从大到小
    if (idxs[v].empty()) continue; // 忽略不存在的值
    // 本轮全为问号的范围
    std::tie(lo, hi) = make_pair(
        min(idxs[v].front(), hi),
        max(idxs[v].back()+1, lo)
    );
 
    // 本轮点 树状数组上标记为1,
    for (int a : idxs[v]) {
      for (; a <= n; a += (a&-a)) fenwick[a-1]++;
    }
    // 区间 [lo, hi) = pre[hi-1] - pre[lo-1]
    for (int a = hi-1; a; a -= (a&-a)) ans += fenwick[a-1];
    for (int a = lo-1; a; a -= (a&-a)) ans -= fenwick[a-1];
  }
  printf("%lld\n", ans);
  return 0;
}

F

https://codeforces.com/contest/1693/problem/F

0/1 字符串 S

每次选择一段 sort, 代价 |cnt(1) - cnt(0)| + 1

求最小总代价,让整个S有序

范围

n 2e5

题解

我的想法

假设最后一次操作了 [l..r]

那么说明 操作之前, [0..l-1] 和目标一样[r+1..n-1] 和目标一样

并且[l..r]中的1和0的个数尽可能的靠近

题解

结论: 只对0和1个数相等的进行排序

证明:

若最优方案中, 对[l,r]排序,且区间中,0比1多d个(d > 0), 代价d+1

如果l上是0, 只需要对[l+1,r]排序,代价为d, 且效果相同, 所以l上一定是1

确定区间左端点,右端点增加时,0和1的差的变化为+1/-1

因此必然存在k < r, 区间 [l,k] 的0和1的个数相等

排序[l,k],代价1, 再排序 [l+1,r] 代价 = d, 总代价 = d+1

所以任何一个0比1多排序, 可以拆成 (0和1相等的排序,代价1) + (0和1的差更小,更短,比原来代价更小的排序)

对于1比0多的情况, 对称关系同理可证

得证

问题变成如何选尽量少的0和1相等区间排序

把0换为-1

又变成经典的,前缀和2维图形化了, 每次选择的是等高的点, 让等高点之间变成 V字形

假设1比-1多,那么也就是结束点比起点高, 如果最后一段是从一个和起点相等的值 一直+1达到 结束点的,那么 把起点和这个值的区间处理即可

所以就是让最后一个连续+1 到的结束点 的那一串尽量长

我们记录达到每个值的首先出现的点, 只考虑(>=0的部分) 显然随着值越大,下标大,( 因为是从0涨过来的

而我们对末端的操作不会改变这个首次出现的位置

贪就完了

-1 比 1多 对称处理即可, 这里只要方案数不要操作细节,(所以还可以把 1变-1,0变1,并旋转字符串)

样例输入1的最后一个数据

这个和上面假设相反, 那就是 把头部可达的值的最小值的最后出现位置之间做区间处理

当然也可以双指针, (总代价移动是线性的

代码

https://codeforces.com/contest/1693/submission/162002156

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
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

char s[200010];
int pre[200010]; // 前缀和
int pos[200010]; // 首次出现的位置

int w(){
  int n = read();
  fill(pos,pos+n+1,-1);
  scanf("%s",s);
  int cnt[] = {0,0};
  rep(i,0,n) cnt[s[i] == '1'] ++;
  if(cnt[0] > cnt[1]) { // 保证 个数1 > 个数0
    swap(cnt[0],cnt[1]);
    rep(i,0,n) s[i] = (1 - (s[i] - '0')) + '0';
    rep(i,0,n/2) swap(s[i],s[n-1-i]);
  }
  int d = cnt[1] - cnt[0];
  rep(i,0,n) pre[i+1] = pre[i] + (s[i] == '0'? -1 : 1);
  rep(i,0,n+1){
    if(pre[i] < 0) continue;
    if(pos[pre[i]] != -1) continue;
    pos[pre[i]] = i;
  }
  int minv = d; // 倒着最小能连续到达的值
  per(i,-cnt[0],d+1){
    if(pre[n - (d-i)] != i) break;
    minv = i;
  }
  int ans = 0;
  while(minv + cnt[0] > 0){ // 已经完成排序
    if(minv < 0) return ans + 1; // 和l=0配
    ans ++ ;
    minv -= ((n-(d-minv))/*r*/-pos[minv]/*l*/)/2; // [l..r]
  }
  return ans;
}

int main(){
  int t = read();
  while(t--) printf("%d\n",w());
  return 0;
}

总结

C

Dijkstra 性质还是不够熟啊

D

直接的dp能想到,也在想转移,倒是转移也可以倒着做, 而且需要推导这个变化的条件,从而得到必定是区间变化,有遍历次数=变化次数=可能次数

另一个方案, 我有大的方向, 说看能不能找不成立的,但是没有得到3412/2143, 一个是这个充要真不知道比赛能不能快速证明,

再就是3412, 就算我知道了, 也不知道怎么去算, 这个按中间位置做遍历, 预处理 两头算是又学了一手

E

总觉得好像见过类似的标记处理, 这里是标记+延后+贪心

哦 像python里的 a,b= b,a+b 可以写成 std::tie(a,b) = make_pair(b,a+b)

原来树状数组还有bit和fenwick写法区别

bit版本的是 a|=a+1

fenwick的是 a+=(a&-a)

逻辑上 bit版本,统计的是末尾连续1的所有子集或上高位1的信息

而fenwick是当前结束向前(a&-a)长度的信息

F

敢于去猜让解答变容易的特殊情况,并证明它

经典的0/1区间个数相等处理, 变成-1,1 和二维图

参考

官方

ecnerwala E