CF1815

cf1815 · 浏览次数 : 5

小编点评

**A. Ian and Array Sorting 秒切题** 考虑将前 \\(n - 1\\) 个数变成一样的一个数 \\(x\\)。可以发现,如果 \\(x\\) 是偶数,则需要分类讨论,否则就按照先前的思路。 **C. Between 构造好题** 考虑包含可以形成依赖。可以形成一张图,从 1 开始 BFS 对其分层,可以发现,第 \\(i\\) 层最多可以放 \\(i\\) 个(包含依赖多套一个)。 **D. XOR Counting 打表好题** * 在 \\(m = 1\\) 的时候答案就是 \\(n\\)。 * 在 \\(m \\gt 3\\) 的时候小小打表,可以发现答案为 \\(\\lceil \\frac n2 \\rceil \\times (\\lfloor \\frac n2 \\rfloor + 1)\\)。 * 证明:在 \\(m \\gt 3\\) 的时候,\\([x, \\frac {n-x}2, \\frac {n-x}2, 0, 0, \\dots]\\) 可以恰好凑出 \\(x\\),所以所有与 \\(n\\) 奇偶性相同的 \\(x\\)(此时 \\(n-x\\) 是偶数)的个数不会变,而和变为原本的两倍再加上个数。

正文

CF1815

Div. 1 确实难,Virtual Contest 上只完成了两道题,想出来了三道题。

A. Ian and Array Sorting

秒切题……考虑将前 \(n - 1\) 个数变成一样的一个数 \(x\)。显然可以完成。

然而考虑此时最后一个数。如果 \(\ge x\),那么是 \(\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}\),如果 \(\lt x\),要分类讨论:

  • 如果前面有奇数个,是 \(\texttt{\colorbox{#E74C3C}{\textcolor{white}{WA}}}\)

  • 反之,则是 \(\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}\)

提交:Submission #211291004 - Codeforces

B. Sum Graph

傻逼交互

好呀好呀,傻逼交互体。想出来了思路,但是就是没有写出来。

考虑 +\(n + 1, n + 2\)。那么整个图会形成一条链。

static int perm[N]; int l = 1, r = n;
for (int i = 1; i <= n; ++i) {
    perm[i] = (i & 1) ? l++ : r--;
}

于是我们可以在 \(n - 1\) 次以内找到链的一端,然后就可以再来 \(n - 1\) 次找到可能的排列。

由于我们可能是找到的两端,所以有两种排列方法。

输出即可。

提交:Submission #211296415 - Codeforces

进阶:参考 https://codeforces.com/blog/entry/114847?#comment-1021812 以及 Editorial of Codeforces Round #865 - Codeforces,可以把次数减少到 \(n + \lfloor \frac n2 \rfloor + 2\) 次询问。

C. Between

构造好题

考虑包含可以形成依赖。

于是可以形成一张图。

我们从 1 开始 BFS 对其分层,可以发现,第 \(i\) 层最多可以放 \(i\) 个(包含依赖多套一个)。

那么考虑如何构造合法方案。

我的方法是每一次,按照 BFS 逆序遍历很多遍,每一次遍历到,如果还有没放的则放一个,否则略过。(好像官方题解就是这样?看不懂)

考虑正确性:按照逆序遍历保证出现次数少的在中间,保证不同层之间的依赖关系;每次放一个保证出现次数相同的交替出现,这样就保证了层内的依赖关系无论如何一定满足(互相依赖也没关系)。

提交:Submission #211298131 - Codeforces

D. XOR Counting

打表好题

\(m = 1\) 的时候答案就是 \(n\)

\(m \gt 3\) 的时候小小打表,可以发现答案为 \(\lceil \frac n2 \rceil \times (\lfloor \frac n2 \rfloor + 1)\)

证明:在 \(m \gt 3\) 的时候,\([x, \frac {n-x}2, \frac {n-x}2, 0, 0, \dots]\) 可以恰好凑出 \(x\),所以所有与 \(n\) 奇偶性相同的 \(x\)(此时 \(n-x\) 为偶数,\(\frac {n-x}2\) 为整数)都可以被凑出。

然后我们发现,加法和异或得到的奇偶性是一样的,并且有 \(a \otimes b \le a + b\),意味着我们只能凑 \(\le n\) 并且与 \(n\) 奇偶性相同的数。

综合两条,我们便可以得出,所有可能凑出的数就是 \(\le n\) 且与 \(n\) 奇偶性相同的数。

推一下公式就是上面的了。

于是问题就只剩下了 \(m = 2\) 的时候。

我们考虑一个 DP,我们记 \(f(n)\) 表示所有可能的异或和的和,\(g(n)\) 表示可能的个数。然后稍微分类讨论一下:

  • 如果 \(n\) 是奇数,我们不妨假设 \(n = a_1 + a_2\),其中 \(a_1\) 为偶数,\(a_2\) 为奇数。设 \(a_1' = \frac {a_1}2, a_2' = \frac {a_2 - 1}2\)。我们可以看出:\(a_1' + a_2' = \frac {n-1}2\) 以及 \(a_1 \otimes a_2 = 2 \times (a_1' \otimes a_2')+1\)。此时个数不会变,而和变为原本的两倍再加上个数。也就是 \(g(n) = g(\frac {n-1}2)\) 以及 \(f(n) = 2f(\frac {n-1}2) + g(\frac {n-1}2)\)

  • 如果 \(n\) 是偶数,那么我们又要分两类讨论:

    • \(n = a_1 + a_2\),其中两者都是偶数,那么类似的,\(a_1' + a_2' = \frac n2\)\(a_1 \otimes a_2 = 2 \times (a_1' \otimes a_2')\)

    • 如果都是奇数,有 \(a_1' + a_2' = \frac n2 - 1\) 以及 \(a_1 \otimes a_2 = 2 \times (a_1' \otimes a_2')\)

    • 因此,我们可以知道 \(f(n) = 2 \times f(\frac n2) + 2 \times f(\frac n2 - 1)\),以及 \(g(n) = g(\frac n2) + g(\frac n2 - 1)\)

FAKE: 于是我们可以得出递推复杂度 \(T(n) = T(\frac n2) + 1\),得出为 \(O(\log n)\)

依据SMB,复杂度似乎不是这样的,但是题解是这么给的,或许是有一些神秘的分析,或者是加了记忆化,所以复杂度是这样的。

其实完全可以用记忆化……快一点吧。

提交:https://codeforces.com/contest/1815/submission/211297560

E. Bosco and Particle

性质好题

性质:

  1. 循环多次 \(=\) 循环一次

  2. \(a_i\) 表示实际上从上面进入这个序列的次数,\(b_i\) 表示实际上向下面出去这个序列的次数。我们把第 \(i\) 个序列单独提出来,类似的定义 \(a_i'\)\(b_i'\)。可以发现,\(\exist k \implies a_i = ka_i', b_i = kb_i'\),也就是有 \(\frac {a_i}{b_i} = \frac {a_i'}{b_i'}\)

  3. \(a_i = b_{i-1}\)

  4. \(f_i = a_{i + 1}\)\(f_0 = a_1\),于是有 \(f_k = \prod_{i = 1}^k \frac {b_i}{a_i} f_0\)

  5. 需要保证 \(\forall k\),$ f_k$ 为整数。

于是就可以写出来啦!!!(不是

提交:Submission #211323975 - Codeforces

竟然比 C++ 快,不可思议

与CF1815相似的内容: