RC-u1 不要浪费金币
哲哲最近在玩一个游戏，击杀怪物能获得金币 —— 这里记击杀第 i 个怪物获得的金币数量为 Pi。
然而这个游戏允许拥有的金币数量是有上限的，当超过时，超过上限的部分就会被系统光明正大地吃掉，哲哲就拿不到了。
为了不浪费金币，哲哲决定，当下一个要击杀的怪物可获得的金币会导致自己拥有的金币数量超过上限时，就去消费一次，把自己已有的金币全部用完。
现在给定哲哲将要击杀的一系列怪物对应的金币数量，请你计算一下哲哲去消费了几次。
输入格式:
输入第一行是两个整数 N,M （1≤N≤103,1≤M≤106），表示击杀的怪物数量以及系统允许拥有金币数量的上限。
接下来一行是由空格隔开的 N 个数 Pi（i=1,⋯,N），依次表示击杀第 i 个怪物能获得的金币数量。假设哲哲是按输入顺序击杀怪物的，并且每个 Pi 都是 不超过 106 的非负整数。
输出格式:
在一行中输出哲哲去消费的次数。
输入样例:
10 10
1 2 3 4 1 2 3 5 11 1
输出样例:
4
样例解释：
消费时间点为：第四个怪物击杀后、第七个怪物击杀后、第八个怪物击杀后、第九个怪物击杀后。
解题：模拟
思路
根据题意模拟即可。
代码
#include <iostream>
using namespace std;
int main() {
int N, M;
scanf("%d%d", &N, &M);
int coin, total = 0, count = 0;
while (N--) {
scanf("%d", &coin);
if (total + coin > M) {
++count;
total = 0;
}
total += coin;
}
printf("%d", count);
return 0;
}
RC-u2 智能服药助手
智能看护中很重要的环节是安排需要服药的老年人的服药计划。
已知机器人需要照顾的某位老年人需要服用 N 种药物，但某些药物不宜间隔过短服用 —— 比如降糖药一般遵医嘱日服 3 次，两次之间需要间隔至少 4 小时。当需要服用的药物比较多，医嘱比较复杂时，如何保证每位老人的服药计划是安全合理的，就成为一个挑战。
本题给定一套服药计划，请你检查一下计划是否存在问题。
输入格式:
输入第一行给出两个整数 N,M（1≤N,M≤103），表示老人需要服用 N 种药物（药物种类从 1 到 N 编号），对应的服药计划有 M 条记录。
接下来首先在一行中给出 N 个用空格隔开的整数 Ti （−1≤*Ti*≤100,Ti!=0)，表示编号为 i 的药物需要间隔至少 Ti 个单位时间服用。如果 Ti 为 −1，则说明这种药物没有间隔要求。
接下来的 M 行，每行给出一条服药计划中的记录，格式为：首先给出两个非负整数 t 和 k (0≤t≤109,0≤k≤N)，表示服药的时刻为 t，服用了 k 种药物；然后紧接着列出 k 个数，每个数对应 t 时刻要吃的药物种类的编号。一行中的数字之间以空格分隔。
题目保证：记录按照服药时刻 t 的递增顺序给出；每一时刻服用的药物种类各不相同。注意：同一种药物可能需要在不同的时刻重复服用。如果一位老人在 ti 时刻和 tj 时刻服用了同一种药物，则他服用的间隔时间为 ∣*ti−tj*∣。
输出格式:
按照输入顺序检查每一条记录中的每一种药物。如果在 Y 时刻不宜服用药物 X，则在一行中输出：
Don't take X at Y!
注意：老人收到提醒后会按照提醒不服用指定的药物。
输入样例:
10 6
1 2 3 4 5 -1 -1 -1 -1 -1
0 1 1
1 2 1 2
2 1 2
3 2 1 3
5 3 1 3 4
6 2 1 4
输出样例:
Don't take 2 at 2!
Don't take 3 at 5!
Don't take 4 at 6!
解题：模拟
思路
也是模拟，注意点：要保证第一次吃药时间被记录而不是误判为间隔过小，需要把上一次吃药时间数组(prev)初始化为一个很小的值，这里我给的是 0x3f3f3f3f (109级别)。
代码
#include <iostream>
using namespace std;
int main() {
int N, M;
scanf("%d%d", &N, &M);
int intervals[N + 1], prevs[N + 1];
fill(prevs, prevs + N + 1, -0x3f3f3f3f);
for (int i = 1; i <= N; i++) scanf("%d", &intervals[i]);
int t, k, med;
while (M--) {
scanf("%d%d", &t, &k);
while (k--) {
scanf("%d", &med);
if (intervals[med] == -1) continue;
if (t - prevs[med] < intervals[med]) {
printf("Don't take %d at %d!\n", med, t);
} else prevs[med] = t;
}
}
return 0;
}
RC-u3 跑团机器人
在桌面角色扮演游戏（TRPG，俗称“跑团”）中，玩家需要掷出若干个骰子，根据掷出的结果推进游戏进度。在线上同样可以跑团，方法是由玩家们向机器人发出指令，由机器人随机产生每个需要掷出的骰子的结果。
玩家向机器人发出的指令是一个仅涉及加法和减法的表达式，即对若干个数字进行一系列加法或减法计算。这些数字可以是直接给出的非负整数（数字不超过 1000），也可以是若干个骰子掷出的结果。
“掷骰子”这个动作对应的指令格式为 xdy，表示摇动 x 个 y 面的骰子（1≤x≤1000,2≤y≤1000）。当 x 为 1 时，1 可以省略。
例如指令 2d3+3-d4 的意思是：先掷出 2 个 3 面骰子（你不必考虑现实中是否存在这样的骰子），不妨假设结果为 1 和 3，则 2d3 的结果就是两个骰子的面值之和 4；然后计算 4 + 3，得到结果为 7；再掷出 1 个 4 面骰子，不妨假设结果为 2，则计算 7 - 2 得到最终结果 5。
本题就请你计算玩家输入的指令里，不同种类的骰子需要掷出几个，以及可能得到的结果在什么区间范围内。
输入格式:
输入在一行中给出一条符合题目描述的玩家输入机器人的指令。题目保证指令长度不超过 2∗104。
输出格式:
首先输出不同种类的骰子分别需要掷出几个。每种骰子的信息占一行，依次输出骰子的面数和投掷的数量，按面数从小到大输出。
输入指令保证至少有一个骰子需要掷出。
最后一行输出两个数，表示根据输入指令可以得到的最小结果和最大结果。
同一行数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例:
d6+3d5+2-2d3+2d5
输出样例:
3 2
5 5
6 1
2 31
解题：模拟 字符串 哈希表
思路
模拟 + 字符串处理。
处理步骤：首先输入一整行存入字符串(line)。把符号(sign)初始化为 '+' 防止第一项的符号为正号省略时符号变量不被初始化。再在字符串后面加一个符号('+')，这是为了让式子中最后一项不被忽略。
遍历字符串中每个字符：
- 如果当前字符是数字(不是
'+'、'-'、‘d’)，那么直接把当前维护的整数a加上该位(乘以 10 再加上该字符表示的整数)。 - 如果当前字符是
'd'，说明该项是一个骰子项，且骰子的个数已经输入到了a里，如果a为 0，就说明个数是 1 被省略了，把a置为 1。然后为了之后输入数字方便，交换a、b，这样b就变成了骰子个数，a中继续解析骰子面数。 - 如果当前字符是
'+'或'-'，就说明上一项解析完成可以计算了。如果骰子个数(b)不为零，说明上一项是骰子项，要算出骰子的最大最小和并把骰子记录进哈希表，骰子能出现的最小结果就是骰子个数，所以b不用变，骰子能出现的最大结果是a * b。为了后面不用加判断，该项不是骰子项时就让最大最小数(a和b)相同。接下来判断该项符号(sign)，如果是加号那么：总最小可能数(mn)加上当前最小可能数(b)，总最大可能数(mx)加上当前最大可能数(a)，否则相反：总最小可能数(mn)减去当前最大可能数(a)，总最大可能数(mx)减去当前最小可能数(b)。完成计算后维护下一项符号，并把a、b置为 0。
最后根据题意输出即可。
代码
#include <iostream>
#include <map>
using namespace std;
int _ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return 0;
}();
int main() {
string line;
getline(cin, line);
line += "+";
int a = 0, b = 0, mn = 0, mx = 0;
char sign = '+';
map<int, int> dices;
for (char& ch : line) {
switch (ch) {
case '+': case '-':
if (b) {
dices[a] += b;
a *= b;
} else b = a;
if (sign == '+') {
mn += b;
mx += a;
} else {
mn -= a;
mx -= b;
}
sign = ch;
a = b = 0;
break;
case 'd':
swap(a, b);
if (!b) b = 1;
break;
default:
a = a * 10 + (ch - '0');
}
}
for (const auto& dice : dices) {
printf("%d %d\n", dice.first, dice.second);
}
printf("%d %d\n", mn, mx);
return 0;
}
RC-u4 攻略分队
副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。
在 MMORPG《最终幻想14》里，有一个攻略人数最大达到 56 人的副本“巴尔德西昂兵武塔”，因为有在副本里死亡不能复活、机制比较整蛊等特点，一度被玩家视作洪水猛兽。
在副本的开始，我们会遇到第一个难关：攻略的玩家要分为两组，同时讨伐副本 BOSS “欧文”和“亚特”。
已知以下信息：
- 玩家会组成 6 支队伍进入副本，其中第 i 队有 Vi 位玩家（i=1,⋯,6）。
- 每支队伍可能会有一些特殊角色：MT（主坦克）、工兵（负责探测陷阱）和指挥（负责指挥玩家）。
我们的任务是合理安排玩家的分组，以最大程度增加副本通过概率。分组的原则如下：
- 要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组；
- 每组必须有至少一个 MT（主坦克）。
如果满足上述原则的分组方案不唯一，则按照下列规则确定唯一解：
- 优先选择每组有至少一个指挥和至少一个工兵的方案；
- 如果规则 1 无法满足，则优先选择每组至少有一个指挥的方案；
- 如果所有方案都不满足规则 2，或经过前 2 个规则筛选后，分组方案仍不唯一，则选择两边人数尽可能接近（即两边人数差尽可能小）的方案；
- 如果满足规则 3 的方案还不唯一，选择讨伐“欧文”的人数比讨伐“亚特”的人数更多的方案；
- 如果满足规则 4 的方案还不唯一，选择讨伐“欧文”的队伍编号方案中最小的一个。
注：一个队伍编号方案 A={a1<⋯<am} 比 B={b1<⋯<bn} 小，当且仅当存在 1≤k≤min(m,n) 使得 ai=bi 对所有 0<i<k 成立，且 ak<bk。
本题就请你给出满足所有分组原则的分配方案。
输入格式:
输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 Vi (0≤Vi≤8,1≤i≤6)。队伍人数为 0 时表示队伍不存在。
随后 6 行，按队伍编号顺序，每行给出一支队伍的特殊角色，格式为 ABC，其中 A 对应 MT，B 对应工兵，C 对应指挥。三种角色对应取值 0 或 1，0 表示没有该角色，1 表示有。
注：由于可能存在一人兼任多个特殊角色的情况，所以一支队伍中的特殊角色数量有可能大于该队伍的玩家数量。
输出格式:
输出分两行，第一行输出讨伐“欧文”的队伍编号，第二行输出讨伐“亚特”的队伍编号。同一行中的编号按升序输出，以 1 个空格分隔，行首尾不得有多余空格。
如果不存在合法的方案，输出GG。
输入样例1:
6 8 7 5 3 0
010
101
110
001
111
000
输出样例1:
2 3
1 4 5
输入样例2:
6 8 7 5 3 0
010
101
010
001
011
000
输出样例2:
GG
解题：待补充
RC-u5 树与二分图
设 G=(V,E) 是一个无向图，如果顶点集合 V 可分割为两个互不相交的子集 (A,B)，并且每条边 (i,j)∈E 的两个端点 i 和 j 分别属于这两个不同的顶点子集，则称图 G 为一个二分图。
现在给定一棵树 T，要求选择树中两个没有边相连的结点 i 和 j，使得将无向边 (i,j) 加进 T 后能够构成二分图。你的任务是计算满足这个要求的选择方案有多少种。
输入格式:
输入第一行给出一个正整数 N (2≤N≤106)，表示树中结点的个数。
接下来 N−1 行，每行给出树中一条边的两端结点编号，以空格分隔。结点编号从 1 开始。题目保证输入给出的是一棵树中所有的边。
输出格式:
在一行中输出方案数。注意：连接 (1,2) 和 (2,1) 视作同一个方案。
输入样例:
7
1 2
2 3
2 4
2 5
2 6
4 7
输出样例:
4
解题：二叉树 图 DFS
思路
待补充。
代码
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
long long odd, even;
void dfs(int u, int t, int curr) {
if (curr & 1) ++odd;
else ++even;
for (const auto& v : graph[u]) {
if (v != t) dfs(v, u, curr + 1);
}
}
int main() {
int N;
scanf("%d", &N);
graph = vector<vector<int>>(N + 1);
int u, v;
for (int i = 1; i < N; ++i) {
scanf("%d%d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, -1, 1);
printf("%lld", odd * even - (N - 1));
return 0;
}
评论区