stdKonjac's Blog

 要做到不可替代,就要与众不同。

【SCUACM Training 1】

题解:

A:

扫一遍字符串把最大出现次数的分配为26,次大分配为25,依次类推。

B:

先找一个起始点a(找不到就输出-1),然后依次匹配当前能变换的字母,由于同一个地方可以变换多次,所以只要x<=当前需要的字母即可将x变为当前需要字母,然后需要字母变为字母表下一位。当所有字母都得到后输出字符串,否则输出-1.

C:

可以计算每一家烧烤店的烧烤单价F[i]/J[i],然后进行排序,显然尽量买便宜的能够买的更多,所以当能够整店买下就整店买,不能的话能买多少就买多少。

D:

将体重从大到小排,为了最大利用座位要尽可能坐两个人,所以从大到小扫一遍,对于每一个人找能坐一起的人中体重最重的那个一起坐,找不到就不管。

E:

这题需要注意已经到对面的人是可以把车骑回来的……对于每一时刻显然出发点有两种比较优秀的决策:

①尽量让两个时间长的一起走:先让最快与次快过去,最快回来,再让最慢和次慢的过去,次快回来,花费时间为v[2]+v[1]+v[n]+ v[2]

②带一个最快的方便回来:先让最快和最慢过去,最快回来,再让最快和次慢的过去,最快回来,花费时间为v[n]+v[1]+v[n-1]+v[1]

最后注意边界,判断一下剩3个人、2个人、一个人的情况即可。

F:

这题为了方便需要用到一个叫做multiset的STL(与set的区别:multiset能够允许重复元素存在而set不行)。

Alice为了能够最大效率的覆盖掉Bob的所有卡片,显然要找长、宽都最接近的卡片,所以首先按长排序,长一样按宽排序。

遍历Alice的每一张卡片,找到Bob的卡片里长比当前卡片小的,加入到multiset里。因此multiset里全是可用的卡片,而且因为Alice的卡片按长度递增,所以比当前卡片长度小的卡片一定也比后来所有的卡片长度小,multiset不用清零。然后使用upper_bound函数找到可用卡片中宽度与当前卡片最接近的,如果能找到则答案+1,然后删掉那张卡片,最后输出答案即可。

G:

显然对于两个串A,B 设A中含有的s数为A.s,h数为A.h,B中含有的s数为B.s,h数为B.h,只考虑两个串之间能产生的收益:

①A放前面,B放后面,两个串能产生的收益为A.s*B.h

②A放后面,B放前面,两个串能产生的收益为A.h*B.s

所以显然用sort对串按此方式排序,最后所有串连接起来,统计(s,h)数目即可。

H:

要使田忌尽可能赢得多,那么就要“用最小的代价赢,输也要输的最值”

考虑所有的情况:

①田忌的最慢马比齐王的最慢马快:直接赢,发挥最慢马的最大价值。

②田忌的最慢马比齐王的最慢马慢:反正都赢不了了,让它去干掉齐王最快的马当然是最好的。

③田忌的最慢马和齐王的最慢马跑的一样快:

I.田忌的最快马能跑赢齐王的最快马:让最快马赢,最慢马留着去消耗之后的快马。

II.田忌的最快马跑不过齐王的最快马(输或者平局)

让田忌的最慢马和齐王的最快马比,注意判断一下最慢马是不是可以和最快马跑成平局。

这样总是最优的,因为就算这局输了,好马被保留下来可以为后来做准备再赢回来,所以输赢不变。

 

 

点赞
  1. 学分说道:

    这就是acm强者的世界吗

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.