Atcoder abc262

發表於 更新於 分類於 ， Disqus： 文章字數： 4.6k 所需閱讀時間 ≈ 15 分鐘
F(优先队列),G(DP),Ex(线段树,DP)

https://atcoder.jp/contests/abc262/tasks

F - Erase and Rotate

给一个长n排列A

问不超过k次操作后能得到的最小字典序列

每次操作 可以删除一个数, 或循环右移1个单位

范围

n 2e5

k [0,n-1]

2s

1024mb

我的思路

考虑两种一个是不移动, 从左删除, 那么就是前 k个中取最小, 然后 后面塞入一个, minPQ维护

右侧移动, 也可以确定 首个数字是啥

问题是 当右侧移动时, 可能和删除是同一个, 这个感觉没啥简单的想法去记录

比如样例数据三

如果看成先移动,再删除, 其实会删除移动过的数字

不知道能不能移动+标记+贪心局部?

然后因为k可能比较大,可以从左侧删除和右侧移动 来得到, 所以考虑两个方向来算, 算完了比较?

代码

https://atcoder.jp/contests/abc262/submissions/35554024

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆
int read(){int r;scanf("%d",&r);return r;}

vector<int> calc(vector<pair<int,bool>>&A,int del){ // {value, free del?}
  vector<int> ret={};
  minPQ<pair<int,int>> vi; // value,index
  int li=0;
  int ri=-1; // [li..ri] 中选择最小的一个作为剩余的头
  auto moveri=[&](int d){
    while(d>=0) {
      if(++ri>=(int)A.size())break;
      if(!A[ri].second)d--;// not free d
      vi.push({A[ri].first,ri});
    }
  };
  moveri(del);
  while(ri<(int)A.size()){
    auto [v,i]=vi.top();
    vi.pop();
    if(i<li)continue;
    // use A[i], [li...i...ri] => [i+1..ri+(1/0)]
    ret.push_back(v);
    li=i+1;
    if(!A[i].second)moveri(0);
  }
  return ret;
}

void p(const vector<int>&A){rep(i,0,A.size())printf("%d%c",A[i]," \n"[i+1==(int)A.size()]);}
int le(const vector<int>&A,const vector<int>&B){ // less equal
  int n = min(A.size(),B.size());
  rep(i,0,n)if(A[i]!=B[i]) return A[i]<B[i];
  return A.size()<B.size();
}

int main(){
  int n = read();
  vector<int>a(n);
  int k = read();
  rep(i,0,n) a[i]=read();
  if(k==0){
    p(a);
    return 0;
  }
  // left del
  int li=0;
  rep(i,0,k+1)if(a[i]<a[li])li=i;
  vector<pair<int,bool>>al={};
  rep(i,li,n)al.push_back({a[i],false});
  auto ansl=calc(al,k-li);
  // right move
  int ri=n-1;
  rep(i,0,k) if(a[n-1-i]<a[ri])ri=n-1-i;
  vector<pair<int,bool>>ar={};
  rep(i,0,n)ar.push_back({a[(ri+i)%n],ri+i<n});
  auto ansr=calc(ar,k-(n-ri));
  p(le(ansl,ansr)?ansl:ansr);
  return 0;
}

G - LIS with Stack

空序列X

空栈S

长n序列A

i=1->N, 每次把S.push(Ai) 或 A中移除

当S非空时, 可以把S顶部移动到X尾部

分数= 若X非严格单调递增, 则为X的元素个数

求最大分数

范围

n 50

ai [1,50]

2s

1024mb

我的思路

感觉说得很玄乎

实际上就是以 i 开始向前连续未取的取反向一段(可以一个也不取

以i+1开始向前连续未取的反向一段

这样拼起来 构成单调递增序列的长度

若 A[i]作为选的第一个, 那么后面[i+1..n-1]所有小于A[i] 的都是一个隔断

而考虑A[i-1] 的值

A[i-1] < A[i] , 那么必定A[i-1] 要么不选, 要么在A[i] 之前选,

想做一个 dp[i][l] = 从第i个向前反选, 总长为l 的最小最大值

问题是 比如 6 4 2 1 3 5

这样的, 后面的还可能选到更前面的, 光是 长度和最大值是不够的

n 有50 也不可能bitmask

然后考虑说倒着做,

如果 i开始向前选, 那么 单调递增必选, 因为如果不选, 也不可能之前选, 所以要么就不连续

而跨过的比它小的 则标记为前向的必选

这样有一个奇怪的

f(arr,i) = 数组倒着选, 最大的不超过a[i] 的方案数, 考虑最后增加一个无限大

f(arr,i) = max(arr[-1] 非必选 && f(arr[:-1],i), 从arr[-1]倒着选一段 f(arr - 移除, arr[-1]对应的a的下标j) )

这个看起来复杂度巨大, 但似乎当必选的时候 分叉有限 , 但是想加记忆化 也不知道怎么加

不会分析

然后对于相同的时候, 如果都要选,那必然是后面选前面

我好像读错题了………………………………………………………..

是 放入S或者从A中移除, 不是一定放入S

题解

假设如果在操作以前 先把 不会放在X的 提前移除

那么最终S为空

同时, 每次放入S的应该小于S中的所有, 而在X中最后一个元素被放入S时 它是i空的

然后dp

dp[li][ri][lv][rv] = , 通过用a[li..ri] 且值范围在 lv<=value<=rv 的最大长度

ans=dp[1][N][1][50]

也就变成3种操作

  1. 还是放入S

  2. 还是把S的出栈 加入X

  3. 删除A中的这个元素(不再是放入S, 对那些最终不会进入X的来说)

考虑转移

如果产生的最长序列X没有rv , 那么dp[li][ri][lv][rv] = dp[li][ri][lv][rv-1]

如果产生的最长序列X有rv, 设a[j] = rv, 且对应是X中的最后一个

那么在a[j] 放入S时, S一定为空(上面有说, 因为如果还有其它的话 也会被放入X中(从S最终为空的角度看))

那么考虑a[li...j-1] a[j] a[j+1..ri] 三段对应的X的三段 (<= v) (>= v, <= rv) rv(a[j])

dp[li][ri][lv][rv] = max(1+dp[li][j-1][lv][v]+dp[j+1][ri][v][rv]), v\in [lv,rv]

代码

https://atcoder.jp/contests/abc262/submissions/35555875

O(n^6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

const int N=50;
int a[N+10]; // 1-index
int dp[N+10][N+10][N+10][N+10];
void setMax(int&a,int b){a=std::max(a,b);}
int main() {
  int n=read();
  rep(i,1,n+1)a[i]=read();
  rep(i,1,n+1)rep(l,1,a[i]+1)rep(r,a[i],N+1)dp[i][i][l][r]=1;
  rep(len,2,n+1)rep(i,1,n-(len-1)+1)rep(l,1,N+1)rep(r,l,N+1){
    int j=i+(len-1);
    int &o=dp[i][j][l][r];
    if(l!=r)setMax(o,dp[i][j][l][r-1]); // r不出现在X中
    rep(k,i,j+1)if(a[k]==r)rep(v,l,r+1)setMax(o,1+dp[i][k-1][l][v]+dp[k+1][j][v][r]); // 无效的范围贡献刚好是0
  }
  printf("%d\n",dp[1][n][1][N]);
  return 0;
}

考虑a[i]是否选, 和a[i] 从S出栈的时刻O(n^5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

const int N=50;
int a[N+10]; // 0-index
int dp[N+10][N+10][N+10][N+10];
void setMax(int&a,int b){a=std::max(a,b);}
int main() {
  int n=read();
  rep(i,0,n)a[i]=read();
  rep(i,0,n)rep(l,1,a[i]+1)rep(r,a[i],N+1)dp[i][i][l][r]=1;
  rep(len,2,n+1)rep(i,0,n-(len-1))rep(l,1,N+1)rep(r,l,N+1){
    int j=i+(len-1);
    setMax(dp[i][j][l][r],dp[i+1][j][l][r]);// a[i] 不选
    if(a[i]>=l && a[i]<=r)rep(k,i,j+1)setMax(dp[i][j][l][r],dp[i+1][k][l][a[i]]+1+dp[k+1][j][a[i]][r]);
  }
  printf("%d\n",dp[0][n-1][1][N]);
  return 0;
}

Ex - Max Limited Sequence

问有多少个长n序列A满足

Ai \in [0,M]

和Q个限制 max(A[li..ri]) = Xi

求 个数 mod 998244353

范围

M [1,998244353)

n 2e5

q 2e5

xi [1,M]

我的思路

如何描述 max(a[l..r]) = X

考虑首个=X的位置是i

a[i] = X

a[l..i-1] \in [0..X-1]

a[i+1..r] \in [0..X]

那么无非是 不同的i的选取

问题是 这q很大, 每个这样拆的话, 似乎没法容斥?

题解

若Xi 全都一样

也就是 只是区间限制了

所有被区间覆盖的不超过Xi, 且每个区间至少一个Xi

dp[i][j] = a的前i个确定时, 且对于所有[L..R] <= i 满足, 最后一个等于X的位置在j的 方案数

虽然这状态数就 n^2, 但通过转移关系发现可以优化

第i个放X: dp[i][i] = sum dp[i-1][...]

第i个不放X: dp[i][j] = dp[i-1][j]*X (R=i的最大的L 满足L<=j) or 0

所以可以滚动掉第一个维度

每次 dp[i] = sum (dp[0..i-1])

然后 把 dp[0..max(L)-1] = 0

注意到 = 0 对于前缀和的贡献是0

所以考虑滑窗+记录和

范围 [j…i-1] 是非0, 和为s

1
2
3
4
5
6
7
8
s表示上一层 [0..i-1]的和
t=表示原始位置上i乘上 t 以后才是这个贡献
dp[i]=s/t/X; // 记录原始值, 因为t会变成t*X
newj = max(j,max(L(R==i)))
for k = [j..newj-1]: s-=dp[j]*t // *t 才是贡献
t*=X;
s*=X;
s+=dp[i];

这样的话 时间 空间都是1维的

回到原问题

准备 长n的 数组B 元素全是M

期望把它变成 全部是Ai的上限, 也就是把Q的限制合并成一个总上限, (因为还有等于的限制无法直接用上限表达

这个 也容易算出(其实把max(a[li..ri])=xi 改成 max(a[li..ri]) <= xi 就变成一个简单的黄色(2000分左右)题?

然后 问题变成了 你不再关心上限了, 因为上面合并出的已经包含了上限, 现在关心的只有存在性

也就是问题变成了

A[i] <= B[i] 的情况下, 满足 [Li..Ri] 中存在一个Xi

然后可选的位置也是 其中上限为Xi的位置中

所以不同的Xi 分开考虑

相同的Xi 考虑的位置就是那些限制为Xi的位置

对于每个X来说, 和上面一样的

dp[i][j] = a的前i个确定时, 且对于所有[L..R] <= i 满足, 最后一个等于X的位置在j的 方案数

(其中注意没有Xi=M的情况

但是转移有区别

dp[i][j] 不再是跟i-1 相关了 而是和上一个限制为X的位置相关, 其它不变

然后另外要注意的是, 上面是考虑R==i时,max(L) 而现在可能 R=i 的那个并不是满足 X的

只考虑Xi=X的所有[L,R]

所以转移也有变化

在i放X dp[i][i] = 要所有 R in [(last i)+1..i-1], 的区间的 最大L, dp[last i][>= max L的 i_L .. last i]

这里可能出现 不存在的情况

看如何逐步变化

1
2
3
4
5
6
dp[i][i] = sum dp[i-1][L限制区间] = s[i-1]
for j in 限制区间:
  dp[i][j] = dp[i-1][j]*x
s[i] = sum dp[i][新限制区间]

ans = s[last]

s改成变化表达

1
2
3
4
5
6
7
8
9
dp[i][i] = sum dp[i-1][L限制区间] = s[i-1]
for j in 限制区间:
  dp[i][j] = dp[i-1][j]*x
s[i] = s[i-1]
s[i]-= sum dp[i-1][移除的区间]
s[i]*= x
s[i]+= dp[i][i]

ans = s[last]

乘法和加法顺序交换

1
2
3
4
5
6
7
8
9
dp[i][i] = sum dp[i-1][L限制区间] = s[i-1]
for j in 限制区间:
  dp[i][j] = dp[i-1][j]*x
s[i] = s[i-1]
s[i]+= dp[i][i]/x;
s[i]-= sum dp[i-1][移除的区间]
s[i]*= x

ans = s[last]
1
2
3
4
5
6
7
8
dp[i][i] = sum dp[i-1][L限制区间] = s[i-1]
for j in 限制区间:
  dp[i][j] = dp[i-1][j]*x
s[i] = s[i-1]
s[i]+= dp[i][i]/x - sum dp[i-1][移除的区间]
s[i]*= x

ans = s[last]

令f[i][j]=dp[i][j]/x^i, 则dp[i][j] = f[i][j]*x^i

令 s[i] = sum dp[i][i+1的L限制区间] = sum f[i][...]*x^{i} = (sum f[i][...])*x^{i}= t[i]*x^{i}

于是t[i] = sum f[i][i+1的L限制区间]

1
2
3
4
5
6
7
8
f[i][i]*x^i = t[i-1]*x^{i-1}
for j in 限制区间:
  f[i][j]*x^i = f[i-1][j]*x^{i-1}*x
t[i]*x^i = t[i-1]*x^{i-1}
t[i]*x^i += f[i][i]*x^i/x - sum f[i-1][移除区间] *x^{i-1}
t[i]*x^i *= x

ans = t[last]*x^last

两边移除 通项

1
2
3
4
5
6
7
8
f[i][i] = t[i-1]/x
for j in 限制区间:
  f[i][j] = f[i-1][j]
t[i] = t[i-1]/x
t[i] += f[i][i]/x - sum f[i-1][移除区间]/x
t[i] *= x

ans = t[last]*x^last

处理 t=t[i-1]/x, 把数组变成复用的变量

1
2
3
4
5
6
7
8
9
f[i][i] = t[i-1]/x = t
for j in 限制区间:
  f[i][j] = f[i-1][j]
t[i] = t[i-1]/x = t
t[i] += f[i][i]/x - sum f[i-1][移除区间]/x
t[i] *= x
t = t[i]/x

ans = t[last]/x*x^{last+1}= t*x^{last+1}
1
2
3
4
5
6
7
8
f[i][i] = t
for j in 限制区间:
  f[i][j] = f[i-1][j]
t[i] = t
t[i] += f[i][i]/x - sum f[i-1][移除区间]/x
t = t[i]

ans = t*x^{last+1}
1
2
3
4
5
6
7
8
f[i][i] = t
for j in 限制区间:
  f[i][j] = f[i-1][j]
t = t
t += f[i][i]/x - sum f[i-1][移除区间]/x
t = t

ans = t*x^{last+1}
1
2
3
4
5
6
f[i][i] = t
for j in 限制区间:
  f[i][j] = f[i-1][j]
t += f[i][i]/x - sum f[i-1][移除区间]/x

ans = t*x^{last+1}

去掉维度

g[i] = f[?][i]/x

1
2
3
4
5
6
g[i] * x = t
for j in 限制区间:
  g[j]*x = g[j]*x
t += g[i] - sum g[移除区间] // 因为上面不变 所以才可以这样

ans = t*x^{last+1}

化简

1
2
3
4
g[i] = t/x
t += g[i] - sum g[移除的区间]

ans = t*x^{last+1}

0-index

再考虑无限制的前缀, 其实 就是 dp[i][i] = sum dp[i-1][L限制区间] 变成了 dp[i][i] = sum dp[i-1][L限制区间]+x^i

这个x^i就是 前[0..i-1]中x一次都不出现的所有情况, 也就是每个在[0..x-1] 之间随便选

所以影响的也一直是第一行, 看第一行的变化

1
2
3
4
5
6
7
8
9
10
11
dp[i][i] = sum dp[i-1][L限制区间]+x^i = s[i-1]+x^i

f[i][i]*x^i = t[i-1]*x^{i-1} + x^i

f[i][i] = t[i-1]/x + 1

f[i][i] = t + 1

g[i] * x = t+1

g[i] = t/x + 1/x

合并一下

1
2
3
4
g[i] = t/x + (无限制前缀?1/x:0)
t += g[i] - sum g[移除的区间]

ans = t*x^{last+1}

移除区间 也就和上面一样的滑窗维护就行了

失效情况

当 出现 [l..r] 都不为x的时候

这时, 会发现 计算的区间为空, 让sum = 0

而这时 已经不会是无限制前缀了, 所以往后的g[i],t 全为0, 能正常处理

这样ans= 所有的X的答案之乘积

代码

离散化 185ms

https://atcoder.jp/contests/abc262/submissions/35558599

unordered_map 191ms

https://atcoder.jp/contests/abc262/submissions/35558963

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
99
100
101
102
103
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r
int read(){int r;scanf("%d",&r);return r;}

const int N=200000;
const int INF=0x3f3f3f3f; // > 998244353
int seg[4*N+10]; // 叶子:min, 非叶子INF表示非区间lazy
int b[N+10];

int build(int o,int l,int r,int v){
  if(l==r)return seg[o]=v;
  build(SEG_L_CHILD,v);
  build(SEG_R_CHILD,v);
  return seg[o]=INF;
}
void setv(int o,int v){seg[o]=min(seg[o],v);}
void down(int o){
  if(seg[o]!=INF){
    setv(SEG_L,seg[o]);
    setv(SEG_R,seg[o]);
    seg[o]=INF;
  }
}
void update(int o,int l,int r,int ql,int qr,int v){
  if(ql<=l&&r<=qr) return setv(o,v);
  down(o);
  if(ql<=mid) update(SEG_L_CHILD,ql,qr,v);
  if(qr> mid) update(SEG_R_CHILD,ql,qr,v);
}

void toB(int o,int l,int r){
  if(l==r){
    b[l]=seg[o];
    return ;
  }
  down(o);
  toB(SEG_L_CHILD);
  toB(SEG_R_CHILD);
}

template <class T>
int lowb(const vector<T>& v, const T& x) {return lower_bound(begin(v), end(v), x)-begin(v);}

int main() {
  int n=read();
  int m=read();
  int Q=read();

  unordered_map<int,vector<pair<int,int>> > query; // query[value] = { {l,r} }
  build(SEG_ROOT,m);
  while(Q--){
    int l=read()-1;
    int r=read()-1;
    int x=read();
    update(SEG_ROOT,l,r,x);
    query[x].push_back({l,r});
  }
  toB(SEG_ROOT); // 计算每个A[i]的上界B[i]

  unordered_map<int,vector<int> > index; // index[value] = {index in A}
  index[m]={}; // 在没有x是m但是有些不被限制时
  rep(i,0,n) index[b[i]].push_back(i);

  mint ans = 1;
  for(auto &[x,list]:index){ // 下标 列表
    int sz=size(list);
    if(query[x].empty()) { // 没有存在性要求, 只会发生在 值为M的时候, 而个数为0, 用下面的算会是0 * 0^0=0
      if(sz) ans*=mint(x+1).pow(sz);
      continue;
    }

    int first = sz;
    vector<int> left(sz+1); // left[R] = list[max(L) ... R-1] 之间需要存在一个, 会出现不合法的情况left[R]=R, 但这种会让 sum = 0, 从而后续dp[i], sum 都为0 , 能正确处理
    for(auto [l,r]: query[x]) {
      int s = lowb(list, l);
      int t = lowb(list, r+1); // list[s,t-1] 之间需要存在一个x
      first = min(first, t);
      left[t] = max(left[t], s);
    }

    mint invx = mint(x).inv(); // x非0, 少做除法
    vector<mint> dp(sz);
    mint sum = 0; // sum 记录没有乘倍数的"原始"值 = sum(dp[j..i-1])
    int j=0;
    rep(i,0,sz){
      dp[i]=sum*invx + (i<first?invx:0); // i放x, dp[i][i]=sum dp[i-1][...] + (无限制前缀?x^i:0)
      sum +=dp[i];
      for(;j<left[i+1];j++) sum -= dp[j];
    }
    ans *= sum*mint(x).pow(sz);
  }
  printf("%d\n",ans.val());
  return 0;
}

总结

F

感觉这种 不算太难想出一个时间复杂度内的方法, 但是想不出一个容易编码的题,好难受啊

G

不要读错题,不要读错题,不要读错题,不要读错题,不要读错题

这种穿插着选取的 感觉遇到了三四次了, 没有悟到什么

一个是不操作的转化为处理时删除

然后万物皆可去想一下作为dp的状态维度, 比如这里完全应该想到的下标, 和 值范围

然后这里从上往下想 竟然比从 贡献角度 想DP 感觉更显然

然后通过端点转移(这里的最大值, 按理说,类似的通过首尾下标也有可能类似的

Ex

特殊->一般

这个特殊虽然还比较好想出方案

但如果告诉我这个特殊,也没想到具体的和一般之间的关系

对于限制 合并一部分,DP另一部分: 这里是合并上限要求, DP存在性要求

从而存在性只于Xi有关

然后 如何优雅的让失效状态失效,感觉也是技术活

另一个是 感觉如果在比赛中,即使 上面我全部得到了, 也很容易对上面的推导过程中出现 笔误问题

或者说, 应该向着 Xi相等的方向去对原问题拆分

参考

官方题解