概述

虽说是 Div2，但也不是特别简单，E 还是不太裸的。。

A

Description

Pasha 有一个正整数长度的木棍 $n$​。他想要完成三次切割以获得四个部分。每个部分必须有一些正整数长度，这些长度的总和显然是 $n$。

Pasha 喜欢长方形但讨厌正方形，所以他想知道，有多少种方法可以将棍子分成四个部分，这样就可以用这些部分形成一个矩形，但不可能形成正方形。

你的任务是帮助 Pasha 并计算这些方式的数量。

Solution

看代码。

Code

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int n;

int main()
{
    cin >> n;
    cout << (n % 2 ? 0 : (n / 2 - 1) / 2) << endl;
}

B

Description

Vika 有 $n$ 桶油漆，第 $i$ 桶有 $a_i$ 升油漆。

Vika 有一张无限长的长方形纸条，她将长方形纸条分成了无限个正方形，她将按照以下规则对正方形涂色。

  • 涂一个正方形需要 $1$ 升油漆。
  • 第一个正方形可以用第任意第 $i$ 桶油漆。
  • 若第 $k$ 个正方形用了第 $x$ 桶油漆，则第 $k+1$ 个正方形将用第 $x+1$ 桶油漆，若 $x=n$，则第 $k+1$ 个正方形将用第 $1$ 桶油漆。若 $a_x = 0$ 则停止涂色。

求 Vika 最多可以涂多少个正方形。

Solution

设最小的元素是 $x$，很显然答案的下界是 $nx$。

把所有元素都减去 $x$ 之后，我们需要找到一段所有元素都大于零的最长连续段，把这部分也加进答案里即可。

这个最长连续段要么就是连续的一段，要么是头尾相接的一段，都模拟一下就好了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;

int a[maxn], n;

long long ans = 0;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int pos = 0;
    a[0] = 2e9;
    for (int i = 1; i <= n; i++)
        if (a[i] <= a[pos])
            pos = i;
    int lpos = 1;
    for (int i = 1; i <= n; i++)
        if (a[i] == a[pos])
        {
            lpos = i;
            break;
        }
    int lst = lpos;
    int sum = lpos + n - pos - 1;
    for (int i = lpos + 1; i <= n; i++)
    {
        if (a[i] != a[pos])
            continue;
        sum = std::max(sum, i - lst - 1);  
        lst = i;
    }
    cout << (long long)a[pos] * n + sum << endl;
}

C

Description

给定 $k$，求 $2^k$ 个 $2^k$ 维向量满足每个向量的坐标表示中任意一维都为 $1$ 或 $-1$，且这些向量两两点积为 $0$。

$0\leq k\leq 9$。

Solution

这个题一看就比较找规律，再联想分治…

先构造一个如下的矩阵（$1$ 表示 $1$，$0$ 表示 $-1$）。

11
10

这是 $k=1$ 的情况，很显然满足要求。

怎么从它扩展到 $k=2$ 呢？可以构造一个如下的矩阵：

1111
1010
1100
1001

就是把 $k=1$​ 的矩阵在四个地方复制一份，再把右下角的矩阵取反就行。

然后重复以上操作就构造完了。

证明一下：首先左半部分在原来两个矩阵内部内积是 $0$，取反之后仍然在内部内积是 $0$，而两个矩阵相同的行内积在右面正好会抵消，于是这么构造就是对的。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1 << 10;

int a[maxn][maxn];

void solve(int x, int y, int len, int opt)
{
    if (len == 1)
    {
        a[x][y] = opt;
        return;
    }
    int p = len / 2;
    solve(x, y, p, opt), solve(x, y + p, p, opt), solve(x + p, y, p, opt), solve(x + p, y + p, p, opt ^ 1);
}

int k;

int main()
{
    cin >> k;
    solve(1, 1, 1 << k, 1);
    for (int i = 1; i <= (1 << k); i++, cout << endl)
        for (int j = 1; j <= (1 << k); j++)
            cout << (a[i][j] ? '+' : '*');  
}

D

Description

有一个网格，给出 $n$ 条线段，每条线段覆盖一些网格，问被覆盖的网格的面积并是多少。

$n\leq10000$。

Solution

太扫描线了！！！

把题目的网格图转成平面直角坐标系，线段转成点，然后扫描线即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <utility>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;
typedef long long ll;

struct node
{
    int x1, x2, y, opt;
    bool operator<(const node &b) const { return y < b.y; }
} a[maxn];
int p[maxn], tot, n, cnt;

struct Tree
{
    struct Node
    {
        int l, r;
        ll sum, lzy;
    } t[maxn << 3];
    inline int ls(int x) { return x * 2; }
    inline int rs(int x) { return x * 2 + 1; }
    inline void push_up(int k) { t[k].sum = t[k].lzy > 0 ? p[t[k].r + 1] - p[t[k].l] : t[ls(k)].sum + t[rs(k)].sum; }
    void build(int l, int r, int k)
    {
        t[k].l = l, t[k].r = r;
        if (l == r)
        {
            t[k].sum = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, ls(k)), build(mid + 1, r, rs(k));
        push_up(k);
    }
    void modify(int x, int y, int v, int k)
    {
        if (p[t[k].r + 1] <= x || p[t[k].l] >= y)
            return;
        if (p[t[k].r + 1] <= y && p[t[k].l] >= x)
        {
            t[k].lzy += v, push_up(k);
            return;
        }
        int mid = floor((x + y) / 2.0); // 注意，坐标有负数，需要向下取整而不是向零取整
        if (x <= mid)
            modify(x, y, v, ls(k));
        if (y > mid)
            modify(x, y, v, rs(k));
        push_up(k);
    }
} t;

signed main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (y1 == y2)
        {
            if (x1 > x2)
                std::swap(x1, x2);
            x2++, y2++;
            a[++tot] = {x1, x2, y1, 1}, a[++tot] = {x1, x2, y2, -1};
            p[++cnt] = x1, p[++cnt] = x2;
        }
        else
        {
            if (y1 > y2)
                std::swap(y1, y2);
            x2++, y2++;
            a[++tot] = {x1, x2, y1, 1}, a[++tot] = {x1, x2, y2, -1};
            p[++cnt] = x1, p[++cnt] = x2;
        }
    }
    std::sort(p + 1, p + 1 + cnt), std::sort(a + 1, a + tot + 1);
    cnt = std::unique(p + 1, p + 1 + cnt) - p - 1;
    t.build(1, cnt - 1, 1);
    ll ans = 0, lst = a[1].y; 
    for (int i = 1; i <= tot; i++)
    {
        ans += (a[i].y - lst) * t.t[1].sum;
        t.modify(a[i].x1, a[i].x2, a[i].opt, 1);
        lst = a[i].y;
    }
    cout << ans << endl;
}

E

Description

给定一个长度为 $n$​​（$n<200000$​）的字符串 $s$，有两种指令：

  1. 将区间 $[L,R]$​ 内的字符变为 $ch$；

  2. 给定长度为 $k$​​​​​（$1\leq k\leq10$​​​​）的字符串排列 $t$​​​，向 $s$​​ 串中添加字符，使得 $s$​ 以 $t$ 为模式循环，求最少的循环次数。

最多 $20000$ 条指令。

字符集大小为 $k$。

Solution

首先有一个结论：当两个相邻字符在字符串排列中前后顺序相同，这两个一定在同一个循环节内（因为不在的话会导致循环节增加一个）。

这样对于一次询问，一个很暴力的想法是：把字符串遍历一遍，看相邻字符在排列中的顺序。

注意到 $k$ 很小，我们尝试把询问的复杂度降到和 $k$ 有关。

发现我们只需要相邻字符的信息，而且这个信息是个数，那我们可以直接把每两种字符的相邻次数存下来询问时 $O(k^2)$ 枚举一遍字符集，把顺序不同的加进答案即可。

询问解决了，下一步是修改。

我们需要区间赋值，整体查询，且维护信息可以合并，那直接选择线段树，每个结点维护这段区间中上文的数组，以及最左元素、最右元素方便合并。

时间复杂度 $O(nk^2+mk^2\log n)$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <utility>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 2e5 + 10, maxk = 11;

char s[maxn];
int n, m, k;

struct Tree
{
    static const int maxn = ::maxn * 4;
    int cnt[maxn][maxk][maxk], lch[maxn], rch[maxn], lzy[maxn];
    inline int ls(int x) { return x * 2; }
    inline int rs(int x) { return x * 2 + 1; }
    void push_up(int x)
    {
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++)
                cnt[x][i][j] = cnt[ls(x)][i][j] + cnt[rs(x)][i][j];
        cnt[x][rch[ls(x)]][lch[rs(x)]]++, lch[x] = lch[ls(x)], rch[x] = rch[rs(x)];
    }
    void access(int x, int ch, int len) { memset(cnt[x], 0, sizeof(cnt[x])), cnt[x][ch][ch] = len - 1, lch[x] = rch[x] = lzy[x] = ch; }
    void push_down(int x, int l, int r)
    {
        if (lzy[x] == -1)
            return;
        int mid = (l + r) / 2;
        access(ls(x), lzy[x], mid - l + 1), access(rs(x), lzy[x], r - mid);
        lzy[x] = -1;
    }
    void build(int l, int r, int k)
    {
        if (l == r)
        {
            lch[k] = rch[k] = s[l] - 'a';
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, ls(k)), build(mid + 1, r, rs(k));
        push_up(k);
    }
    void modify(int l, int r, int x, int y, int v, int k)
    {
        if (l >= x && r <= y)
        {
            access(k, v, r - l + 1);
            return;
        }
        int mid = (l + r) / 2;
        push_down(k, l, r);
        if (x <= mid)
            modify(l, mid, x, y, v, ls(k));
        if (y > mid)
            modify(mid + 1, r, x, y, v, rs(k));
        push_up(k);
    }
    Tree() { memset(lzy, -1, sizeof(lzy)); }
} t;

int pos[maxk];

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m >> k >> (s + 1);
    t.build(1, n, 1);
    int opt, x, y;
    char ch;
    while (m--)
    {
        cin >> opt;
        if (opt == 1)
            cin >> x >> y >> ch, t.modify(1, n, x, y, ch - 'a', 1);
        else
        {
            long long ans = 0;
            cin >> (s + 1);
            for (int i = 1; i <= k; i++)
                pos[s[i] - 'a'] = i;
              
            for (int i = 0; i < k; i++)
                for (int j = 0; j < k; j++)
                    if (pos[i] >= pos[j])
                        ans += t.cnt[1][i][j];
            cout << ans + 1 << endl;
        }
    }
}