Codeforces Round 906

發表於 更新於 分類於 ， Disqus： 文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘
C2(DP)D(智力)E()F()

https://codeforces.com/contest/1889

C2

长n数组上有m个区间[li,ri]

问删除k 个区间后 未被任何区间覆盖的 位置个数最多能有多少

$n \le 2\cdot 10^5$

$m \le 2\cdot 10^5$

$k \le 10$

4s

1024mb

我的思路

题目C1中,k=2, 这样的话

被覆盖0次，则一定贡献

被覆盖1次，则对应区间删除则贡献

被覆盖2次，则对应两个区间删除则贡献

被覆盖> 3次，则一定不贡献

对于被覆盖恰好两次的部分，考虑到如果 区间A和B相交， 则可以看成变为 A并B的新区间 和 A交B的消耗区间, 这样可以继续相互重叠的区间个数 -1， 所以恰好两次的部分的种类数 $\le m$

可以 线段树，for一遍之类的 完成对应的统计，

统计，单色=>个数，色对=>个数

ans = max(max两个单色，色对AB+单色A+单色B)

这样的思路下，C2感觉就很复杂了, 像是颜色集合子集的个数和

题解

dp[i][j] 表示 前i个位置,删除了j个区间,且第i个位置未被覆盖, 的未被覆盖的位置的个数

考虑从位置t到i的贡献转移，令$d_t = $满足$t < l \le i \le r$的区间$[l,r]$个数, 也就是 包含了i，但是未包含t的区间

转移 $dp_{i,j} = 1+\max_{t=0}^{i-1} dp_{t,j-d_t}$

也就是这里其实在让i是不被覆盖的时候，其实也处理了所有左端点 $\le i$ 的区间, 也就是暗含了这个性质

而且 这里+1是 表示t和i之间是相邻 的 未覆盖, 也就是t是上一个未被覆盖

又注意到对于给定i, $d_t$随着$t$减小而非严格单调递增

又$d_t \le k$ 才有用, 而k很小

代码

https://codeforces.com/contest/1889/submission/230305444

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (ll i = (a); i < (ll)(n); i++)
 
const int INF = 0x3f3f3f3f;
const int PWR = 20;
ll read() { ll r; scanf("%lld", &r); return r; }
 
void w() {
  int n = read();
  int m = read();
  int k = read();  // <= 10
  // DP + ST-table
  // dp[0..i][del range][PWR] = empty
  vector dp(n + 1, vector(k + 1, vector<int>(PWR, -INF)));
  dp[0][0][0] = 0;
  vector l2idx(n + 1, vector<int>());  // l => idx
  vector r2idx(n + 1, vector<int>());  // r => idx
 
  vector<array<int, 2>> lr;
  rep(i, 0, m) {
    int l = read();
    int r = read();
    lr.push_back({l, r});
    l2idx[l].push_back(i);
    r2idx[r].push_back(i);
  }
  // in out
  set<pair<int, int>, greater<pair<int, int>>> lidx;
 
  int ans = -INF;
  auto setMax = [&](auto& a, const auto& b) {
    if (b < 0) return;
    a = max(a, b);
    ans = max(ans, a);
  };
 
  auto max_range = [&](int l, int r, int j) {
    // [l,r)
    if (l >= r) return -INF;
    int p = 0;
    for(int diff = r-l;diff > 1;diff/=2) p++;
    return max(dp[l][j][p], dp[r - (1 << p)][j][p]);
  };
 
  rep(i, 1, n + 1) {
    for (auto idx : l2idx[i]) lidx.insert({i, idx});
    auto itr = lidx.begin();
    int lastpos = i;
    rep(d, 0, k + 1) {
      auto calc = [&](int l) {
        if (l >= lastpos ) return ; // [l,lastpos)
        rep(j, d, k + 1) setMax(dp[i][j][0], 1 + max_range(l, lastpos, j - d));
      };
      if (itr == lidx.end()) {
        calc(0);
        break;
      }
      auto [pos, _] = *itr;
      calc(pos);
      lastpos = pos;
      itr++;
    }
 
    rep(d,0,k+1) rep(p, 1, PWR) {
      int ii = i - (1<<p)+ 1;
      if (ii < 0) break;
      dp[ii][d][p] = max(dp[ii][d][p - 1], dp[ii + (1<<(p-1))][d][p - 1]);
    }
 
    for (auto idx : r2idx[i]) {
      int l = lr[idx][0];
      lidx.erase({l, idx});
    }
  }
 
  printf("%d\n", max(ans, 0));
}
 
int main() {
  int t = read();
  while (t--) w();
  return 0;
}

D

给定初始 n个 stacks, 每个有一些 范围在[1,n]内的整数

1
2
3
4
5
6
7
8
9
10
11
function init(pos):
    stacks := 一个包含n个stacks的数组 r[1], r[2], ..., r[n]
    return get(stacks, pos)

function get(stacks, pos):
    if stacks[pos] 为空:
        return pos
    else:
        new_pos := stacks[pos] 栈顶元素
        pop stacks[pos] 栈顶元素
        return get(stacks, new_pos)

n个独立询问，输出 init(1),init(2),…,init(n)的结果

$n \le 10^5$

所有栈里数字保证合法，且总个数 $\le 1e6$

1s

256mb

我的思路

就是 初始n个栈

每次从第pos个栈顶pop()出决定接下来访问哪个栈, 直到访问到空栈

如果对于单独的 init(1), 那就是div2b难度的简单模拟

现在问题是 有n个 init(i)的独立询问, 如果还是暴力就 O(n 总个数) , $10^{11}$肯定时间过不了

而且两个询问之间的相同点感觉很少

i->j->k->p

但如果从j开始，后面可能访问到前面位置i而和i开始就会不同路线了

然后(i->j->...)->i首次再到i

那么这个状态，和从j开始,(j->...->i) 消耗的内容是一样的

只是第一个 将从i开始，而第二个将从j开始

所以state从i开始再次首次到i的 f(state,start=i,next=i) 和 f(state,start=next[i],next=i)的 状态是一样的

有了这个观察, 那么任意点开始暴力

无非两种情况:

  1. 在过程中遇到重复的
  2. 直接结束

对于2来说，路径上的点都返回这个结束点, 而且从链尾倒着向上搜索

那么就是遇到重复点的了

st->...->p->...->p

注意到 中间(p->...->p)是一个环, 所以这些点可以批量 的降低状态, 而环外的(同样可以倒着搜索, 直到发现首个和环重叠的点????)

没啥想法，总觉得虽然这样能批量完成状态转移，但是状态带来的分叉，以及有一部分状态还是无法转移

题解

先考虑简单版本, 如果每个栈只有一个元素，那么就是多个 pseudo trees

每个里面有且只有一个环，而如果进入环则肯定回到进入环的点，如果删去环剩下的就是树

然后对于原来问题也是一样的，只要不停的删环就完了

啊？

其实就是上面 的p->...->p如果是环中的，那么删除环等价

如果是环外的点那么首次 x->....->q->...->p->..->q 也是一定走环的

因为q作为首次进入环的点，说明(x->...->)q的这一段即不在环上，也自身无重复

代码

C++17 498ms, C++20 TLE

https://codeforces.com/contest/1889/submission/230430905

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = (a); i < (int)(n); i++)
int r() { int _; scanf("%d", &_); return _; }
const int N = 100000;
stack<int> s[N + 10];
vector<int> idx;
vector<int> ans;
vector<int> path;
int dfs(int u) {
  auto _ = [&](int x) { for (auto i : path) ans[i] = x; path.clear(); return x;};
  if (ans[u]) return _(ans[u]);
  if (idx[u] != -1) {  // 遇到环 [path[idx[u]] -> ... -> path.back() -> u]
    while (idx[u] != -1 and (int) path.size() >= idx[u]) {  // 删环
      s[path.back()].pop();
      idx[path.back()] = -1;
      path.pop_back();
    }
  }
  idx[u] = path.size();
  path.push_back(u);
  if (s[u].empty()) return _(u);  // 空栈
  return dfs(s[u].top());  // 模拟, 注意可能是环上点,可能被移除了, 所以不要在这里设置ans
}
int main() {
  int n = r();
  rep(i, 1, n + 1) {
    int k = r();
    while (k--) s[i].push(r());
  }
  idx = vector<int>(n + 1, -1);
  ans = vector<int>(n + 1, 0);
  rep(i, 1, n + 1) printf("%d%c", dfs(i), " \n"[i == n]);
  return 0;
}

总结

C2

哇这个dp看着好 怪 啊，虽然i是前缀末尾 且保证了被删除，但是，和区间的l,r看上去很分离， 而且转移关系实际上是靠区间连续性保证从i能截断的！

太久没打，都没往dp那里想

DP完全不会了

D

好有道理，我都观察到了，如果有p->...->p那么里面等价，却没观察到任意与环有关的都可以删除

没有智力

参考

官方题解