[Codeforces]1438E Yurri Can Do Everything 题解
本文最后更新于 69 天前,其中的信息可能已经有所发展或是发生改变。

一道神奇的题目。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1438e/

题解

容易想到固定一端点,统计另一端点的常见套路。

然后想想数据结构维护?发现动态更改异或不好做,不会。

发现左边的值应该挺小的,右边的值应该挺大的,那么可能满足的点应该很少。

$$a_l \oplus a_r = \sum \limits _{i = l+1}^{r-1} a_i$$

给异或找一个上界,有:$a_l + a_r \ge a_l \oplus a_r$

所以原式有:

$$a_l + a_r \ge \sum \limits _{i = l + 1}^{r-1}a_i$$

可以发现,当这个 $r$ 更大的时候,$a_r$ 会被统计到右边的一团里面,从而导致需要的 $a_r$ 大小急剧上升。

稍微变形一下:

$$\sum \limits _{i=l}^r a_i \ge 2 \times \sum \limits _{i=l+1}^{r-1}a_i$$

考虑当 $r$ 更新时,新的 $r$ 的范围要求是怎么样的。

首先假定当前右端点是 $r_1$,新的右端点是 $r_2$,有:

$$\sum \limits _{i=l}^{r_1} a_i \ge 2 \times \sum \limits _{i=l+1}^{r_1-1}a_i$$

$$\sum \limits _{i=l}^{r_2} a_i \ge 2 \times \sum \limits _{i=l+1}^{r_2-1}a_i$$

$$\sum \limits _{i=l+1}^{r_2-1} a_i \ge \sum \limits _{i=l+1}^{r_1-1} a_i + a_{r_1}$$
$$a_l + a_{r_1} \ge \sum \limits _{i=l+1}^{r_1-1}a_i$$
$$\implies a_{r_1} \ge \sum \limits _{i=l+1}^{r_1-1}a_i – a_l$$

$$\sum \limits _{i=l}^{r_2} a_i \ge 2 \times \sum \limits _{i=l+1}^{r_2-1}a_i \ge 2 \times (\sum \limits _{i=l+1}^{r_1-1} a_i + a_{r_1}) \ge 2 \times (\sum \limits _{i=l+1}^{r_1-1} a_i + \sum \limits _{i=l+1}^{r_1-1}a_i – a_l)$$
$$\sum \limits _{i=l}^{r_2} a_i \ge 4 \times \sum \limits _{i=l+1}^{r-1}a_i – 2 \times a_l$$

然后就没救了,这个做法行不通,抄官方题解吧。

看看官方题解,同样利用了异或的性质。

$$a_l \oplus a_r < 2^{highbit + 1}$$
此处 $highbit$ 指 $a_l$ 与 $a_r$ 的最高为 $1$ 的
首先枚举左端点,跳右端点,我们假定 $a_l \ge a_r$ 来统计。等一会翻转数组,再统计一遍,就可以覆盖所有的情况。再去个重就行了。

然后考虑怎么统计。

对于每个 $l$,暴力枚举 $r$ 去检查,保证 $\sum \limits _{i=l+1}^{r-1} a_i < 2^{highbit+1}$ 即可。

这样复杂度是如何保证的?看上去每个 $l$ 都可能跑满 $O(n)$,而导致最后退化为 $O(n^2)$ 的复杂度。
然而使用奇怪的整体分析,可以发现这样复杂度是真的。

对每一个 $highbit$ 单独考虑复杂度。
对于若干个 $a_{b_i}$ 满足其最高位为 $highbit$ 时,其下标序列为 $b_1 < b_2 < \ldots < b_k$

考虑 $l = b_i$ 时的情况,可以发现它的右端点 $r$ 至多走到 $b_{i+2}$ 就会停止,因为两个最高位相加进位了,不再满足 $\sum \limits _{i=l+1}^{r-1} a_i < 2^{highbit+1}$。

那么一共会走过 $\sum \limits _{i = 1}^k (b_{i+2} – b_i)$ 个位置,这个的上界是 $2 \times n$,那么每位的总时间都是线性的。

总复杂度 $O(n \log a_i)$

#include <cstdio>
#include <algorithm>
#include <set>
#include <ctype.h>
using namespace std;
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int n, a[maxn], hb[maxn];
set<pair<int,int> > S;
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 29; j >= 0; --j) if (a[i] & (1 << j)) { hb[i] = j; break; }
    for (int l = 1; l <= n; ++l)
    {
        int maxx = 1 << (hb[l] + 1);
        long long now = a[l + 1];
        for (int r = l + 2; r <= n; ++r)
        {
            if (now >= maxx) break;
            if ((a[l] ^ a[r]) == now) S.insert(make_pair(l, r));
            now += a[r];
        }
    }
    for (int r = n; r > 0; --r)
    {
        int maxx = 1 << (hb[r] + 1);
        long long now = a[r - 1];
        for (int l = r - 2; l > 0; --l)
        {
            if (now >= maxx) break;
            if ((a[l] ^ a[r]) == now) S.insert(make_pair(l, r));
            now += a[l];
        }
    }
    printf("%d\n",S.size());
    return 0;
}
本文标题:[Codeforces]1438E Yurri Can Do Everything 题解
本文作者:Clouder
本文链接: https://www.codein.icu/cf1438e/
转载请标明。

评论

  1. 2月前
    2020-11-16 7:52:53

    Clouder Can Do Everything! orz

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇