2022省赛
题目1：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<bits/stdc++.h>
using namespace std;
int main(){
int n;
int m;
int p[1200];
cin>>n>>m;//n只怪兽，金币上限m
for(int i=0;i<n;i++){
cin>>p[i];
}
int sum=0;
int c=0;
for(int i=0;i<n;i++){
sum+=p[i];
if(sum>m){sum=p[i];
c++;
}
}
cout<<c;
return 0;
}
题目2：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!题目3：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
代码：
#include<bits/stdc++.h>//关键处理好符号，统计个数问题。while（cin>>)是为了控制输入结束退出循环
using namespace std;
int n[1200];
int main()
{
char a;
int t=0;
int g=0;//个数
int s=0;//最小
int b=0;//最大
bool flag=true;
int fh=1;//正
while(cin>>a){
if(a>='0'&&a<='9'){
t=10*t+a-'0';
}
if(a=='d'){
if(t==0)
{
t=1;
}
g=t;
t=0;
}
if(a=='+'||a=='-'){
if(g==0){
s=s+fh*t;
b=b+fh*t;
}
if(fh==1) {
s=s+1*g;
b=b+t*g;
}
else if(fh==-1){
s=s-g*t;
b=b-1*g;
}
if(a=='+')fh=1;
else if(a=='-'){
fh=-1;
}
n[t]+=g;
g=0;
t=0;
}
}
if(fh==1) {
s=s+1*g;
b=b+t*g;
}
else if(fh==-1){
s=s-g*t;
b=b-1*g;
}
if(g==0){
s=s+fh*t;
b=b+fh*t;
}
n[t]+=g;
for(int i=0;i<1200;i++){
if(n[i]) cout<<i<<" "<<n[i]<<endl;
}
cout<<s<<" "<<b;
return 0;
}
答案：利用map和string
#include <bits/stdc++.h>
using namespace std;
map<int, int> num;//存储每种骰子被掷的总数
int Max, Min;//点数的最大最小值
void Solution(string str)
{
//l指向当前要处理指令的第一个字符， sign为当前指令的正负号， 1为正， -1为负
int r = str.length()-1, l = 0, sign = 1;//r为字符串最大下标
while(l <= r)
{
int x = 0, y = 0;//x统计个数y统计面数
//读取x，个数
while(l<=r && str[l] != 'd' && str[l] != '+' && str[l] != '-')
x = x*10 + str[l++] - '0';
//以d划分指令/常数
//读取完x后停止在d字符， 说明是一个指令
if(str[l] == 'd')
{
if(x == 0) x = 1;//d前面没有字符时， x默认为1
l++;
//读取y，面数
while(l<=r && str[l] != '+' && str[l] != '-')
y = y*10 + str[l++] - '0';
num[y] += x;//y面骰子的掷数增加x
if(sign == 1)
{
//为正时， Max加上最大数， Min加上最小数
Max += y*x;//每次都掷y点
Min += x;//每次都掷1点
}
else//为负时， 同上
{
Max -= x;
Min -= y*x;
}
}
//常数
else//读取完x后停止在+/-或越界， 说明是一个常量， 乘上符号直接加到Max, Min里即可
{//常数！
Max += sign*x;
Min += sign*x;
}
if(l <= r)//此时l要么越界, 要么停在+/-
sign = str[l++] == '+' ? 1 : -1;//判断下一个操作对象的符号， l后移指向它的第一个字符
/*符号： sign = str[l++] == '+' ? 1 : -1等价于
if（ str[l++] == '+' ）{//当前是+号，向后一位
sign=1;
}
else{
sign=-1;
}
*/
}
}
int main() {
string str;
cin >> str;
Solution(str);
for ( auto it = num.begin(); it != num.end(); it++) {
cout << it -> first << " " << it -> second << endl;//map的第一个域统计是几面的骰子，第二个域是这种骰子有几个
}
cout << Min << " " << Max << endl;
return 0;
}
题目5：RC-u5 树与二分图
考点：dfs+邻接表存图
设 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 <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
ll n;
int h[N], e[N], ne[N], idx;
//邻接表
void add(int x, int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}
bool st[N];
ll m;
void dfs(int v, bool color)
{
st[v] = true;//遍历过
if(color) m++;
for(int i=h[v]; i!=-1; i=ne[i])
{
int j = e[i];
if(!st[j]) dfs(j, !color);//j不在m集合。
}
}
int main()
{
cin >> n;
//邻接表
for(int i=1; i<=n; i++) h[i] = -1;
int x, y;
for(int i=1; i<n; i++)
{
cin >> x >> y;
add(x, y), add(y, x);
}
dfs(1, true);//从任一顶点开始遍历
cout << m*(n-m) - (n-1);
return 0;
}
访问相邻结点
for(int i=h[a];i!=-1;i=ne[i]){//初始条件i=h[a],然后判断i是否为-1，接着执行函数体，最后i=ne[i]指针后移！
int j=e[i];//去除当前点
}代码：
#include<bits/stdc++.h>//问的是在这个树的基础上最多加几条边使得它还是二分图
using namespace std;
typedef long long int ll;
ll n;
ll m=0;
//邻接表的准备：
int h[1000006];//头指针
int ne[1000006];//next指针
int e[1000006];//当前值
int idx=0;//下标
void add(int x,int y){
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
bool st[1000006];
void dfs(int a,bool color){
st[a]=true;//搜过
if(color){//没染过色
m++;
}
for(int i=h[a];i!=-1;i=ne[i]){//访问与该点相邻的点
int j=e[i];//取出相邻点，i只是指针
if(!st[j])dfs(j,!color);//如果这个点没访问过就dfs，注意因为他与a相邻所以状态相反不能在一个集合!color
}
}
int main(){
cin>>n;//n个顶点
for(int i=1;i<=n;i++ ){
//n个顶点初始化头指针，因为顶点从1开始所以下标从1开始
h[i]=-1;
}
for(int i=1;i<=n-1;i++){//n个顶点的树有n-1条边
int x,y;
cin>>x>>y;
//无向图双向存
add(x,y);
add(y,x);
}
//从第一个点开始搜
dfs(1,true);//true表示可以放入m集合
cout<<m*(n-m)-(n-1);//做法是二分图需要保证所有点分成两个集合，并且集合内无相交，所以分成两个集合一个集合里有m个顶点，另一个有n-m个顶点所以最多m*（n-m）条边（两边分别连接），减去树边n-1
return 0;
}RC-u4 攻略分队
考点：dfs
副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。
在 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。
本题就请你给出满足所有分组原则的分配方案。
感谢 王宪泉 同学对规则 4 的指正，于 2022-08-04 修改
输入格式:
输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 Vi (0≤Vi≤8,1≤i≤6)。队伍人数为 0 时表示队伍不存在。
随后 6 行，按队伍编号顺序，每行给出一支队伍的特殊角色，格式为 ABC，其中 A 对应 MT，B 对应工兵，C 对应指挥。三种角色对应取值 0 或 1，0 表示没有该角色，1 表示有。
注：由于可能存在一人兼任多个特殊角色的情况，所以一支队伍中的特殊角色数量有可能大于该队伍的玩家数量。
输出格式:
输出分两行，第一行输出讨伐“欧文”的队伍编号，第二行输出讨伐“亚特”的队伍编号。同一行中的编号按升序输出，以 1 个空格分隔，行首尾不得有多余空格。
如果不存在合法的方案，输出GG。（不合法情况：不满足每组至少一个坦克，因为一共两组所以坦克数<2不符合条件，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
#include <bits/stdc++.h>
using namespace std;
const int N = 7;
int num[N];//各队伍的人数
bool A[N], B[N], C[N];//各队伍是否有坦克、工兵、指挥(三个数组)
int totalA;//坦克的总数
//目前的最优方案， ans1、ans2 对应 欧文、亚特
vector<int> ans1, ans2;
/* RO, R1, R2对应前三个规则所要求的性质
* R0: 是否满足 每组必须有至少一个 MT（主坦克）。
* R1: 是否满足 每组有至少一个指挥和至少一个工兵
* R2: 是否满足 每组至少有一个指挥
*/
bool R0, R1, R2;
vector<int> tmp1, tmp2;//当前要判断的方案
//最关键判定：
void judge()
{
//所有人都在一组， 不符合分组要求， 直接退出
if(tmp1.empty() || tmp2.empty()) return;
//当前方案的r0, r1, r2性质， 以及临时变量t1, t2
bool r0, r1, r2, t1, t2;
//判断方案的r0性质
t1 = t2 = false;
for(int i : tmp1)
if( A[i] ) {//有坦克这个组
t1 = true;
break;
}
for(int i : tmp2)
if( A[i] ) {
t2 = true;
break;
}
r0 = t1 && t2;//每个组至少一个坦克
if(!r0) return;//r0是硬性要求， 不满足直接不考虑（每组必须一个坦克，不满足就不用）
//判断方案的r2性质, 先判断r2是因为r2是r1的组成部分
t1 = t2 = false;
for(int i : tmp1)
if( C[i] ) {
t1 = true;
break;
}
for(int i : tmp2)
if( C[i] ) {
t2 = true;
break;
}
r2 = t1 && t2;
//判断方案的r1性质
t1 = t2 = false;
for(int i : tmp1)
if( B[i] ) {
t1 = true;
break;
}
for(int i : tmp2)
if( B[i] ) {
t2 = true;
break;
}
r1 = r2 && t1 && t2;
//规则0, R0为false说明最优方案为空
if( !R0 )
{
ans1 = tmp1, ans2 = tmp2;
R0 = r0, R1 = r1, R2 = r2;
return;
}
//规则1
if(R1 && !r1) return;
if(r1 && !R1)
{
ans1 = tmp1, ans2 = tmp2;
R0 = r0, R1 = r1, R2 = r2;
return;
}
//都不满足规则1时执行规则2
if(!R1 && !r1)
{
if(R2 && !r2) return;
if(r2 && !R2)
{
ans1 = tmp1, ans2 = tmp2;
R0 = r0, R1 = r1, R2 = r2;
return;
}
}
//规则3
int an1 = 0, an2 = 0, tn1 = 0, tn2 = 0;//各组人数
for(int i : ans1) an1 += num[i];
for(int i : ans2) an2 += num[i];
for(int i : tmp1) tn1 += num[i];
for(int i : tmp2) tn2 += num[i];
int d1 = abs(an1 - an2), d2 = abs(tn1 - tn2);//人数差
if(d1 < d2) return;
if(d1 > d2)
{
ans1 = tmp1, ans2 = tmp2;
R0 = r0, R1 = r1, R2 = r2;
return;
}
//规则四
t1 = (an1 > an2), t2 = (tn1 > tn2);
if(t1 && !t2) return;
if(t2 && !t1)
{
ans1 = tmp1, ans2 = tmp2;
R0 = r0, R1 = r1, R2 = r2;
return;
}
//规则5
for(int k=0; k<ans1.size() && k < tmp1.size(); k++)
{
if(ans1[k] < tmp1[k]) return;
else if(ans1[k] > tmp1[k])
{
ans1 = tmp1, ans2 = tmp2;
R0 = r0, R1 = r1, R2 = r2;
return;
}
}
/*
可以发现虽然代码长, 但其实都差不多
基本就是:
如果最优方案满足某个规则而当前方案不满足, 判断结束
如果最优方案不满足某个规则而当前方案满足, 则当前方案替换最优方案, 判断结束
如果都满足, 执行下一个规则
*/
}
//标准dfs
void dfs(int i)
{
if(i > 6)//出口！
{//超过6个因为一共6个队-->说明遍历了一遍所以做judge
judge();
return;
}
if(num[i] == 0)
{//当前队伍0人没这个队就跳过
dfs(i+1);
return;
}
//标准dfs：操作-->dfs下一层-->恢复现场
tmp1.push_back(i);
dfs(i+1);
tmp1.pop_back();
tmp2.push_back(i);
dfs(i+1);
tmp2.pop_back();
}
int main()
{
for(int i=1; i<=6; i++)//队号从1开始
cin >> num[i];
string ABC;
for(int i=1; i<=6; i++)
{
cin >> ABC;
if(ABC[0] == '1') A[i] = true, totalA++;
if(ABC[1] == '1') B[i] = true;
if(ABC[2] == '1') C[i] = true;
}
if(totalA < 2)//出现GG的情况有且仅有少于两个队伍有坦克
{
cout << "GG";
return 0;
}
else
{
dfs(1);
//欧文
for(int i=0; i<ans1.size(); i++)
{
cout << ans1[i]<<" ";
}
cout << endl;
//亚特
for(int i=0; i<ans2.size(); i++)
{
cout << ans2[i]<<" ";
}
}
return 0;
}
分析：
（1）main函数
int main()
{
for(int i=1; i<=6; i++)
cin >> num[i];//输入每个队的人数
string ABC;//字符串存放每个队伍情况
for(int i=1; i<=6; i++)
{
cin >> ABC;//输入当前队伍情况
if(ABC[0] == '1') A[i] = true, totalA++;//有坦克，统计坦克数totalA
if(ABC[1] == '1') B[i] = true;//工兵
if(ABC[2] == '1') C[i] = true;//指挥
}
if(totalA < 2)//出现GG的情况有且仅有少于两个队伍有坦克
{
cout << "GG";
return 0;
}
else//合法-->就dfs开始分人
{
dfs(1);
//欧文
for(int i=0; i<ans1.size(); i++)
{
cout << ans1[i]<<" ";//欧文组号
}
cout << endl;
//亚特
for(int i=0; i<ans2.size(); i++)
{
cout << ans2[i]<<" ";//亚特组号
}
}
return 0;
}
map的遍历
num是一个map类型的变量名称
for ( auto it = num.begin(); it != num.end(); it++) {//用指针访问
cout << it -> first << " " << it -> second << endl;
}
标签：return,int,tmp1,dfs,2022,省赛,true,输入 From： https://www.cnblogs.com/luckyhappyyaoyao/p/18299252