Codeforces Round 1008 (Div. 1)

發表於 更新於 分類於 ， Disqus： 文章字數： 3k 所需閱讀時間 ≈ 10 分鐘
D(字典序,子序列)E(奇偶)F()G()

https://codeforces.com/contest/2077

D Maximum Polygon

评分3100

最大多边形

3s

256mb

给定一个长度为 $n$(2e5) 的数组 $a$，找出字典序最大的子序列(不要求连续)$s$，使得 $s$ 可以作为多边形的边长。

回忆一下，$s$ 可以作为多边形的边长当且仅当 $|s| \geq 3$ 且满足以下条件：

$2 \cdot \max(s_1, s_2, \ldots, s_{|s|}) < s_1 + s_2 + \ldots + s_{|s|}.$

如果不存在这样的子序列 $s$，输出 $-1$。

$s_i$ (1e9)

输出具体选的 值（不是下标）

我的思路

那么就是无序的，先sort一下?

如果 一个方案可以，那么在不改变最大的值的情况下 剩余全部向右移动，依然可以

所以每个方案总有一个 连续方案, 这样对每个值可以贪心长度

但是 这一切都 没有满足 字典序最大，也就是 这里不要要更长，而是要字典序大

那么字典序大的，想法是 贪心首个位置，从大到小，只要合法那么就钦定了首个，然后再考虑更多，先考虑如何合法

1
2
3
4
5
6
7
.................
        i
        从这作为选择的第一个，那么它后面不大于它的都要选，如果满足上面不等式则合法, 在这种情况下，s[i]是不等式左边出现的

        如果选了比它大的某个j
             j
        那么 所有i后面，不大于s[j]的都要选，如果能合法就好，这样的过程是 按照i后面的比s[i]大的，值从小到大的尝试，可以O(len) 这样总的时间复杂度已经来到了n^2

如何 一边控制 首位 一边 控制选中的最大值 还要在 n^2内

题解

提示1: 考虑如果固定了最大值 或者 序列的第一个值 如何找方案

提示2: 足够长 (which is not that long) 的数组一定是多边形边

如果 最大钦定是x, 那么要求 和 > 2x

s初始为空

for i in range(size(a)) and a_i <= x:

  • if s非空 and a_i > s.back()
    • while s.pop() 之后 后续的和最大能否超过 2x
      • 换句话说bool(s[:-1] + sum(a[i…]) > 2x), 其中 a[i…] <= x
      • 那么 s.pop()
  • s.push(a i)

这样 我们可以得到 x的最大元素是x，且s是字典序最大的

  • 其中 最大元素x 是通过 上面步骤保证的，首先每个<= x都会被push，而被移除时 需要 后面有比它大 且 满足和的要求的才行
  • 而字典序是最大的
    • 如果 方案找到的从位置i开始更小，存在更大的方案 从位置j开始
    • j < i,不可能 因为上述过程j一定被放入后又剔除，s中的下标顺序不会变，那么j 只能被 (j,i)之间比a[j]更大的踢除，而这个更大的也不存在，这个过程是单调递增离散的，不能全部都不存在
    • j > i, s: [i...k]j, 如果k < j,那么k会被消除，如果$k > j$, 用k替代j 变成 和上面一样的 离散向i逼近的子问题
    • 这个过程我真的自己没想出来啊！！！！，这应该算字典序构造的某个技巧吧？？

然后 hint2 ，哇这个很有道理，这个应该要自己能想到的（虽然 没有想到上面的，这个也没用）

一个排序向量 v 的最大可能大小是多少，使得不存在 v 的任何子序列可以形成有效多边形的边？

  • 哦 好有道理第二点，因为如果 选的数组的子数组都不是边长，那么我们把它们排序，有每个更大的需要比前面和都大，这个增长是2倍的概念，所以32的里面总能找到 显然 log 级别的长度L
  • 这说明了 如果我们把原序列中 最大的 这么多元素 选出来得到数组b，那么数组b总是 有合法子序列的！！，从而 我们的max候选只有log级别
  • for max 候选，暴力上面的hint1方法

下面分析相等的时候，上面在 选最大L个的时候，重复的也统计，但是在for max候选的时候我们不用for位置，而是for值，这样 能保证for的量 <= L的

代码

https://codeforces.com/contest/2077/submission/316452899

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;)
ll read() { ll r;scanf("%lld", &r);return r; }

void w() {
  ll n = read();
  vector<ll> ans;
  vector<ll> a(n);
  for (auto& v : a)v = read();
  vector<ll> sa = a; // sorted a
  sort(begin(sa), end(sa));
  rep(i, 0, min(60ll, n)) { // 60个保证远大于 log 级别
    ll x = sa[sa.size() - 1 - i]; // 钦定 x
    vector<ll> cur;
    vector<ll> suf(n, 0); // <=x 的后缀和
    per(i, 0, n) suf[i] = (i + 1 < n ? suf[i + 1] : 0) + (a[i] <= x ? a[i] : 0);
    if (suf[0] <= 2 * x) continue; // 整个不满足
    ll sumcur = 0;
    rep(i, 0, n) if (a[i] <= x) {
      while (!cur.empty() and cur.back() < a[i] and sumcur - cur.back() + suf[i] > 2 * x) { // 比队尾大 且 存在方案
        sumcur -= cur.back();
        cur.pop_back();
      }
      cur.push_back(a[i]);
      sumcur += a[i];
    }
    ans = max(ans, cur); // wow std::max支持比较
  }
  if (ans.empty()) {
    printf("-1\n");
    return;
  }
  printf("%d\n", (int)size(ans));
  for (auto v : ans) printf("%d ", v);
  printf("\n");
  return;
}

int main() {
  int t = read();
  while (t--) w();
  return 0;
}

E Another Folding Strip

2s

256mb

m长条带 初始0，你可以沿着两个格子之间折叠 任意多次（0次也行

目标bi

然后 在折叠后 选一个位置滴黑色颜料，重叠的位置全部+1，展开纸带

f(b)=最少的次数使得全0的 变为b

给定 a[n(2e5)](1e9)

求 $\sum f(a[l\cdots r]) \mod 998’244’353$

我的思路

每次折叠 本质上是让奇偶交替

也就是每次可以选 奇偶交替，递增的下标，全部+1

那么 反过来，从b变到0，就是每次选奇偶交替递增的下标，全部-1

感觉很有贪心的冲动，如果当前全部>0,那么可以全部-1

如果位置 i=0, 那么意味着 i-1和i+1不能在一次中同时选中，这时，删除i，合并i-1和i+1

类似的想法，即使i!=0 如果一次中没有选择i,那么 也是i-1和i+1不能同时选中

所以想法是，全部-=min

完成合并，全部-=min

如此循环，这样的 合并过程需要加速

ordered set: {值,下标}, 维护最小值

off = set 中全部的减去的偏移量来实现批量减

每次有0 会删除一个合并两个 => i 并查集或者lower_bound {下标} 都可以，这样 总次数=O(n)

但这样 只能解决单个数组，效率对于原题目要算所有连续子数组的代价还是不够

对于首次全部 减去最小 可以变成 (1+n)n/2 个的贡献

但是 当构成 a b 0 c d时， 如果只含b，那么是 a b的形状，如果同时含有b,c那么是 a b+c的形状，没法单分支的划分

  • 这里分类讨论是 l..r 是否同时选b,c，如果有
  • f(a,b+c, d) 这里还需要里面 一定选中了 b+c 否则和下面的统计重复了
  • 如果没有 f(a,b) + f(c, d)

这里另一个分类是 控制区间 l,r的可选范围

题解

也是 首先看到，某次的操作选的下标按增序排序，那么一定是奇偶间隔

考虑如何计算 $f(a[1..n])$

啊 考虑把数组变为 $b_i=(-1)^i a_i$

那么 操作后对于任意$l,r$有 $|\sum_{i=l}^r (b_i’-b_i)|\le 1$, 哇 ！！道理的确是的

因此，每次操作 任意范围的 $|\sum b_i|$最多下降1

$f(a[1..n])$有了操作的下界

for i = 1..n

  • if bi==0 continue
  • if s is empty:
    • s.append(i)
  • elif i%2 != s.back()%2:
    • s.append(i)

对于s中 对于所有l,r找到最大的 $|\sum_{l}^r b_i|$, 我们上面的操作能让这个每个最大的 $|\sum_{l}^r b_i|$ 的每次下降1

  • 因为可能有多个最大的
  • 如果能证明任何最大的一次操作后会下降1，那么每个最大的在一次操作后依然是最大的。
  • 所以只需要证明任何最大的经过这个操作都会下降1即可

证明:

  • 首先 如果 l,r 位置有0，那么选择一定不会选择对应位置，可以缩小范围到一个非零
  • 如果 最大的，绝对值内部是+, 那么l,r处都是+,对称的绝对值内部是-，则l,r处都是-，因为如果符号不同，那么去掉那个不同号的会更大
  • 那么接下来选择 我们可以知道 和 绝对值内同号的一定被选了比异号的多一次，
    • 证明：奇偶间隔，所以 如果同样次数，要么首部不同号，要么尾部不同号，说明l,r至少可以补充多选一个
    • r的情况是根据选择顺序自然的补充多选
    • l的情况是:
      • i +l (被选择的) +r
      • 如果l不被选，那么说明l的左侧最近的非零被选的某个i处是 和l同号的，这种情况下， [i..r]会有更大绝对值，所以l左侧最近的不能同号，所以l一定被选

至此 我们证明了

  1. 对于给定串a, 它全部变为0的下界是 $\max_{l,r}|\sum_l^r b_i|$
  2. 上述方法保证这个下界永远可达
  3. 综上 $f(a)=\max_{l,r}|\sum_l^r b_i|$

下面问题变成了

  • $\sum_{l}^r f(a[l..r])$
  • 区间和 = 前缀和的差
    • max前缀和的差 = 前缀和最大值-前缀和最小值
    • 这里题解没有偏移个l吗？
    • 按理说 [l…r]之前的区间和 应该是 r0 in [l..r], l1 in [l-1…r0-1], 也就是 [l..r] - [l-1..r-1]的对应，然后有绝对值，这里可以反过来，那么 补充的话会有 l-1 x l-1,r x r 这两个都是0 不影响一定为正的max，所以应该也是 [l-1...r]的max和min的差吧!?

那么

$\text{ans}=\sum_{l=1}^n\sum_{r=l}^n (\max \mathrm{pre}_b[l-1..r]-\min \mathrm{pre}_b[l-1..r])$

  • 可以分开统计

常见的为了解决 同值冲突，同值时比较一下下标（不影响结果）

  • pl[ v作为最大的 ]pr
  • 有候选区，那么贡献是 v * ((pv-pl)*(pr-pv)-1) 长度不能为1，且覆盖v

综上 $O(n)$可做

然后 发现 标程里真的就sz = ((p - l) * (r - p)) % MOD 也是对的，没有-1

我反正从逻辑上没有懂 它为什么前缀和那样，但我们能证明 这里sz多任何常数 不会对结果有影响，因为其实这里多出来的就是 max 长度1的情况 - min长度1的情况，那刚好抵消

代码

https://codeforces.com/contest/2077/submission/316481643

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read() { ll r;scanf("%lld", &r);return r; }

void w() {
  ll n = read();
  vector<ll> c(n + 1, 0);
  rep(i, 0, n) {
    ll v = read();
    c[i + 1] = c[i] + (i % 2 ? v : -v);
  }
  auto _ = [&](vector<ll> d) {
    set<ll> s; // s来维护更大的左右范围，也可以 递增队列做都行 反正不会TLE
    s.insert(-1); // -1[0.....n]n+1
    s.insert(n + 1);
    vector<pair<ll, ll>> cii; // c[i], i
    ll sum = 0;
    rep(i, 0, n + 1) cii.push_back({ c[i],i });
    sort(rbegin(cii), rend(cii)); // 从大到小
    for (auto [v, p] : cii) {
      s.insert(p);
      ll l = *(prev(s.lower_bound(p)));
      ll r = *(next(s.lower_bound(p)));
      ll sz = ((p - l) * (r - p) - 1) % MOD;
      (sum += (v%MOD) * sz % MOD) %= MOD;
    }
    return sum;
    };
  ll ans = _(c);
  rep(i, 0, n + 1) c[i] = -c[i]; // 要求 - min(ci) = max(-ci)
  printf("%lld\n", (ans + MOD + _(c) + MOD) % MOD);
  return;
}

int main() {
  int t = read();
  while (t--) w();
  return 0;
}

F

G

小总结

D 3100

E 2700

  • 赛时读错题了不应该，以为只能折一次
  • 但这个 -1 的转化是有点神奇了, 想不出这个