湖南大学 2021 程序设计训练笔记

所有代码均已上传至 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；

输出形式

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

样例输入

样例输出

解题思路

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

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

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；

输出形式

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

样例输入

样例输出

解题思路

实际上这是一个 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

输出形式

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

样例输入

        text
        
    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
 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

样例输出

        text
        
    manutd fcbarca 
d b

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”（输出没有引号）占一行。

样例输入

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

1
2
3
4
5
6
7


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

样例输出

        text
        
    Yes
No
Yes
Yes
No
No

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 行，表示进入淘汰赛阶段的球队，按照字典序进行排列，每个球队名字占一行

样例输入

text

1

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

样例输出

text

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 的英文字符，大小写区分。

输出形式

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

样例输入

text

1

33applebananapear2pearbanana2applebanana

样例输出

text

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 名范围。

样例输入

        text
        
    9 6
350102200609166049
350102200609163286
250342323545313434
130502201805070787
110101196003074525
430102201102181455

1
2
3
4
5
6
7


9 6
350102200609166049
350102200609163286
250342323545313434
130502201805070787
110101196003074525
430102201102181455

样例输出

        text
        
    2
3 4
Sorry
6
2/3
Sorry

1
2
3
4
5
6


2
3 4
Sorry
6
2/3
Sorry

代码框架

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

        cpp
        
    #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;

}

 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 的字符串，表示二叉树后序遍历的结果。

样例输入

        text
        
    8
12457836
42758136
4
abcd
abcd
4
abcd
dcba
0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


8
12457836
42758136
4
abcd
abcd
4
abcd
dcba
0

样例输出

        text
        
    47852631
dcba
dcba

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。其顺序与输入的操作次序一致。

样例输入

text

1

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

样例输出

text

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。

样例输入

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

1
2
3
4
5


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

样例输出

解题思路

这玩意有啥解题思路？算就是了。记得适时用 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 的位数。

样例输入

        text
        
    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
6


5
255.255.255.0
127.0.0.1
0.0.0.1
1.2.3.4
0.0.0.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”。

样例输入

text

1

31 1-1 -12 -1

样例输出

text

1

Yes

解题思路

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

15. 字符串反转 3

个人难度评级：3

问题描述

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

输入形式

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

输出形式

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

样例输入

text

1

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

样例输出

text

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

text

1

20 7

样例输出 1

text

1

7 14 17

样例输入 2

text

1

200 11

样例输出 2

text

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 行，表示排序之后的字符串。

样例输入

text

1

10 6AACATGAAGGTTTTGGCCAATTTGGCCAAAGATCAGATTTCCCGGGGGGAATCGATGCAT

样例输出

text

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 位。

样例输入

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

1
2
3


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

样例输出

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) 标识它是否是循环数。

样例输入

text

1

142857

样例输出

text

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）, 表示工作期间的开始时间和结束时间。

输出形式

输出总的耗电量。

样例输入

text

1

2 8 4 2 5 1020 3050 100

样例输出

text

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）。

样例输入

样例输出

样例说明

第一行的 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 整除，则加上的这个数就是校验码。