7-1 找规律
请从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性。
输入格式:
无
输出格式:
大写字母
输入样例:
输出样例:
#include<stdio.h>
int main(){
printf("D");
return 0;
}
7-2 蜡烛燃烧时间
有粗细不同的两只蜡烛,细蜡烛的长度是粗蜡烛长度的2倍,点完细蜡烛需要1小时,点完粗蜡烛需要2小时。有一次停电,将这样两只蜡烛同时点燃,来电时,发现这两只蜡烛所剩长度一样,则此次停电共停了( ? )分钟。
输入格式:
无输入
输出格式:
数字
输入样例:
无
输出样例:
无
#include<iostream>
using namespace std;
int main(){
cout<<40;
return 0;
}
7-3 我没K
小袁最近被洗脑歌词“我没K”洗脑了,因此他打开了学习软件,用程序画了一个“K”型图案。
输入格式:
无。
输出格式:
无。
输入样例:
在这里给出一组输入。例如:
无
输出样例:
在这里给出相应的输出。例如:
****
***
**
*
**
***
****
#include<bits/stdc++.h>
using namespace std;
int main()
{
cout<<"****\n***\n**\n*\n**\n***\n****";
return 0;
}
7-4 帮帮胡桃画菱形边框
我去淦原神了,你们直接看样例吧!
输入格式:
先输入一个N(N>=1)(表示菱形的边长),再输入一个字符ch(用于打印菱形的边)。
输出格式:
每一行的行末不能有多余的空格
输入样例:
6 o
输出样例:
o
o o
o o
o o
o o
o o
o o
o o
o o
o o
o
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
char ch;
cin>>n>>ch;
for(int i=1;i<=n;i++){
for(int k=1;k<=n-i;k++) cout<<' ';//打印左边的空格。
cout<<ch;//打印左边的字符。
for(int k=1;k<=2*(i-1)-1;k++) cout<<' ';//打印中间的空格;
if(i!=1) cout<<ch;//如果i大于1,那么有右边,就打印字符。
cout<<endl;
}//上边的菱形,打印高度为n。
for(int i=n-1;i>=1;i--){
for(int k=1;k<=n-i;k++) cout<<' ';//打印左边的空格。
cout<<ch;//打印左边的字符。
for(int k=1;k<=2*(i-1)-1;k++) cout<<' ';//打印中间的空格;
if(i!=1) cout<<ch;//如果i大于1,那么有右边,就打印字符。
cout<<endl;
}//下边的菱形,打印高度为n-1。
return 0;
}
7-5 比较大小
ysy非常喜欢1.1这个数字。
输入格式:
输入两个整数x和y,比较x与1.1*y之间的大小关系。
输出格式:
如果x>1.1*y,则输出”>”,同理输出“=”或“<”。
输入样例:
在这里给出一组输入。例如:
110 100
输出样例:
在这里给出相应的输出。例如:
=
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
if(x*10<y*11)cout<<"<";
else if(x*10>y*11)cout<<">";
else cout<<"=";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
double x,y;
cin>>x>>y;
if(x-1.1*y>0.000000000001)cout<<'>';
else if(1.1*y-x>0.000000000001)cout<<"<";
else cout<<"=";
}
7-6 小袁的进制转换
小袁是23级新生,在学过进制转换的知识点后,他决定用代码来实现。
输入格式:
输入一个十进制的整数,将它转换成一个2进制数。
输出格式:
输出转换后的结果。
输入样例:
在这里给出一组输入。例如:
-10
输出样例:
在这里给出相应的输出。例如:
-1010
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x[105],i,j=0;
cin>>n;
if(n<0){cout<<"-";n=-n;}
if(n==0){cout<<"0";return 0;}
while(n){
x[j++]=+n%2;
n/=2;
}
for(i=j-1;i>=0;i--)
cout<<x[i];
return 0;
}
7-7 我爱贵工程
输入格式:
输入一个整数n,接着输入n串字符。
输出格式:
对于每串字符,输出出现次数最多的那个数字及其次数,如果出现多个数字次数一样,输出最小的那个数字;如果0-9每个数字都出现至少一次,那就再换行输出”I Love GUES!”。每串字符包含任意字符,但保证至少包含1个数字。
输入样例1:
在这里给出一组输入。例如:
1
1234567890
输出样例1:
在这里给出相应的输出。例如:
0 1
I Love GUES!
输入样例2:
在这里给出一组输入。例如:
2
1234567890
absd123 sdd
输出样例2:
在这里给出相应的输出。例如:
0 1
I Love GUES!
1 1
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;int n;
cin>>n;
getchar();
while(n--){
getline(cin,s);
map<int,int>a;
for(int i=0;i<s.size();i++){
if(s[i]>='0'&&s[i]<='9')a[s[i]-'0']++;
}
map<int,int>::iterator it;
int x=0,y=0,k=0;
for(it=a.begin();it!=a.end();it++){
if(it->second>x){x=it->second;y=it->first;}
}
cout<<y<<' '<<x;
for(int i=0;i<10;i++){
if(a[i])k++;
}
if(k==10)cout<<"\nI Love GUES!";
cout<<endl;
}
return 0;
}
7-8 cpa协会观景计划
2023年我们cpa协会又增加了新的成员,为了让学弟学妹们知道我们协会的财力,于是会长申请了一笔资金M,带大家去一个或者多个景点玩^_^,为了让大家玩得开心,贴心的会长亲自去了N个景点实地考察,记录了每一个景点大家去玩一共需要的花费V以及对于该景点的满意度S(满分为10),请计算出这一笔资金M能让大家获得的最大满意度之和MaxTotalS。
输入格式:
第一行输入M和N,随后N行依次输入name(该景点的名字),V(去该景点需要的花费),S(该景点的满意度)。
输出格式:
如果大家能出去玩就依次输出大家能去玩的景点名字(按数据输入的顺序从上到下输出),每一个名字后面都跟一个空格,第二行输出这几个景点的满意度之合。
如果哪里都去不了就只输出“insufficient funds.”
。
样例解释:
资金一共10,因此大家可以去:织金洞 ,阿西里西韭菜坪,百里杜鹃。一共花费2+2+5=9,会长对这几个景点的满意度之合9+7+9=25。
输入样例:
10 5
织金洞 2 9
阿西里西韭菜坪 2 7
织金古城 6 7
百里杜鹃 5 9
毕节市人民公园 4 8
输出样例:
织金洞 阿西里西韭菜坪 百里杜鹃
25
// #include<bits/stdc++.h> //二维数组解法
// using namespace std;
// const int MAXN = 1005;
// int v[MAXN]; // 体积
// int w[MAXN]; // 价值
// int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值
// string name[MAXN]; //景点名字
// int main()
// {
// int n, m;
// cin >> m >> n;
// queue<string> visit[n+1][MAXN];
// for(int i = 1; i <= n; i++)
// cin>> name[i] >> v[i] >> w[i];
// for(int i = 1; i <= n; i++)
// for(int j = 1; j <= m; j++)
// {
// if(j < v[i]){ // 当前背包容量装不进第i个物品,则价值等于前i-1个物品,且参观的景点集合也为前i-1个。
// f[i][j] = f[i - 1][j];
// visit[i][j]=visit[i-1][j];
// }else{ // 能装,需进行决策是否选择第i个物品
// f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
// if(f[i - 1][j]>f[i - 1][j - v[i]] + w[i]) visit[i][j]=visit[i-1][j]; //参观的景点集合为前i-1个。
// else{
// visit[i][j]=visit[i-1][j-v[i]];
// visit[i][j].push(name[i]);
// }
// }
// }
// if(f[n][m]){
// while(!visit[n][m].empty()){
// cout<<visit[n][m].front()<<' ';
// visit[n][m].pop();
// }
// cout << endl << f[n][m] << endl;
// }else cout<<"insufficient funds.";
// return 0;
// }
#include<bits/stdc++.h> //一维数组解法
using namespace std;
const int MAXN = 1005;
int f[MAXN];
string a[MAXN];
int main()
{
int n, m;
cin >> m >> n;
for(int i = 1; i <= n; i++) {
int v, w;
string k;
cin >> k >> v >> w; // 边输入边处理
for(int j = m; j >= v; j--){
f[j] = max(f[j], f[j - v] + w);
if(f[j]<=f[j-v]+w){ //选第i个物品
a[j]=a[j-v]+k+' ';
}
}
}
if(f[m]){
cout<<a[m]<<endl<<f[m];
}else cout<<"insufficient funds.";
return 0;
}
7-9 没有圣遗物的胡桃
你说得对,但是原神是一款二次元开放世界冒险游戏。
张博坤已经在提瓦特大陆上坚持使用胡桃进行了练习时长两年半的……打火史莱姆(?),终于,他不再满足于此了,他决定去挑战无数原神玩家们闻风丧胆、谈之色变的Boss,蒙德城的四风守护之一——北风王狼!然而由于太过激动,他居然忘记给胡桃装备上圣遗物就上战场了!不过不用担心,作为曾经的大哥,张博坤已经在脑海中将原神即时变幻的战斗机制转变为了简朴单一的回合制,并且为自己的胡桃构思出了一套理想化的出招顺序表(所谓理想化,也就是可以做到E技能之后还可以接E技能,Q技能之后也能接Q技能),在战斗中张博坤会严格的遵循这一套出招表。
但是,张博坤制定的出招表并不一定是完美的,可能并不能让他取得最终的胜利,但是张博坤已经决定开摆了。现在,为了帮助张博坤,请你设计出一个程序来模拟他的战斗过程,给出战斗最终的结果。这样的话,如果张博坤能够提前知道战斗的结果,就可以提前选择改变战术或者去圣遗物本里面继续坐牢了。
张博坤将回合制原神的战斗规则制订如下:
(1)胡桃与Boss双方各自拥有生命值上限Hhp和Ghp;
(2)每一回合都是胡桃先手攻击Boss,然后Boss再攻击胡桃,胡桃的每一次攻击伤害都是Hatk,Boss的每一次攻击伤害都是Gatk;
(3)若某一方的生命值小于等于0,则判断该方被另一方击败了。
(4)若Boss攻击前被胡桃击败,那么胡桃胜出;若胡桃攻击Boss后被Boss击败,那么Boss胜;
胡桃有以下三种攻击方式:
攻击方式0:平a一下,造成伤害值为Hatk
攻击方式1:使用E技能重击一下,会先损失自身当前血量的1/3,之后产生伤害(胡桃当前血量低于50%生命值上限时,伤害为200%Hatk+Hhp*0.1;胡桃当前血量大于等于50%生命值上限时,伤害为150%Hatk+Hhp*0.1)。
攻击方式2:使用Q技能横扫一下,会先产生伤害(胡桃当前血量低于50%生命值上限时,伤害为350%Hatk+Hhp*0.1;胡桃当前血量大于等于50%生命值上限时,伤害为250%Hatk+Hhp*0.1),之后回复自身生命值上限的10%。
注:
(1)胡桃使用E技能损耗血量时,不会让自身生命值等于或小于0。
(2)胡桃使用Q技能时全程处于免伤状态,此时Boss的下一次攻击不对胡桃造成伤害。
(3)胡桃回复自身生命值时,当前的生命值不可能会大于生命值上限。
输入格式:
第一行依次输入Ghp(boss的生命值上限),Hhp(胡桃的生命值上限),Gatk(Boss的攻击力),Hatk(胡桃的平a造成的伤害值)
第二行输入一个N(胡桃N个回合的攻击方式)
第三行依次输入N次胡桃每回合的攻击方式op
输出格式:
如果直到回合结束,Boss和胡桃都尚未分出胜负(双方生命值都大于0),就在第一行中输出Boss的当前血量
如果胡桃胜出,第一行中输出”I am the first fire.”
(引号不输出)
如果Boss胜出,第一行中输出”I want the relic.”
(引号不输出)
第二行输出”Played x rounds”
(x为胡桃战斗的回合总数)
题目保证所有数据都在int范围内(包括数据的计算和输出)。
输入样例:
20000 30000 800 1000
5
0 1 0 2 1
输出样例:
3000
Played 5 rounds
#include<iostream>
using namespace std;
int ghp,hhp,gatk,hatk,now_hhp,rounds;
int N,op;
int main()
{
cin>>ghp>>hhp>>gatk>>hatk;
cin>>N;
now_hhp=hhp;
while(N--){
rounds++;
cin>>op;
switch(op)
{
case 0:{
//平a一下伤害为Hatk
ghp-=hatk;
}break;
case 1:{
// 开小技能重击一下(胡桃当前血量低于50%最大血量时伤害为200%Hatk+Hhp*0.1,
// 胡桃当前血量大于等于50%最大血量时伤害为150%Hatk+Hhp*0.1)。
now_hhp=now_hhp*2/3; //胡桃扣除血量
if(now_hhp<=0) now_hhp=1;
if(now_hhp>=hhp/2) ghp-=1.5*hatk+0.1*hhp;
else ghp-=2*hatk+0.1*hhp;
}break;
case 2:{
// 开大(胡桃当前血量低于50%最大血量时伤害为350%Hatk+Hhp*0.1,
// 胡桃当前血量大于等于50%最大血量时伤害为250%Hatk+Hhp*0.1)。
if(now_hhp>=hhp/2) ghp-=2.5*hatk+0.1*hhp;
else ghp-=3.5*hatk+0.1*hhp;
now_hhp+=0.1*hhp; //胡桃开大回血
if(now_hhp>=hhp) now_hhp=hhp;//若开大回血后的血量大于最大血量,那么当前的血量就是最大血量。
}break;
}
if(ghp<=0) break;
if(op!=2) now_hhp-=gatk;
if(now_hhp<=0) break;
}
if(ghp>=1&&now_hhp>=1) cout<<ghp;
else if(ghp>=1) cout<<"I want the relic.";
else cout<<"I am the first fire.";
cout<<"\nPlayed "<<rounds<<" rounds";
return 0;
}
7-10 会活字印刷技术的胡桃
胡桃这段时间在学习使用活字印刷术印刷英语句子,为了在印刷时能够快速找到对应的字母方块,胡桃把所有的字母方块都进行了分类,并将相同的字母方块放入一个收纳箱里面,而为了知道每一个收纳箱里面的方块种类和数量,胡桃便给收纳箱上贴了标签,(标明字母方块的种类和数量,当收纳箱里的方块只有一个时,胡桃便不会标明数量),分类好后将收纳箱整齐的排成一行。为了检验自己的活字印刷技术,便想着印刷出一个成品,胡桃就提笔写下了一句英语句子。而为了知道自己方块的种类和数量够不够印刷出这一英语句子,于是请聪明的旅行者帮忙统计一下,而旅行者正在学习C语言,便写了一个程序去统计方块的种类和数量够不够^_^。
输入格式:
第一行给出胡桃的收纳箱序列以@符号结束
第二行给出胡桃提笔写下的英语句子以@符号结束
输出格式:
如果胡桃的字母方块够就输出”You still left x square“
(x为胡桃剩下的方块数量)
不够就输出”You need x square“
(x为胡桃差的方块数量)。
样例解释: 以下两行的数据对应方式为‘方块所打印的字母’(方块数量)
胡桃的方块分别有: ’A’(1) ‘r‘(2) ‘e‘(1) ‘s‘(1) ‘t‘(1) ‘ ‘(2) ‘q‘(2) ‘i‘(2) ‘k‘(3) ‘m’(2)。
印刷英语句子需要:’A’(1) ‘r‘(2) ‘e‘(1) ‘s‘(1) ‘t‘(1) ‘ ‘(2) ‘q‘(2) ‘i‘(2)。
可以看出胡桃的方块拿出需要的去印刷英语句子后还剩下了3个k和2个m,所以胡桃的方块数量和种类都够,输出”You still left 5 square“
。
注: 输入数据保证没有数字种类的方块,数字只表示方块数量。
输入样例:
Ar2est 2q2i2k3m2@
Arrest qi qi@
输出样例:
You still left 5 square
#include<bits/stdc++.h>
using namespace std;
int A[128],B[128];
int main()
{
char c;
int flag=1,i=0;
string a,b;
getline(cin,a);
getline(cin,b);
while(a[i]!='@'){
int f=0,k=0;
A[(int)a[i]]=1;
c=a[i++];
while(a[i]>='0'&&a[i]<='9'){
k=k*10+(a[i++]-'0');
f=1;
}
if(f) A[(int)c]=k;
}
i=0;
int s1=0,s2=0;
while(b[i]!='@') B[(int)b[i++]]++;
for(i=0;i<=127;i++){
if(A[i]<B[i]){
flag=0;
}
s1+=A[i]-B[i];
if(B[i]>=A[i]) s2+=B[i]-A[i];
}
if(flag) cout<<"You still left "<<s1<<" square";
else cout<<"You need "<<s2<<" square";
return 0;
}
7-11 合并区间
输入若干个区间,将这些区间合并,然后输出合并后的区间以及区间的个数 。
例如,[1,2] 和 [2,3] 可以合并为 [1,3] 。
输入格式:
第一行输入一个整数 n ( 1 ≤ n ≤ 10000) 。
接下来 n 行,每行输入两个整数 l , r(-2^31 ≤ l ≤ r ≤ 2^31-1)。
输出格式:
输出合并后的区间以及区间的个数。
输入样例:
在这里给出一组输入。例如:
5
1 3
2 4
5 6
7 8
8 9
输出样例:
在这里给出相应的输出。例如:
[1,4]
[5,6]
[7,9]
3
#include<bits/stdc++.h>
using namespace std;
struct node{
int l, r;
}w[10010];
bool cmp(struct node a, struct node b)
{
return a.l < b.l;
}
int n, ans = 1;
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)
cin >> w[i].l >> w[i].r;
sort( w, w+n, cmp);
int l1 = w[0].l, r1 = w[0].r;
for(int i = 1; i < n; i ++){
if(r1 < w[i].l) {
printf("[%d,%d]\n", l1, r1);
l1 = w[i].l, r1 = w[i].r;
ans ++;
}
else if(r1 < w[i].r) r1 = w[i].r;
}
if( r1 >= w[n-1].l)
printf("[%d,%d]\n", l1, max( w[n-1].r, r1 ) );
cout << ans << endl;
return 0;
}
7-12 猫抓老鼠
猫抓老鼠
最近贵工程掀起了一股"猫抓老鼠"的游戏热潮,我们将猫抓老鼠的游戏规则修改为老鼠被猫猫抓了之后可以被救,游戏刚开始,鼠鼠们自主分为若干个团体开始进行逃亡(有直接联系关系的老鼠在一个团体),当然有一些团体会比较特殊,只有一个老鼠,而针对每个团体,都有一只鼠王存在。如果某团体鼠王被猫猫抓到,该团体会被打散分为与被抓鼠王有直接联系的小弟所在的若干个团体(比如1和2、3直接联系,2和4直接联系,3和5直接联系,那么1号被抓了之后,这个团体就会被分为两个鼠王分别为2和3的团体)。本题要求你编写一个通报程序,每当有一只鼠王被抓到时,就发出通报。
注意:对于每个团体,我们默认当前团体编号最小的为鼠王,打散后的团体也不例外。
输入格式:
输入在第一行给出两个整数M和N,分别代表参与游戏的"老鼠"人数(默认老鼠从1-M编号)和直接联系两只老鼠的连接个数。随后N行,每行给出一个连接关系所联系的两只老鼠的编号,其间以1个空格分隔。接下来给出若干个操作,每个操作占一行,每行首先输入一个操作字符C,如果C为'Z',其后输入一个整数A,代表A老鼠被抓;如果C为'J',其后输入两个整数A和B,代表A老鼠被B老鼠所救,救援关系也属于直接联系关系。如果C为'.',标志输入的结束。
输出格式:
对于每一个抓住老鼠的操作,如果是鼠王被抓,输出"x号鼠王被抓",除此之外,如果所有老鼠都被抓住,输出"猫猫胜利",并结束游戏,如果最后是以输入.为结束,需要按"当前有X1 X2···Xn号老鼠没被抓"的格式输出当前没有被抓的老鼠编号,编号间以空格隔开,末尾不得有对于空格,以上每个输出单独占一行。
输入样例:
在这里给出一组输入。例如:
5 3
1 5
2 4
1 3
Z 1
Z 3
J 3 2
Z 3
J 1 2
Z 2
.
输出样例:
在这里给出相应的输出。例如:
1号鼠王被抓
3号鼠王被抓
当前有1 4 5号老鼠没被抓
输入样例:
在这里给出一组输入。例如:
5 3
1 5
2 4
1 3
Z 1
Z 2
Z 3
Z 4
J 1 5
Z 5
Z 1
.
输出样例:
在这里给出相应的输出。例如:
1号鼠王被抓
2号鼠王被抓
3号鼠王被抓
4号鼠王被抓
1号鼠王被抓
猫猫胜利
#include<bits/stdc++.h>
using namespace std;
int m,n,g[10001],p[10001],a[501],b[501],z;
char c;
int find(int a){
if(g[a]==a) return a;
else return g[a]=find(g[a]);
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
while(1){
cin>>c;
if(c=='.'){
cout<<"当前有";
int j=0;
for(int i=1;i<=m;i++){
if(!p[i]){
if(j++) cout<<' ';
cout<<i;
}
}
cout<<"号老鼠没被抓\n";
break;
}
for(int i=1;i<=m;i++){
g[i]=i;
}
for(int i=1;i<=n;i++){
if(!p[a[i]]&&!p[b[i]]){
g[find(max(a[i],b[i]))]=find(min(a[i],b[i]));
}
}
if(c=='Z'){
cin>>z;
if(g[z]==z) cout<<z<<"号鼠王被抓\n";
p[z]=1;
}else{
cin>>a[n]>>b[n];
p[a[n++]]=0;
}
int o=1;
for(int i=1;i<=m;i++){
if(!p[i]) o=0;
}
if(o){
cout<<"猫猫胜利\n";
break;
}
}
}
7-13 寰宇蝗灾——树状位面跃迁
黑塔女士是一位奇女子,作为天才俱乐部序列83的天才,她总是有着自己的奇思妙想。开拓者今天收到了黑塔的邀请函,原来是她一直在捣鼓的得意之作——模拟宇宙又新开辟了一处宇宙位面,黑塔将它命名为“寰宇蝗灾”,开拓者正是被邀请去里面测试数据的。但是开拓者是第一次进入寰宇蝗灾,他不知道需要怎么移动和攻略这个位面,并且在测试过程中黑塔得时刻在空间站稳定位面紊流,不能够指引开拓者的道路,于是黑塔决定在寰宇蝗灾的基层位面入口立上告示牌,上面写好开拓者可以选择经过的路经,这样开拓者就不会迷失在茫茫星海之中了。由于黑塔是天才,不会亲手去做分析路经这种简单的事,于是她决定把这项任务交给你,她只会告诉你自己是怎么建立起这个位面的,需要你自己根据她的建立原理还原出这个位面,从而分析出开拓者可选择的路经。
黑塔告诉你的信息如下:
(1)寰宇蝗灾位面本质上是一颗二叉树,其中每个结点均使用唯一的键值(整数)来表示。
(2)位面的建立过程中会受到紊流影响,入口位置和邻接块的关系不能够同时确定,从而开辟空间时选择了结合前序遍历和中序遍历的方法。
(3)位面内存在一个首领位于根结点,只有击败首领之后才可以进行下一个位面的跃迁。
(4)开拓者对位面内的祝福和事件有着极强的探索欲,他的行动模式无非有两种:
i:先避开首领所在的结点,规划出获取资源的路经,把其余结点的资源全部搜集完毕后再去挑战首领,这在二叉树中体现为后序遍历。
ii:放弃思考,先击败首领,然后线性地探索位面中其他的所有区域,这在二叉树中体现为层序遍历。
(5)存在一种特殊的“元位面”,它的性质如下:
对于任一结点:
i:其左子树中所有结点的键值小于该结点的键值。
ii:其右子树中所有结点的键值大于该节点的键值。
iii:其左右子树也都满足“元位面”前两条的定义。
(6)还存在一种“空位面”,即位面内一个结点都没有。
输入格式:
第一行输入一个整数N,指位面中的结点数。
第二行输入N个整数,表示位面进行前序遍历的路经。
第三行输入N个整数,表示位面进行中序遍历的路经。
题目保证所给数据均合法。
输出格式:
若该位面不是空位面,那么输出共有三行,
第一行输出N个整数,每个整数之后跟着一个空格,表示这个位面进行后序遍历的路经。
第二行输出N个整数,每个整数之后跟着一个空格,表示这个位面进行层序遍历的路经。
第三行输出这个位面的深度(二叉树的高度)和叶子结点数,中间用一个空格隔开。
若该位面还是一个“元位面”,那么再增添一行输出”nice!”
(引号不输出)。
若该位面为空位面,那么仅输出一行”null”
(引号不输出)。
输入样例:
3
1 2 3
2 1 3
输出样例:
2 3 1
1 2 3
2 2
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int MAX=40;
typedef int type;
type pre[MAX], in[MAX];
struct node{
type data;
struct node *left;
struct node *right;
};
typedef struct node *BiTree;
BiTree pre_in_CreTree(type*, type*, int);
void post(BiTree );
void level(BiTree , int);
int leafcount(BiTree );
int highcount(BiTree );
bool isBST(BiTree );
int main(void){
IOS;
int N;
cin>>N;
for(int i=0;i<N;i++)
cin>>pre[i];
for(int i=0;i<N;i++)
cin>>in[i];
BiTree T=pre_in_CreTree(pre, in, N);
if(!T)
cout<<"null\n";
else{
post(T);
cout<<endl;
level(T, N);
cout<<endl;
cout<<highcount(T)<<' '<<leafcount(T)<<endl;
if(isBST(T))
cout<<"nice!\n";
}
return 0;
}
BiTree pre_in_CreTree(type pre[], type in[], int N){
BiTree root;
if(!N) root=NULL;
else{
root=new node;
root->data=pre[0];
root->left=root->right=NULL;
int flag=0;
for(flag=0;flag<N;flag++){
if(in[flag]==pre[0])
break;
}
root->left=pre_in_CreTree(pre+1, in, flag);
root->right=pre_in_CreTree(pre+flag+1, in+flag+1, N-flag-1);
}
return root;
}
void post(BiTree T){
if(T){
post(T->left);
post(T->right);
cout<<T->data<<' ';
}
return ;
}
void level(BiTree T, int N){
BiTree q[MAX], p;
int f=-1, r=-1;
if(T){
q[++r]=T;
while(r!=f){
p=new node;
p=q[++f];
cout<<p->data<<' ';
if(p->left)
q[++r]=p->left;
if(p->right)
q[++r]=p->right;
}
}
}
int leafcount(BiTree T){
if(!T) return 0;
else if(!T->left&&!T->right) return 1;
return leafcount(T->left)+leafcount(T->right);
}
int highcount(BiTree T){
if(!T) return 0;
else{
int l=highcount(T->left)+1;
int r=highcount(T->right)+1;
return max(l,r);
}
}
bool isBST(BiTree T){
if(T){
if(T->left){
if(T->left->data>T->data) return false;
if(T->left->right&&T->left->right->data>T->data) return false;
}
if(T->right){
if(T->right->data<T->data) return false;
if(T->right->left&&T->right->left->data<T->data) return false;
}
}
return true;
}
7-14 魔界将军的对弈
日向和凑两位魔界将军(中二病)为了减少战争的伤亡开展了一场博弈,在一个N*N的棋盘上移动棋子来决定胜负。假设最开始棋子落在了棋盘左上方,规定棋子每次只能往上下左右一个方向移动一格,并且所到之处以前不能到过。两位魔界将军(中二病)都乃大将之才,所以假设每步都是最优策略,如果每次都是日向先移动~~别问为什么,凑是护妻狂魔!~~那么最后谁能胜出呢?
输入格式:
本题有多组输入~~绝对不是日向不服输~~。每次输入一个数N表示棋盘大小。当N=0时表示输出结束。
1<=N<=100000000
输出格式:
对于每次输入N输出胜负关系,如果日向赢了就输出”I'am the champer!”否则输出”ni li haiQAQ”。
输入样例:
在这里给出一组输入。例如:
2
0
输出样例:
在这里给出相应的输出。例如:
I'am the champer!
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
while(n!=0)
{
if(n%2==0) cout<<"I'am the champer!"<<endl;
else cout<<"ni li haiQAQ"<<endl;
cin>>n;
}
return 0;
}
7-15 松鼠搬粮仓
松鼠在一圈原型的树上存了N堆松果,现在要将他们合并为一堆,规定每次搬运的体力值消耗为需要合并的两堆松果的数量,并且每次合并操作只能出现在相邻的树上。那么松鼠最累和最轻松分别需要多少体力值。
输入格式:
第一行输入一个N表示总共的松果堆数,第二行输入N个数字x,表示每堆有x个松果。
0<N<=100, 0<x<100
输出格式:
输出最小和最大的需求体力值,分别占两行。
输入样例:
在这里给出一组输入。例如:
4
4 5 9 4
输出样例:
在这里给出相应的输出。例如:
43
54
#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
int n,m,ans1,ans2;
int A[205],f1[205][205],f2[205][205];
int dfs1(int L,int R)
{ //求出最小得分
if(f1[L][R])return f1[L][R]; //已保存的状态不必搜索
if(L==R) return f1[L][R]=0; //L==R时返回0
int res=INF; //初始值赋为最大值以求最小值
for(int k=L;k<R;k++) //枚举K搜索
res=min(res,dfs1(L,k)+dfs1(k+1,R)+A[R]-A[L-1]);
return f1[L][R]=res; //记录状态
}
int dfs2(int L,int R)
{ //求出最大得分
if(f2[L][R])return f2[L][R];
if(L==R) return f2[L][R]=0; //若初始值为0可省略该句
int res=0; //初始值设为0
for(int k=L;k<R;k++)
res=max(res,dfs2(L,k)+dfs2(k+1,R)+A[R]-A[L-1]);
return f2[L][R]=res;
}
int main()
{
std::ios::sync_with_stdio(false);//取消cin与stdin同步,加速读入
cin>>n;
for(int i=1;i<=n;i++){
cin>>A[i];
A[i+n]=A[i]; //因为是环所以保存为长度为2n的链以保证不会漏解
}
for(int i=1;i<=2*n;i++) //求出前缀和
A[i]+=A[i-1];
dfs1(1,2*n);dfs2(1,2*n); //搜索出1-2n的最大得分与最小得分
ans1=INF; ans2=0;
for(int i=1;i<=n;i++){
ans1=min(f1[i][n+i-1],ans1);//选出答案
ans2=max(f2[i][n+i-1],ans2);
}
cout<<ans1<<"\n"<<ans2;
return 0;
}
7-16 为迎新晚会购买物品
为了迎接新生的到来,信工院准备举办迎新晚会来欢迎新同学进入大家庭,因此蔡老师要求周同学采购一些物品,例如,奖品,荧光棒,气球等等。
周同学接到任务以后,他背着他的背包去一个商城采购,他的背包可以装下m件商品。商城中有n种商品,第i种商品的价格为ai,由于商城比较大,每种商品的数量可以无限供应,周同学不用担心商品卖光。
周同学是一个有责任心的人,会把他的背包塞满才会停止购买,简单来说他会装满m件商品到背包中。现在请各位同学给周同学计算出购买的商品的总价钱的可能取值有哪些?求出来的答案按升序排序再输出,以便于他可以直观看见花最少的钱买到m件商品。
输入格式:
第一行输入n,m, 1 <= n, m <= 1000。
第二行输入n个物品的价格 ai, 1 <= ai <= 1000。
输出格式:
按照案例输出即可。
输入样例1:
3 2
1 2 3
输出样例1:
2 3 4 5 6
输入样例2:
5 5
1 1 1 1 1
输出样例2:
5
输入样例3:
3 3
3 5 11
输出样例3:
9 11 13 15 17 19 21 25 27 33
#include<bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
#define IOS std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr)
#define all(v) (v).begin(),(v).end()
void debug(std::vector <int> &a, int n){for (int i = 1; i <= n; i ++){std::cout << a[i] << " \n"[i == n];}}
void YES(){std::cout << "YES\n";}
void NO(){std::cout << "NO\n";}
void Yes(){std::cout << "Yes\n";}
void No(){std::cout << "No\n";}
void yes(){std::cout << "yes\n";}
void no(){std::cout << "no\n";}
const int N = 1e3 + 10;
constexpr i64 mod1 = 998244353, mod2 = 1e9 + 7;
//dp表示总价格为i时装了多少件物品
int dp[N * N];
int main()
{
IOS;
int n, m;
std::cin >> n >> m;
int a[N] = {0}, b[N] = {0};
for (int i = 1; i <= n; i ++){
std::cin >> a[i];
}
//排序找最小的一个数
std::sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++){
b[i] = a[i] - a[1];
}
for (int i = 0; i < N * N; i ++){
dp[i] = 1e9 + 10;
}
dp[0] = 0;
for (int i = 1; i <= n; i ++){
for (int j = 1; j < N * N; j ++){
if (j - b[i] >= 0){
dp[j] = std::min(dp[j], dp[j - b[i]] + 1);
}
}
}
for (int i = 0; i < N * N; i ++){
if (dp[i] <= m){
std::cout << m * a[1] + i << " ";
}
}
return 0;
}
7-17 巧克力的困惑
NEKOPARA推出新菜单之后客人太多了,每天从早忙到晚。但是细心的巧克力发现了一件事,有的客人比较挑剔,而有的比较注重性价比,挑剔的客人不会吃美味度小于一定数值的甜品,而注重性价比的客人不会吃大于一定价格的甜品,并且他们每次都点不一样的甜品。这时巧克力突发奇想想知道季节特供菜单多少天被全点一次。
输入格式:
输入四个数N,M,P,Q表示有N个特别的客人(每人每天仅仅会来一次),季节特供菜单共有M道甜品,N个客人中有P个挑剔的客人,有Q个注重性价比的客人。之后的M行每行两个整数表示每个甜品的美味度和价格。之后一行输入P个数表示每个挑剔客人最低能接受的美味度,之后一行Q个数表示注重性价比的客人分别能接受的价格上限。输出至少多少天他们可以把特供菜品全部点完一次。如果无论几天都不可能点完就输出”Nya~QAQ”。
规定P+Q=N<=50000,M<=200000
输出格式:
一个整数表示至少多少天能够点完所有的甜品。
输入样例:
在这里给出一组输入。例如:
2 3 1 1
5 2
5 3
6 4
5
1
输出样例:
在这里给出相应的输出。例如:
3
#include<bits/stdc++.h>
using namespace std;
const int Len = 4e5 + 5;
int n,m,p,q,tas[Len],costt[Len];
struct node
{
int x,y;
node(){x = y = 0;}
node(int X,int Y){x = X , y = Y;}
bool operator < (const node &Ano) const
{
return y < Ano.y;
}
}s[Len],now[Len];
priority_queue<node> Q;
bool cmp1(node x,node y)
{
return x.x > y.x;
}
bool cmp2(node x,node y)
{
return x.y < y.y;
}
bool check(int len)
{
if(1ll * (n - p - q) * len >= m) return 1;
while(!Q.empty()) Q.pop();
int idx = 1;
for(int i = 1 ; i <= p ; i ++)
{
while(idx <= m && s[idx].x >= tas[i])
Q.push(s[idx ++]);
for(int j = 1 ; j <= len && !Q.empty() ; j ++)
Q.pop();
}
int nowl = 0;
while(!Q.empty())
{
now[++ nowl] = Q.top();
Q.pop();
}
for(int i = idx ; i <= m ; i ++)
now[++ nowl] = s[i];
sort(now + 1 , now + 1 + nowl , cmp2);
idx = 1;
for(int i = 1 ; i <= q ; i ++)
{
while(idx <= nowl && now[idx].y <= costt[i])
Q.push(now[idx ++]);
for(int j = 1 ; j <= len && !Q.empty() ; j ++)
Q.pop();
}
int surp = 0;
while(!Q.empty())
{
surp ++;
Q.pop();
}
surp += nowl - idx + 1;
return surp <= (n - p - q) * len;
}
int main()
{
scanf("%d %d %d %d",&n,&m,&p,&q);
for(int i = 1 ; i <= m ; i ++)
scanf("%d %d",&s[i].x,&s[i].y);
for(int i = 1 ; i <= p ; i ++)
scanf("%d",&tas[i]);
for(int i = 1 ; i <= q ; i ++)
scanf("%d",&costt[i]);
sort(tas + 1 , tas + 1 + p);
reverse(tas + 1 , tas + 1 + p);
sort(costt + 1 , costt + 1 + q);
sort(s + 1 , s + 1 + m , cmp1);
int l = 1 , r = m , anss = -1;
while(l <= r)
{
int mid = (l + r) >> 1;
if(check(mid)) anss = mid , r = mid - 1;
else l = mid + 1;
}
if(anss==-1) puts("Nya~QAQ");
else printf("%d\n",anss);
return 0;
}