文章目录
-
-
- 1、不要浪费金币
- 2、智能服药助手
- 3、跑团机器人
- 4、攻略分队
- 5、树与二分图
-
1、不要浪费金币
哲哲最近在玩一个游戏，击杀怪物能获得金币 —— 这里记击杀第 i 个怪物获得的金币数量为 P
i
。
然而这个游戏允许拥有的金币数量是有上限的，当超过时，超过上限的部分就会被系统光明正大地吃掉，哲哲就拿不到了。
为了不浪费金币，哲哲决定，当下一个要击杀的怪物可获得的金币会导致自己拥有的金币数量超过上限时，就去消费一次，把自己已有的金币全部用完。
现在给定哲哲将要击杀的一系列怪物对应的金币数量，请你计算一下哲哲去消费了几次。
输入格式:
输入第一行是两个整数 N,M （1≤N≤10
3
,1≤M≤10
6
），表示击杀的怪物数量以及系统允许拥有金币数量的上限。
接下来一行是由空格隔开的 N 个数 P
i
（i=1,⋯,N），依次表示击杀第 i 个怪物能获得的金币数量。假设哲哲是按输入顺序击杀怪物的，并且每个 P
i
都是 不超过 10
6
的非负整数。
输出格式:
在一行中输出哲哲去消费的次数。
输入样例:
10 10
1 2 3 4 1 2 3 5 11 1
输出样例:
4
样例解释：
消费时间点为：第四个怪物击杀后、第七个怪物击杀后、第八个怪物击杀后、第九个怪物击杀后。
思路：
- 扫一遍加起来，如果>m就从新计数，答案+1。
//AC
#include<bits/stdc++.h>
using namespace std;
int main(){int n, m; cin>>n>>m;int sum = 0, cnt = 0;for(int i = 1; i <= n; i++){int x; cin>>x;sum += x;if(sum > m){sum = x;cnt++;}}cout<<cnt<<"\n";return 0;
}
2、智能服药助手
智能看护中很重要的环节是安排需要服药的老年人的服药计划。
已知机器人需要照顾的某位老年人需要服用 N 种药物，但某些药物不宜间隔过短服用 —— 比如降糖药一般遵医嘱日服 3 次，两次之间需要间隔至少 4 小时。当需要服用的药物比较多，医嘱比较复杂时，如何保证每位老人的服药计划是安全合理的，就成为一个挑战。
本题给定一套服药计划，请你检查一下计划是否存在问题。
输入格式:
输入第一行给出两个整数 N,M（1≤N,M≤10
3
），表示老人需要服用 N 种药物（药物种类从 1 到 N 编号），对应的服药计划有 M 条记录。
接下来首先在一行中给出 N 个用空格隔开的整数 T
i
（−1≤T
i
≤100,T
i
=0)，表示编号为 i 的药物需要间隔至少 T
i
个单位时间服用。如果 T
i
为 −1，则说明这种药物没有间隔要求。
接下来的 M 行，每行给出一条服药计划中的记录，格式为：首先给出两个非负整数 t 和 k (0≤t≤10
9
,0≤k≤N)，表示服药的时刻为 t，服用了 k 种药物；然后紧接着列出 k 个数，每个数对应 t 时刻要吃的药物种类的编号。一行中的数字之间以空格分隔。
题目保证：记录按照服药时刻 t 的递增顺序给出；每一时刻服用的药物种类各不相同。注意：同一种药物可能需要在不同的时刻重复服用。如果一位老人在 t
i
时刻和 t
j
时刻服用了同一种药物，则他服用的间隔时间为 ∣t
i
−t
j
∣。
输出格式:
按照输入顺序检查每一条记录中的每一种药物。如果在 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!
思路：
- 无脑特判
//AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn], last[maxn];
int main(){memset(last,-1,sizeof(last));int n, m; cin>>n>>m;for(int i = 1; i <= n; i++){cin>>a[i];}while(m--){int t, k; cin>>t>>k;for(int i = 1; i <= k; i++){int x; cin>>x;if(last[x]==-1 || a[x]==-1 || t-last[x] >= a[x]){last[x] = t;}else{cout<<"Don't take "<<x<<" at "<<t<<"!\n";}}}return 0;
}
3、跑团机器人
在桌面角色扮演游戏（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∗10
4
。
输出格式:
首先输出不同种类的骰子分别需要掷出几个。每种骰子的信息占一行，依次输出骰子的面数和投掷的数量，按面数从小到大输出。
输入指令保证至少有一个骰子需要掷出。
最后一行输出两个数，表示根据输入指令可以得到的最小结果和最大结果。
同一行数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例:
d6+3d5+2-2d3+2d5
输出样例:
3 2
5 5
6 1
2 31
思路：
- 无脑特判
//AC
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int main(){map<int,int>mp;string s; cin>>s;s = s+"+";int mx = 0, mi = 0;int now = 0, last = 1;int ok = 1;//jiaint dd = 0;for(int i = 0; i < s.size(); i++){if(s[i]=='d' || s[i]=='+' || s[i]=='-'){if(s[i]=='d'){if(now==0)now = 1;last = now;now = 0;dd = 1;}else{if(dd==1)mp[now] += last;if(dd==1){if(ok==1){mx += now*last;mi += 1*last;}else{mi -= now*last;mx -= 1*last;}}else{if(ok==1){mx += now;mi += now;}else{mi -= now;mx -= now;}}if(s[i]=='+')ok = 1;else ok = 0;now = 0;last = 0;dd = 0;}}else{now = now*10+s[i]-'0';}}for(auto x : mp){cout<<x.first<<" "<<x.second<<"\n";}cout<<mi<<" "<<mx<<"\n";return 0;
}
4、攻略分队
副本是游戏里的一个特色玩法，主要为玩家带来装备、道具、游戏资源的产出，满足玩家的游戏进程。
在 MMORPG《最终幻想14》里，有一个攻略人数最大达到 56 人的副本“巴尔德西昂兵武塔”，因为有在副本里死亡不能复活、机制比较整蛊等特点，一度被玩家视作洪水猛兽。
在副本的开始，我们会遇到第一个难关：攻略的玩家要分为两组，同时讨伐副本 BOSS “欧文”和“亚特”。
已知以下信息：
玩家会组成 6 支队伍进入副本，其中第 i 队有 V
i
位玩家（i=1,⋯,6）。
每支队伍可能会有一些特殊角色：MT（主坦克）、工兵（负责探测陷阱）和指挥（负责指挥玩家）。
我们的任务是合理安排玩家的分组，以最大程度增加副本通过概率。分组的原则如下：
要将所有队伍分成 2 组，每支队伍必须且仅属于其中一组；
每组必须有至少一个 MT（主坦克）。
如果满足上述原则的分组方案不唯一，则按照下列规则确定唯一解：
优先选择每组有至少一个指挥和至少一个工兵的方案；
如果规则 1 无法满足，则优先选择每组至少有一个指挥的方案；
如果所有方案都不满足规则 2，或经过前 2 个规则筛选后，分组方案仍不唯一，则选择两边人数尽可能接近（即两边人数差尽可能小）的方案；
如果满足规则 3 的方案还不唯一，选择讨伐“欧文”的人数比讨伐“亚特”的人数更多的方案；
如果满足规则 4 的方案还不唯一，选择讨伐“欧文”的队伍编号方案中最小的一个。
注：一个队伍编号方案 A={a
1
<⋯<a
m
} 比 B={b
1
<⋯<b
n
} 小，当且仅当存在 1≤k≤min(m,n) 使得 a
i
=b
i
对所有 0<i<k 成立，且 a
k
<b
k
。
本题就请你给出满足所有分组原则的分配方案。
输入格式:
输入第一行给出 6 支队伍的玩家数量，即 6 个非负整数 V
i
(0≤V
i
≤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
思路：
- 继续无脑特判
//AC（90行）
#include<bits/stdc++.h>
using namespace std;int V[8], js[8][3];
vector<int>a,b,c;
int ok = -1, rs = 10000, rr = -1;int check(vector<int>&x, vector<int>&y){if(x.size()==0 || y.size()==0)return 0;//统计出2组的人数，以及拥有的角色int okk = -1, r1 = 0, r2 = 0;int q1[3], q2[3];memset(q1,0,sizeof(q1));memset(q2,0,sizeof(q2));for(int u : x){r1 += V[u];for(int j = 0; j < 3; j++)if(js[u][j])q1[j]++;}for(int u : y){r2 += V[u];for(int j = 0; j < 3; j++)if(js[u][j])q2[j]++;}//规则1>规则2>规则0，存在1就绝不采用2和0if(q1[0]==0 || q2[0]==0)return 0;if(q1[1]&&q1[2] && q2[1]&&q2[2]){//规则1, 最好都有(WA1,1分)if(ok < 2){ok = 2; rs = abs(r1-r2); rr = r1-r2>0?1:0;return 1;}okk = 2;}else if(q1[2] && q2[2]){//规则2，有主坦+指挥就行if(ok < 1){ok = 1; rs = abs(r1-r2); rr = r1-r2>0?1:0;return 1;}okk = 1;}else{ //规则0，有主坦就行if(ok < 0){ok = 0; rs = abs(r1-r2); rr = r1-r2>0?1:0;return 1;}okk = 0;}//规则012相同下，判断后面的规则if(okk==ok){if(abs(r1-r2)<rs){//规则3，人数相差rs = abs(r1-r2); rr = r1-r2>0?1:0;return 1;}else if(abs(r1-r2)==rs){int rr2 = r1-r2>0?1:0;if(rr < rr2){//规则4，欧文>亚特rr = rr2; return 1;}else if(rr==rr2){ //规则5，欧文字典序return x<a;}}}return 0; //不满足规则的返回0
}int main(){for(int i = 1; i <= 6; i++){cin>>V[i]; //第i队的人数if(V[i]!=0)c.push_back(i);}for(int i = 1; i <= 6; i++){string s; cin>>s;for(int j = 0; j < 3; j++)js[i][j] = s[j]-'0';//第i队有没有角色j（主坦，工兵，指挥）}int n = c.size(); //一共n个队for(int i = 1; i < (1<<n); i++){//每个队可以组1或组2，共2^nvector<int>x, y; //临时分组for(int j = 0; j < c.size(); j++){if(i>>j&1)x.push_back(c[j]);else y.push_back(c[j]);}if(check(x,y))a=x,b=y;}if(!a.size() || !b.size()){cout<<"GG\n"; return 0;}for(int i = 0; i < a.size(); i++){if(i!=0)cout<<" "; cout<<a[i];}cout<<"\n";for(int i = 0; i < b.size(); i++){if(i!=0)cout<<" "; cout<<b[i];}return 0;
}//21/25分
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
int V[7]; string cz[7];
int mt, gb, zh; //主坦，工兵，智慧的总人数
vector<int>sc;//一个人两个角色int cc[8]; //01, 表示第1组或第2组
vector<int>p1, p2;//临时方案
vector<int>pp1, pp2; //最优方案
int gz1 = 0;//答案是否满足规则1
int gz2 = 0;//答案是否满足规则2
int rs = 0; //人数差
int cnt = 0;
void dfs(int cur){if(cur == 7){// cnt++;//规则0if(p1.size()==0 || p2.size()==0)return ;int mt1=0,mt2=0;// for(int x : p1)cout<<x<<"\n";for(int x : p1) mt1 += cz[x][0]-'0';for(int x : p2) mt2 += cz[x][0]-'0';if(mt1==0 || mt2 == 0)return ;int now1= 0, now2 = 0;//规则1int zh1 = 0, zh2 = 0, gb1 = 0, gb2 = 0;for(int x : p1) zh1 += cz[x][1]-'0', gb1 += cz[x][2]-'0';for(int x : p2) zh2 += cz[x][1]-'0', gb2 += cz[x][2]-'0';if(zh1>0 && gb1>0 && zh2>0 && gb2>0){now1 = 1;if(gz1 == 0){// cout<<"asd";gz1 = 1; pp1 = p1; pp2 = p2;return ;}}//规则2if(zh1>0 && zh2>0){now2 = 1;if(gz2 == 0 && gz1==0){gz2 = 1; pp1 = p1; pp2 = p2;return ;}}if(now2==0)return ;if(now1==0 && gz1==1)return ;// cout<<"asdf";//规则3int rr1 = 0, rr2 = 0;for(int x : p1)rr1 += V[x];for(int x : p2)rr2 += V[x];int rrs1 = 0, rrs2 = 0;for(int x : pp1)rrs1 += V[x];for(int x : pp2)rrs2 += V[x];// int rss = abs((int)p1.size()-(int)p2.size());// rs = abs((int)pp1.size()-(int)pp2.size());int rss = abs(rr1-rr2);rs = abs(rrs1-rrs2);if(rss < rs){pp1 = p1; pp2 = p2; rs = rss;return ;}//规则4, 5if(rss == rs){// if(p1.size()-p2.size() > pp1.size()-pp2.size()){if(rr1-rr2>rrs1-rrs2){pp1 = p1; pp2 = p2;return ;// }else if(p1.size()-p2.size() == pp1.size()-pp2.size()){}else if(rr1-rr2==rrs1-rrs2){// cout<<"asf";int ok = 0;for(int i = 0; i < p1.size() && i<pp1.size(); i++){if(p1[i]<pp1[i]){ok = 1;break;}else if(p1[i]>pp1[i]){ok = -1;break;}}if(ok==1){pp1 = p1; pp2 = p2;return ;}else if(ok==0 && p1.size()<pp1.size()){pp1 = p1; pp2 = p2;return ;}}}return ;}if(V[cur]!=0){p1.push_back(cur);dfs(cur+1);p1.pop_back();// cc[cur] = 1;p2.push_back(cur);dfs(cur+1);p2.pop_back();// cc[cur] = 0;}else{dfs(cur+1);}}int main(){for(int i = 1; i <= 6; i++){cin>>V[i];// if(V[i]==0)n--;}for(int i = 1; i <= 6; i++){cin>>cz[i];mt += cz[i][0]-'0';gb += cz[i][1]-'0';zh += cz[i][2]-'0';int x = cz[i][0]-'0'+cz[i][1]-'0'+cz[i][2]-'0';if(x > V[i]){sc.push_back(i);}}if(mt<=1){ cout<<"GG\n"; return 0; }//数据只有这个会ggdfs(1);// cout<<cnt<<"\n";for(int i = 0; i < pp1.size(); i++){if(i!=0)cout<<" "; cout<<pp1[i];}cout<<"\n";for(int i = 0; i < pp2.size(); i++){if(i!=0)cout<<" "; cout<<pp2[i];}return 0;
}5、树与二分图
设 G=(V,E) 是一个无向图，如果顶点集合 V 可分割为两个互不相交的子集 (A,B)，并且每条边 (i,j)∈E 的两个端点 i 和 j 分别属于这两个不同的顶点子集，则称图 G 为一个二分图。
现在给定一棵树 T，要求选择树中两个没有边相连的结点 i 和 j，使得将无向边 (i,j) 加进 T 后能够构成二分图。你的任务是计算满足这个要求的选择方案有多少种。
输入格式:
输入第一行给出一个正整数 N (2≤N≤10
6
)，表示树中结点的个数。
接下来 N−1 行，每行给出树中一条边的两端结点编号，以空格分隔。结点编号从 1 开始。题目保证输入给出的是一棵树中所有的边。
输出格式:
在一行中输出方案数。注意：连接 (1,2) 和 (2,1) 视作同一个方案。
输入样例:
7
1 2
2 3
2 4
2 5
2 6
4 7
输出样例:
4
思路：
- 无脑结论
- 好吧鉴于某人的要求，详细讲一下，给的是一棵树，所以画出来很明显可以发现只有相邻的层之间会有边。
所以直接就13579层一个集合，2468层一个集合嘛，两个集合之间不可能有其他边。
然后dfs遍历一遍就可以得到两个集合的大小x和y。 - 然后考虑方案，对于第一个集合的每个点，肯定是要和第二个集合的每个点都连一遍的，所以总的方案数显然x*y。 考虑到有些边本来已经连上了，那我们就遍历的时候把原来有的边的数量累加一下（其实好像就是n-1啦）最后减掉就可以啦。
- 因为x，y都是1e6的，乘起来会爆int，所以要ll，不然只有23分。
//AC
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e6+10;
vector<LL>G[maxn];
LL x = 0, y = 0, xx = 0, yy = 0;
void dfs(LL u, LL fa, LL dep){if(dep%2==1){ x++; xx += G[u].size();}else{ y++; yy += G[u].size(); }for(LL to : G[u]){if(to != fa){dfs(to, u, dep+1);}}
}
int main(){LL n; cin>>n;for(LL i = 1; i < n; i++){LL u, v; cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}dfs(1, -1, 1);cout<<x*y-xx<<"\n";return 0;
}