程序设计小能手 省赛（程序设计小能手）
程序设计小能手 省赛（程序设计小能手）**************************Welcome ContestantNo.1!*输出三行，表示贺卡。1*************************
第一题：欢迎(welcome.cpp) 本题总分：70 分问题描述
欢迎参加 2020 年常州市“程序设计小能手”比赛！小 X 想为你献上一张贺卡，不过...你得自己打印出来。
贺卡由三行组成。其中第二行为”*Welcome ContestantNo.A!*”，其中 A 是选手的编号。第一行和第三行相同，是和第二行字符数量相同的”*”组成。你可以通过样例来理解。
输入格式输入数据只有一行，包含一个正整数 A，表示选手的编号。
输出格式输出三行，表示贺卡。
样例输入 11
样例输出 1*************************
*Welcome ContestantNo.1!*
*************************
样例输入 2233
样例输出 2***************************
*Welcome ContestantNo.233!*
***************************
数据范围本题共有 5 个测试点，每个测试点 14 分对于测试点 1 ：A=8
对于测试点 2 ：A=88
对于测试点 3-5：A<=10^9
提示：你可以通过复制样例输出来避免一些问题
题解：先求出输入的编号A的位数，就能确定第一行和第三行的长度，按照输出格式要求输出即可。
参考程序：
问题描述
小 X 参加了一场作文比赛的初赛。算上小 X，他的学校一共有 n 个人参加了这场比赛。一个礼拜后，小 X 兴奋地打开比赛官网，发现一等奖、二等奖、三等奖的分数线和所有人的得分都已经公布了，但没有提到获得什么奖项才能进入复赛。小 X 想问问你，如果要获得了 A 等奖才能进入复赛的话，他的学校有多少人能进入复赛呢？
假设 A 等奖的分数线是 x，一个人的分数是 y，那么如果 y 大于等于 x，这个人就获得了 A 等奖。
输入格式输入数据共有四行。
第一行一个正整数 n，表示小 X 的学校一共有 n 个人参加了比赛。第二行 n 个正整数，表示小 X 的学校中所有人的得分。
第三行三个正整数 L3 L2 L1，分别表示三等奖、二等奖、一等奖的分数线。第四行一个正整数 A，表示要获得了 A 等奖才能进入复赛。
输出格式输出一行包含一个整数，表示有多少人进入复赛。
样例输入4
99 101 200 300
100 200 300
2
样例输出2
样例解释第一个人 99 分，没有奖项
第二个人 101 分，获得了三等奖
第三个人 200 分，获得了三等奖、二等奖
第四个人 300 分，获得了三等奖、二等奖、一等奖
一共有 2 个人获得了二等奖，所以有 2 个人进入复赛
数据范围本题共有 10 个测试点，每个测试点 8 分
对于全部数据：所有人的得分<=1000，L3<=L2<=L1<=1000，A 是{1 2 3}中的一个
对于测试点 1-2 ：n=1
对于测试点 3-6 ：n<=10
对于测试点 7-10：n<=10000
题解：获得A等奖的条件就是满分>=LA.，因此只要枚举所有人统计出进入复赛的人数。
参看程序：
问题描述
小 X 是 C 城著名的考古学家。一日，他被重金聘请调查一座荒漠中的宫殿。宫殿大门紧闭，但这难不倒聪明的小X。他在隐蔽处发现了两个数字正方形：
小 X 略加思索便发现了其中的奥妙：把数字从小到大依次填入正方形中，每次填最外面的一圈；每一圈从左上角开始，按照顺时针、逆时针、顺时针……的顺序填。
作为小 X 的助手，他希望你帮助他以相同的规律填上旁边 n*n 的空白方阵。这里方阵是数字正方形的简称，通常用二维数组来存放其中的数字。
输入格式输入数据仅有一行，包含一个正整数 n，表示方阵的边长，即每行每列有多少个数。
输出格式输出仅 n 行，每行 n 个正整数，相邻两数之间严格用一个空格隔开。
样例输入6
样例输出1 2 3 4 5 6
20 21 32 31 30 7
19 22 33 34 29 8
18 23 36 35 28 9
17 24 25 26 27 10
16 15 14 13 12 11
数据规模本题共有 10 个测试点，每个测试点 10 分对于测试点 1 ：n=1； 对于测试点 2 ：n=2
对于测试点 3 ：n=3； 对于测试点 4 ：n=4 对于测试点 5 ：n=7； 对于测试点 6 ：n=8
对于测试点 7 ：n=10；对于测试点 8 ：n=15 对于测试点 9 ：n=25；对于测试点 10：n=50
题解：
先考虑顺时针旋转的情况：先从小到大填每一个数，用变量x y dx dy分别表示当前数的坐标和上一个数到这一个数的方向。如果(x dx y dy)没有被填过，那么下一个数就填这个位置；否则就先交换dx和.dy 再将dy变成-dy。
再考虑逆时针旋转的情况：逆时针填一圈可以先顺时针填这一圈，然后沿y=x这条直线翻折，即逆时针中（x y）处的数等于顺时针中（y x）处的数。所以可以先将所有圈顺时针填，然后再将逆时针的圈翻折一下。
参考程序：
问题描述
回家后，小 X 望着自己打瞌睡时写的英语笔记陷入了迷茫。由于太困了，他会时不时地把一个字母多写几次：比如可能把“she”写成“shhe”，也可能写成“ssshee”。
但他依稀记得这堂课只讲了一个重点单词。为了找到这个单词，他想先把每个单词中连续重复的字母压缩起来：把“coool”压缩为“col”，把“aabbaa” 压缩为“aba”。接下来找到压缩后出现次数最多的单词，这样就能找到重点单词了。
由于工作量太大，小 X 希望你帮助他找到重点单词。他向你保证压缩后的单词出现次数最多的一定唯一。
输入格式第一行一个整数 n 表示笔记上共写了 n 个单词。接下来 n 行，每行一个字符串，表示一个单词。
输出格式输出数据只有一行，包含一个字符串，表示压缩后出现次数最多的单词。
样例输入3 qaaqqq qwwwwq qqqqaq
样例输出qaq
样例解释“qaaqqq”压缩成“qaq” “qwwwwq”压缩成“qwq” “qqqqaq”压缩成“qaq”
“qaq”出现了两次，“qwq”出现了一次 所以“qaq”出现次数最多
数据范围本题共有 10 个测试点，每个测试点 10 分对于全部数据：单词长度<=50
对于测试点 1 ：n=1，单词长度为 1
对于测试点 2-3 ：n<=10000，单词长度为 1 对于测试点 4-6 ：n=1
对于测试点 7-8 ：n<=10
对于测试点 9-10：n<=10000
题解
第一步：可以按照以下流程来压缩一个字符串S。增加一个临时字符串stemp 初始值为空串，然后从前到后枚举S中的每一个字符c ，如果stemp是空串或者stemp的最后一个字符和c不同 那么将c添加到stemp的末尾 而其他情况不进行任何操作。
第二步：再将所有压缩后的字符串进行排序，所有相同的字符串肯定连续排列，只要扫描一遍数组就可以求出出现次数最多的目标串。
参考程序：
第五题:勇士斗恶龙 (fight.cpp)本题总分：150 分
问题描述
小 X 穿越到了异世界，国王命令他招揽勇士，杀死恶龙，救回公主。
异世界是高度数据化的。恶龙有一个攻击力 ATK，一个生命值 HP。类似的， 每个勇士也有一个攻击力 Ai，一个生命值 Hi。
战斗是回合制的，并且每次只能由一个勇士和恶龙单挑。战斗中，每个回合 恶龙的生命值会减去这个勇士的攻击力，这个勇士的生命值会减去恶龙的攻击力。如果回合结束的时候恶龙的生命值小于等于 0，那么恶龙就被杀死了；如果这个勇士的生命值小于等于 0，那么这个勇士就被击败了，需要换上另一个勇士继续战斗。当然，如果恶龙还没有被杀死，勇士却全部被击败了，那么这场战役就彻 底失败了。
不过聪明的小 X 安排了一个特殊的战术：在一名勇士被击败后立刻让另一名勇士发起攻击，这样恶龙在勇士们的车轮战术下疲于招架，受到第二个勇士的伤害变为两倍，受到第三个勇士的伤害变为三倍……以此类推。
现在一共有 n 名勇士报名，小 X 想问问你，如果合理安排勇士出战的顺序， 最少要招揽多少名勇士才能杀死恶龙？
输入格式第一行为一个正整数 n，表示一共有 n 名勇士报名。
第二行两个正整数 ATK 和 HP 表示恶龙的攻击力和生命值。
接下来共有n 行，每行两个正整数 Ai 和 Hi 表示这名勇士的攻击力和生命值。
输出格式输出一个整数，表示最少要招揽多少名勇士才能杀死恶龙。如果不可能杀死恶龙，输出”Fail”。
样例输入2
1 9
2 2
1 1
样例输出2
样例解释两名勇士都招揽。先派出 2 号勇士
第一回合，恶龙生命值变为 8，勇士生命值变为 0。勇士被击败紧接着派出 1 号勇士
第二回合，恶龙生命值变为 4（两倍伤害），勇士生命值变为 1 第三回合，恶龙生命值变为 0，勇士生命值变为 0。恶龙被杀死勇士虽然也被击败了，但恶龙已经死了，所以还是胜利了！
数据范围本题共有 10 个测试点，每个测试点 15 分
对于测试点 1-4 ：n<=5，ATK Hi Ai<=10，HP<=100
对于测试点 5-7 ：n<=1000，ATK Hi Ai<=1000，HP<=10^9 对于测试点 8-10 ：n<=10^5，ATK Hi Ai<=10^6，HP<=10^18
题解：
这是一道贪心题。由于恶龙的攻击力ATK是不变，即每个勇士坚持的轮数Hi/ATK不变。如果第i个勇士的基础伤害为Bi=Hi/ATKAi 第i个勇士第j个战斗造成的伤害为Bij。
要打败恶龙，一定是要对恶龙造成尽可能多的伤害。如果选择n个勇士出战，那么一定要选择Bi最大的n个出战。
本题中，考虑两个勇士x y的相对顺序，假设只有这两个勇士。那么x在前的 总伤害为Bx 2By y在前的总伤害为By 2BX。判断x y哪个应该放在前面，即判断 Bx 2By和By 2BX的大小。两者最差得到By-Bx。当By-Bx<0时，即Bx〉By时 y在前更优；当By-Bx〉0时，即Bx<By时，x在前面更优，也就是B值小的勇士应该先出战。
注意到出战的勇士越多，造成的伤害就越大。所以可以二分答案，找到能杀死恶龙的最小人数。根据上面的结论，可以知道当有k个勇士出战的时候，出战的人选和顺序都是确定的 可以计算出造成的总伤害。
参考程序：
