还是比去年要难的。

种花

Description

给一个 $n\times m$ 的 01 矩阵，问其中有多少个由 0 组成的 C 形状和 F 形状。

$n,m\leq1000$

Solution

从上向下扫，记录每一列 $\Gamma$ 形状的数量和二阶 $\Gamma$ 形状（其实就是 F）的数量即可，利用行后缀 0 数量统计即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

namespace solve
{
    const int maxn = 1010;
    typedef long long ll;
    const int mod = 998244353;

    int a[maxn][maxn], n, m, c, f;

    void main()
    {
        cin >> n >> m >> c >> f;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                char ch;
                cin >> ch;
                a[i][j] = ch - '0';
            }
        static ll C[maxn], suf[maxn], sum[maxn];
        memset(C, 0, sizeof(C)), memset(suf, 0, sizeof(suf)), memset(sum, 0, sizeof(sum));
        ll resc = 0, resf = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = m; j >= 1; j--)
            {
                if (a[i][j] == 1)
                {
                    C[j] = suf[j] = sum[j] = 0;
                    continue;
                }
                (resc += 1ll * C[j] * suf[j + 1] % mod) %= mod;
                (resf += sum[j]) %= mod;
                (sum[j] += C[j] * 1ll * suf[j + 1] % mod) %= mod;
                if (suf[j])
                    C[j] += suf[j] - 1;
                suf[j] = suf[j + 1] + 1;
            }
        }
        cout << resc * c % mod << " " << resf * f % mod << '\n';
    }
}

int main()
{
    // freopen("plant.in", "r", stdin), freopen("plant.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T, id;
    cin >> T >> id;
    while (T--)
        solve::main();
}

喵了个喵

Description

有一个长度为 $m$ 的卡牌队列，共有 $k$ 种不同图案的卡牌，你有 $n$ 个栈。有两种操作。

  • 选择一个栈，将牌堆顶上的卡牌放入栈的顶部。如果这么操作后，这个栈最上方的两张牌有相同的图案，则会自动将这两张牌消去。

  • 选择两个不同的栈，如果这两个栈栈底的卡牌有相同的图案，则可以将这两张牌消去，原来在栈底上方的卡牌会成为新的栈底。如果不同，则什么也不会做。

$m\leq 2\times 10^6,n\leq300, k=2n-1,1\leq a_i\leq k$。

有一个部分分是 $k=2n-2$。

Solution

一眼看起来非常神秘，完全不可做，题目保证了 $k=2n-2$ 或 $k=2n-1$，只能从此入手。

首先当一个栈顶的牌和要放的牌一样时，显然一定要消掉。

当 $k=2n-2$，一个显然的做法是留出一个空栈，其他的栈都放两张不同的牌，这样再来一张牌肯定能消掉一张牌，就赢了。

当 $k=2n-1$，可以尝试让一个栈里面有 $3$ 种牌，然后对于这一堆，要保证最下面的牌在后面的队列里先出现。

考虑到我们可能被迫会往剩下的那个空栈放牌，我们要保证在出现这种情况后，被盖在下面的牌不会寄，这就对当若干个栈里只有一张牌的时候，新牌放哪个栈里有要求。

当没有一个合法的两牌栈的时候，我们优先把这张牌放到出现最晚的牌上面。这样就能满足我们的要求了。

Code


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <array>
#include <cassert>
using namespace std;

namespace solve
{
    const int maxn = 2e6 + 10;

    vector<int> s[maxn];
    int n, m, KKK, a[maxn], nxt[maxn], lst[maxn], match[maxn], pos[maxn];
    
    void main()
    {
        cin >> n >> m >> KKK;
        for (int i = 1; i <= KKK; i++)
            match[i] = pos[i] = lst[i] = 0;
        for (int i = 1; i <= m; i++)
            cin >> a[i];
        for (int i = m; i >= 1; i--)
            nxt[i] = lst[a[i]], lst[a[i]] = i;
        for (int i = 1; i <= n; i++)
            s[i].clear();
        vector<array<int, 3>> ans;
        for (int i = 1; i <= m; i++)
        {
            if (pos[a[i]])
            {
                int x = pos[a[i]];
                pos[a[i]] = 0;
                if (s[x].back() == a[i])
                    ans.push_back({0, x, 0}), s[x].pop_back();
                else
                {
                    int p = 0;
                    for (int i = 1; i <= n; i++)
                        if (s[i].size() == 0)
                        {
                            p = i;
                            break;
                        }
                    ans.push_back({0, p, 0}), ans.push_back({1, x, p});
                    assert(s[x][0] == a[i]);
                    s[x].erase(s[x].begin());
                }
            }
            else
            {
                int p = 0;
                auto find1 = [&]()
                {
                    for (int j = 1; j <= n; j++)
                        if (s[j].size() == 2 && match[s[j][0]] < match[s[j][1]])
                            return j;
                    return 0;
                };
                auto find2 = [&]()
                {
                    int mx = 0, res = 0;
                    for (int j = 1; j <= n; j++)
                        if (s[j].size() == 1 && match[s[j][0]] > mx)
                            mx = match[s[j][0]], res = j;
                    return res;
                };
                auto find3 = [&]()
                {
                    for (int j = 1; j <= n; j++)
                        if (s[j].size() == 0)
                            return j;
                    assert(0);
                    return 0;
                };
                p = find1();
                if (!p)
                    p = find2();
                if (!p)
                    p = find3();
                pos[a[i]] = p, s[p].push_back(a[i]), ans.push_back({0, p, 0});
                match[a[i]] = nxt[i];
            }
        }
        cout << ans.size() << '\n';
        for (const auto &o : ans)
            if (o[0] == 0)
                cout << "1 " << o[1] << '\n';
            else
                cout << "2 " << o[1] << " " << o[2] << '\n';
    }
}

int main()
{
    // freopen("meow.in", "r", stdin), freopen("meow.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve::main();
}

建造军营

Description

有一个 $n$ 个点，$m$ 个边的无向图，A 国要选择至少一个城市建造军营。B 国可以摧毁一条道路。

现在 A 国可以保护任意条道路，被保护的道路不会被 B 国摧毁。A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。求可能的建造军营和看守道路的方案数共有多少。

$n\leq5\times10^5,m\leq10^6$。

Solution

对于一个边双，摧毁是没用的，启发我们边双缩点成一个树。

然后考虑树形dp，每种方案在若干个要建兵营的点的lca处贡献答案。计算的时候保护一次边答案就记得除以 $2$，最后再乘上 $2^m$ 即可得到最终答案。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <array>
#include <cassert>
using namespace std;

namespace solve
{
    const int maxn = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int inv2 = (mod + 1) / 2;
    typedef long long ll;

    ll mi[maxn];

    vector<int> e[maxn], e2[maxn];
    inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

    int dfn[maxn], low[maxn], stk[maxn], top, cnt;
    int scc[maxn], tot, siz[maxn];

    int n, m;

    void tarjan(int x, int fa)
    {
        stk[++top] = x, dfn[x] = low[x] = ++cnt;
        for (int v : e[x])
            if (v != fa)    
            {
                if (!dfn[v])
                    tarjan(v, x);
                low[x] = min(low[x], low[v]);
            }
        if (low[x] == dfn[x])
        {
            tot++;
            int now = 0;
            while (now != x)
            {
                now = stk[top--];
                siz[tot]++, scc[now] = tot;
            }
        }
    }

    ll ans = 0;

    ll f[maxn];

    void dfs(int x, int fa)
    {
        (ans += f[x] = mi[siz[x]] - 1) %= mod;
        for (int v : e2[x])
            if (v != fa)
            {
                dfs(v, x);
                (ans += f[x] * f[v] % mod * inv2 % mod) %= mod;
                (f[x] += f[v] * (f[x] + 1) % mod * inv2 % mod) %= mod;
                // 这里只在子树里的情况已经在儿子处统计过了，因此f[x]要加上的是f[v]/2而不是f[v]
            }
    }

    void main()
    {
        mi[0] = 1;
        for (int i = 1; i < maxn; i++)
            mi[i] = mi[i - 1] * 2 % mod;
        cin >> n >> m;
        for (int i = 0, x, y; i < m; i++)
            cin >> x >> y, add(x, y);
        tarjan(1, 0);
        for (int i = 1; i <= n; i++)
            for (int v : e[i])
                if (scc[i] != scc[v])
                    e2[scc[i]].push_back(scc[v]);
        dfs(1, 0);
        cout << ans * mi[m] % mod << endl;
    }
}

int main()
{
    // freopen("barrack.in", "r", stdin), freopen("barrack.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve::main();
}

比赛

Description

给出两个长度为 $n$ 的序列 $a, b$，$q$ 次询问，每次询问给出 $l,r$，求出

$$ \sum_{p = l}^r \sum_{q = p}^r \bigl(\max\nolimits_{i=p}^q a_i\bigr)\bigl(\max\nolimits_{i=p}^q b_i\bigr). $$

$n,q\leq2.5\times10^5$。

Solution

和其他题解说的一样，这道题可以离线询问，把询问挂在右端点上，进行扫描线。这部分别的题解都说了，我就简单说一下。

扫描右端点（记为 $pos$）的同时，用线段树各自维护每个位置到当前右端点中 $a,b$ 的最大值 $x_i,y_i$，用单调栈可以得出每次新数影响的区间，对应线段树的区间赋值操作。接着我们需要把 $[1,pos]$ 的答案都加上 $x_i\times y_i$。

整理一下需要支持的操作：

  • 序列 $x$ 区间赋值；

  • 序列 $y$ 区间赋值；

  • 区间答案加上 $x_iy_i$；

  • 查询区间答案和。

三操作提示我们记录区间 $\sum x_iy_i$，而为了维护区间 $x_i,y_i$，我们需要维护 $\sum x_i,\sum y_i$ 和区间长度 $len$。

直接做可能不太方便，我们可以用矩阵方便地描述转移：

答案矩阵是

$$ \begin{bmatrix} ans \\ \sum xy \\ \sum x \\ \sum y \\ len \end{bmatrix} $$

赋值 $x$，赋值 $y$，区间加 $xy$ 都可以用矩阵表示： $$ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & x & 0 \\ 0 & 0 & 0 & 0 & x \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & y & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & y \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

直接用线段树维护矩阵，复杂度 $O(5^3q\log n)$，进行一些普通的常数优化后在 loj 上可以卡着时限通过，但洛谷显然不行。

注意到矩阵很稀疏，打一个表可以发现很多地方永远会是 $0$，因此可以把矩阵乘法展开，手动乘，常数会下降很多。

Code

在洛谷上最大点跑 1.55s，不算太慢。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

bool MEM1;

namespace IO
{
    const int mxsiz = 1 << 14;

    char inbuf[mxsiz], *p1, *p2;
    char outbuf[mxsiz], *op = outbuf;

    inline void flush() { fwrite(outbuf, 1, op - outbuf, stdout), op = outbuf; }
    struct endio
    {
        endio(){};
        ~endio() { flush(); }
    } useless_var;
    inline char gc()
    {
        if (p1 == p2)
            p1 = inbuf, p2 = p1 + fread(inbuf, 1, mxsiz, stdin);
        return p1 == p2 ? EOF : *p1++;
    }
    inline int read()
    {
        int x = 0, f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        return x * f;
    }
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        int f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        x *= f;
    }
    template <typename T, typename... Args>
    inline void read(T &x, Args &...args) { read(x), read(args...); }
    inline void read(char &ch)
    {
        ch = gc();
        while (!isgraph(ch))
            ch = gc();
    }
    inline void push(char ch)
    {
        if (op - outbuf == mxsiz)
            fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
        *op++ = ch;
    }
    template <typename... Args>
    inline void push(char ch, Args... args) { push(ch), push(args...); }
    inline void endln() { push('\n'); }
    inline void space() { push(' '); }
    template <typename T>
    inline void work_wt(T x)
    {
        if (x > 9)
            work_wt(x / 10);
        push(x % 10 + '0');
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            x = -x, push('-');
        work_wt(x);
    }
    inline void write(char ch) { push(ch); }
    inline void write(const char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n; i++)
            push(s[i]);
    }
    template <typename T, typename... Args>
    inline void write(T x, Args... args) { write(x), write(args...); }
    template <typename T>
    inline void write_with_space(T x) { write(x), space(); }
    template <typename T, typename... Args>
    inline void write_with_space(T x, Args... args) { write_with_space(x), write_with_space(args...); }
    template <typename... Args>
    inline void writeln(Args... x) { write_with_space(x...), endln(); }
};
using IO::endln;
using IO::gc;
using IO::read;
using IO::space;
using IO::write;
using IO::write_with_space;
using IO::writeln;

namespace solve
{
    typedef unsigned long long ull;
    const int maxn = 2.5e5 + 10;

    const vector<int> qwq[5] =
        {
            {0, 1, 2, 3, 4},
            {1, 2, 3, 4},
            {2, 4},
            {3, 4},
            {4}};

    struct matrix
    {
        ull a[5][5];
        int n, m;
        const ull *operator[](int x) const { return a[x]; }
        matrix operator+(const matrix &b) const
        {
            matrix res;
            for (int i = 0; i < 5; i++)
                for (int j = 0; j < 1; j++)
                    res.a[i][j] = a[i][j] + b[i][j];
            return res;
        }
        matrix operator*(const matrix &b) const
        {
            matrix res;
            res.clear();
            /*
11111
01111
00101
00011
00001
            */
            // for (int i = 0; i < 5; i++)
            //     for (int k : qwq[i])
            //         for (int j : qwq[k])
            //             res.a[i][j] += a[i][k] * b[k][j];
            res.a[0][0] = a[0][0] * b[0][0];
            res.a[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
            res.a[0][2] = a[0][0] * b[0][2] + a[0][1] * b[1][2] + a[0][2] * b[2][2];
            res.a[0][3] = a[0][0] * b[0][3] + a[0][1] * b[1][3] + a[0][3] * b[3][3];
            res.a[0][4] = a[0][0] * b[0][4] + a[0][1] * b[1][4] + a[0][2] * b[2][4] + a[0][3] * b[3][4] + a[0][4] * b[4][4];
            res.a[1][1] = a[1][1] * b[1][1];
            res.a[1][2] = a[1][1] * b[1][2] + a[1][2] * b[2][2] + a[1][3] * b[3][2];
            res.a[1][3] = a[1][1] * b[1][3] + a[1][3] * b[3][3];
            res.a[1][4] = a[1][1] * b[1][4] + a[1][2] * b[2][4] + a[1][3] * b[3][4] + a[1][4] * b[4][4];
            res.a[2][2] = a[2][2] * b[2][2];
            res.a[2][4] = a[2][2] * b[2][4] + a[2][4] * b[4][4];
            res.a[3][3] = a[3][3] * b[3][3];
            res.a[3][4] = a[3][3] * b[3][4] + a[3][4] * b[4][4];
            res.a[4][4] = a[4][4] * b[4][4];
            return res;
        }
        matrix operator&(const matrix &b) const
        {
            matrix res;
            res.clear();
            for (int i = 0; i < 5; i++)
                for (int k = 0; k < 5; k++)
                    for (int j = 0; j < 1; j++)
                        res.a[i][j] += a[i][k] * b[k][j];
            return res;
        }
        void init()
        {
            memset(a, 0, sizeof(a));
            a[0][0] = a[1][1] = a[2][2] = a[3][3] = a[4][4] = 1;
        }
        void clear()
        {
            memset(a, 0, sizeof(a));
        }
    } lzy[maxn << 2], sum[maxn << 2];
    bool vis[maxn << 2];

    matrix opt3 =
        {
            {{1, 1, 0, 0, 0},
             {0, 1, 0, 0, 0},
             {0, 0, 1, 0, 0},
             {0, 0, 0, 1, 0},
             {0, 0, 0, 0, 1}},
            5,
            5};
    inline matrix opt1(ull x)
    {
        return {
            {{1, 0, 0, 0, 0},
             {0, 0, 0, x, 0},
             {0, 0, 0, 0, x},
             {0, 0, 0, 1, 0},
             {0, 0, 0, 0, 1}},
            5,
            5};
    }
    inline matrix opt2(ull x)
    {
        return {
            {{1, 0, 0, 0, 0},
             {0, 0, x, 0, 0},
             {0, 0, 1, 0, 0},
             {0, 0, 0, 0, x},
             {0, 0, 0, 0, 1}},
            5,
            5};
    }

    ull a[maxn], b[maxn];

    int n, m;

    struct Q
    {
        int l, r, id;
    } q[maxn];

    inline int ls(int x) { return x * 2; }
    inline int rs(int x) { return x * 2 + 1; }

    inline void push_up(int x)
    {
        sum[x] = sum[ls(x)] + sum[rs(x)];
    }
    inline void push_tag(int k, const matrix &x)
    {
        sum[k] = x & sum[k];
        lzy[k] = x * lzy[k];
        vis[k] = 1;
    }
    inline void push_down(int k)
    {
        if (!vis[k])
            return;
        push_tag(ls(k), lzy[k]), push_tag(rs(k), lzy[k]);
        vis[k] = 0, lzy[k].init();
    }

    void build(int l, int r, int k)
    {
        lzy[k].init(), lzy[k].n = lzy[k].m = 5;
        sum[k].n = 5, sum[k].m = 1;
        if (l == r)
        {
            sum[k].a[4][0] = 1, sum[k].a[3][0] = b[l], sum[k].a[2][0] = a[l], sum[k].a[1][0] = b[l] * a[l];
            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, const matrix &v, int k)
    {
        if (l >= x && r <= y)
        {
            push_tag(k, v);
            return;
        }
        push_down(k);
        int mid = (l + r) / 2;
        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);
    }

    ull query(int l, int r, int x, int y, int k)
    {
        if (l >= x && r <= y)
            return sum[k][0][0];
        push_down(k);
        int mid = (l + r) / 2;
        ull res = 0;
        if (x <= mid)
            res += query(l, mid, x, y, ls(k));
        if (y > mid)
            res += query(mid + 1, r, x, y, rs(k));
        return res;
    }

    ull ans[maxn];

    void main()
    {
        read(n);
        for (int i = 1; i <= n; i++)
            read(a[i]);
        for (int i = 1; i <= n; i++)
            read(b[i]);
        read(m);
        for (int i = 1; i <= m; i++)
            read(q[i].l, q[i].r), q[i].id = i;
        sort(q + 1, q + 1 + m, [&](const Q &x, const Q &y) { return x.r != y.r ? x.r < y.r : x.l < y.l; });
        int pos = 1;
        static int stk1[maxn], stk2[maxn], top1 = 0, top2 = 0;
        build(1, n, 1);
        for (int i = 1; i <= n; i++)
        {
            while (top1 && a[stk1[top1]] < a[i])
                top1--;
            while (top2 && b[stk2[top2]] < b[i])
                top2--;
            modify(1, n, stk1[top1] + 1, i, opt1(a[i]), 1);
            modify(1, n, stk2[top2] + 1, i, opt2(b[i]), 1);
            modify(1, n, 1, i, opt3, 1);
            stk1[++top1] = i, stk2[++top2] = i;
            while (pos <= m && q[pos].r == i)
                ans[q[pos].id] = query(1, n, q[pos].l, i, 1), pos++;
        }
        for (int i = 1; i <= m; i++)
            write(ans[i]), endln();
    }
}

bool MEM2;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int id;
    read(id);
    solve::main();
}