Codeforces Round #654 (Div. 2)

        Codeforces Round #654 (Div. 2)题解。

A. Magical Sticks

        当然就是排序后首尾拼接在一起是最优的，注意奇数的时候答案会加一。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 1)
            printf("1\n");
        else {
            if (n & 1) {
                printf("%d\n", n / 2 + 1);
            } else {
                printf("%d\n", n / 2);
            }
        }
    }
    return 0;
}

B. Magical Calendar

        当$k\geq n$时，只有涂一行$n$个这一种可能。对于$k

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n, k; scanf("%d%d", &n, &k); int s = min(n - 1, k); long long ans = 1ll * (1 + s) * (s) / 2; printf("%lld\n", ans + (k >= n)); } return 0; }

C. A Cookie for You

        首先总体不够吃的情况显然是$NO$。对于够吃的情况，可以贪心地考虑。
        二号客人总是会吃较少的那一个，这样很容易将其中一个吃到没有，于是最优策略应该是让一号客人吃较多的一个，调平两种Cookie，然后和二号客人轮流吃。但无论如何，两种Cookie中较少的一个的数量不能少于二号客人的数量。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        long long a, b, n, m;
        scanf("%lld%lld%lld%lld", &a, &b, &n, &m);
        if (n + m > a + b) {
            printf("No\n");
        } else {
            if (m > min(a, b))
                printf("No\n");
            else
                printf("Yes\n");
        }
    }
    return 0;
}

D. Grid-00100

        构造题。
        先求$k/n$，向下取整，然后对于每一行$i$，将$[i,i+k/n)$列涂上$1$（列数超过$n$就折回$1$）。这样可以证明此时结果是$0$，显然是最小的。
        对于剩下的$k\%n$个数，在前$k\%n$行的$1$末尾再补一个$1$，这样可以让行和列的最大最小值之差正好为$1$，最后答案就是$2$，也是最小的。

#include <bits/stdc++.h>
using namespace std;
int op[305][305], n, k, r[305], c[305], sv[305];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) op[i][j] = 0;
        }
        for (int i = 1; i <= n; i++) {
            if (i <= k % n) {
                for (int j = i; j <= i + k / n; j++) op[i][j > n ? j - n : j] = 1;
            } else {
                for (int j = i; j < i + k / n; j++) op[i][j > n ? j - n : j] = 1;
            }
        }
        for (int i = 1; i <= n; i++) r[i] = c[i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (c[j] < sv[j] && r[i] < sv[i]) op[i][j] = 1, ++c[j], ++r[i];
            }
        }
        for (int i = 1; i <= n; i++) {
            r[i] = 0;
            for (int j = 1; j <= n; j++) r[i] += op[i][j];
        }
        for (int i = 1; i <= n; i++) {
            c[i] = 0;
            for (int j = 1; j <= n; j++) c[i] += op[j][i];
        }
        printf("%d\n", (MM(r) - mm(r)) * (MM(r) - mm(r)) + (MM(c) - mm(c)) * (MM(c) - mm(c)));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) printf("%d", op[i][j]);
            printf("\n");
        }
    }
    return 0;
}

E. Asterism

        假设$a$数组中不小于$i$的数有$s(i)$个，那么有：

$$f(x)=\prod_{x}^{x+n-1}(s(i)-(i-x))=\prod_{x}^{x+n-1}(x-(i-s(i)))$$

        由于$p$是一个质数，要想使得$p$不能整除$f(x)$，只能不整除其每一个因子，即对于$x\leq i\leq x+n-1$，都有：

$$i-s(i)\not\equiv x\pmod p$$

        考虑$x$的取值范围。若记$a$数组最大值为$u$，那么$x$的范围应为$u-n\leq x\leq u$。否则$f(x)$要么为$0$要么为$n!$，它们显然都是$p$的倍数。
        根据这个$x$的范围预处理出$i-s(i)$对$p$的模数，然后枚举$x$，$O(n)$或者$O(nlogn)$地判断$x$的合法性。

#include <bits/stdc++.h>
using namespace std;
int n, p, a[100005], b[100005], num[100005];
vector<int> ansv;
int main()
{
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    sort(a + 1, a + n + 1);
    int maxNum = *max_element(a + 1, a + n + 1), ss = 0;
    for (int i = maxNum - n; i <= maxNum + n; i++) {
        while (ss + 1 <= n && a[ss + 1] <= i) ++ss;
        b[i - (maxNum - n) + 1] = ((i - ss) % p + p) % p;
    }
    for (int i = maxNum - n; i <= maxNum - 1; i++) ++num[b[i - (maxNum - n) + 1]];
    for (int i = maxNum - n; i <= maxNum; i++) {
        if (i > 0) {
            if (num[i % p] == 0) ansv.push_back(i);
        }
        --num[b[i - (maxNum - n) + 1]], ++num[b[i + n - (maxNum - n) + 1]];
    }
    printf("%d\n", ansv.size());
    for (int i = 0; i < ansv.size(); i++) printf("%d ", ansv[i]);
    return 0;
}

F. Raging Thunder

        数据结构（线段树）。
        先考虑不修改，只求和如何操作。线段树上每一个节点维护若干个值，分别是：

• len。区间长度
• ll。左起连续$<$的数量
• rr。右起连续$>$的数量
• lr。左起连续$>$加上之后连续的$<$的总数量
• rl。右起连续$<$加上之前连续的$>$的总数量
• ans。答案

        根据以上信息可以合并两个子区间并更新答案。
        再考虑如何翻转区间。考虑到每一段自区间只有两种状态，不妨一开始就处理好每一个区间节点的两种状态，当需要翻转时直接交换这两个状态，并打上懒标记。这里注意使用这种方法时在合并区间时，需要同时更新两种状态的节点。

#include <bits/stdc++.h>
#define N 500005
using namespace std;
struct Node
{
    int len, ans, lz, rr, ll, rl, lr;
} tr[2][N << 2];
Node operator+(const Node& a, const Node& b)
{
    Node s;
    s.lz = 0;
    s.len = a.len + b.len;
    s.ans = max(a.ans, b.ans);
    s.ans = max(s.ans, max(a.rl + b.ll, b.lr + a.rr));
    s.ans = max(s.ans, a.rr + b.ll);
    if (a.ll == a.len)
        s.ll = a.len + b.ll;
    else
        s.ll = a.ll;
    if (b.rr == b.len)
        s.rr = b.len + a.rr;
    else
        s.rr = b.rr;
    if (a.lr == a.len) {
        if (a.rr != a.len)
            s.lr = a.len + b.ll;
        else
            s.lr = a.len + max(b.lr, b.ll);
    } else
        s.lr = a.lr;
    if (b.rl == b.len) {
        if (b.ll != b.len)
            s.rl = b.len + a.rr;
        else
            s.rl = b.len + max(a.rl, a.rr);
    } else
        s.rl = b.rl;
    return s;
}
int n, m;
char s[N];
inline void pud(int k)
{
    if (tr[0][k].lz == 0) return;
    swap(tr[0][k << 1], tr[1][k << 1]), tr[0][k << 1].lz = tr[1][k << 1].lz ^ 1;
    swap(tr[0][k << 1 | 1], tr[1][k << 1 | 1]), tr[0][k << 1 | 1].lz = tr[1][k << 1 | 1].lz ^ 1;
    tr[0][k].lz = 0;
}
inline void upd(int id, int x)
{
    int lz = tr[id][x].lz;
    tr[id][x] = tr[id][x << 1] + tr[id][x << 1 | 1];
    tr[id][x].lz = lz;
}
void build(int l, int r, int id, int k)
{
    if (l == r) {
        if (s[l] == '<') {
            tr[id][k].len = 1, tr[id][k].ans = 1;
            tr[id][k].ll = 1, tr[id][k].rr = 0;
            tr[id][k].lr = 0, tr[id][k].rl = 1;
        } else {
            tr[id][k].len = 1, tr[id][k].ans = 1;
            tr[id][k].ll = 0, tr[id][k].rr = 1;
            tr[id][k].lr = 1, tr[id][k].rl = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, id, k << 1), build(mid + 1, r, id, k << 1 | 1), upd(id, k);
}
Node query(int l, int r, int L = 1, int R = n, int k = 1)
{
    if (L >= l && R <= r) return tr[0][k];
    pud(k);
    int mid = (L + R) >> 1;
    if (r <= mid) return query(l, r, L, mid, k << 1);
    if (l > mid) return query(l, r, mid + 1, R, k << 1 | 1);
    Node a = query(l, mid, L, mid, k << 1);
    Node b = query(mid + 1, r, mid + 1, R, k << 1 | 1);
    return a + b;
}
void modify(int l, int r, int L = 1, int R = n, int k = 1)
{
    if (L >= l && R <= r) {
        swap(tr[0][k], tr[1][k]), tr[0][k].lz = tr[1][k].lz ^ 1;
        return;
    }
    pud(k);
    int mid = (L + R) >> 1;
    if (r <= mid)
        modify(l, r, L, mid, k << 1);
    else if (l > mid)
        modify(l, r, mid + 1, R, k << 1 | 1);
    else
        modify(l, mid, L, mid, k << 1), modify(mid + 1, r, mid + 1, R, k << 1 | 1);
    upd(0, k), upd(1, k);
}
int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    build(1, n, 0, 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '<')
            s[i] = '>';
        else
            s[i] = '<';
    }
    build(1, n, 1, 1);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        modify(l, r);
        printf("%d\n", query(l, r).ans);
    }
    return 0;
}