F、斗兽棋

签到题，注意关系就行了，只有在牛妹赢了才输出 $图片说明$ 其余都输出 $图片说明$

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

bool check(string& a, string& b) {
    if (a == "elephant" && b == "tiger")    return true;
    if (a == "tiger" && b == "cat") return true;
    if (a == "cat" && b == "mouse") return true;
    if (a == "mouse" && b == "elephant")    return true;
    return false;
}

int main() {
    js;
    string a, b;
    cin >> a >> b;
    if (check(b, a))    cout << "tiangou txdy" << endl;
    else    cout << "tiangou yiwusuoyou" << endl;
    return 0;
}

G、做题

简单贪心，花费时间越短越先考虑完成，这样就可以使得完成题目数最大。
具体做法就是对 $a$ 数组升序排序，求前缀和，通过pos=lower_bound()查询大于等于m的下标，如果sum[pos]!=m的话，说明sum[pos]>m，输出完成题目数需要减1。

#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 ll read() {
    ll 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 int N = 5e5 + 7;
ll a[N], sum[N];

int main() {
    ll n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + 1 + n);

    //也可以通过直接一个个求前缀和>m  break
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + a[i];
    int pos = lower_bound(sum + 1, sum + 1 + n, m) - sum;
    if (sum[pos] != m)  --pos;
    printf("%d\n", pos);
    return 0;
}

B、组队

对 $a$ 数组升序排序之后，我的做法是选择双游标这里时间复杂度 $图片说明$ ，快排 $图片说明$ 的时间复杂度。总的就是 $图片说明$ 的时间复杂度
对一个下标 $图片说明$ ，假设上次的最大人数是 $图片说明$ 那么下次可能更新答案选项一定在 $图片说明$ 之后。通过判断一步步更新答案。

#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 ll read() {
    ll 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 int N = 2e5 + 7;
ll a[N];

int main() {
    int T = read();
    while (T--) {
        ll n = read(), m = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        sort(a + 1, a + 1 + n);
        int maxi = 1;
        for (int i = 1; i <= n; ++i) {
            int j = i + maxi;
            while (j <= n && a[j] - a[i] <= m)
                ++j;
            maxi = max(maxi, j - i);
        }
        printf("%d\n", maxi);
    }
    return 0;
}

J、建设道路

如果我们朴素的双重循环枚举 $图片说明$ 在这个数据规模稳定 $图片说明$ ，那么想想办法去优化一下，我试着把平方项打开，最后在合并二次项和乘积项，你会发现

全部的平方项都是 $图片说明$ 每一个乘积项从 $图片说明$ 开始提公因子，你会发现 $图片说明$
$图片说明$
所以我们可以通过求前缀和在 $图片说明$ ，再通过取模运算，注意负数的情况。
这样只后时间复杂度就变成快排的 $图片说明$ 了。

#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 ll read() {
    ll 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 int N = 5e5 + 5;
const int MOD = 1e9 + 7;
ll a[N];
ll sum[N];

int main() {
    ll n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        sum[i] = sum[i - 1] + a[i];
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (((n - 1) * a[i] % MOD) * a[i]) % MOD;
        ans -= ((2 * a[i]) % MOD) * ((sum[n] - sum[i]) % MOD) % MOD;
        (ans += MOD) %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

I、求和

树链剖分模板题。一次dfs对整棵树进行重新编号，编号只后可以让任意的一颗子树序号连续，把树形结构变成线性结构，只后再利用线段树，进行单点维护，和区间查询。
这里不知道为什么我数组开1e6MLE，开2e6,A了。。。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define Rint register int
#define mem(a,b) memset(a,(b),sizeof(a))
#define Temp template<typename T>
using namespace std;
typedef long long LL;
Temp inline void read(T& x) {
    x = 0; T w = 1, ch = getchar();
    while (!isdigit(ch) && ch != '-')ch = getchar();
    if (ch == '-')w = -1, ch = getchar();
    while (isdigit(ch))x = (x << 3) + (x << 1) + (ch ^ '0'), ch = getchar();
    x = x * w;
}

#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (1LL*r-l+1)

const int maxn = 2e6 + 7;
int n, m, r;
//见题意
int e, beg[maxn], nex[maxn], to[maxn];
LL w[maxn], wt[maxn];
//链式前向星数组，w[]、wt[]初始点权数组
LL a[maxn << 2];
//线段树数组、lazy操作
int son[maxn], id[maxn], fa[maxn], cnt, dep[maxn], siz[maxn], top[maxn];
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
LL res = 0;
//查询答案

void add(int x, int y) {//链式前向星加边
    to[++e] = y;
    nex[e] = beg[x];
    beg[x] = e;
}
//-------------------------------------- 以下为线段树

void build(int rt, int l, int r) {
    if (l == r) {
        a[rt] = wt[l];
        return;
    }
    build(lson);
    build(rson);
    a[rt] = a[rt << 1] + a[rt << 1 | 1];
}

void query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) { res += a[rt]; return; }
    else {
        if (L <= mid)query(lson, L, R);
        if (R > mid)query(rson, L, R);
    }
}

inline void update(int rt, int l, int r, int L, int R, LL k) {
    if (L <= l && r <= R) {
        a[rt] += k;
    }
    else {
        if (L <= mid)update(lson, L, R, k);
        if (R > mid)update(rson, L, R, k);
        a[rt] = a[rt << 1] + a[rt << 1 | 1];
    }
}
//---------------------------------以上为线段树
LL qSon(int x) {
    res = 0;
    query(1, 1, n, id[x], id[x] + siz[x] - 1);//子树区间右端点为id[x]+siz[x]-1
    return res;
}

void updSon(int x, LL k) {//同上
    update(1, 1, n, id[x], id[x], k);
}

void dfs1(int x, int f, int deep) {//x当前节点，f父亲，deep深度
    dep[x] = deep;//标记每个点的深度
    fa[x] = f;//标记每个点的父亲
    siz[x] = 1;//标记每个非叶子节点的子树大小
    int maxson = -1;//记录重儿子的儿子数
    for (Rint i = beg[x]; i; i = nex[i]) {
        int y = to[i];
        if (y == f)continue;//若为父亲则continue
        dfs1(y, x, deep + 1);//dfs其儿子
        siz[x] += siz[y];//把它的儿子数加到它身上
        if (siz[y] > maxson)son[x] = y, maxson = siz[y];//标记每个非叶子节点的重儿子编号
    }
}

void dfs2(int x, int topf) {//x当前节点，topf当前链的最顶端的节点
    id[x] = ++cnt;//标记每个点的新编号
    wt[cnt] = w[x];//把每个点的初始值赋到新编号上来
    top[x] = topf;//这个点所在链的顶端
    if (!son[x])return;//如果没有儿子则返回
    dfs2(son[x], topf);//按先处理重儿子，再处理轻儿子的顺序递归处理
    for (Rint i = beg[x]; i; i = nex[i]) {
        int y = to[i];
        if (y == fa[x] || y == son[x])continue;
        dfs2(y, y);//对于每一个轻儿子都有一条从它自己开始的链
    }
}

int main() {
    read(n); read(m); read(r);
    for (Rint i = 1; i <= n; i++)read(w[i]);
    for (Rint i = 1; i < n; i++) {
        int a, b;
        read(a); read(b);
        add(a, b); add(b, a);
    }
    dfs1(r, 0, 1);
    dfs2(r, r);
    build(1, 1, n);
    while (m--) {
        int k, x, y;
        read(k);
        if (k == 1) {
            read(x); read(y);
            updSon(x, y);
        }
        else {
            read(x);
            printf("%lld\n", qSon(x));
        }
    }
}

H、人人都是好朋友

并查集+离散化
这个题目数据规模是 $图片说明$ 数据大小是 $图片说明$ 直接开 $图片说明$ 的并查集数组会爆内存，所以我们只能通过离散化处理这样 $图片说明$ 的数组就开的下了。A和B两两各一半。再去一次循环合并朋友关系，第二次循环查询敌人关系，判断是否存在冲突。

#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 int N = 1e6 + 7;
int fa[N << 1];
int a[N], b[N], c[N];
vector<int> p;

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main() {
    int T = read();
    while (T--) {
        int n = read();

        //初始化
        p.clear();
        for (int i = 1; i <= 2 * n; ++i) fa[i] = i;
        for (int i = 1; i <= n; ++i) {
            a[i] = read(), b[i] = read(), c[i] = read();
            p.push_back(a[i]);
            p.push_back(b[i]);
        }

        //离散化
        sort(p.begin(), p.end());
        p.erase(unique(p.begin(), p.end()), p.end()); //去重
        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(p.begin(), p.end(), a[i]) - p.begin() + 1;
            b[i] = lower_bound(p.begin(), p.end(), b[i]) - p.begin() + 1;
        }

        //并查集
        for (int i = 1; i <= n; ++i) {
            if (c[i]) {
                int A = find(a[i]), B = find(b[i]);
                fa[B] = A;
            }
        }
        bool flag = true;
        for (int i = 1; i <= n; ++i)
            if (!c[i]) {
                int A = find(a[i]), B = find(b[i]);
                if (A == B) {
                    flag = false;
                    break;
                }
            }
        if (flag)   puts("YES");
        else    puts("NO");
    }
    return 0;
}

D、牛妹吃豆子

二位前缀和模板题如果对二位前缀和不了解的小伙伴可以康康这个博客戳我
一开始初始化矩阵，读入对应数据 $图片说明$ 对应在区间中，(x1,y1),(x2,y2)对应矩形权值加一，只需要(x1,y1)、(x2+1,y2+1)两点加一，(x1,y2+1)、(x2+1,y1)两点减一。在查询也是类似，不过就是把起始区间-1，终止区间不动。

#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 int N = 2005;
ll a[N][N];

ll calc(int x1, int y1, int x2, int y2) {
    return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}

int main() {
    int n = read(), m = read(), k = read(), q = read();
    for (int i = 1; i <= k; ++i) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        ++a[x1][y1];
        ++a[x2 + 1][y2 + 1];
        --a[x1][y2 + 1];
        --a[x2 + 1][y1];
    }

    // 一次二位前缀和得到真正的矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];

    //第二次求前缀和得到矩阵的前缀和
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];

    while (q--) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        printf("%lld\n", calc(x1, y1, x2, y2));
    }
    return 0;
}

C、十面埋伏

题意比较简单，把连接在一起的士兵围起来就行了，通过一次 $图片说明$ 计算空地上下左右是不是全是士兵，如果上下左右全是士兵，说明这个点不需要放陷阱。
再通过二重循环，如果一个位置上下左右存在一个士兵，并且这个位置是空地，而且上下左右不全是士兵，就把这个位置改成 $图片说明$ 号。
时间复杂度 $图片说明$

#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 int N = 505;
char s[N][N];
bool vis[N][N];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        scanf("%s", s[i] + 1);
    queue<pair<int, int> >    q;
    q.push(make_pair(1, 1));
    while (q.size()) {
        pair<int, int> x = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int xx = x.first + dx[i];
            int yy = x.second + dy[i];

            //防止越界
            if (xx < 1 || yy<1 || xx>n || yy > m)
                continue;

            /*
            防止     #        情况
                   #.#
                    #
            */
            if (s[xx][yy] == '#' || vis[xx][yy])
                continue;
            vis[xx][yy] = true;
            q.push(make_pair(xx, yy));
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1][j] == '#' || s[i][j - 1] == '#' || s[i][j + 1] == '#' || s[i + 1][j] == '#') {
                if (s[i][j] != '#' && vis[i][j])
                    s[i][j] = '*';
            }
            printf("%c", s[i][j]);
        }
        puts("");
    }
    return 0;
}

E、旅旅旅游

$图片说明$ +并查集
题目给出的是无向图，我们可以通过一次正向 $图片说明$ 求到 $图片说明$
一次反向 $图片说明$ 求到 $图片说明$ ，这个时候 $图片说明$
我们选取 $图片说明$ 为最小花费，那么再遍历全部的路，如果这条路的 $图片说明$
或者 $图片说明$ 说明这条路是最短路中的一条，否则把不是最短路中的 $图片说明$ 进行合并，最后统计 $图片说明$ 如果所有 $图片说明$ 在一个集合里面，说明可以不走最短路遍历全部 $图片说明$ 。

#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 int N = 1e5 + 7;
const int M = 5e5 + 7;
const ll INF = 1e18;
int father[N];
int u[M], v[M], w[M];
ll d1[N], d2[N];//d1正向图，d2反向图
struct Node {
    int v;
    ll cost;
    bool operator < (Node b)const {
        return cost > b.cost;
    }
};
vector<Node> e[N];
int n, m;

void dijkstra(int s, ll d[]) {
    priority_queue<Node>  pq;
    fill(d, d + N, INF);
    d[s] = 0;
    pq.push(Node{ s,0 });
    while (!pq.empty()) {
        Node    x = pq.top();
        pq.pop();
        if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过
        for (auto it : e[x.v]) {
            if (d[it.v] > x.cost + it.cost) {
                d[it.v] = x.cost + it.cost;
                pq.push(Node{ it.v,d[it.v] });
            }
        }
    }
}

int find(int x) {
    if (father[x] == x) return x;
    return father[x] = find(father[x]);
}

int main() {
    //dijkstra求一次正向最短路，再求一次反向图
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read(), w[i] = read();
        e[u[i]].push_back(Node{ v[i], w[i] });
        e[v[i]].push_back(Node{ u[i], w[i] });
    }
    dijkstra(1, d1);
    dijkstra(n, d2);
    ll mini = d1[n];

    //建立并查集并且维护
    for (int i = 1; i <= n; ++i)
        father[i] = i;
    int ans = n;
    for (int i = 1; i <= m; ++i) {
        if (d1[u[i]] + d2[v[i]] + w[i] == mini
            || d1[v[i]] + d2[u[i]] + w[i] == mini)
            continue;
        int fa = find(u[i]), fb = find(v[i]);
        if (fa != fb) {
            father[fa] = fb;
            --ans;
        }
    }
    if (ans == 1)printf("YES\n");
    else printf("NO\n");
    return 0;
}

A、最短路

待补

【非官方题解】牛客小白月赛24