牛客小白月赛27

个人博客：http://www.kindkidll.com/index.php/archives/156

A-巨木之森

知识点：树的直径

• 求出从每个点出发遍历完块区域的最短路程，排序后贪心选择最短路程小的点。
• 从一个点出发遍历完个点并返回起点，要经过每条边两次，现在不返回起点则最短路的终点应该是距离起点最远的点，最短路程等于所有边长度之和的两倍减去起点到其最远点的距离。
• 树上距离一个点最远的点一定是树的直径的端点之一，详见博客树的直径。
• 通过两遍搜索可以得到直径两端点到其余点的距离，即可求出从每个点出发遍历完块区域的最短路程。

#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;
LL m;
int l, r;// 直径的端点
int head[MAXN], tot;
LL sum, dist[MAXN][2], ans[MAXN];
struct Edge {
    int v, ne;
    LL w;
} edge[MAXN];
void init() {
    l = r = sum = tot = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, LL w) {
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
void dfs(int id, int root, int flag) {
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        if(edge[i].v != root) {
            dist[edge[i].v][flag] = dist[id][flag] + edge[i].w;
            dfs(edge[i].v, id, flag);
        }
    }
}
int main() {
    scanf("%d%lld", &n, &m);
    init();
    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);
        sum += w;
    }

    dfs(1, 0, 0);
    for(int i = 1; i <= n; i++)
        if(dist[l][0] < dist[i][0]) l = i;

    dist[l][0] = 0;
    dfs(l, 0, 0);
    for(int i = 1; i <= n; i++)
        if(dist[r][0] < dist[i][0]) r = i;

    dfs(r, 0, 1);
    for(int i = 1; i <= n; i++) ans[i] = sum * 2 - max(dist[i][0], dist[i][1]);
    sort(ans + 1, ans + n + 1);

    int i;
    LL t;
    for(i = 1, t = 0; i <= n; i++) {
        t += ans[i];
        if(t > m) break;
    }
    printf("%d\n", i - 1);
    return 0;
}

B-乐***对

知识点：、贪心

将从小到大排序后，设表示前个乐手可以组成的乐团数，有状态转移方程：

• 若，则。
• 否则，，优先选择能力值大的组成乐团。

#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;
int a[MAXN], dp[MAXN], num[MAXN];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        if(i < a[i]) dp[i] = 0;
        else dp[i] = num[i - a[i]] + 1;
        num[i] = max(num[i - 1], dp[i]);
    }
    printf("%d\n", dp[n] == 0 ? -1 : dp[n]);
    return 0;
}

C-光玉小镇

知识点：状态压缩

• 直接搜索复杂度太高，考虑关键点最多只有15个，对关键点进行建图后两两之间跑得到最短时间。
• 对关键点建图后直接搜索复杂度还是太高，考虑状态压缩。设表示在状态时最后一个修理好电线杆所需的最短时间，状态表示二进制上为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 = 1e6 + 117;

int n, m;
LL t;
LL dp[1 << 16][17], ans;

char ma[207][207];
int sx, sy, tot;
struct pole {
    int x, y;
} T[17];

struct node {
    int x, y, step;
} now, ne;
bool vis[207][207];
int dx[4] = { -1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
LL dist1[17], dist2[17][17];
bool check(node a) {
    if(a.x < 0 || a.x >= n) return false;
    if(a.y < 0 || a.y >= m) return false;
    if(ma[a.x][a.y] == '#') return false;
    if(vis[a.x][a.y]) return false;
    vis[a.x][a.y] = true;
    return true;
}
LL bfs(int sx, int sy, int ex, int ey) {
    memset(vis, false, sizeof(vis));
    queue<node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = true;
    while(!q.empty()) {
        now = q.front();
        q.pop();
        if(now.x == ex && now.y == ey) return now.step;
        for(int i = 0; i < 4; i++) {
            ne.x = now.x + dx[i];
            ne.y = now.y + dy[i];
            ne.step = now.step + 1;
            if(check(ne)) q.push(ne);
        }
    }
    return -1;
}
int main() {
    scanf("%d%d%lld", &n, &m, &t);
    for(int i = 0; i < n; i++) scanf("%s", ma[i]);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(ma[i][j] == 'S') sx = i, sy = j;
            if(ma[i][j] == 'T') {
                T[tot].x = i;
                T[tot++].y = j;
            }
        }
    }

    //关键点建图
    memset(dp, INF, sizeof(dp));
    for(int i = 0; i < tot; i++) {
        dist1[i] = bfs(sx, sy, T[i].x, T[i].y);
        dp[1 << i][i] = dist1[i];
        if(dist1[i] == -1) {
            puts("-1");
            return 0;
        }
    }
    for(int i = 0; i < tot; i++) {
        for(int j = 0; j < tot; j++) {
            dist2[i][j] = bfs(T[i].x, T[i].y, T[j].x, T[j].y);
        }
    }

    //状态i向状态i|j转移
    for(int i = 0; i < (1 << tot); i++) {
        for(int j = 0; j < tot; j++) {
            if(i & (1 << j)) continue;//j已被修理
            for(int k = 0; k < tot; k++) {
                if((i & (1 << k)) == 0) continue;//k未被修理无法从k转移到j
                dp[i | 1 << j][j] = min(dp[i | 1 << j][j], dp[i][k] + dist2[k][j]);
            }
        }
    }

    ans = (LL)INF * INF;
    for(int i = 0; i < tot; i++) ans = min(ans, dp[(1 << tot) - 1][i] + dist1[i] + tot * t);
    printf("%lld\n", ans);
    return 0;
}

D-巅峰对决

知识点：线段树

题目数据保证任何时候个数字均互不相同，则当区间满足时区间内的数字是连续的，多次修改和查询使用线段树维护，详见博客线段树从零开始。

#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, q;
int x, op;
struct node {
    LL minnum;
    LL maxnum;
} tree[MAXN];
void init() {
    for(int i = 0; i < MAXN; i++) {
        tree[i].minnum = INF;
        tree[i].maxnum = -INF;
    }
}
void to_up(int i) {
    tree[i].minnum = min(tree[i * 2].minnum, tree[i * 2 + 1].minnum);
    tree[i].maxnum = max(tree[i * 2].maxnum, tree[i * 2 + 1].maxnum);
}
void update(int i, int l, int r, int p, LL x) {
    if(l == r) {
        tree[i].minnum = tree[i].maxnum = x;
        return;
    }
    int mid = (l + r) / 2;
    if(p <= mid) update(i * 2, l, mid, p, x);
    else update(i * 2 + 1, mid + 1, r, p, x);
    to_up(i);
}
node require(int i, int l, int r, int left, int right) {
    if(left <= l && r <= right) {
        return tree[i];
    }

    node ret, ll, rr;
    ret.minnum = INF;
    ret.maxnum = -INF;
    int mid = (l + r) / 2;
    if(left <= mid) {
        ll = require(i * 2, l, mid, left, right);
        ret.minnum = min(ret.minnum, ll.minnum);
        ret.maxnum = max(ret.maxnum, ll.maxnum);
    }
    if(right > mid) {
        rr = require(i * 2 + 1, mid + 1, r, left, right);
        ret.minnum = min(ret.minnum, rr.minnum);
        ret.maxnum = max(ret.maxnum, rr.maxnum);
    }
    return ret;
}
int main() {
    init();
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &x);
        update(1, 1, n, i, x);
    }

    while(q--) {
        int l, r;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1) update(1, 1, n, l, r);
        else {
            node now = require(1, 1, n, l, r);
            if(now.maxnum - now.minnum == r - l) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

E-使徒袭来

知识点：数论

基本不等式：。

#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;
int main() {
    scanf("%d", &n);
    printf("%.3f\n", 3 * pow(n, 1.0 / 3));
    return 0;
}

F-核弹剑仙

知识点：搜索

根据武器破坏力的强弱建图，对每个武器搜索一遍比它破坏力大的有多少。

注：出题人题解使用了bitset+拓扑排序，效率更高。

#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 u, v, cnt;
bool vis[1017];
int a[1017][1017];
void dfs(int i) {
    for(int j = 1; j <= n; j++) {
        if(a[i][j] && !vis[j]) {
            vis[j] = true;
            cnt++;
            dfs(j);
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    while(m--) {
        scanf("%d%d", &u, &v);
        a[v][u] = 1;
    }
    for(int i = 1; i <= n; i++) {
        memset(vis, false, sizeof(vis));
        vis[i] = true;
        cnt = 0;
        dfs(i);
        printf("%d\n", cnt);
    }
    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 = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
char s[MAXN * 10];
int cnt[999];
int main() {
    scanf("%d%s", &n, s);
    for(int i = 0; i < n; i++) cnt[s[i]]++;
    int ans = min(cnt['i'], cnt['n']);
    ans = min(ans, cnt['g']);
    if(ans > cnt['k'] * 2) ans = cnt['k'] * 2;
    printf("%d\n", ans);
    return 0;
}

H-社团游戏

知识点：二维前缀和、二分

二维前缀和预处理出每种小写字母的数量，枚举左上角并二分边长判断是否满足条件。

#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, kk;
char s[507][507];
int a[507][507][27];
bool check(int i, int j, int len) {
    int x = i + len, y = j + len;
    for(int k = 0; k < 27; k++) {
        int num = a[x][y][k] - a[i - 1][y][k] - a[x][j - 1][k] + a[i - 1][j - 1][k];
        if(num > kk) return false;
    }
    return true;
}
int main() {
    scanf("%d%d%d", &n, &m, &kk);
    for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k < 27; k++)
                a[i][j][k] = a[i - 1][j][k] + a[i][j - 1][k] - a[i - 1][j - 1][k];
            a[i][j][s[i][j] - 'a']++;
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int l = 0, r = min(n - i, m - j);
            while(l <= r) {
                int mid = (l + r) / 2;
                if(check(i, j, mid)) l = mid + 1;
                else r = mid - 1;
            }
            printf("%d ", r + 1);
        }
        putchar(10);
    }
    return 0;
}

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 = 1e7 + 117;
const int MAXM = 1e6 + 117;

int n, k;
LL a[MAXN], b, c, ans;
int l1, r1, l2, r2;// l1队头,r1-1队尾
int q1[MAXN], q2[MAXN];// q1最大值,q2最小值
int main() {
    scanf("%d%lld", &n, &k);
    scanf("%lld%lld%lld", &a[0], &b, &c);
    for(int l = 1, r = 1; r <= n; r++) {
        a[r] = (a[r - 1] * b + c) % 1000000000;

        while(l1 < r1 && a[q1[r1 - 1]] <= a[r]) r1--; //当前值不小于队尾，队尾出队
        q1[r1++] = r;

        while(l2 < r2 && a[q2[r2 - 1]] >= a[r]) r2--; //当前值不大于队尾，队尾出队
        q2[r2++] = r;

        while((a[q1[l1]] - a[q2[l2]]) > k) {
            ans += n - r + 1;
            l++;
            while(q1[l1] < l) l1++;//队头不在区间内，队头出队
            while(q2[l2] < l) l2++;//队头不在区间内，队头出队
        }
    }
    printf("%lld\n", ans);
    return 0;
}

J-逃跑路线

知识点：位运算

因为，所以次操作后的结果只与每次操作的个位有关。

#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;
char s[MAXN];
int main() {
    scanf("%d", &n);
    int sum = 0;
    while(n--) {
        scanf("%s", s);
        int len = strlen(s);
        sum += s[len - 1] - '0';
    }
    printf("%d\n", sum % 2);
    return 0;
}