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

作业训练1

1. 众数

个人难度评级：1

问题描述

一组数据中出现最多的数，称为众数。比如

1 2 3 3

众数为3。一组数据中也可能有多个众数，以最先出现的作为众数。比如

2 2 3 3

众数为2。

   问题是一组按升序排好的数据，指出它的众数。

输入形式

有多组测试数据（不超过100组测试数据）。

每组测试数据占两行，第一行是正整数N：表示这组测试数据中数据项数。

第二行是N个用空格隔开的正整数，表示这组测试数据的数据元素。每个数据元素都不大于10000。

N=0，表示输入结束，并且不需要处理。

40% 的测试数据N 1 ≤N≤ 10；

30% 的测试数据N 10 < N≤ 100；

20% 的测试数据N 100 < N≤ 1000；

10% 的测试数据N 1000 < N≤ 10000；

输出形式

对于每组测试数据，输出一行包含一个正整数：对应的众数。

样例输入

1
2
3
4
5

4
1 2 3 3
4
2 2 3 3
0

样例输出

1
2

3
2

解题思路

使用桶排序的思想，设一个数组，存储每个数的出现次数。再遍历这个数组，取最大值。

数据是按升序排好的，所以也许一遍循环能走完，而且能省下桶排的数组空间？

2. 错误的里程碑

个人难度评级：2

问题描述

三月八日，小明买了台新车。但很快小明发现汽车的里程表有问题：里程表上每一位都不显示数字3和数字8，也就是说直接从数字2跳到数字4，直接从数字7跳到数字9。小明纳闷：这车到底行驶里程是多少。

现在，小明向你求助：根据里程表显示的数字，给出真实的行驶里程。

输入形式

输入有多组测试数据。

输入第一行正整数T，表示有多少组测试数据。

后面有T行，每行一个非负整数，表示里程表显示数字，里面不含有数字3和8。该数字不超过10位。

40% 的测试数据组数T  10≤T≤ 102；

30% 的测试数据组数T  102≤T≤ 103；

20% 的测试数据组数T  103≤T≤ 104；

10% 的测试数据组数T  104≤T≤ 105；

输出形式

对于每组测试数据，输出一个整数占一行：真实的行程里程。

样例输入

1
2
3
4
5
6
7

6
0
1
12
159
111224459
124567976

样例输出

1
2
3
4
5
6

0
1
10
103
19212007
21913077

解题思路

实际上这是一个8进制里程表，因为只有0、1、2、4、5、6、7、9，也就相当于0、1、2、3、4、5、6、7。做一个八进制转十进制即可。可能需要使用long long类型。

3. 拳王阿里

此题有些问题，暂不处理。

4. 欧洲冠军联赛

个人难度评级：2

问题描述

       欧洲冠军联赛常被誉为全世界最具影响力的俱乐部级赛事。在比赛的小组赛阶段，欧洲的各个足球俱乐部被分为八个小组，每个小组中四支球队。每个小组中的球队按照如下规则排序：

• 球队会根据比赛结果获得积分。一场比赛的双方被称为主队和客队。如果其中一方进球数多于另一方，那么进球较多的一方获得3分，另一方获得0分。如果双方打成平手，则各得1分。
• 球队的净胜球数是其进球数减去失球数（不考虑该球队在比赛中作为主队还是客队）。
• 积分较高的球队排名更加靠前。
• 如果两支球队积分相同，那么净胜球数较多的球队排名靠前。

      小组的各队伍进行循环赛，即每两支球队之间进行两场比赛，双方交替作为主队。给定一个小组内12场比赛的结果，请求出小组的出线队伍：即排名第一和第二的两支球队。

保证答案唯一。

输入形式

      输入的第一行包含一个整数T，代表测试数据的组数。接下来是T组数据。

      每组数据共有12行，每行描述一场比赛，格式为：“主队队名主队进球数vs. 客队进球数客队队名”，其中 “主队队名” 和“客队队名”为字符串，“主队进球数”和 “客队进球数” 为两球队在本场比赛中各自的进球数量。

• 1 ≤ T ≤ 50
• 球队队名仅包含小写英文字母
• 球队队名长度不超过10个字符
• 0 ≤ 进球数 ≤ 100

输出形式

       对于每组数据，输出一行，包含两个字符串，代表排名第一和第二的球队的队名。

样例输入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2
manutd 8 vs. 2 arsenal 
lyon 1 vs. 2 manutd 
fcbarca 0 vs. 0 lyon 
fcbarca 5 vs. 1 arsenal 
manutd 3 vs. 1 fcbarca 
arsenal 6 vs. 0 lyon 
arsenal 0 vs. 0 manutd 
manutd 4 vs. 2 lyon 
arsenal 2 vs. 2 fcbarca 
lyon 0 vs. 3 fcbarca 
lyon 1 vs. 0 arsenal
fcbarca 0 vs. 1 manutd
a 3 vs. 0 b 
a 0 vs. 0 c 
a 0 vs. 0 d 
b 0 vs. 0 a 
b 4 vs. 0 c 
b 0 vs. 0 d 
c 0 vs. 0 a 
c 0 vs. 0 b 
c 1 vs. 0 d 
d 3 vs. 0 a 
d 0 vs. 0 b 
d 0 vs. 0 c

样例输出

1
2

manutd fcbarca 
d b

样例说明

第一组数据：每支球队的积分与净胜球数分别为：

• manutd：16分，净胜球数12。
• manutd：8分，净胜球数4。
• manutd：5分，净胜球数 −5。
• manutd：4分，净胜球数 −11。

第二组数据：每支球队的积分与净胜球数分别为：

• d：7分，净胜球数2。
• b：7分，净胜球数1。
• a：7分，净胜球数0。
• c：7分，净胜球数 −3。

所有球队的积分相同，但是净胜球数较多的队伍排名更加靠前。

解题思路

使用结构体存储球队的名称、净进球数和得分，使用一个结构体数组存储所有球队信息。

注意找不到已记录球队就新建球队的操作。

5. 合法的括号串

个人难度评级：3

问题描述

一个合法的括号串，是指只包含括号的串，如果满足如下条件：

（1）<> () [] {} 这四对括号是合法的；

（2）如果r是合法括号串，则 <r> (r) [r] {r} 也是；

（3）如果r，s是合法括号串，则rs也是；

所以 «» , [<>{}(())],[({<>})] 是合法的括号串，而)(,[( ])就不是。

输入形式

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行一个只包含8种括号符号的括号串。

40% 的括号串的长度L 2 ≤ L≤ 20；

30% 的括号串的长度L 2 ≤ L≤ 200；

20% 的括号串的长度L 2 ≤ L≤ 2000；

10% 的括号串的长度L 2 ≤ L≤ 20000；

输出形式

对于每组测试数据，如果括号串是合法的，输出 “Yes”（输出没有引号）占一行，否则，输出 “No”（输出没有引号）占一行。

样例输入

1
2
3
4
5
6
7

6
<<>> 
)(
[<>{}(())]
[({<>})]
[(])
<([{

样例输出

1
2
3
4
5
6

Yes
No
Yes
Yes
No
No

解题思路

括号配对是老例题了。使用栈来存储前面未配对的左括号，遇到右括号检验一下是否匹配，然后弹栈。惟需注意：

• 整组数据算完之后将栈清空，否则下一组即使匹配，最后也会栈内还有元素而不匹配；
• 弹栈之前检测栈空，这个应该很容易看出来，一般样例就能反映。

6. 世界杯来了

个人难度评级：3

问题描述

       2018年俄罗斯世界杯结束了，法国获得冠军，全世界球迷度过了一个非常愉快的夏天。作为中国球迷，不能总是看别人踢球，这不福利来了，根据FIFA（国际足联）及全体成员协会的一致决定，2118年世界杯将在中国举办，作为东道主，中国队将无需参加预选赛而直接参加决赛阶段的比赛。

   比赛规则如下：

• 总共n（n为偶数）个球队参加比赛
• 按照分组赛积分排名，前n/2的球队进入淘汰赛
• 积分排名的规则如下：球队获胜得3分，平局得1分，失利得0分，按照积分递减、净胜球递减以及进球数递减方式排名编写一个程序，根据给出的参赛队伍名单和所有比赛的结果，找出成功进入淘汰赛阶段的球队名单。

输入形式

       第一行输入包含唯一整数n(1<=n<=50)，参加世界杯决赛的球队数量。接下来的n行是各球队的名字，为长度不超过30个字符的英文字符。接下来的n*(n-1)/2行，每行格式name1-name2 num1:num2（0<=num1, num2<=100），表示对阵球队及比分. 

输出形式

       输入n/2行，表示进入淘汰赛阶段的球队，按照字典序进行排列，每个球队名字占一行

样例输入

1

4ABCDA-B 1:1A-C 2:2A-D 1:0B-C 1:0B-D 0:3C-D 0:3

样例输出

1

AD

解题思路

跟第4题整体思路差不多，增加了一点难度主要在字符串的分割上。只要掌握根据分隔符将字符串分割成两半的方法就行。

7.F1方程式冠军

个人难度评级：3

问题描述

  一级方程式F1锦标赛由一系列称为大奖赛的分站赛组成。每一场比赛的车手都根据他们的最后位置获得积分。只有前10名车手按以下顺序获得分数：25、18、15、12、10、8、6、4、2、1。在锦标赛结束时，得分最多的车手是冠军。如果有平分，则冠军是赢的最多的人（即排位第一）。如果还是平分，则选择得到排位第二最多的人，依此类推，直到没有更多的排位进行比较。

  后来又提出了另一个得分制度，其中冠军是赢的最多的。如果有平手，冠军是得分最多的。如果仍然存在平手，则按原来的得分制度进行，即比较第二、第三、第四、… 排位的次数。

  在本赛季，你会得到所有比赛的结果，你将根据两个得分系统来分别确定冠军。数据保证两套系统都能得到唯一的冠军。

输入形式

  第一行一个整数t（1<=t<=20），t是分站赛的场次数。之后是每个分站赛的最终排位情况，每个的第一行一个整数n(1<=n<=100) 表示排位车手人数，之后n行按排位列出车手的名字，排位从第一到最后，车手的名字为长度不超过50的英文字符，大小写区分。

输出形式

  输出为两行，第一行为按照原始规则确定的冠军，第二行是按照可选规则确定的冠军。

样例输入

1

33applebananapear2pearbanana2applebanana

样例输出

1

bananaapple

解题思路

和第4题差不多的壳，但主要考察的是结构体的排序，手写不同的比较函数是重点。

注意比较的时候最多可能比较到得到10-20名的次数，所以得到某名次计数的数组要开得大些。

8. 买房与选房

个人难度评级：7

问题描述

       在 X 国许多一线城市住房非常紧张，政府部门制定了相关的政策，重点满足住房刚性需求（住房面积为0，社保缴纳必须超过2年），然后才能照顾改善性需求（住房面积大于0）。

       具体的原则为：

• 对于刚性需求，缴纳社保月数多者优先
• 对于改善性需求，现有自有住房面积小者优先

       由于房源有限，为公平起见，开发商在不违背上述原则下特意指定同等条件下申报时间同时作为排队的条件，时间越早优先级越高。

       最近有一批新楼盘准备开盘，总共有 m （≤1000）套房，所有的网上申报工作都已经完成并保存到二进制文件house.bin中，申请者提交了自己的基本材料，格式为：身份证号（18位，加1位空字符 ‘\0’，共19位）、社保缴纳月数、自有住房面积、申报时间 (格式为：MM-DD-YYYY，10位字符串，加1位空字符’\0’，共11位)，社保缴纳月数、自有住房面积均为整数，文件最后为总报名人数 n（≤105）。

       申请者可以通过身份证号查询最终的结果。

输入形式

       输入的第一行为两个正整数 m（≤1000）和 T （ **T_ ≤ n**_ ），分别表示本次开盘的楼盘可供申请的套数以及查询的组数

       接下来的 T 行，每行为一个18位的字符串，表示需要查询的身份证号

输出形式

       输出为 T 行，对应每个查询的输出结果：

       1. 申请者不符合购房条件或排位超出了所推出的房源数量不能中签，则输出 “Sorry”;

       2. 申请者符合购房条件，且该名次人数为1人，则直接输出一个整数，表示选房顺序号;

       3. 申请者符合购房条件，且该名次人数有多人，同时人数不大于所剩房源数量，则直接输出用空格分隔的两个整数，表示选房顺序号区间;

       4. 申请者符合购房条件，且该名次人数有多人，同时人数大于所剩房源数量，则输出用 / 分隔两个整数，如 A/B，表示 B 人中选 A 人，选房顺序为排名倒数 A 名范围。

样例输入

1
2
3
4
5
6
7

9 6
350102200609166049
350102200609163286
250342323545313434
130502201805070787
110101196003074525
430102201102181455

样例输出

1
2
3
4
5
6

2
3 4
Sorry
6
2/3
Sorry

代码框架

** 建议复制以下代码框架， 在此基础上完成本题需求。此建议不是必须，你可以忽略。**

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>

using namespace std;

struct people

{

    char id[19];                  /* 身份证号码 */

    int social;                     /* 社保缴纳月数 */

    int area;                       /* 现有住房面积 */

    char date[11];              /* 申报日期 */

};

people* getMess(int &n);

int main()

{

    people *person;          /* 指向所有报名人的基本资料首地址，通过调用函数 getMess 获取 */     

    int n;                            /* n 为报名人数，通过调用函数 getMess 获取 */

    person=getMess(n);



    // ...



    return 0;

}

people* getMess(int &n)            /* 将文件数据读入内存 */

{

    FILE *fp;

    fp=fopen("house.bin","rb");

    fseek(fp,-1*(long)sizeof(int), 2);

    fread(&n, sizeof(int),1, fp);

    rewind(fp);

    people *tmp=new people[n];

    fread(tmp, sizeof(people), n, fp);

    fclose(fp);

    return tmp;

}

测试用例说明

  10% 的用例无同等条件的数据，30% 的用例只有刚性需求，20% 的用例只有改善性需求。

文件下载

请下载压缩文件（见CG平台）并在存放源程序文件的文件夹下解开，其中二进制文件house.bin包含了相关的测试数据，test.txt是相关测试数据的文本格式，可用于程序测试。

解题思路

我引入了一个”优先级 “整型变量来决定排到房源的优先级，使这个变量必满足刚性需求社保久> 刚性需求社保少>改善需求小房子>改善需求大房子>没有购房资格，在此顺序绝对成立的基础上，申请早的优先级高。这个可以从我的代码里详细了解。

然后，将其与对应的people结构体组成pair并使用stable_sort排序，按优先级从大到小。这样就可以很容易地得到某个人的名次和同名次人的范围。

我的代码一个点都没过，但我觉得我的思路是对的……

9. 二叉树遍历，从前序、中序到后序

个人难度评级：4

问题描述

二叉树是一种非常重要的 数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，深度遍历有前序、中序以及后序三种遍历方法。

三种基本的遍历思想为：

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树 —> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

比如，求以下二叉树的各种遍历

前序遍历：1  2  4  5  7  8  3  6 

中序遍历：4  2  7  5  8  1  3  6

后序遍历：4  7  8  5  2  6  3  1

需要你编写程序解决的问题是：已知一个二叉树的前序遍历和中序遍历的结果，给出该二叉树的后序遍历的结果。

输入形式

有多组测试数据，每组测试数据三行，每组测试数据第一行只有一个正整数n，表示二叉树节点的数目，n=0意味着输入结束并且不需要处理。

每组测试数据第二行是二叉树的前序遍历的结果，是一个长度为n的字符串，每个节点由一个字符表示，字符是大小写英文字母及10个数字, 不同的节点用不同的字符表示，也即无论前序遍历和中序遍历的字符串中没有重复的字符。

每组测试数据第二行是二叉树的中序遍历的结果，也是一个长度为n的字符串。

40% 的测试数据1 ≤ n≤ 10；

30% 的测试数据1 ≤ n≤ 20；

20% 的测试数据1 ≤ n≤ 40；

10% 的测试数据1 ≤ n≤ 62；

输出形式

对于每组测试数据，输出一行，是一个长度为n的字符串，表示二叉树后序遍历的结果。

样例输入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

8
12457836
42758136
4
abcd
abcd
4
abcd
dcba
0

样例输出

1
2
3

47852631
dcba
dcba

解题思路

使用递归方法。对于每个子树（输入数据本身也算一棵子树），先得到根节点，然后利用其分别分割左子树和右子树并分别传入递归，最后输出根节点。

部分参考了 9. 二叉树遍历，从前序、中序到后序 (递归即可解决)_yogdzewa 的博客 - CSDN 博客。

10. 内存管理

来源：Codeforces 7B

个人难度评级：4

问题描述

       离第一个操作系统HNU-OS发布已经没有多少时间了，但它的一些组件还没有完成，内存管理器就是其中之一。根据开发人员的计划，在第一个版本中，内存管理器将非常简单和直观。它将支持三个操作： 

• alloc n —— 分配n个字节内存，返回已分配块的正整数标识符x(x初始值为0，每次分配增长1)
• erase x —— 删除标识符x所在的块
• defragment —— 整理空余内存碎片，将所有块尽量靠近内存的开始位置，并保持各自的顺序

       在此情况下，内存模型非常简单，它是一个m字节的序列，为了方便起见，从第一个字节到第m字节进行编号。

       第一个操作alloc n有一个参数n，表示被分配的内存块大小。在处理此操作时，内存中将分配n个连续字节的空闲块。 如果这些块的数量超过一个，则优先选择最接近内存开始 (即第一个字节) 的块。 所有这些字节都被标记为非空闲，内存管理器返回一个32位整数数字令牌，代表该块的标识符。 如果不可能分配这样大小的空闲块，则返回NULL。

       第二个操作erase x以x为参数，表示某个块的标识符。此操作释放系统内存，将此块的字节标记为空闲以供进一步使用。 如果此标识符没有指向先前分配的块 (该块尚未被释放)，则返回ILLEGAL_ERASE_ARGUMENT。

       最后一个操作defragment没有任何参数，只会使占用的内存部分更接近内存的开始，而不会更改它们各自的顺序。

       在当前的实现中，将使用从1开始的连续整数作为标识符。每个成功的alloc操作过程都应该返回接下来的编号。不成功的alloc操作不影响计数。 

       编写内存管理器的实现，为每个alloc命令输出返回的值，为所有失败的erase命令输出ILLEGAL_ERASE_ARGUMENT。

输入形式

       输入数据的第一行包含两个正整数t和m（1<=t<=500, 1<=m<=105)，其中t表示需要内存管理器来处理的操作个数，m表示有效的内存字节大小。接下来的t行每一行代表一个操作。

输出形式

       输出有多行，每行或者是alloc操作的结果，或者是失败的erase操作的结果ILLEGAL_ERASE_ARGUMENT。其顺序与输入的操作次序一致。

样例输入

1

6 10alloc 5alloc 3erase 1alloc 6defragmentalloc 6

样例输出

1

12NULL3

解题思路

定义memblock结构体存储内存块，包含标识符、开始点和结束点，和一个是否已经被释放的bool标记。

借鉴了堆的思想，将靠前的内存块前置，靠后的内存块后置，已经释放的内存块则放到最后面去。在插入和释放完成后进行排序，因为相对位置已经改变。

分配新内存块时，先寻找块间的剩余空间，如果不够再尝试从尾部插入，然后排序。释放时将编号对应的块记为已经释放，然后排序。碎片整理操作则是挨个移动已经有序的各个块即可。

11. 平均方差

个人难度评级：1

问题描述

一个数列的平均方差是指数列中的每个元素与数列的平均值的差的平方和的平均值，比如下面数列：

1 2 3 4 5 6 7

其平均值为4，每个元素与平均值的差的平方为

9 4 1 0 1 4 9

其平方和为28，所以该数列的平均方差为4。

对给定的数列，求出其平均方差。

输入形式

有多组测试数据。

每组测试数据第一行是一个正整数N，表示数列中元素个数，接下来一行N个用空格分隔开的正整数，表示数列的N个元素，每个元素的值都是不大于500的正整数。

N=0表示输入结束，并且不需要处理。

40% 的数列元素个数N 1 ≤ N≤ 10；

30% 的数列元素个数N 1 ≤ N≤ 100；

20% 的数列元素个数N 1 ≤ N≤ 1000；

10% 的数列元素个数N 1 ≤ N≤ 10000；

输出形式

对于每组测试数据，输出一个整数：平均方差。平均方差不是整数的，输出其向下取整的整数。比如平均方差是4.5，输出4。

样例输入

1
2
3
4
5

7
1 2 3 4 5 6 7
4
1 2 3 4
0

样例输出

1
2

4
1

解题思路

这玩意有啥解题思路？算就是了。记得适时用double。

12. IP地址

个人难度评级：2

问题描述

一个IP地址由32位二进制的数组成，比如：

111111111111111111111111000000002

为了便于记忆，我们将8个二进制位用一个十进制数表示，一个IP地址由四个十进制数表示，上述的IP地址表示为：

255.255.255.0

现在给你一个上述形式的IP地址，请回答IP地址的32个二进制位中，有多少位是1。

如IP地址为255.255.255.0，其中24位是1。

输入形式

有多组测试数据。

测试数据第一行是一个正整数T，表示测试数据组数。

每组测试数据是一个IP地址，形式为：

IP1.IP2.IP3.IP4

其中0 ≤IP1,IP2,IP3,IP4≤ 255, 用十进制表示。每个IP地址不保证是实用IP地址。

40% 的测试数据组数T  10≤T≤ 102；

30% 的测试数据组数T  102≤T≤ 103；

20% 的测试数据组数T  103≤T≤ 104；

10% 的测试数据组数T  104≤T≤ 105；

输出形式

对于每个IP地址，输出一行包含一个非负整数：该IP地址的32个二进制位中，1的位数。

样例输入

1
2
3
4
5
6

5
255.255.255.0
127.0.0.1
0.0.0.1
1.2.3.4
0.0.0.0

样例输出

1
2
3
4
5

24
8
1
5
0

提示：样例中32位的IP地址为：

111111111111111111111111000000002

011111110000000000000000000000012

000000000000000000000000000000012

000000010000001000000011000001002

000000000000000000000000000000002

解题思路

核心在于进制转换的思想，以及第6题分割字符串的方法。先分割再转换进制，不就很简单了吗？

13. 开关与灯

来源：CodeForces 985B（我湖不愧是9B5）

个人难度评级：2

待完善

14. 可删除的点

个人难度评级：1

问题描述

  平面上有n个不同的点，没有在Y轴的点，检查是否存在这样一个点，将其删除后其余所有的点均位于Y轴的同一边。

输入形式

  输入第一行包含一个正整数n(2<=n<=105)。

  接下来的n行，包含所有点的坐标，第i行包含两个整数xi和yi(|xi|、|yi|<=109，xi<>0)。

输出形式

  如果存在这样的点，则输入 “Yes”，否则输出 “No”。

样例输入

1

31 1-1 -12 -1

样例输出

1

Yes

解题思路

有一个坑点，就是如果所有点本来就在一边，也是符合要求的，别的没什么好说的。

15. 字符串反转3

个人难度评级：3

问题描述

       给出一个字符串，请将其每个单词反转后输出。

输入形式

      输入第一行为一个正整数N，表示测试用例数，接下来的N行，每行一个字符串。

输出形式

      输出N行，每行对应一个反转后的字符串。

样例输入

1

3olleh !dlrowm'I morf .unhI ekil .tae

样例输出

1

hello world!I'm from hnu.I like eat.

解题思路

这题蛋疼就蛋疼在数据5规模相当大，用C++ 的库函数似乎很容易在第5个点超时（没错我也超了）。据大佬说，写一个仅基于C的版本能够大幅度提升效率。如果不是难以预计的TLE（数据规模都没给），这个题并不是很难。

16. n， 还是n

个人难度评级：2

问题描述

输出 包含n或者是n的倍数的所有数

输入形式

正整数m,n（0<m，n<1000000）

输出形式

从小到大排列的不大于m的特殊正整数（包含n，或者是n的倍数）。

样例输入1

1

20 7

样例输出1

1

7 14 17

样例输入2

1

200 11

样例输出2

1

11 22 33 44 55 66 77 88 99 110 111 112 113 114 115 116 117 118 119 121 132 143 154 165 176 187 198

样例说明

包含n的数可以考虑使用字符串查找解决

解题思路

数据规模不大，倍数这个条件直接 % 就行。包含这个条件可以用字符串find成员函数处理。

17. 字符串排序

个人难度评级：1

问题描述

       定义一个字符串的无序度为所有位置后面的字母比该位置的字母小的总数之和。比如 “DAABEC’‘这个字符串的无序度是5，因为D后面有4个位置比它小（AABC），E后面有1个比它小（C），其它位置后面没有比自己小的。” AACEDGG “的无序度为1（E后面有一个D比它小）。” ZWQM " 的无序度为6，每个位置后面所有的字母都比它小。
       现在你的任务是给定一些字符串（只由大写字母组成），把他们按照无序度从小到大排序，如果无序度一样，那么就按照输入的相对顺序排序。

输入形式

    单组测试数据。
    第一行有两个整数n(0 < n <= 50) 和m (0 < m <= 100)，分别表示输入的字符串的长度和字符串的个数。
    接下来m行，每一行包含一个长度为n的字符串，只由大写字母组成。

输出形式

   输出m行，表示排序之后的字符串。

样例输入

1

10 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT

样例输出

1

CCCGGGGGGAAACATGAAGGGATCAGATTTATCGATGCATTTTTGGCCAATTTGGCCAAA

解题思路

照着题目要求算无序度即可。我建议用pair类型分别存储字符串和无序度两个键值，然后用stable_sort自定义排序函数排序，以保持原有输入顺序。没必要排序的时候再算无序度，会很慢。

18. 三角形的面积

个人难度评级：1

问题描述

已知三角形的三个顶点的坐标，求该三角形的面积。

输入形式

有多组测试数据。

每组测试数据占一行，6个用空格分隔开的浮点数：x1,y1,x2,y2,x3,y3。表示三角形三个顶点的坐标。

一行6个0（形如0 0 0 0 0 0），表示输入结束，并且不需要处理。

40% 的顶点坐标 -10 ≤ xi,yi≤ 10；i=1,2,3

30% 的顶点坐标 -100 ≤ xi,yi≤ 100；i=1,2,3

20% 的顶点坐标 -1000 ≤ xi,yi≤ 1000；i=1,2,3

10% 的顶点坐标 -10000 ≤ xi,yi≤ 10000；i=1,2,3

输出形式

对于每组测试数据，输出对应三角形面积，保留小数点后6位。

样例输入

1
2
3

1 2 3 4 -2 8
0 0 0 1 1 0
0 0 0 0 0 0

样例输出

1
2

9.000000
0.500000

Tips：如果使用浮点数，请注意精度问题，推荐使用double

解题思路

数论题，如果会了海伦公式，很简单。

19. 循环数

来源：POJ 1047

个人难度评级：3

问题描述

      循环数是n位长度的整数，当乘以从1到n的任何整数时，产生原始数字的 “循环”。也就是说，如果考虑最后一个数字之后的数字“绕” 回到第一个数字，两个数字中的数字序列将是相同的，尽管它们可能从不同的位置开始。例如，数字142857是循环的，如下表所示： 

        142857 *1 = 142857
        142857 *2 = 285714
        142857 *3 = 428571
        142857 *4 = 571428
        142857 *5 = 714285
        142857 *6 = 857142 

       编写一个程序来确定数字是否是循环数。

输入形式

       输入一个数，长度在2到60位之间 (请注意，前面的零不应该被删除，它们被认为是确定n的大小和计数的一部分，因此，“01” 是一个两位数的数字，与 “1” 是一个一位数的数字不同。) 。

输出形式

       对于每个输入，输出一行 (Yes或No) 标识它是否是循环数。 

样例输入

1

142857

样例输出

1

Yes

解题思路

主要的麻烦是如何判断一个数和另一个是可以绕回来，以及如何处理60位数字的乘法问题。

事实上，如果一个序列可以分成两部分，调换顺序之后与另一个序列相等（或者进一步地，两个部分都是另一个序列的子串），那就可以” 绕回来 “。我枚举了分界线，使用std::string的substr成员函数分割字符串，并使用上文提到的find成员函数判断子串。

如此长数字的乘法，属于高精乘低精的问题，可以仿照竖式计算的方法计算。

20. 电能消耗

来源：Codeforces 10A

个人难度评级：1

问题描述

      汤姆对他最喜欢的笔记本电脑的耗电量很感兴趣。他的笔记本电脑有三种模式。在正常模式下，笔记本电脑每分钟消耗P1瓦。在汤姆最后一次移动鼠标或触摸键盘后的T1分钟，屏幕保护程序启动，每分钟的功耗变化为P2瓦。最后，从屏幕保护程序启动到T2分钟后，笔记本电脑切换到 “睡眠” 模式，每分钟消耗P3瓦。 当笔记本电脑处于第二或第三模式时，如果汤姆移动鼠标或触摸键盘，则切换到第一种 (正常) 模式。 汤姆使用笔记本电脑工作的时间可以分为n个时间间期 [l1, r1]、[l2, r2]、…、[ln, rn]。在每个间期，汤姆连续移动鼠标并按下键盘。 在间期之间，汤姆什么都不做。请找出在间期 [l1, rn]笔记本电脑的总耗电量。

输入形式

      第一行包含6个整数n、P1、P2、P3、T1、T2(1<=n<=100，0<=P1、P2、P3<=100，1<=T1、T2<=60)。接下来的n行包含了汤姆工作的期间，第i行是两个用空格分隔的整数li和ri(0<=li<=ri<=1440, 当i<n时ri<li+1）, 表示工作期间的开始时间和结束时间。

输出形式

      输出总的耗电量。

样例输入

1

2 8 4 2 5 1020 3050 100

样例输出

1

570

解题思路

如果要说有难点的话，就是L1和Rn的选取存储。我的办法是将第一组特殊处理，具体的可以直接看我代码。

21. 计算校验码

个人难度评级：3

问题描述

传送一个B（B≤16）进制的数值N时，最后加上一个一位（B进制的）校验码，使得N加上校验位后能被B-1整除。比如十进制的数值12310，其校验码就是3，因为十进制数值123310能被9整除。16进制的数7816，其校验码为0，因为16进制的78016是15的倍数。超过十进制后，用字母a表示10，字母b表示11，字母c表示12，字母d表示13，字母e表示14，字母f表示15。

告诉你进制B，以及一个B进制的正整数N，要求你计算正整数N在B进制下的校验码。

输入形式

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行两个正整数B，N（2≤ B≤16），中间用一个空格隔开，B是10进制整数，N用B进制形式表示。测试数据保证没有非法的B进制数N（也即N中每一位都是在0到B-1之间，没有前导0）。

40% 的测试数据N的位数L 1 ≤ L≤ 10；

30% 的测试数据N的位数L 1 ≤ L≤ 102；

20% 的测试数据N的位数L 1 ≤ L≤ 103；

10% 的测试数据N的位数L 1 ≤ L≤ 104；

输出形式

对于每组测试数据，输出一位占一行：正整数N在B进制下的校验码。（如果校验码可以为B-1，也可以为0，输出0）。

样例输入

1
2
3
4
5

4
10 123
16 78
16 1234321
12 ab

样例输出

1
2
3
4

3
0
e
1

样例说明

第一行的4表示有4组测试数据，下面四行，每行一组测试数据。

第一组测试数据10进制数123最后添加检验码3，10进制数1233是9（=10-1）的倍数

第二组测试数据16进制数78最后添加检验码0，16进制数780是15（=16-1）的倍数

第三组测试数据16进制数1234321最后添加检验码e（=14），16进制数1234321e是15（=16-1）的倍数

第四组测试数据12进制数ab最后添加检验码1，12进制数ab1是11（12-1）的倍数

【Tips】

B进制的数能被B-1整除，当且仅当各位数字和能被B-1整除。

第一组测试数据10进制数123最后添加检验码3，10进制数1233各位数字和是9，是9的倍数

第二组测试数据16进制数78最后添加检验码0，16进制数780各位数字和是15，是15的倍数

第三组测试数据16进制数1234321最后添加检验码e，16进制数1234321e各位数字和是30，是15的倍数

第四组测试数据12进制数ab最后添加检验码1，12进制数ab1各位数字和是22，是11的倍数

解题思路

获取校验码的过程，本质上是一个高精度除法，大数除小数。先将每一位用十进制整数表示（即使转换完大于10也算作一位），然后再使用竖式计算的方式算出余数，要求将其乘以10再加上校验码，除以进制 - 1能够整除。这样可以枚举从0到n-1的整数作校验码。

每一组数据完成后，一定要清空按位存储原数字的数组，否则会遗留除法计算结果，影响下一组数据计算！

不建议使用itoa函数将数字转换为二进制字符串，更推荐自己实现（反正只需要转一位，即将整型校验码转为char），因为它是GNU C++ 标准的函数，不被许多ISO C++ 的编译器支持。

此外，朋友提供了一种数论的办法：将整个数的每一位相加，再加上一个0到n-2的数，如果能够被n整除，则加上的这个数就是校验码。