牛客小白月赛24

前排弱弱地说：如果对你有帮助的话，下方求赞QAQ
顺便悄悄的贴一下自己新搭的小破站http://www.kindkidll.com/

A-最短路

数学几何题，不会，卒。

B-组队

题意： $n$ 个数里选若干个数，任意两个数的差值小于等于 $k$ 。

基本思路：滑动窗口--由暴力优化而来。

很容易想到的一种方法是先从小到大排序，然后枚举右端点 $i$ ，由0往右找最小的 $j$ 满足 $a[i]-a[j] \leq k$ ，这样做的时间复杂度是 $O(n^2)$ 的。
考虑一下当 $i$ 已经找到满足要求的 $j$ 时， $i+1$ 还需要从0开始找吗？显然是不需要的，因为 $a[i]-a[j-1]>k$ ，则 $a[i+1]-a[j-1]>k$ ，所以 $i+1$ 只需要从 $j$ 开始即可。滑动窗口每次右端点滑动一位，左端点要滑动若干位来满足条件限制（此题的限制是差值不能超过 $k$ ）。每个点最多被访问两次，时间复杂度 $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int T;
int n, k;
int a[MAXN];
int l, r, ans;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; i++) scanf("%d", &a[i]);
        sort(a, a + n);
        ans = l = r = 0;
        while(r < n) {
            ans = max(ans, r - l + 1);
            r++;//右端点移动
            while(a[r] - a[l] > k) l++;//左端点移动
        }
        printf("%d\n", ans);
    }
    return 0;
}

C-十面埋伏

注意题目中的一个限制：保证地图的边界处不会有士兵。这样我们把士兵看成障碍物，以地图的边界作为起点搜索一遍就可以找出外围的空间，并且在搜索的过程中碰到士兵则需要放置陷阱。如下图所示我们不关心士兵的连通块形成什么样的图案(是否有圈)，我们只关心连通块的外围(上色的部分)，把外围最靠近士兵的部分防止炸弹即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 500 + 117;
const int MAXM = 2e6 + 117;

int n, m;
char s[MAXN][MAXN];
bool vis[MAXN][MAXN];
void dfs(int i, int j) {
    if(i < 1 && i > n) return;
    if(j < 1 && j > m) return;
    if(vis[i][j]) return;
    if(s[i][j] != '.') return;
    vis[i][j] = true;

    if(s[i - 1][j] == '#') s[i][j] = '*';
    if(s[i + 1][j] == '#') s[i][j] = '*';
    if(s[i][j - 1] == '#') s[i][j] = '*';
    if(s[i][j + 1] == '#')  s[i][j] = '*';

    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    dfs(1, 1);
    for(int i = 1; i <= n; i++) puts(s[i] + 1);
    return 0;
}

D-牛妹吃豆子

注意修改和查询不是交替进行而是分开的，且矩阵的规模不会超过2000。

先把问题简化成一维的，考虑一维的怎么做。对于区间更新，我们维护其差分序列将问题转化成点修改，如下图所示：
修改操作完后，我们对差分序列求一遍前缀和即可得到原序列。现在问题剩下区间求和，很显然得到原序列的前缀和序列 $sum$ ，区间 $[l,r]$ 的和为 $sum[r]-sum[l-1]$ 。
如果你能想明白一维的情况，那么二维也能轻松的推出相应的关系。推不出的话可以参照出题人分享的https://www.cnblogs.com/hulean/p/10824752.html。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 117;
const int MAXM = 2e6 + 117;

int n, m, k, q;
LL a[2017][2017];
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &q);
    int x1, y1, x2, y2;
    //维护差分
    while(k--) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        a[x1][y1]++;
        a[x1][y2 + 1]--;
        a[x2 + 1][y1]--;
        a[x2 + 1][y2 + 1]++;
    }
    //得到原来的值
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
        }
    }
    //得到前缀和
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
        }
    }
    //区间查询
    while(q--) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%lld\n", a[x2][y2] + a[x1 - 1][y1 - 1] - a[x2][y1 - 1] - a[x1 - 1][y2]);
    }
    return 0;
}

E-旅旅旅游

图论结论：以1为起点的最短路和以 $n$ 为起点的最短路分别为 $dist1$ 和 $dist2$ ，对于边 $[u,v]$ 若 $dist1[u]+[u,v]+dist2[v]=dist1[n]$ 或 $dist1[v]+[u,v]+dist2[u]=dist1[n]$ ，则该边一定在1到 $n$ 的某条最短路中。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int fa[MAXN];
struct qnode {
    int v;
    LL c;
    qnode(int _v = 0, LL _c = 0): v(_v), c(_c) {}
    bool operator <(const qnode &r)const {
        return c > r.c;
    }
};
struct Edge {
    int u, v;
    LL w;
    int ne;
} edge[MAXM];
int head[MAXN], tot;
void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
    for(int i = 0; i <= n; i++) fa[i] = i;
}
void addedge(int u, int v, LL w) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
bool vis[MAXN];
LL dist1[MAXN], dist2[MAXN];
void dijkstra(int start, LL dist[]) {
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++) dist[i] = (LL)INF * INF;
    priority_queue<qnode> que;
    while(!que.empty()) que.pop();
    dist[start] = 0;
    que.push(qnode(start, 0));
    qnode tmp;
    while(!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i != -1; i = edge[i].ne) {
            int v = edge[i].v;
            LL cost = edge[i].w;
            if(!vis[v] && dist[v] > dist[u] + cost) {
                dist[v] = dist[u] + cost;
                que.push(qnode(v, dist[v]));
            }
        }
    }
}
int get_fa(int i) {
    if(fa[i] == i) return i;
    return fa[i] = get_fa(fa[i]);
}
int main() {
    scanf("%d%d", &n, &m);
    init();
    while(m--) {
        int u, v;
        LL w;
        scanf("%d%d%lld", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    dijkstra(1, dist1);
    dijkstra(n, dist2);
    for(int i = 0; i < tot; i += 2) {
        int u = edge[i].u;
        int v = edge[i].v;
        LL w = edge[i].w;
        if(dist1[u] + w + dist2[v] == dist1[n]) continue;
        if(dist1[v] + w + dist2[u] == dist1[n]) continue;
        fa[get_fa(u)] = get_fa(v);
    }
    int flag = get_fa(1);
    for(int i = 2; i <= n; i++) {
        if(get_fa(i) != flag) {
            flag = -1;
            break;
        }
    }
    if(flag == -1) puts("NO");
    else puts("YES");
    return 0;
}

F-斗兽棋

单判牛妹赢的情况即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

string s, t, ss[7];
int main() {
    ss[0] = "elephant";
    ss[1] = "tiger";
    ss[2] = "cat";
    ss[3] = "mouse";
    ss[4] = "elephant";
    cin >> s >> t;
    for(int i = 0; i < 4; i++) {
        if(t == ss[i]) {
            if(s == ss[i + 1]) puts("tiangou txdy");
            else puts("tiangou yiwusuoyou");
        }
    }
    return 0;
}

G-做题

总的时间是固定的，贪心的选择所需时间少的题目。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;

int n;
LL m;
int a[MAXN];
int main() {
    scanf("%d%lld", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    LL sum = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        if(sum + a[i] > m) break;
        sum += a[i];
        cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

H-人人都是好朋友

手下的编号范围到了 $10^9$ ，但是关系的数量级只有 $10^6$ ，所以需要（离散化==排序+去重）。
注意题目只说朋友的朋友是朋友，但没有说敌人的敌人不是敌人，切记不要自己加条件。
并查集，给每个集合设置一个标记 $fa[]$ ，合并集合的时候合并标记。例如集合 $A=\{a,b,c\}$ ，集合 $B=\{e,d,f\}$ ，现在 $e$ 和 $c$ 是朋友则需要合并两个集合，只需要把 $B$ 指向 $A$ 即可。一般情况下为了方便编码我们初始化每个值得标记为其本身，即 $fa[i]=i$ 。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2210000 + 117;
const int MAXM = 2e6 + 117;

int T;
int n, m, a[MAXN];
int fa[MAXN];
struct node {
    int a, b, c;
} p[MAXN];
void init() {
    for(int i = 0; i <= n * 2; i++) fa[i] = i;
    sort(a, a + n * 2);
    m = unique(a, a + n * 2) - a;
}
int get_hash(int x) {
    return lower_bound(a, a + m, x) - a;
}
bool cmp(node x, node y) {
    return x.c > y.c;
}
int get_fa(int i) {
    if(fa[i] == i) return i;
    return fa[i] = get_fa(fa[i]);
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
            a[i * 2] = p[i].a;
            a[i * 2 + 1] = p[i].b;
        }
        sort(p, p + n, cmp);
        init();
        bool pr = true;
        for(int i = 0; i < n; i++) {
            int u = get_fa(get_hash(p[i].a));
            int v = get_fa(get_hash(p[i].b));
            if(p[i].c == 1) fa[u] = v;
            else if(u == v) {
                pr = false;
                break;
            }
        }
        if(pr) puts("YES");
        else puts("NO");
    }
    return 0;
}

I-求和

神奇的东西--dfs序，如下图所示对树dfs一遍，在dfs的过程中进入某个结点和返回时都进行赋值，则结点 $i$ 的子树为 $[l,r]$ 。
有了dfs序后就可以 $O(1)$ 的得到子树区间，问题转变成一维上的区间修改区间求和，使用线段树即可解决。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e6 + 117;

int n, m, k;
int u, v, w, num;
LL tree[MAXN * 8];
int val[MAXN], ll[MAXN], rr[MAXN];
bool vis[MAXN];
struct Edge {
    int u, v;
    int ne;
} edge[MAXM];
int head[MAXN], tot;
void init() {
    num = 1;
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(vis, false, sizeof(vis));
    memset(tree, 0, sizeof(tree));
}
void addedge(int u, int v) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
void dfs(int id) {
    vis[id] = true;
    ll[id] = num++;
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        if(!vis[edge[i].v]) dfs(edge[i].v);
    }
    rr[id] = num++;
}
void update(int i, int l, int r, int pos, int x) {
    if(l == r) {
        tree[i] += x;
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid) update(i * 2, l, mid, pos, x);
    else update(i * 2 + 1, mid + 1, r, pos, x);
    tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
LL query(int i, int l, int r, int left, int right) {
    if(left <= l && r <= right) return tree[i];
    int mid = (l + r) / 2;
    LL ret = 0;
    if(left <= mid) ret += query(i * 2, l, mid, left, right);
    if(mid < right) ret += query(i * 2 + 1, mid + 1, r, left, right);
    return ret;
}
int main() {
    init();
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(k);
    for(int i = 1; i <= n; i++) update(1, 1, n * 2, ll[i], val[i]);
    while(m--) {
        int op, pos, x;
        scanf("%d%d", &op, &pos);
        if(op == 1) {
            scanf("%d", &x);
            update(1, 1, n * 2, ll[pos], x);
        } else printf("%lld\n", query(1, 1, n * 2, ll[pos], rr[pos]));
    }
    return 0;
}

J-建设道路

$\sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i-a_j)^2\\= \sum_{i = 1}^{n} \sum_{j = 1}^{i-1} (a_i^2-2*a_i*a_j+a_j^2)\\= \sum_{i = 1}^{n} ((n-1)*a_i^2-a_i*((\sum_{j = 1}^{n}a_j)-a_i))$

Markdown的渣渣实在不知道怎么打第三个式子……

第二个式子到第三个式子是把 $2*a_i*a_j$ 拆成两个 $a_i*a_j$ 分给 $i$ 和 $j$ 各一个即可。把总和预处理出来之后第三个式子可以 $O(n)$ 的求值。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 2e6 + 117;

int n;
LL a[MAXN], sum, ans, num;
int main() {
    sum = ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        sum = (sum + a[i]) % mod;
    }
    for(int i = 0; i < n; i++) {
        ans = (ans + (n - 1) * a[i] % mod * a[i] % mod) % mod;
        num = a[i] * ((sum - a[i]) % mod + mod) % mod;
        ans = ((ans - num) % mod + mod) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}