B.Fire-Fighting Hero

题意：

有个着火点和条联通的路保证整张图联通，现在有一个消防英雄和支消防队伍，消防英雄要一个人从点灭完所有的火，支消防队伍可以合作灭完所有的火，比较消防英雄灭完最短路最大值点的距离除和消防队伍灭完最短路最大值点的距离

题解：

题意比较难读懂，消防英雄的答案只需要以点作为起点跑一遍最短路即可，消防队伍可以合作，因此可以将这个点都作为起点放入优先队列中跑一遍最短路

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int VN = 1005;
const int EN = VN * VN / 2;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int v, next, w;
} E[EN];
priority_queue<pii, vector<pii>, greater<pii>> q;
int n, m, s, k, c, siz;
int head[VN];
int d[VN];
int u[EN], v[EN], w[EN], used[VN];
vector<int> V;
void init()
{
    siz = 0;
    memset(head, -1, sizeof(head));
    while (!q.empty())
        q.pop();
}
void addEdge(int u, int v, int w)
{
    E[siz].v = v;
    E[siz].w = w;
    E[siz].next = head[u];
    head[u] = siz++;
}
int Dijkstra()
{
    for (int i = 1; i <= n; i++)
        d[i] = INF, used[i] = 0;
    for (int k : V)
        d[k] = 0, q.push(pii(d[k], k));
    while (!q.empty())
    {
        pii t = q.top();
        q.pop();
        int u = t.second;
        if (d[u] < t.first || used[u])
            continue;
        used[u] = 1;
        for (int e = head[u]; e != -1; e = E[e].next)
        {
            if (d[E[e].v] > d[u] + E[e].w)
            {
                d[E[e].v] = d[u] + E[e].w;
                q.push(pii(d[E[e].v], E[e].v));
            }
        }
    }
    int maxans = 0;
    for (int i = 1; i <= n; i++)
        if (maxans < d[i])
            maxans = d[i];
    return maxans;
}
int main()
{
    int t, m;
    scanf("%d", &t);
    while (t--)
    {
        init();
        scanf("%d%d%d%d%d", &n, &m, &s, &k, &c);
        V.clear();
        for (int i = 1, x; i <= k; i++)
            scanf("%d", &x), V.push_back(x);
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u[i], &v[i], &w[i]);
            addEdge(u[i], v[i], w[i]);
            addEdge(v[i], u[i], w[i]);
        }
        int ans = Dijkstra();
        V.clear();
        V.push_back(s);
        int t = Dijkstra();
        if (t <= ans * c)
            ans = t;
        printf("%d\n", ans);
    }
    return 0;
}

C.Hello 2019

题意：

给定一个长度为的序列和次询问，询问区间是否存在的子序列，并且至少删除多少个字符使得不存在的子序列

题解：

设置个状态。表示初始状态，表示只有，表示只有，表示只有，表示只有这四个状态。用一个的矩阵来进行状态转移，表示从状态到状态的最小花费。因为考虑到区间维护，因此用线段树来维护

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
const int inf = 1e9;

struct node
{
    int a[5][5];
    node operator+(const node b) const
    {
        node c;
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
            {
                c.a[i][j] = inf;
                for (int k = 0; k < 5; k++)
                    c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
            }
        return c;
    }
} e[maxn << 2];

char s[maxn];
int n, Q;

void build(int x, int l, int r)
{
    if (l == r)
    {
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                e[x].a[i][j] = (i == j) ? 0 : 1e9;
        if (s[l] == '2')
        {
            e[x].a[0][0] = 1;
            e[x].a[0][1] = 0;
        }
        else if (s[l] == '0')
        {
            e[x].a[1][1] = 1;
            e[x].a[1][2] = 0;
        }
        else if (s[l] == '1')
        {
            e[x].a[2][2] = 1;
            e[x].a[2][3] = 0;
        }
        else if (s[l] == '9')
        {
            e[x].a[3][3] = 1;
            e[x].a[3][4] = 0;
        }
        else if (s[l] == '8')
        {
            e[x].a[3][3] = 1;
            e[x].a[4][4] = 1;
        }
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    e[x] = e[x << 1] + e[x << 1 | 1];
}

node query(int x, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return e[x];
    int mid = l + r >> 1;
    if (qr <= mid)
        return query(x << 1, l, mid, ql, qr);
    if (ql > mid)
        return query(x << 1 | 1, mid + 1, r, ql, qr);
    return query(x << 1, l, mid, ql, mid) + query(x << 1 | 1, mid + 1, r, mid + 1, qr);
}

int main()
{
    scanf("%d%d%s", &n, &Q, s + 1);
    reverse(s + 1, s + n + 1);
    build(1, 1, n);
    while (Q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = n - l + 1, r = n - r + 1;
        swap(l, r);
        int ans = query(1, 1, n, l, r).a[0][4];
        if (ans == inf)
            printf("-1\n");
        else
            printf("%d\n", ans);
    }
}

E.Magic Master

题意：

给定张牌和一个数，每次操作将最上面的牌取出，再进行次把最上面的牌放到最下面，直至所以牌都被取出，要使得所有被取出的牌恰好满足，询问一开始牌的摆放顺序

题解：

这题的难点在于读题，首先可以明确第一次取出的牌肯定是，因此肯定摆在首位，再明确最后一次肯定只剩下号牌，那么不妨倒序遍历，每次都把第张牌放入头部，再把最后的张牌依次放到头部，因为第一次固定取，所以后面顺序就变成了先排张牌，再取一张牌，这样操作就能保证第张号肯定在第次被取到。这个操作可以用双端队列来实现，模拟即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        deque<int> s;
        int n, m;
        scanf("%d%d", &n, &m);
        s.push_front(n);
        for (int i = n - 1; i > 1; i--)
        {
            s.push_front(i);
            for (int j = 1; j <= m; j++)
            {
                int tmp = s.back();
                s.pop_back();
                s.push_front(tmp);
            }
        }
        s.push_front(1);
        int q, x;
        scanf("%d", &q);
        while (q--)
        {
            scanf("%d", &x);
            printf("%d\n", s[x - 1]);
        }
    }
    return 0;
}

G.Pangu Separates Heaven and Earth

题意：

输入为时输出，否则输出

题解：

签到题

#include <stdio.h>
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        if (n == 1)
            printf("18000\n");
        else
            printf("0\n");
    }
}

H.The Nth Item

题意：

给定一个序列。次询问每次询问第项对取模的值。

题解：

猜想存在循环节，因此可以用map记忆化搜索把答案存储下来，每次结果取的左上角值即为答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 998244353;

struct Matrix
{
    int t;
    ll a[3][3];
    Matrix(int t0) : t(t0)
    { // 初始化成t阶单位矩阵
        memset(a, 0, sizeof(a));
        for (int i = 0; i < t; i++)
            a[i][i] = 1;
    }
    Matrix operator*(const Matrix &y);
    void Output();
};

Matrix Matrix::operator*(const Matrix &y)
{ // 矩阵乘法的运算符重载
    Matrix r(t);
    for (int i = 0; i < t; i++)
        for (int j = 0; j < t; j++)
        {
            r.a[i][j] = 0;
            for (int k = 0; k < t; k++)
                r.a[i][j] += a[i][k] * y.a[k][j];
            r.a[i][j] %= p;
        }
    return r;
}

Matrix ksm(Matrix A, ll n)
{
    Matrix B(2), M(2);
    B = Matrix(2);
    M = A; // 保存A的2整数次幂的幂
    while (n)
    {
        if (n & 1)
            B = B * M;
        n >>= 1;
        M = M * M;
    }
    return B;
}
map<ll, ll> mp;
int main()
{
    ll q, n;
    scanf("%lld%lld", &q, &n);
    Matrix A(2);
    A.a[0][0] = 3;
    A.a[0][1] = 2;
    A.a[1][0] = 1;
    A.a[1][1] = 0;
    ll ans = 0, tmp;
    Matrix res(2);
    for (int i = 1; i <= q; i++)
    {

        if (mp[n] == 0)
        {
            res = ksm(A, n - 1ll);
            tmp = res.a[0][0];
            mp[n] = tmp;
        }
        else
            res.a[0][0] = mp[n];

        n = n ^ (tmp * tmp);
        ans ^= tmp;
    }
    printf("%lld\n", ans);
    return 0;
}

I.Yukino With Subinterval

题意：

给定一个长度为的序列，有两种操作： ：将的值改为
:询问区间有多少个最长相等字串，且值在之间

题解：

把所有连续段缩到它的左端点，查询的时候只要查区间内有多少个左端点即可。但是考虑到可能也属于一个最长相等字串内，因此要特判一下是否等于。查询左端点数用主席树即可实现，考虑到修改，可以用树状数组来维护主席树，因此就是树状数组套主席树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, m, a[N];
inline int lowbit(int x) { return x & -x; }
struct PST
{
    int sum[N * 200], ls[N * 200], rs[N * 200];
    int rt[N], tot, maxn;
    void update_SgT(int &rt, int l, int r, int pos, int val)
    {
        if (!rt)
            rt = ++tot;
        sum[rt] += val;
        if (l == r)
            return;
        int mid = l + r >> 1;
        if (pos <= mid)
            update_SgT(ls[rt], l, mid, pos, val);
        else
            update_SgT(rs[rt], mid + 1, r, pos, val);
    }
    void update_BIT(int x, int pos, int v)
    {
        for (; x <= maxn; x += lowbit(x))
            update_SgT(rt[x], 1, n, pos, v);
    }
    int rt1[30][30], rt2[30][30], cnt1, cnt2;
    void locate(int l, int r)
    {
        cnt1 = cnt2 = 0;
        for (int i = l - 1; i; i -= lowbit(i))
            rt1[++cnt1][0] = rt[i];
        for (int i = r; i; i -= lowbit(i))
            rt2[++cnt2][0] = rt[i];
    }
    int query(int dep, int l, int r, int ql, int qr)
    {
        if (ql > qr)
            return 0;
        int res = 0;
        if (l >= ql && r <= qr)
        {
            for (int i = 1; i <= cnt1; i++)
                res -= sum[rt1[i][dep]];
            for (int i = 1; i <= cnt2; i++)
                res += sum[rt2[i][dep]];
            return res;
        }
        int mid = l + r >> 1;
        if (ql <= mid)
        {
            for (int i = 1; i <= cnt1; i++)
                rt1[i][dep + 1] = ls[rt1[i][dep]];
            for (int i = 1; i <= cnt2; i++)
                rt2[i][dep + 1] = ls[rt2[i][dep]];
            res += query(dep + 1, l, mid, ql, qr);
        }
        if (qr > mid)
        {
            for (int i = 1; i <= cnt1; i++)
                rt1[i][dep + 1] = rs[rt1[i][dep]];
            for (int i = 1; i <= cnt2; i++)
                rt2[i][dep + 1] = rs[rt2[i][dep]];
            res += query(dep + 1, mid + 1, r, ql, qr);
        }
        return res;
    }
} PST;
int main()
{
    scanf("%d%d", &n, &m);
    PST.maxn = n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] != a[i - 1])
            PST.update_BIT(i, a[i], 1);
    }
    while (m--)
    {
        int op, l, r, x, y;
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1)
        {
            if (a[l] == r)
                continue;
            if (a[l] != a[l - 1])
                PST.update_BIT(l, a[l], -1);
            if (a[l] == a[l + 1])
                PST.update_BIT(l + 1, a[l + 1], 1);
            else if (r == a[l + 1])
                PST.update_BIT(l + 1, a[l + 1], -1);
            a[l] = r;
            if (a[l] != a[l - 1])
                PST.update_BIT(l, a[l], 1);
        }
        else
        {
            scanf("%d%d", &x, &y);
            PST.locate(l, r);
            int ans = PST.query(0, 1, n, x, y);
            if (a[l] == a[l - 1] && a[l] >= x && a[l] <= y)
                ans++;
            printf("%d\n", ans);
        }
    }
    return 0;
}