XCPC 寒假集训班 D4 个人笔记

Coast23
  2025-01-16 20:38:31 2025-01-16 20:38:31 创建   2025-03-31 17:38:37 2025-03-31 17:38:37 更新    4.1k 字  20 分钟  

集训题

A - 单词查找树

传送门

建一棵Trie, 求Trie的结点数.

太裸了, 而且题目把做法也讲的很清楚了, 就算没学过Trie也能直接模拟做出来.

介绍一下Trie(字典树):

Trie简介

Trie是一种用于实现字符串快速检索的多叉树, 它的每个结点都有若干字符指针. 如果在插入或检索的时候扫描到字符c, 就沿着该结点的c字符指针走到下一层结点, 就像题目里那张图.

初始化

空Trie仅有一个根结点, 其所有指针都指向空.
其定义为trie[SIZE][C], SIZE为结点个数, C为字符集大小.

插入

插入一个字符串时, 从根结点开始扫描字符串, 如果遇到一个字符c, 就沿着该结点的c字符指针走到下一层结点, 如果该结点的c字符指针为空, 就创建新的结点, 并将其指针指向空. 重复这个过程直到字符串扫描完毕.

当插入完最后一个字符时, 可以在该结点上做一个结尾标记, 表示从根结点到这里是一个完整单词.

检索

若要检索字符串S是否在Trie中, 就和插入一样遍历Trie, 当且仅当Trie中存在这样的字符路径, 且最后一个结点上有结尾标记, 才说明存在.

代码实现:

#define SIZE 32005
int trie[SIZE][27], tot = 1; // 结点个数(编号). 1是根结点.
bool end[SIZE];
void insert(char *str){ // 插入字符串
    int p = 1; // 指向根结点
    for(int i = 0; str[i]; ++i){
        int ch = str[i] - 'A';
        if(!trie[p][ch]) trie[p][ch] = ++tot; // 若该结点的ch指针为空, 则创建新结点
        p = trie[p][ch]; // 指向下一层结点
    }
    end[p] = 1; // 标记结尾
}

bool search(char *str){ // 检索字符串是否存在
    int p = 1; // 指向根结点
    for(int i = 0; str[i]; ++i){
        int ch = str[i] - 'A';
        if(!trie[p][ch]) return 0; // 若该结点的ch指针为空, 则不存在
        p = trie[p][ch]; // 指向下一层结点
    }
    return end[p]; // 若最后一个结点有结尾标记, 则存在
}

这道题并未要求我们实现Trie的检索操作. 只需要不断插入字符串, 最后输出tot即可.

AC Code:

#include <cstdio>
#include <ctype.h>

#define SIZE 32005
int trie[SIZE][27], tot = 1;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

void insert(char *str){
    int p = 1;
    for(int i = 0; str[i]; ++i){
        int ch = str[i] - 'A';
        if(!trie[p][ch]) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
}

int main(){
    char str[100];
    while(~scanf("%s", str)) insert(str);
    printf("%d\n", tot);
    return 0^(0-0)^0;
}

B - Dropping Balls

传送门

很容易想到依题意模拟, 设t[p]表示第p个结点的状态, 把第个球到第个球一个一个放到树里, 就能得到第个球停止时的叶子序号.

Code:

#include <cstdio>
#include <ctype.h>
#include <cstring>

int T, n, d;
bool t[2 << 21];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    T = read();
    while(T--){
        d = read(), n = read();
        memset(t, 0, sizeof(t));
        int p;
        for(int i = 1; i <= n; ++i){ // 第几个小球
            p = 1;
            for(int j = 1; j < d; ++j){
                // 第几层
                if(!t[p]) t[p] = 1, p = p << 1;
                else t[p] = 0, p = p << 1 | 1;
            }
        }
        printf("%d\n", p);
    }
    T = read();
    return 0;
}

这份代码的时间复杂度为, TLE.

思考一下就能发现, 我们其实不需要通过模拟前个小球来判断第个球下落前所有结点的状态. 可以直接由的奇偶性确定当前结点的状态:

  • 每个结点的状态仅由经过它的小球个数的奇偶性决定. 奇数小球往左走, 偶数小球往右走.
  • 如果第个小球到达这个点, 它会是接下来向左走的第个小球.
  • 如果第个小球到达这个点, 它会是接下来向右走的第个小球.

我们就可以由此得出第个小球的下落过程:

  • 如果为奇数, 则令, 并往左走.
  • 如果为偶数, 则令, 并往右走.
  • 直到走到第层, 输出结点编号, 结束.

此外, 还要知道一棵按层序编号的二叉树(题目画的那样), 结点的左儿子为, 右儿子为.

时间复杂度.

AC Code:

#include <cstdio>
#include <ctype.h>

int T, D, I;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    T = read();
    while(T--){
        D = read(), I = read();
        int p = 1; // 当前结点编号
        for(int i = 1; i < D; ++i){ // 因为1本来就占一层, 接下来只要往下掉D-1层 
            if(I & 1) p = p << 1, I = (I + 1) >> 1; // 往左走
            else p = p << 1 | 1, I = I >> 1; // 往右走
        }
        printf("%d\n", p);
    }
    T = read(); // 读不读这个-1无所谓.
    return 0;
}

C - 医院设置

传送门

注意到, 无脑暴力, 枚举每个点作为医院, 遍历整颗树统计距离.

AC Code:

#include <cstdio>
#include <ctype.h>
#include <cstring>

#define N 100005

int n, tot;
int ver[N], nxt[N], head[N];
int val[N];
bool vis[105];
long long tmp, ans = 1145141919LL;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

void add(int x, int y){
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

void dfs(int u, long long dis){
    tmp += dis * val[u]; // 累计距离
    vis[u] = 1;
    for(int i = head[u]; i; i = nxt[i]){
        if(!vis[ver[i]]) dfs(ver[i], dis + 1);
    }
}

int main(){
    n = read();
    for(int i = 1; i <= n; ++i){
        val[i] = read();
        int l = read(), r = read();
        if(l) add(i, l), add(l, i); // 如果有左儿子, 就连双向边
        if(r) add(i, r); add(r, i); // 如果有右儿子, 就连双向边
    }
    for(int i = 1; i <= n; ++i){ // 枚举每个点作为起点
        tmp = 0; memset(vis, 0, sizeof(vis)); // 记得重置状态
        dfs(i, 0);
        ans = ans > tmp? tmp : ans; // 更新答案
    }
    printf("%lld\n", ans);
    return 0;
}

D - 畅通工程续

HDU传送门

单源最短路板子, 一开始没注意到结点编号为~, 吃了个罚时…

记得多测要清空.

AC Code:

#include <bits/stdc++.h>
#define int long long
#define N 40005
#define M 40005
#define inf 1145141919810LL

int n, m, s, t, tot;
int ver[N], edge[M], nxt[M], head[N], d[N];
bool vis[N];

void add(int x, int y, int z){ 
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

void dijkstra(int s){
    std::priority_queue<std::pair<int, int> > q;
    for(int i = 0; i < n; ++i) d[i] = inf;
    d[s] = 0; q.push({0, s});
    while(q.size()){
        int x = q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i; i = nxt[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}

signed main(){
//    n = read(), m = read();
//    freopen("1.c", "r", stdin);
    while(~scanf("%d%d", &n, &m)){
        memset(ver, 0, sizeof ver);
        memset(edge, 0, sizeof edge);
        memset(nxt, 0, sizeof nxt);
        memset(head, 0, sizeof head);
        memset(vis, 0, sizeof vis);
        tot = 0;
        for(int i = 1; i <= m; ++i){
            int x = read(), y = read(), z = read();
            add(x, y, z);
            add(y, x, z);
        }
        s = read(), t = read();
        dijkstra(s);
        printf("%lld\n", d[t] == inf ? -1: d[t]);
    }
    return 0;
}

E - Cow Contest S

传送门

把每头奶牛视为顶点, 把奶牛的强弱关系看成边: 若强于, 则在图中连一条指向的边.

而奶牛x的排名确定, 意味着x和其它奶牛都有明确的强弱关系, 在图中的表现就是x和其它顶点都连通.

这句话反过来更好理解, 如果x和y的强弱关系不明确, 也就是在x和y在图中不连通, 那怎么知道x和y谁排在前?

问题转化为判顶点间的连通性, 这个做法就很多了, 可以DFS或BFS遍历图 (最短路算法同样适用), 最简单的写法是用Floyd做传递闭包. (毕竟, 随便搞都能过)

AC Code:

#include <cstdio>
#include <ctype.h>
#include <cstring>

#define N 105

int n, m, ans;
int f[N][N];

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read();
        f[x][y] = 1;
    }
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                f[i][j] |= f[i][k] & f[k][j];
    for(int i = 1; i <= n; ++i){
        bool flag = 1;
        for(int j = 1; j <= n; ++j){
            if(i != j && !f[i][j] && !f[j][i]){flag = 0; break;} // 不连通, flag置0并跳出.
        }
        ans += flag;
    }
    printf("%d\n", ans);
    return 0;
}

F - 单源最短路径（标准版）

传送门

板子题, 不多解释, 用Dijkstra算法.

AC Code:

#include <bits/stdc++.h>
#define int long long
#define N 2000005
#define M 20000005
#define inf 1145141919810LL

int n, m, s, tot;
int ver[N], edge[M], nxt[M], head[N], d[N];
bool vis[N];

void add(int x, int y, int z){ 
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

void dijkstra(int s){
    std::priority_queue<std::pair<int, int> > q;
    for(int i = 1; i <= n; ++i) d[i] = inf;
    d[s] = 0; q.push({0, s});
    while(q.size()){
        int x = q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = head[x]; i; i = nxt[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}

signed main(){
    n = read(), m = read(), s = read();
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read();
        add(x, y, read());
    }
    dijkstra(s);
    for(int i = 1; i <= n; ++i) printf("%lld ", d[i] == inf? (1LL << 31) - 1 : d[i]);
    return 0;
}

G - 香甜的黄油 Sweet Butter

传送门

和C题很像, 不过这次给的不是树了, 没办法直接DFS遍历求出最短路了, 需要用Dijkstra或SPFA求最短路.

做法就是枚举每个牧场放糖, 求出有牛的牧场.

Subtask #1的数据很大, inf设为0x3f3f3f3f会WA, 改成0x7f7f7f7f过了.

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>
#include <cstring>

#define N 805
#define M 3000
#define inf 0x7f7f7f7f

int n, p, c, tot, ans = inf;
int cow[N];
int head[N], nxt[M], ver[M], edge[M], d[N];
bool vis[N];

void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

void dijkstra(int s){
    std::priority_queue<std::pair<int, int> > q;
    memset(d, 0x7f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[s] = 0; q.push({0, s});
    while(q.size()){
        int x = q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = head[x]; i; i = nxt[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}

int main(){
    n = read(), p = read(), c = read();
    for(int i = 1; i <= n; ++i) cow[i] = read();
    for(int i = 1; i <= c; ++i){
        int x = read(), y = read(), z = read();
        add(x, y, z); add(y, x, z);
    }
    for(int i = 1; i <= p; ++i){
        dijkstra(i);
        int sum = 0;
        for(int j = 1; j <= n; ++j) sum += d[cow[j]];
        ans = ans > sum? sum : ans;
    }
    printf("%d\n", ans);
    return 0^(0-0)^0;
}

H - 最短路计数

传送门

稍微修改一下Dijkstra算法的松弛过程.

  • 如果, 则的最短路数量要加上的最短路数量.
  • 如果, 则的最短路要更新为, 且到的最短路数量就是到的最短路数量.

如果理解Dijkstra算法, 就能明白这个做法的正确性.

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>
#include <cstring>

#define N 1000006
#define M 4000006
#define mod 100003
#define inf 0x7f7f7f7f

int n, m, tot, ans = inf;

int head[N], nxt[M], ver[M], d[N], cnt[N];
bool vis[N];

void add(int x, int y){
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

void dijkstra(int s){
    std::priority_queue<std::pair<int, int> > q;
    memset(d, 0x7f, sizeof(d));
    d[s] = 0; cnt[s] = 1;
    q.push({0, s});
    while(q.size()){
        int x = q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = head[x]; i; i = nxt[i]){
            int y = ver[i];
            if(d[y] == d[x] + 1) cnt[y] = (cnt[y] + cnt[x]) % mod;
            if(d[y] > d[x] + 1){
                d[y] = d[x] + 1;
                cnt[y] = cnt[x];
                q.push({-d[y], y});
            }
        }
    }
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    dijkstra(1);
    for(int i = 1; i <= n; ++i) printf("%d\n", cnt[i] % mod);
    return 0^(0-0)^0;
}

I - 加工零件

传送门

首先, 如果号工人和号工人有一条长为的路径, 且刚好为, 那号工人肯定是要提供原材料的.

如果为呢?

我们假设路径长这样子:

那么,需要生产阶段的零件, 他就要求生产阶段的零件, 最后号工人就要提供这个阶段的原材料了…

以此类推, 如果为, 那么号工人就需要提供原材料.

同样地容易验证, 如果不存在一条路径=, 那么号工人就不需要提供原材料.

于是乎, 问题就转变为: 判断和间是否存在一条路径, 路径长满足: ① 和奇偶性相同 ② 长度不大于.

课上学长介绍了分层建图的做法, 我的做法是用BFS分别计算每个点到的最小奇偶路径长度.

AC Code:

#include <queue>
#include <cstdio>
#include <ctype.h>
#define N 200005
#define inf 0x3f3f3f3f

int n, m, q, tot;
int ver[N], nxt[N], head[N];
bool vis[N];

int d1[N], d2[N];
// d1: 奇数路径. d2: 偶数路径

void add(int x, int y){
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f ? x : -x;
}

void bfs(int s){
    std::queue<std::pair<int, int> > q;
    for(int i = 1; i <= n; ++i) d1[i] = d2[i] = inf;
    for(int i = head[s]; i; i = nxt[i]){
        d1[ver[i]] = 1;
        q.push({1, ver[i]});
    } // 把和s距离为1的点先加入队
    while(q.size()){
        int x = q.front().second, dis = q.front().first; q.pop();
        // x为起点, dis为1到x的最小距离
        for(int i = head[x]; i; i = nxt[i]){
            int y = ver[i];
            if(dis & 1 && d2[y] > d1[x] + 1){ // 如果是奇数路径, 那么再经过一条边就变成偶数路径, 所以用d1[x] + 1来更新d2[y]
               d2[y] = d1[x] + 1;
               q.push({d2[y], y});
            }
            if(!(dis & 1) && d1[y] > d2[x] + 1){ // 理由同上
                d1[y] = d2[x] + 1;
                q.push({d1[y], y});
            }
        }
    }
}

int main(){
    n = read(), m = read(), q = read();
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    bfs(1);
    while(q--){
        int a = read(), l = read();
        if(l & 1) puts(d1[a] <= l? "Yes" : "No");
        else puts(d2[a] <= l? "Yes" : "No");
    }
    return 0;
}

J - 阿狸和桃子的游戏

传送门

题目看起来很唬人, 但想做出这题只需要发现: 边权均分给个端点不会影响二人得分之差.

我们分类讨论来说明这个结论的正确性:

证明: 边权均分给个端点不会影响二人得分之差

如图,和为点权,为边权.

  • 甲染了和, 显然得分差, 结论成立.

  • 乙染了和, 显然得分差, 结论成立.

  • 甲染了, 乙染了, 依题意无人获得的分数, 得分差=, 结论成立.

  • 乙染了, 甲染了, 依题意无人获得的分数, 得分差=, 结论成立.

所以, 直接把边权摊给点权, 然后两个人每次都贪心选择最大点权, 作差即得答案.

通过将输入的点权乘以来避免除法.

AC Code:

#include <cstdio>
#include <ctype.h>
#include <algorithm>

#define N 10005

int n, m;
long long a[N];
long long ans;

int read(){
    int x = 0, f = 1; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) f ^= (ch == '-');
    for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch xor 48);
    return f? x : -x;
}

int main(){
    n = read(); m = read();
    for(int i = 1; i <= n; ++i) a[i] = read() << 1;
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read(), v = read();
        a[x] += v, a[y] += v;
    }
    std::stable_sort(&a[1], &a[n+1]);
    for(int i = n; i; i -= 2) ans += a[i] - a[i-1];
    printf("%lld\n", ans >> 1);
    return 0;
}
  • 标题: XCPC 寒假集训班 D4 个人笔记
  • 作者: Coast23
  • 创建于 : 2025-01-16 20:38:31
  • 更新于 : 2025-03-31 17:38:37
  • 链接: https://coast23.github.io/2025/01/16/XCPC-寒假集训班-D4-个人笔记/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
XCPC 寒假集训班 D4 个人笔记
  1. 集训题
    1. A - 单词查找树
    2. B - Dropping Balls
    3. C - 医院设置
    4. D - 畅通工程续
    5. E - Cow Contest S
    6. F - 单源最短路径（标准版）
    7. G - 香甜的黄油 Sweet Butter
    8. H - 最短路计数
    9. I - 加工零件
    10. J - 阿狸和桃子的游戏