A.打怪

题解：

如果的话就能杀死无数只，输出
否则用除于杀死一只怪所要消耗的血量就是答案
考虑到数据范围很小，直接暴力模拟也是可以的
公式计算：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int h, a, H, A;
        scanf("%d%d%d%d", &h, &a, &H, &A);
        if (a >= H)
            puts("-1");
        else
            printf("%d\n", (h - 1) / ((H - 1) / a * A));
    }
    return 0;
}

暴力模拟:

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

B.吃水果

题解：

假设，两数之差,如果每天各吃一个苹果和香蕉，的值不变。

1. 如果，每天各吃一个苹果和香蕉，直到,此时,将翻倍使得，然后每天各吃一个苹果和香蕉，天后吃完
2. 如果,将翻倍，直到满足情况。

所以该题一定有解,在此过程可以发现只要将变成就一定有解
考虑到数据范围很小，直接暴力模拟也是可以的
公式计算：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n, m;
        scanf("%lld%lld", &n, &m);
        if (n > m)
            swap(n, m);
        ll cnt = 0;
        while (n < m)
            n *= 2, cnt++;
        printf("%lld\n", cnt + m);
    }
    return 0;
}

暴力模拟:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n, m;
        scanf("%lld%lld", &n, &m);
        if (n > m)
            swap(n, m);
        ll ans = 0;
        while (1)
        {
            if (n * 2 <= m)
                n *= 2, ans++;
            else
                n--, m--, ans++;
            if (n == m)
            {
                ans += n;
                break;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C.四个选项（dp/dfs）

题解：

考虑到有个限制，则可以将这个限制看成几个联通块，将它们打包，那么对处理过后的点就可以转换成背包问题求解，表示考虑到第个物品，四个背包被装填的体积分别为的方案数
同时考虑到数据范围很小，也可以用枚举

:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int maxn = 1e5 + 5;
int fa[13], sum[13], dp[2][13][13][13][13];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
vector<int> v;
int main()
{
    for (int i = 1; i <= 12; i++)
        fa[i] = i;
    int na, nb, nc, nd, m;
    scanf("%d%d%d%d%d", &na, &nb, &nc, &nd, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        fa[find(x)] = find(y);
    }
    for (int i = 1; i <= 12; i++)
        sum[find(i)]++;
    for (int i = 1; i <= 12; i++)
        if (fa[i] == i)
            v.push_back(sum[i]);
    dp[0][0][0][0][0] = 1;
    int cur = 0, nxt = 1;
    for (int x : v)
    {
        for (int i = 0; i <= na; i++)
            for (int j = 0; j <= nb; j++)
                for (int k = 0; k <= nc; k++)
                    for (int h = 0; h <= nd; h++)
                        if (dp[cur][i][j][k][h])
                        {
                            if (i + x <= na)
                                dp[nxt][i + x][j][k][h] += dp[cur][i][j][k][h];
                            if (j + x <= nb)
                                dp[nxt][i][j + x][k][h] += dp[cur][i][j][k][h];
                            if (k + x <= nc)
                                dp[nxt][i][j][k + x][h] += dp[cur][i][j][k][h];
                            if (h + x <= nd)
                                dp[nxt][i][j][k][h + x] += dp[cur][i][j][k][h];
                        }
        swap(cur, nxt);
        memset(dp[nxt], 0, sizeof(dp[nxt]));
    }
    printf("%d\n", dp[cur][na][nb][nc][nd]);
    return 0;
}

:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<pii> v;
int num[5], op[13];
int ans = 0;
void dfs(int s)
{
    if (s > 12)
    {
        bool flag = true;
        for (auto it : v)
            if (op[it.first] != op[it.second])
            {
                flag = false;
                break;
            }
        if (flag)
            ans++;
        return;
    }
    for (int i = 1; i <= 4; i++)
    {
        op[s] = i;
        if (num[i])
        {
            num[i]--;
            dfs(s + 1);
            num[i]++;
        }
    }
}
int main()
{
    int m;
    scanf("%d%d%d%d%d", &num[1], &num[2], &num[3], &num[4], &m);
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v.push_back({x, y});
    }
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

D.最短路变短了（最短路）

题解：

让表示里点到点的最短路径，表示点到点的最短路径，我们可以通过两次求出这两个数组。
然后，考虑一次查询，两个点翻转后，判断是否小于原来的最短路长度即可。
正确性：注意到，翻转后可能不能到达点，但我们如果原来有路径，那么上述求出来的长度会是这条路径，可以发现路径长度增长了，显然不可能比，不影响答案，如果本来没有路径，也不影响答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<pii> G1[maxn], G2[maxn];
ll d1[maxn], d2[maxn];
int n, m, u[MAXN], v[MAXN], c[MAXN];
bool vis[maxn];
void dij(int s, ll d[], vector<pii> G[])
{
    for (int i = 1; i <= n; i++)
        d[i] = 1e18, vis[i] = 0;
    priority_queue<pii> q;
    q.push({0, s});
    d[s] = 0;
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto it : G[u])
        {
            int v = it.first, w = it.second;
            if (d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({-d[v], v});
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u[i], &v[i], &c[i]);
        G1[u[i]].push_back({v[i], c[i]});
        G2[v[i]].push_back({u[i], c[i]});
    }
    dij(1, d1, G1), dij(n, d2, G2);
    int q;
    scanf("%d", &q);
    for (int i = 0, x; i < q; i++)
    {
        scanf("%d", &x);
        puts(d1[v[x]] + d2[u[x]] + c[x] < d1[n] ? "YES" : "NO");
    }
    return 0;
}

E.相似的子串（二分+哈希）

题解：

题目只要求最长公共前缀，所以对于每个字符串后面多余的部分其实可以舍去，那么问题就变成求个相同字串的最大长度，显然考虑二分来求最大
关于函数，只需要从后往前遍历，对于每个，只要判断组成的字串是否已经出现个即可。
具体做法贴下官方题解：
设为字符串长度。
倒着,设代表从开始长度为的子串哈希值。
设代表考虑从到范围，取和这个位置开始的子串相同的子串最多能取多少个。
则
所以我们开一个，
从后往前枚举i,1令
最后取所有值的最大值，判断和的大小关系即可。
关于字符串的哈希可以看这篇帖子，戳我

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 3;
const ll base = 13331;
int n, k;
ll p[maxn] = {1ll}, h[maxn], dp[maxn];
char str[maxn];
ll get(int l, int r) { return ((h[r] - h[l - 1] * p[r - l + 1]) % mod + mod) % mod; }
bool check(int mid)
{
    if (!mid)
        return 1;
    unordered_map<int, int> mp;
    memset(dp, 0, sizeof(dp));
    for (int i = n - mid + 1; i >= 1; i--)
    {
        if (i + mid * 2 - 1 <= n)
            mp[get(i + mid, i + mid * 2 - 1)] = dp[i + mid];
        dp[i] = mp[get(i, i + mid - 1)] + 1;
        if (dp[i] >= k)
            return 1;
    }
    return 0;
}
int main()
{
    scanf("%d%d", &n, &k);
    scanf("%s", str + 1);
    for (int i = 1; i <= n; i++)
        p[i] = p[i - 1] * base % mod;
    for (int i = 1; i <= n; i++)
        h[i] = (h[i - 1] * base + str[i]) % mod;
    int l = 0, r = n / k;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", r);
    return 0;
}

F.苹果树（动态点分治）

题解：

如果没有修改的话，这道题就是一道点分治板题，加上修改其实就是变成了动态点分治。
考虑到加一个点其实只会对点分树上这个点到根节点路径上的所有点产生影响，那么我们只需要记录这个点到根节点路径上每个节点的编号，插入一个节点就令整条路径上的节点全部更新即可。
而对每一个节点动态开线段树记录每个成熟度下的最短距离，那么最小距离就是当前节点到根节点路径上每个节点为根求一次再加上当前节点到每个节点的距离取最小即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, m, a[maxn];
struct E
{
    int to, w, next;
} Edge[maxn << 1];
int tot, Head[maxn];
void init()
{
    memset(Head, -1, sizeof(Head));
    tot = 0;
}
inline void AddEdge(int u, int v, int w)
{
    Edge[tot] = (E){v, w, Head[u]};
    Head[u] = tot++;
}

int rt, sum; // rt记录重心，sum记录当前树大小
// siz记录子树大小，maxp用于找重心，vis记录被删除的结点
int siz[maxn], maxp[maxn], vis[maxn];
// dis[rt][i]为rt与i之间的距离,fa[i][j]为点分树上i的第几个父节点,dep为父节点个数
int dis[maxn][40], fa[maxn][40], dep[maxn];
//找重心
void getrt(int u, int f)
{
    siz[u] = 1, maxp[u] = 0; //maxp初始化为最小值
    //遍历所有儿子，用maxp保存最大大小的儿子的大小
    for (int i = Head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to;
        if (v == f || vis[v])
            continue; //被删掉的也不要算
        getrt(v, u);
        siz[u] += siz[v];
        if (siz[v] > maxp[u])
            maxp[u] = siz[v]; //更新maxp
    }
    maxp[u] = std::max(maxp[u], sum - siz[u]); //考虑u的祖先结点
    if (maxp[u] < maxp[rt])
        rt = u; //更新重心（最大子树大小最小）
}
//处理经过根结点的路径
void solve(int u, int f, int rt, int d)
{
    for (int i = Head[u]; ~i; i = Edge[i].next)
    {
        int v = Edge[i].to, w = Edge[i].w;
        if (v == f || vis[v])
            continue;
        fa[v][++dep[v]] = rt;
        dis[v][dep[v]] = d + w;
        solve(v, u, rt, d + w);
    }
}
//分治
void divide(int u)
{
    vis[u] = true;                                //删除根结点
    solve(u, 0, u, 0);                            //计算经过根结点的路径
    for (int i = Head[u]; ~i; i = Edge[i].next) //分治剩余部分
    {
        int v = Edge[i].to;
        if (vis[v])
            continue;
        maxp[rt = 0] = sum = siz[v]; //把重心置为0，并把maxp[0]置为最大值
        getrt(v, 0);
        divide(rt);
    }
}

int root[maxn], tree[maxn * 50], lson[maxn * 50], rson[maxn * 50], cnt;
void update(int &rt, int l, int r, int pos, int val)
{
    if (!rt)
    {
        rt = ++cnt;
        tree[rt] = INF;
    }
    tree[rt] = min(tree[rt], val);
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (pos <= mid)
        update(lson[rt], l, mid, pos, val);
    else
        update(rson[rt], mid + 1, r, pos, val);
}
int query(int rt, int l, int r, int L, int R)
{
    if (!rt || r < L || l > R)
        return INF;
    if (L <= l && r <= R)
        return tree[rt];
    int mid = l + r >> 1;
    return min(query(lson[rt], l, mid, L, R), query(rson[rt], mid + 1, r, L, R));
}
int main()
{
    init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
    maxp[rt=0] = sum = n; //maxp[0]置为最大值（一开始rt=0）
    getrt(1, 0);       //找重心
    divide(rt);           //找好重心就可以开始分治了
    for (int i = 1; i <= n; i++)
        fa[i][++dep[i]] = i;
    for (int i = 1; i <= n; i++)
        for (int j = dep[i]; j >= 1; j--)
            update(root[fa[i][j]], 1, 10000, a[i], dis[i][j]);
    while (m--)
    {
        int op, u, x, y;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d", &u, &x);
            for (int i = dep[u]; i >= 1; i--)
                update(root[fa[u][i]], 1, 10000, x, dis[u][i]);
        }
        else
        {
            scanf("%d%d%d", &u, &x, &y);
            int ans = INF;
            for (int i = dep[u]; i >= 1; i--)
                ans = min(ans, query(root[fa[u][i]], 1, 10000, x, y) + dis[u][i]);
            if (ans == INF)
                puts("-1");
            else
                printf("%d\n", ans * 2);
        }
    }
    return 0;
}

官方题解