A、打怪

传送戳我

解题思路

1、先特判输出-1的情况，即一回合秒杀怪物，永远是我先手，所以杀无数只怪物。
2、计算我杀怪物需要多久记作a回合，可以考虑用向上取整ceil函数。同理计算怪物杀我所要回合数，记作b回合。
3、%d输出(b-1) / (a-1)。因为我是先手所以我需要花费的回合 -1，又因为我的血量需要大于等于0，所以怪物杀我回合数也需要 -1。

时间复杂度 O (N) 。

代码

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    int T = read();
    while (T--) {
        int n = read(), m = read(), a = read(), b = read();
        if (m >= a) {
            puts("-1");
            continue;
        }
        int ans = ceil(1.0 * a / m);//杀一只怪
        int tmp = ceil(1.0 * n / b);//怪杀了我
        printf("%d\n", (tmp - 1) / (ans - 1));
    }
    return 0;
}

B、吃水果

传送戳我

解题思路

因为数据规模小，直接模拟，开一个时间计数器初始化为0。先保证 图片说明 ，每次做决策，如果 图片说明 我们这次选择 n*2，否则选择 --n,--m。每次决策时间计数器加一。

时间复杂度 O（N*log(N)）。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    int T = read();
    while (T--) {
        int n = read(), m = read();
        int ans = 0;
        if (n > m)    swap(n, m);
        else if (n == m) {
            printf("%d\n", n);
            continue;
        }
        while (n) {
            if ((n << 1) <= m) n <<= 1;
            else     --n, --m;
            ++ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

C、四个选项

传送戳我

解题思路

并查集 + dfs暴搜；先通过并查集处理区域块，绑定的绑定，后面从1，开始向下 dfs ，选A，选B，选C，选D。并且记录选项编号，当达到递归出口，n==13的时候，先判断是否符合题目给的ABCD数量，在判断并查集在一起的方案是否相同。如果都相同，++ans。

时间复杂度 O（图片说明 ）应该还会更小，题目ABCD有数量限制。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

#define N 15
ll ans;
int pa[N]; //记录填涂方案
int father[N];

int Find(int root) {
    if (father[root] == root)   return root;
    return father[root] = Find(father[root]);
}

void Merge(int a, int b) { //路径压缩
    int fa = Find(a);
    int fb = Find(b);
    if (fa > fb) swap(fa, fb);
    if (fa != fb) {
        father[fa] = fb;
    }
}

void dfs(int n, int a, int b, int c, int d) {
    if (a < 0 || b < 0 || c < 0 || d < 0)  return; //可行性剪枝
    if (n == 13) {
        if (a || b || c || d)       return;
        for (int i = 1; i <= 12; ++i)
            if (pa[i] != pa[father[i]]) return;
        ++ans;
        return;
    }
    pa[n] = 1, dfs(n + 1, a - 1, b, c, d);
    pa[n] = 2, dfs(n + 1, a, b - 1, c, d);
    pa[n] = 3, dfs(n + 1, a, b, c - 1, d);
    pa[n] = 4, dfs(n + 1, a, b, c, d - 1);
}

int main() {
    for (int i = 0; i < N; ++i)  father[i] = i;
    int a = read(), b = read(), c = read(), d = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int x = read(), y = read();
        if (x > y)   swap(x, y);
        Merge(x, y);
    }
    dfs(1, a, b, c, d);
    printf("%lld\n", ans);
    return 0;
}

D、最短路变短了

传送戳我

解题方法

通过一次dji可以算出 1-n 的最短路，那么如果路径进行翻转呢？我们如果重新去dji一遍重复q次，肯定TLE，而且边权信息不好删除，不好操作所以这种方法Pass。这时候我们画个图，如下：图片说明
我们可以发现，如果我们吧2->5这条路径翻转，变成5->2，这时新的最短路径为 1->5 + 5->2 + 2->5；如果写的通常一点就是：i->j翻转；带来的影响之后的最短路径就是：len(1->j) + len(j->i) + len(i->5) 如果这个花费小于原来1->n的最小花费，那么puts("YES")， else puts("NO")。

时间复杂度 O(N + Q)

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;
int u[N << 1], v[N << 1], w[N << 1];// 记录边权信息
int n, m;
struct Node {
    int v;
    ll cost;
    friend bool operator<(Node a, Node b) { //自定义priority_queue的less规定，注意false排在前面，给坑了一发。。
        return a.cost > b.cost;
    }
};
ll d[N], f[N]; //d正向图，f反向图
vector<Node> D[N]; // pair<终点，花费>
vector<Node> F[N];

void dji1(int x) {
    priority_queue<Node> pq;
    while (pq.size())    pq.pop();
    memset(d, 0x3f, sizeof(d));
    d[x] = 0;
    pq.push({ x,0 });
    while (pq.size()) {
        Node tmp = pq.top();
        pq.pop();
        ll v = tmp.v;
        if (d[v] < tmp.cost)    continue; //原先这个节点花费更少 跳过
        for (int i = 0; i < D[v].size(); ++i) {
            Node s = D[v][i];
            if (d[s.v] > d[v] + s.cost) {
                d[s.v] = d[v] + s.cost;
                pq.push({ s.v,d[s.v] });
            }
        }
    }
}

void dji2(int x) {
    priority_queue<Node> pq;
    while (pq.size())    pq.pop();
    memset(f, 0x3f, sizeof(f));
    f[x] = 0;
    pq.push({ x,0 });
    while (pq.size()) {
        Node tmp = pq.top();
        pq.pop();
        ll v = tmp.v;
        if (f[v] < tmp.cost)    continue; //原先这个节点花费更少 跳过
        for (int i = 0; i < F[v].size(); ++i) {
            Node s = F[v][i];
            if (f[s.v] > f[v] + s.cost) {
                f[s.v] = f[v] + s.cost;
                pq.push({ s.v,f[s.v] });
            }
        }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read(), w[i] = read();
        D[u[i]].push_back({ v[i], w[i] });
        F[v[i]].push_back({ u[i], w[i] });
    }
    dji1(1);
    dji2(n);
    int T = read();
    while (T--) {
        int x = read();
        ll a = u[x], b = v[x], c = w[x];
        ll ans = d[b] + c + f[a];
        if (ans < d[n])    puts("YES");
        else    puts("NO");
    }
    return 0;
}

E、相似的子串

传送戳我

知识点：字符串hash+二分

解题思路

题目要我们找k个位置，最长公共前缀是x，并且x需要最大，那我们就只考虑子串内容为前缀相同部分，保证最大。
通过O(N)的hash预处理字符串，就可以通过O(1)查找到该字符串，散列表的话可以通过STL的unordered_map<>实现，我这里遇到了点小插曲，是因为我使用的编译器是VS2019，因为微软自己的宏__cplusplus一直都没有修改是C++99的版本，就算你改了编译器版本这个宏还是不变，以至于不能再万能头文里面直接用。如果需要修改的小伙伴可以通过VS的项目属性，找到C/C++，在命令行加上 /Zc : __cplusplus这样就可以使用了，回归正题，在这个map里面，键对应的值的内容我们需要使用一个pair去定义，first为子串最后出现的位置，second为子串个数，这样我们通过二分查找去寻找ans，如果当前mid不符合，那么左区间查找，如果mid符合，右区间查找。至于check(mid)函数，从x开始求对应hash表中长度为x的前缀和，如果这个字符串在表中位置减去上次在表中位置大于等于mid，说明子串没有重叠部分，把字符串的最后位置赋值为i，子串个数加1，如果长度为mid的子串存在k个及以上就return true。

时间复杂度 O(N * log(N))

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull; //物理取模

struct Node {
    int pos, cnt; //最后一次出现位置，子串中元素个数
};

const int N = 2e5 + 7;
unordered_map<ull, pair<int, int> > mp; // 使用umap建立hash表
int base = 131; // 字符串hash值 一般取131 or 13331
ull po[N], has[N];

int n, k;
char s[N];

bool check(int x) {
    mp.clear();
    for (int i = x; i <= n; ++i) {
        ull tmp = has[i] - has[i - x] * po[x];
        if (i - mp[tmp].first >= x) {
            mp[tmp].first = i; //最后一次出现位置为结尾位置
            ++mp[tmp].second; //子串数量+1
        }
        if (mp[tmp].second >= k)    return true;
    }
    return false;
}

int main() {
    scanf("%d %d %s", &n, &k, s + 1);
    po[0] = 1;
    for (int i = 1; i <= n; ++i) {
        has[i] = has[i - 1] * base + s[i] - 'a';
        po[i] = po[i - 1] * base;
    }
    int l = 0, r = n + 1, ans = 0;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else    r = mid;
    }
    printf("%d\n", ans);
}

F、苹果树

传送戳我

待补