前言

策略不变, 心态放平

看题

\(\rm{T1}\)

构构造造, 不活了

\(\rm{T2}\)

应该比 \(\rm{T1}\) 难

\(\rm{T3}\)

贡贡献献

\(\rm{T4}\)

困难

---

肯定是难得, \(\rm{B}\) 组, 把暴力打好

\(\rm{T1}\)

每次都栽在这上面, 反正就是不要慌, 然后按照时间分配去做
注意策略的选择和心态, 加油吧
不要死磕, 剩的时间不多了直接去暴力
太复杂了一定要换思路

思路

首先题意

求一个长度为 \(n\) 的 \(01\) 串 \(S\) , 使得 \(\displaystyle\sum_{l = 1}^{n} \sum_{r = l}^{n} \left[\lvert S[l : r] \rvert \textrm{ mod } 2 = 1\right ]\)

观察到 \(k = 1, 2\) 这两种情况, 应该是很重要的提示

考虑如果只有一个 \(1\) , 那么怪的区间应当包含这个位置, 组合数学算一下是简单的

考虑如果有两个 \(1\) , 我们可以计算包含其中 \(1\) 个的情况即可
具体怎么计算, 考虑两个 \(1\) 的位置在 \(p_1, p_2\)
你发现总的区间个数为

\[\begin{align*} & p_1 \times (p_2 – p_1) + (p_2 – p_1) \times (n – p_2 + 1) \\ = & (p_2 – p_1) \times [n – (p_2 – p_1) + 1] \\ \end{align*} \]

令 \(p_2 – p_1 = x\) , 容易有 \(1 \leq x < n\)

\[\begin{align*} & x \times (n – x + 1) \end{align*} \]

\(x\) 显然可以取到最大值, 任意输出一种方案即可

那么如果 \(k\) 更大怎么办?
考虑一个区间包含三个 \(1\) 的情况, 我们先打个暴力出来看性质

---

打出来发现非常明显的性质, 都是一堆 \(1\) 加上平均分配的 \(1\)
考虑证明

好吧看起来证明不来, 打了再说, 比较冒险

---

具体的, 注意到答案的性质为

• \(k = 1\) : 直接把 \(1\) 放在中间任意一个位置
• \(k = 2\) : 均分
• \(k > 2\) : 把 \(k – 2\) 个 \(1\) 堆在前面, 然后最后两个 \(1\) 均分, 均分的方式按照 \(k\) 的奇偶性决定

但是怎么输出具体的答案?

实现

#include <bits/stdc++.h>
#define int long long

int n, k;

signed main()
{
    scanf("%lld %lld", &n, &k);
    if (k == 0) {
        printf("0\n");
        for (int i = 1; i <= n; i++) printf("0 ");
    } else if (k == 1) {
        printf("%lld\n", (n / 2 + 1) * (n - n / 2));
        for (int i = 1; i <= n / 2; i++) printf("0 ");
        printf("1 ");
        for (int i = 1; i <= n - n / 2 - 1; i++) printf("0 ");
    } else {
        printf("%lld\n", (n / 2 + 1) * (n - n / 2));
        for (int i = 1; i <= k - 2; i++) printf("1 ");
        n -= k - 2;
        if (k % 2) {
            printf("1 "); for (int i = 2; i <= n / 2; i++) printf("0 ");
            printf("1 "); for (int i = 2; i <= n - n / 2; i++) printf("0 ");
        } else {
            printf("1 "); for (int i = 2; i <= n - n / 2; i++) printf("0 ");
            printf("1 "); for (int i = 2; i <= n / 2; i++) printf("0 ");
        }
    }

    return 0;
}

反正是单测, 最多挂几组

\(\rm{T2}\)

在简单一点的题上浪费了很多时间, 接下来冷静一点, 赶紧拼暴力

思路

转化题意

给你 \(q\) 次修改, 判断给定的 \(m\) 个区间什么时候完全互不相同

我会 \(\mathcal{O} (qm)\) !

你发现区间只有不交或者包含的关系, 关键

• 考虑特殊性质 \(\rm{A}\), 仅包含包含关系且每次大小增加 \(1\) , 也就是说我们随便搞搞就能过
• 考虑特殊性质 \(\rm{B}\) , 不知道有什么用, 意思是包含关系产生的连通块大小不超过 \(40\) ?
• 考虑特殊性质 \(\rm{C}\) , 更不知道有什么用了

考虑出去上个厕所冷静一下

性质 \(\rm{B}\) 怎么做?
你可以考虑把每个位置对应的区间存下来, 然后乱搞搞
发现不会搞

性质 \(\rm{C}\) 怎么做?
你发现如果一个区间长度为 \(size\) , 其被修改 \(size – 1\) 个位置后就符合条件, 考虑继续深入
不敢深入了, 时间不多

实现

框架

• 对于 \(n, m, q \leq 5 \times 10^3\) , 维护每个区间对应的颜色出现次数, 修改就直接对次数修改顺便标记答案

• 对于性质 \(\rm{A}\) , 每次询问只考虑单指针指向的位置, 对于单指针 \(i\) 新开数组表示 \(1 \sim i – 1\) 有哪些数字

\(\rm{T3}\)

这后面的题肯定就是暴力

思路

时间不够, 边打边想, 不在这里写了, 虽然可能导致错误, 但是必须拼一下

总结

不要死磕

然后就是继续每日一练, 没了

这把不知道什么水平, 寄了

---

后记, 实外倒数 \(\textrm{rk 1}\) , 但是要是揪着这个不放也是无敌

来源链接：https://www.cnblogs.com/YzaCsp/p/18676920