湖南大学2021程序设计训练笔记 – 作业训练3
本文最后更新于 508 天前,其中的信息可能已经有所发展或是发生改变。

所有代码均已上传至 homework/CSP-Training at master · cyp0633/homework (github.com)不保证代码均正确,正确的也不保证为最优解,可以查看 Commit 详情进一步了解。

1.部分A+B

个人难度评级:1

问题描述

正整数A的“DA(为1位整数)部分”定义为由A中所有DA组成的新整数PA。例如:给定A = 3862767,DA = 6,则A的“6部分”PA是66,因为A中有2个6;给定A = 3862767,DA = 1,则A的“1部分”PA是0,因为A中有0个1。

现给定A、DA、B、DB,请编写程序计算PA + PB

输入形式

输入在一行中依次给出A、DA、B、DB,中间以空格分隔,其中0 < A, B < 1010

输出形式

在一行中输出PA + PB的值。

样例输入

3862767 6 13530293 3

样例输出

399

解题思路

这个题都不会的话建议去面壁……没开long long导致WA掉的话情有可原。

2.导弹拦截系统

来源:NOIP 1999 普及组不知道第几题(洛谷P1020)(有改动)

个人难度评级:3

问题描述

某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。 

输入形式

每组输入有两行,

第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),

第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。

输出形式

每组输出只有一行,包含一个整数,表示最多能拦截多少枚导弹。

样例输入

8
300 207 155 300 299 170 158 65

样例输出

6

解题思路

贪心就完事了,建议去翻洛谷的题解,那个更难,但估计讲得比我明白。

本题数据很弱,开O(n2)的算法完全能过。

3.魔咒词典

来源:HDU 1880(无法访问可移步Vjudge

个人难度评级:2

问题描述

哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒,哈利很难全部记住,但是为了对抗强敌,他必须在危急时刻能够调用任何一个需要的魔咒,所以他需要你的帮助。

给你一部魔咒词典。当哈利听到一个魔咒时,你的程序必须告诉他那个魔咒的功能;当哈利需要某个功能但不知道该用什么魔咒时,你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中,就输出“what?”

输入形式

首先列出词典中不超过100000条不同的魔咒词条,每条格式为:

[魔咒] 对应功能

其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串,字符串中保证不包含字符“[”和“]”,且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束,这一行不属于词典中的词条。
词典之后的一行包含非负整数N(0=<N<=1000),随后是N个测试用例。每个测试用例占一行,或者给出“[魔咒]”,或者给出“对应功能”。

输出形式

每个测试用例的输出占一行,输出魔咒对应的功能,或者功能对应的魔咒。如果魔咒不在词典中,就输出“what?”

【样例输入】

[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky

样例输出

light the wand
accio
what?
what?

解题思路

咒语和效果都不一定只有一个词,所以需要使用getline一次读一行,然后再根据]的位置分割(substr大法好)。别的应该没什么难的。

4.打牌

个人难度评级:2

问题描述

牌只有1到9,手里拿着已经排好序的牌a,对方出牌b,用程序判断手中牌是否能够压过对方出牌。 
规则:出牌牌型有5种   
[1]一张 如4 则5…9可压过 
[2]两张 如44 则55,66,77,…,99可压过 
[3]三张 如444 规则如[2] 
[4]四张 如4444 规则如[2] 
[5]五张 牌型只有12345 23456 34567 45678 56789五个,后面的比前面的均大。

输入形式

输入有多行,第一行代表手中的牌,长度不超过200个数字。接下来的每一行代表每次对方出的牌。

输出形式

输出有多行,代表手中的牌是否能压过对方出的牌,压过输出YES, 并列出所有可选项,可选项之间用空格分隔。 否则输出NO。

样例输入

17624234556367
33
222
34567

样例输出

YES 44 55 66 77
YES 666
NO

解题思路

题意似乎没说牌放不放回……不过没说过出牌规则,应该是出牌后放回手牌的。

直接模拟即可,分几张牌的情况。五张牌情况不多,而且取起来也麻烦,建议直接对每种情况做特判。

(WA了一半多,不确定做法是否正确)

5.最大报销额

来源:HDU 1864(无法访问可移步Vjudge

个人难度评级:3

问题描述

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书(A类)、文具(B类)、差旅(C类),要求每张发票的总额不得超过1000元,每张发票上,单项物品的价值不得超过600元。现请你编写程序,在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

输入形式

测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N,其中 Q 是给定的报销额度,N(N<=30)是发票张数。随后是 N 行输入,每行的格式为:
      m Type_1:price_1 Type_2:price_2 … Type_m:price_m
      其中正整数 m 是这张发票上所开物品的件数,Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时,全部输入结束,相应的结果不要输出。

输出形式

对每个测试用例输出1行,即可以报销的最大数额,精确到小数点后2位。

样例输入

200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0

样例输出

123.50
1000.00
1200.50

解题思路

第一个困难其实是阅读理解。很容易能看出来这题是一个01背包问题,但背包里装的是什么呢?其实是发票。将发票各物品的总价值作为整一件物品的价值,而对于每组数据,有多张发票,那就是求如何取整张发票,能够让报销额尽可能接近报销上限而不超过。所以,只需要存储每张发票的总金额就可以了。

第二个困难是允许报销类型限制、每件物品金额限制和发票总金额限制。因为报销只能整张一起报,所以出现任何一个上述的例外情况,整张发票作废(可将金额存储为0)。

第三个困难是如何写DP。相信很多人已经背熟01背包了,但对于没背熟的人来说,这也许不算什么困难,毕竟当看到N<=30的时候,我相信你和我是一样的反应:直接暴力搜,管那么多干什么?确实,数据范围太菜,直接搜确实没问题。

第四个困难是初始化变量。老生常谈了,有多组数据的题要记得初始化。

6.带通配符的数

个人难度评级:2

问题描述

给定一个可以带通配符问号的正整数W,问号可以代表任意一个一位数字。再给定一个正整数X,和W具有同样的长度。问有多少个整数符合W的形式并且比X大?

输入形式

多组数据,每组数据两行,第一行是W,第二行是X,它们长度相同,在[1..10]之间。

输出形式

每行一个整数表示结果。

样例输入

36?1?8
236428
8?3
910
?
5

样例输出

100
0
4

解题思路

通配符的数量不确定,那就dfs啊。

7.愚人节的礼物

个人难度评级:1

问题描述

四月一日快到了,Vayko 想了个愚人的好办法——送礼物。嘿嘿,不要想的太好,这礼物可没那么简单,Vayko 为了愚人,准备了一堆盒子,其中只有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子,B表示礼物,Vayko 想让你帮她算出愚人指数,即最少需要拆多少个盒子才能拿到礼物。

输入形式

本题目包含多组测试,请处理到文件结束。每组测试包含一个长度不大于 1000, 只包含'(‘,’)’和’B’三种字符的字符串,代表 Vayko 设计的礼物透视图。你可以假设,每个透视图画的都是合法的。

输出形式

对于每组测试,请在一行里面输出愚人指数。

样例输入

((((B)()))())
(B)

样例输出

4
1

解题思路

可别把它当括号匹配做啊,题目给出的括号串是完全合法的,不需要检验合法性,甚至用不到STL stack,只需要一个整型模拟栈的元素数量,统计左括号数量就行了。

8. ab串

个人难度评级:3

问题描述

       给定一个由字符’a’和字符’b’组成的字符串,可以删除若干字符,使得剩下来的字符串满足前后段为a,中间段为b(aaa….aaabbbb…..bbbbaaa…..aaa),区段可以没有字符(ba,ab,b,aa都是合法的),求最长剩下字符串的长度。

输入形式

      输入为一行一个长度不超过5000的非空字符串,字符串仅由字符’a’和字符’b’组成。

输出形式

      输出为一个整数,表示符合要求的最长剩下字符串长度

样例输入1

abba

样例输出1

4

样例输入2

bab

样例输出2

2

解题思路

前缀和?什么是前缀和?影响我打暴搜吗?题目数据似乎很菜,分块不多,要不然真搜不完。

这道题的核心思想

将原字符串分割为内部完全由a/b组成的小块,用pair<int,string>存储,比如aabaa可以分割成长度为2的a块、长度为1的b块、长度为2的a块。这里可以使用string的find函数减少工作量。遇到b开头的串其实也不用慌,完全可以先统计a块,最终会在最前面形成一个长度为0的a块,并不影响做题。

然后开始逐块进行深搜。将其化为三种阶段,前面的a串、中间的b串和后面的a串。具体的我再想想怎么讲,建议先去看看代码。大致上就是根据当前搜到a串还是b串来分,然后在此基础上再分1、2或3阶段分情况讨论。

9.占座位

个人难度评级:4

问题描述

sun所在学校的教室座位每天都是可以预占的。
一个人可以去占多个座位,而且一定是要连续的座位,如果占不到他所要求的这么多座位,那么他就一个座位也不要了。为了降低难度,每次分配座位按座位号从小到大查找,采用最先适配法分配座位。

输入形式

输入有多组数据。
每组数据输入座位排数n,0<n<=100(座位的排列数相等,座位是按每行从左到右依次排序的, 第1行的最右边一个座位与第二行的第一个座位视为连续座位),m( 0<m<=min(100,n*n) )个人。
然后输入k(0<k<=100),最后输入k个命令。
命令只有两种:
1.in id num(代表id,0<=id<m,要占num个座位,若占不到连续的num(0<num<=20)个座位表示该命令无效)
2.out id(代表id要释放他之前占的所有座位)
注意:如果id之前占过座还没释放那么之后他的in命令都是无效的,
如果id之前没占过座位那么他的out命令也是无效的。

输出形式

对每个in命令输出yes或者no,如果命令有效则输出yes,无效则输出no。
在yes no后面只带有回车,不带其他任何字符。

样例输入

4 10
9
in 1 7
in 2 3
in 3 3
in 3 3
in 4 3
out 2
in 5 6
out 3
in 5 6

样例输出

yes
yes
yes
no
yes
yes
no
yes
yes

解题思路

这题几乎完全是内存管理一题的翻版……甚至还要简单些,因为阅读理解的困难变小了很多,并且没有碎片整理部分。

座位好几排?没有关系,前一行最后一个和下一行第一个视为连续座位,那不就和内存空间差不多了嘛……

顺便吐槽一下CG的样例,格式也太不标准了点。

10. Maya历法

个人难度评级:2

问题描述

在学术休假期间,M.A. Ya教授在古老的Maya历法上有一个惊人的发现。从一个古老的令人棘手的信息中,教授发现Maya文明以365天为一年,称为Haab,包含19个月。前18个月每月有20天,月份名字为:pop、no、zip、zotz、tzec、xul、yoxkin、mol、chen、yax、zac、ceh、mac、kankin、muan、pax、koyab、cumhu。每月的天数使用数字来表示,从0~19,而不是用名字。Haab的最后一个月叫做uayet,有5天,表示为0、1、2、3、4。玛雅人认为这个月是不吉利的,法院不开庭,贸易停止了,人们甚至停止清扫地板。

       出于宗教的目的,Maya人使用另外一套历法,叫做Tzolkin(冬青年)。一年被分为13个期间,每个期间20天。每天被表示为由数字和日期名表示的数对。使用20个名字:imix、ik、akbal、kan、chicchan、cimi、manik、lamat、muluk、ok、chuen、eb、ben、ix、mem、cib、caban、eznab、canac、ahau,以及13个数字,双循环使用。

       请注意,每一天都有一个明确的描述。例如,在年初的日子被描述如下:

       1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, 在下一个期间开始为 8 imix, 9 ik, 10 akbal . . .

       年份(包含Haab和Tzolkin)用数字0、1、…来表示,数字0是世界的开始。因此,第一天表示为:

       Haab: 0. pop 0

      Tzolkin: 1 imix 0

      请帮M.A.Ya教授写一个程序,将Haab日历转换为Tzolkin日历。  

输入形式

       在Haab中日期用以下形式表示:

               NumberOfTheDay. Month Year

       输入文件的第一行包含文件中输入日期的数目。接下来的n行包含Haab日历格式的n个日期,年份小于5000。

输出形式

        Tzolkin日期用一下格式:

               Number NameOfTheDay Year

        输出包括n行,按照与输入日期对应的顺序,输出tzolkin日历格式日期。 

样例输入

3
10.zac 0
0.pop 0
10.zac 1995

样例输出

3 chuen 0
1 imix 0
9 cimi 2801

解题思路

阅读理解题,难度全在对两种历法的阅读理解上。如果觉得题目读不懂,可以阅读一下玛雅历 – 维基百科,自由的百科全书 (需要魔法上网)。

还读不懂?不妨这样:

输入的历法叫Haab历,它一年有365天,其中包含19个月,前18个月每月20天,第19个月只有5天。这20个月用名字来表示,分别叫做pop、no、zip、zotz、tzec、xul、yoxkin、mol、chen、yax、zac、ceh、mac、kankin、muan、pax、koyab、cumhu。每个月的日期使用数字表示。

需要输出的历法叫Tzolkin历。它并没有传统意义上的“月”和“日”,而是用20个“日名”和13个“日数”的组合来确定一年中唯一的日期,比较像中国的天干地支纪年法。日名和日数各自独立循环使用。天干地支纪年法60年一个循环,那么Tzolkin历就是260天一个循环,也就是一”年“。日名循环的每一天分别叫做imix、ik、akbal、kan、chicchan、cimi、manik、lamat、muluk、ok、chuen、eb、ben、ix、mem、cib、caban、eznab、canac、ahau,而日数循环则直接用1-13的自然数表示。

顺便,注意“0日”和“13日”的转换。

11.数码管

个人难度评级:1

问题描述

液晶数码管用七笔阿拉数字表示的十个数字,把横和竖的一 个短划都称为一笔,即7有3笔,8有7笔等。对于十个数字一种排列,要做到两相邻数字都可以由另一个数字加上几笔或减去几笔组成,但不能又加又减。比如 7→3是允许的,7→2不允许。任意输入一组数,判断是否符合上述规则,注意,1在右边。

输入形式

每行输入一个0~9的排列,数字之间用空格分隔,以-1作为输入结束

输出形式

输出YES或NO

样例输入

4 1 0 7 3 9 5 6 8 2
3 5 1 6 2 7 9 0 4 8
-1

样例输出

YES
NO

解题思路

打表神题,直接预先在纸上算出数字转换关系的邻接矩阵,用的时候直接读取即可。这个关系是对称的,也就是说a能转换为b则b也能转换为a。特别要注意打表的准确性,如果打错了那就完蛋了……建议打2遍。

bool isTransferrable[10][10] = {{1, 1, 0, 0, 0, 0, 0, 1, 1, 0},
                                {1, 1, 0, 1, 1, 0, 0, 1, 1, 1},
                                {0, 0, 1, 0, 0, 0, 0, 0, 1, 0},
                                {0, 1, 0, 1, 0, 0, 0, 1, 1, 1},
                                {0, 1, 0, 0, 1, 0, 0, 0, 1, 1},
                                {0, 0, 0, 0, 0, 1, 1, 0, 1, 1},
                                {0, 0, 0, 0, 0, 1, 1, 0, 1, 0},
                                {1, 1, 0, 1, 0, 0, 0, 1, 1, 1},
                                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                                {0, 1, 0, 1, 1, 1, 0, 1, 1, 1}};

可以使用stringstream承接一行一行的输入,然后逐个读取。

12.多项式加法

个人难度评级:2

问题描述

一个多项式可以表示为一组数对,数对中第一个数始终为整数,且唯一,表示多项式的次数,另一数表示为对应的系数且不为0。输入两组数对,每组以0 0作为结束,实现对两个多项式的加法并按降幂输出结果数对

输入形式

每行输入一个数对,以空格为分隔符,以0 0结束

输出形式

每行输出一个数对,以空格为分隔符

样例输入

5 12
3 8
1 2
15 5
0 10
0 0
3 12
30 1
15 5
0 0

样例输出

30 1
15 10
5 12
3 20
1 2
0 10

解题思路

很容易想到使用数组来存放各个次数的系数,但次数只说了是整数,先不必说太大咋办,首先负系数就能把数组方案毙掉了(虽然还是能得大约60分)。这时候使用std::map就十分有必要了,不过这样的话要考虑相加之后系数为0的情况。

正常考试的时候应该会有数据范围的,只要能看到,就一般能想到不能用数组存。

13.数字统计

个人难度评级:1

问题描述

给定一个k位整数N = dk-1*10k-1 + … + d1*101 + d0 (0<=di<=9, i=0,…,k-1, dk-1>0),请编写程序统计每种不同的个位数字出现的次数。例如:给定N = 100311,则有2个0,3个1,和1个3。

输入形式

每个输入包含1个测试用例,即一个不超过1000位的正整数N。

输出形式

对N中每一种不同的个位数字,以D:M的格式在一行中输出该位数字D及其在N中出现的次数M。要求按D的升序输出

样例输入

100311

样例输出

0:2
1:3
3:1

解题思路

这个有啥好讲的啊……

14. A除以B

个人难度评级:1

问题描述

本题要求计算A/B,其中A是不超过1000位的整数(A>=0),B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。

输入形式

输入在1行中依次给出A和B,中间以1空格分隔。

输出形式

在1行中依次输出Q和R,中间以1空格分隔。

样例输入

123456789050987654321 7

样例输出

17636684150141093474 3

解题思路

挺简单一道题,就是高精除低精。但是要注意两点:

  1. 去掉前导0;
  2. 不要把商为0当成前导0给去掉了(这个会卡测试数据3)。

15.公交系统

个人难度评级:2

问题描述

        城市公交系统有一个记录仪,用于记录每个站点的乘客人数的变化情况,例如:x表示到站前公交车上的乘客人数,y表示离站时公交车上的乘客人数,则该记录仪记录的该站的数字为y-x。

        对于一辆公交车和n个车站,a1,a2,…,an为该公交车在各站的记录数据。

        假定w为该公交车可容纳的最大乘客人数,编程求出在第一站停靠之前公交车上人数的可能数据有多少种?

输入形式

        第一行包含两个数据n和w(1<=n<=1000, 1<=w<=109),分别表示车站的数目和公交车可容纳的最大乘客人数。

        第二行包含一个序列a1,a2,…,an,表示记录仪记录的各站的数据。

输出形式

        输出一个整数,表示公交车在第一站停靠之前可能的乘客人数数据的个数,如果没有,则输出0。

样例输入1

3 5
2 1 -3

样例输出1

3

样例输入2

2 4
-1 1

样例输出2

4

样例输入3

4 10
2 4 1 2

样例输出3

2

样例说明

在第一个样例中,乘客数可能有0、1、2,共3种情况

在第二个样例中,乘客数可能有1、2、3、4,共4种情况

在第三个样例中,乘客数可能为0或1,共2种情况

解题思路

假定一开始车上有0个人,然后录入变动情况,记录车上的最大最小人数。

如果最大人数超过额定载客量,或者最大人数和最小人数的差大于额定载客量,则输出0。

在最小人数大于等于0的情况下,只需要满足最大人数+初始人数<=额定载客量即可;如果小于0,则还需要满足最小人数+初始人数>=0。

满足以上条件的初始人数情况数,即为结果。

16.成绩大派对

个人难度评级:1

问题描述

读入n名学生的姓名、学号、成绩,分别输出成绩最高和成绩最低学生的姓名和学号。

输入形式

每个测试输入包含1个测试用例,格式为

 第1行:正整数n
  第2行:第1个学生的姓名 学号 成绩
  第3行:第2个学生的姓名 学号 成绩
  ... ... ...
  第n+1行:第n个学生的姓名 学号 成绩

其中姓名和学号均为不超过20个字符的字符串,成绩为0到100之间的一个整数,这里保证在一组测试用例中没有两个学生的成绩是相同的。

输出形式

对每个测试用例输出2行,第1行是成绩最高学生的姓名和学号,第2行是成绩最低学生的姓名和学号,字符串间有1空格。

样例输入

3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

样例输出

Mike CS991301
Joe Math990112

解题思路

分别维护姓名、学号和成绩的临时变量、最大值、最小值,边输入边更新即可。

17.字符串数字置换

个人难度评级:1

问题描述

从键盘接收用户输入的字符串, 对用户输入的每个字符串的处理是:将字符串内的每一个十进制数字字符置换成下列表格中右边所对应的一个字符串(所有其他字符不变),然后将转换的结果显示在屏幕上;并分别计算每个数字的置换次数。

十进制数字字符置换成
0(Zero)
1(One)
2(Two)
3(Three)
4(Four)
5(Five)
6(Six)
7(Seven)
8(Eight)
9(Nine)

例如,若用户输入的字符串为

         Page112-Line3,

则程序5的输出是:

         Page(One) (One) (Two)-Line(Three),

数字0到9的置换次数分别是  0 2 1 1 0 0 0 0 0 0

输入形式

输入一行字符串,其中可包含字母、数字、空格或其他符号(英文)

输出形式

第一行为将字符串中的数字转换为表格中的内容后输出

第二行为数字0~9被转换的次数

样例输入

Page112-Line3

样例输出

Page(One)(One)(Two)-Line(Three)
0 2 1 1 0 0 0 0 0 0

解题思路

没什么好讲的

18.写出来吧

个人难度评级:1

问题描述

读入一个自然数n,计算其各位数字之和,用汉语拼音写出和的每一位数字。

输入形式

每个测试输入包含1个测试用例,即给出自然数n的值。这里保证n小于10的100次方。

输出形式

在一行内输出n的各位数字之和的每一位,拼音数字间有1 空格,但一行中最后一个拼音数字后没有空格。

样例输入

1234567890987654321123456789

样例输出

yi san wu

样例说明

友情提示汉语拼音

0~9:ling yi er san si wu liu qi ba jiu shi

解题思路

没什么好讲的,倒是这拼音提示挺侮辱智商的。

19.到底买不买

个人难度评级:1

问题描述

小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串,但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下,某串珠子里是否包含了全部自己想要的珠子?如果是,那么告诉她有多少多余的珠子;如果不是,那么告诉她缺了多少珠子。

为方便起见,我们用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。例如在图1中,第3串是小红想做的珠串;那么第1串可以买,因为包含了全部她想要的珠子,还多了8颗不需要的珠子;第2串不能买,因为没有黑色珠子,并且少了一颗红色的珠子。

pimg1030_1.jpg

输入形式

每个输入包含1个测试用例。每个测试用例分别在2行中先后给出摊主的珠串和小红想做的珠串,两串都不超过1000个珠子。

输出形式

如果可以买,则在一行中输出“Yes”以及有多少多余的珠子;如果不可以买,则在一行中输出“No”以及缺了多少珠子。其间以1个空格分隔。

样例输入

ppRYYGrrYBR2258
YrR8RrY

样例输出

Yes 8

解题思路

这是一个很好想很好写很好调但未必快的思路。

我们都知道char本质上是用ASCII码存储的,那么统计某个字符串中某字符出现数量,可以直接加到对应ASCII码下标的数组值里面。

遍历一遍待买的字符串和想要的字符串,分别加到两个数组里,然后分别统计少的和多的即可。

注意数组要开大点,ASCII码范围是0-127,我们需要的最大是z即122。

一个更好的方案是使用std::map来维护对应关系。

20.挖掘机技术哪家强

个人难度评级:1

问题描述

为了用事实说明挖掘机技术到底哪家强,组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

输入形式

输入在第1行给出不超过105的正整数N,即参赛人数。随后N行,每行给出一位参赛者的信息和成绩,包括其所代表的学校的编号、及其比赛成绩(百分制),中间以空格分隔。

输出形式

在一行中给出总得分最高的学校的编号、及其总分,中间以空格分隔。题目保证答案唯一,没有并列。

样例输入

6
3 65
2 80
1 100
2 70
3 40
3 0

样例输出

2 150

问题说明

建议练习使用STL中的map

解题思路

建议翻别人用map写的题解,我没用。毕竟总共105个学校,又不是不能用数组。

21. Web导航

个人难度评级:1

问题描述

标准的Web浏览器具有在最近访问的页面中前后移动的特性。实现这些特性的一种方法是使用两个堆栈来跟踪可以通过前后移动到达的页面。在这个问题中,我们要求实现这一点。

       需要支持以下命令:

       BACK:将当前页面压入前向堆栈的顶部;从后向堆栈的顶部弹出该页,使其成为新的当前页。如果后向堆栈为空,则该指令忽略。

       FORWARD:将当前页面压入后向堆栈的顶部;从前向堆栈的顶部弹出该页,使其成为新的当前页。如果前向堆栈为空,则该指令忽略。

       VISIT:将当前页面压入后向堆栈的顶部,将URL指定为新的当前页。前向堆栈被清空。

       QUIT:退出浏览器。

       假设浏览器最初在网址http://www.game.org/上加载网页。

输入形式

输入是一个命令序列。命令关键字BACK、FORWARD、VISIT和QUIT都是大写。URL中无空格,最多有70个字符。假定在任何时候,每个堆栈中没有问题实例需要超过100个元素。输入的结尾由QUIT命令标识。

输出形式

除QUIT外的每个命令,如果命令没有被忽略,则在命令执行后输出当前页面的URL,否则,打印”Ignored”。每个命令的输出独立打印一行。QUIT命令无输出。

样例输入

VISIT http://game.ashland.edu/
VISIT http://game.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.our.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

样例输出

http://game.ashland.edu/
http://game.baylor.edu/acmicpc/
http://game.ashland.edu/
http://www.game.org/
Ignored
http://game.ashland.edu/
http://www.our.com/
http://game.ashland.edu/
http://www.game.org/
http://game.ashland.edu/
http://www.our.com/
Ignored

解题思路

直接照着题上的提示写就行了,没有特殊情况。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇