2024年ICPC贵州省赛题解

2024贵州省赛题解

A. 破解住宿信息

简单判断。输入字符串含空格，整行输入。

string s;
getline(cin,s);
int sum=0,x;
x=s.find("GZU");
while(x!=-1){
    sum++;
    x=s.find("GZU",x+1);
}
if(sum==0) cout<<"yezhulin";
else if(sum%2) cout<<"heshangpo";
else cout<<"qingrenpo";

B. 小帅的车费

分层图最短路模板题。直接建立 k+1 层图，层与层间依次用打折后的边权相连。跑一遍 Dijkstra 即可。

C. 细胞的合并

数据量为 \(2000^2=4e6\)，暴力枚举细胞是否相连，相连就并查集加入。

D. 还在排队的人

双端队列的模拟，使用 deque 直接秒。

E. 打怪兽

二分 + 尺取法。二分 damage，在 check 函数中计算所需最少次数。维护一段数组存放造成伤害的下标，如果某造成伤害下标对当前第 i 处造成不了伤害，左指针前移。

F. 关灯

暴力枚举最大长度 len。每次操作使 \([i,i+k-1]\) 内的数都减一，利用差分数组实现。需要考虑负数取模的影响。

G. 小帅的骰子

模拟两次投出来的结果，然后判断满足条件的可能结果有多少种，求最大公因数约分即可。

H. 粉刷匠小帅

线段树，待学习。

I. 寻找宝藏数

数位 DP。先利用质数筛预处理出所有 4 位合数。设 \(dp[N][i][j][k]\) 表示最高位为 i、次高位为 j、第三位为 k 的 N 位宝藏数的个数。时间复杂度 \(O(n*10^4)\)。

J. 数字游戏

设删掉一个数字及其生成的所有数字所需要的次数的奇偶性为 f[x]。通过打表观察到只有 f[1]=1，其余为 0。所以只需要统计数字 1 的个数的奇偶性即可。

K. 最好的好朋友活动

若 a[i] 是负数，则在 b 数组中找一个最小的负数，负负得正则乘积最大；反之正数找最大正数。时间复杂度 \(O(max(n,m))\)。

L. GZU的建筑

字典树 + 树上启发式合并（dsu on tree），待学习。

M. 递增的鸭鸭

离散化 + DP + 组合计数。DP 状态：\(dp[j]\) = 前 j 只鸭子的合法方案数。遍历所有离散段，在每个段上使用隔板法（C(n+r-l, n)）更新状态。

N. 乐乐爱购物

莫比乌斯反演，待学习。