题意

试题编号:201712-2

试题名称:游戏

时间限制:1.0s

内存限制:256.0MB

问题描述

有n个小朋友围成一圈玩游戏,小朋友从1至n编号,2号小朋友坐在1号小朋友的顺时针方向,3号小朋友坐在2号小朋友的顺时针方向,……,1号小朋友坐在n号小朋友的顺时针方向。

游戏开始,从1号小朋友开始顺时针报数,接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数(即数的个位)为k,则该小朋友被淘汰出局,不再参加以后的报数。当游戏中只剩下一个小朋友时,该小朋友获胜。

例如,当n=5, k=2时:
1号小朋友报数1;
2号小朋友报数2淘汰;
3号小朋友报数3;
4号小朋友报数4淘汰;
5号小朋友报数5;
1号小朋友报数6淘汰;
3号小朋友报数7;
5号小朋友报数8淘汰;
3号小朋友获胜。

给定n和k,请问最后获胜的小朋友编号为多少?

输入格式

输入一行,包括两个整数n和k,意义如题目所述。

输出格式

输出一行,包含一个整数,表示获胜的小朋友编号。

样例输入1

1
5 2

样例输出1

1
3

样例输入2

1
7 3

样例输出2

1
4

数据规模和约定

对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ k ≤ 9。

分析

一个普通的链表绕圈和删除问题。

代码

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
#include <iostream>
using namespace std;

struct Node {
int num;
Node* next;

Node() {
num = 0;
next = NULL;
}

Node(int x) {
num = x;
next = NULL;
}
};

int main() {
int n, k;
cin >> n >> k;
if (n == 1) {
cout << 1 << endl;
return 0;
}

Node* head = new Node(1);
Node* p = head;
for (int i = 2; i <= n; i++) {
p->next = new Node(i);
p = p->next;
}
p->next = head;

Node* last = p;
p = head;
int i = 1;
while (p->next != p) {
if (i % k == 0 || i % 10 == k) {
p = p->next;
delete last->next;
last->next = p;
}
else {
last = p;
p = p->next;
}
i++;
}
cout << p->num << endl;
return 0;
}

题意

试题编号:201712-1

试题名称:最小差值

时间限制:1.0s

内存限制:256.0MB

问题描述

给定n个数,请找出其中相差(差的绝对值)最小的两个数,输出它们的差值的绝对值。

输入格式

输入第一行包含一个整数n。

第二行包含n个正整数,相邻整数之间使用一个空格分隔。

输出格式

输出一个整数,表示答案。

样例输入1

1
2
5
1 5 4 8 20

样例输出1

1
1

样例说明1

相差最小的两个数是5和4,它们之间的差值是1。

样例输入2

1
2
5
9 3 6 1 3

样例输出2

1
0

样例说明2

有两个相同的数3,它们之间的差值是0.

数据规模和约定

对于所有评测用例,2 ≤ n ≤ 1000,每个给定的整数都是不超过10000的正整数。

分析

Leetcode 539基本是一样的。

代码

时间:15ms

空间:520.0KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdlib>
using namespace std;

int cmp(const void* x, const void* y) {
return *(int*)x - *(int*)y;
}

int a[1005];

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
qsort(a, n, sizeof(int), cmp);

int ans = a[1] - a[0];
for (int i = 1; i < n; i++)
ans = min(ans, a[i] - a[i - 1]);

cout << ans << endl;
return 0;
}
CSP

题意

试题编号:201803-2

试题名称:碰撞的小球

时间限制:1.0s

内存限制:256.0MB

问题描述

数轴上有一条长度为L(L为偶数)的线段,左端点在原点,右端点在坐标L处。有n个不计体积的小球在线段上,开始时所有的小球都处在偶数坐标上,速度方向向右,速度大小为1单位长度每秒。

当小球到达线段的端点(左端点或右端点)的时候,会立即向相反的方向移动,速度大小仍然为原来大小。

当两个小球撞到一起的时候,两个小球会分别向与自己原来移动的方向相反的方向,以原来的速度大小继续移动。

现在,告诉你线段的长度L,小球数量n,以及n个小球的初始位置,请你计算t秒之后,各个小球的位置。

提示

因为所有小球的初始位置都为偶数,而且线段的长度为偶数,可以证明,不会有三个小球同时相撞,小球到达线段端点以及小球之间的碰撞时刻均为整数。

同时也可以证明两个小球发生碰撞的位置一定是整数(但不一定是偶数)。

输入格式

输入的第一行包含三个整数n, L, t,用空格分隔,分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。

第二行包含n个整数a1, a2, …, an,用空格分隔,表示初始时刻n个小球的位置。

输出格式

输出一行包含n个整数,用空格分隔,第i个整数代表初始时刻位于ai的小球,在t秒之后的位置。

样例输入1

1
2
3 10 5
4 6 8

样例输出1

1
7 9 9

样例输入2

1
2
10 22 30
14 12 16 6 10 2 8 20 18 4

样例输出2

1
6 6 8 2 4 0 4 12 10 2

数据规模和约定

对于所有评测用例,1 ≤ n ≤ 100,1 ≤ t ≤ 100,2 ≤ L ≤ 1000,0 < ai < L。L为偶数。

保证所有小球的初始位置互不相同且均为偶数。

分析

这题看着很像紫书上的一道例题,同样可以用交换速度的思路去看,唯一的区别是小球会在线段端点处反射(好像?),但这并没有改变小球之间只是交换速度(或互相穿越),而相对顺序不变的事实。所以其实不需要模拟,直接按初始位置排序,然后计算出所有最终位置,再排序,然后根据初始顺序就可以知道每个小球的最终位置了。

事实上我又忘了怎么用两种排序方法调用std::sort了。事实上我觉得这种东西是不可能记住的,不如背诵一下qsort的用法。

参数:

  • 数组起始位置
  • 元素个数
  • 元素size
  • 比较函数,要求两个参数都是const void*类型,返回值为int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// http://www.cplusplus.com/reference/cstdlib/qsort/
/* qsort example */
#include <stdio.h> /* printf */
#include <stdlib.h> /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}

int main ()
{
int n;
qsort (values, 6, sizeof(int), compare);
for (n=0; n<6; n++)
printf ("%d ",values[n]);
return 0;
}

代码

时间:15ms

空间:504.0KB

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
#include <iostream>
#include <cstdlib>
using namespace std;

struct Position {
int pos;
int num;
};

int cmpPos(const void* x, const void* y) {
return ((Position*) x)->pos - ((Position*) y)->pos;
}

int cmpNum(const void* x, const void* y) {
return ((Position*) x)->num - ((Position*) y)->num;
}

Position initPos[105], laterPos[105];

int main() {
int n, L, t;
cin >> n >> L >> t;

// 按顺序排序
for (int i = 0; i < n; i++) {
cin >> initPos[i].pos;
initPos[i].num = i;
}
qsort(initPos, n, sizeof(Position), cmpPos);

// 计算之后的“模拟”位置
// 撞墙多次的情况显然循环了
t %= 2 * L;
for (int i = 0; i < n; i++) {
// 没撞到墙
if (initPos[i].pos + t <= L)
laterPos[i].pos = initPos[i].pos + t;
// 撞墙一次
else if (L < initPos[i].pos + t && initPos[i].pos + t <= 2 * L)
laterPos[i].pos = L - (t - (L - initPos[i].pos));
// 撞墙两次
else
laterPos[i].pos = t - (2 * L - initPos[i].pos);
}
qsort(laterPos, n, sizeof(Position), cmpPos);

for (int i = 0; i < n; i++)
laterPos[i].num = initPos[i].num;
qsort(laterPos, n, sizeof(Position), cmpNum);

cout << laterPos[0].pos;
for (int i = 1; i < n; i++)
cout << ' ' << laterPos[i].pos;
cout << endl;

return 0;
}
CSP

题意

试题编号:201803-1

试题名称:跳一跳

时间限制:1.0s

内存限制:256.0MB

问题描述

近来,跳一跳这款小游戏风靡全国,受到不少玩家的喜爱。

简化后的跳一跳规则如下:玩家每次从当前方块跳到下一个方块,如果没有跳到下一个方块上则游戏结束。

如果跳到了方块上,但没有跳到方块的中心则获得1分;跳到方块中心时,若上一次的得分为1分或这是本局游戏的第一次跳跃则此次得分为2分,否则此次得分比上一次得分多两分(即连续跳到方块中心时,总得分将+2,+4,+6,+8...)。

现在给出一个人跳一跳的全过程,请你求出他本局游戏的得分(按照题目描述的规则)。

输入格式

输入包含多个数字,用空格分隔,每个数字都是1,2,0之一,1表示此次跳跃跳到了方块上但是没有跳到中心,2表示此次跳跃跳到了方块上并且跳到了方块中心,0表示此次跳跃没有跳到方块上(此时游戏结束)。

输出格式

输出一个整数,为本局游戏的得分(在本题的规则下)。

样例输入

1
1 1 2 2 2 1 1 2 2 0

样例输出

1
22

数据规模和约定

对于所有评测用例,输入的数字不超过30个,保证0正好出现一次且为最后一个数字。

分析

一道模拟水题。直接模拟就行了。

代码

时间:15ms

空间:500.0KB

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
#include <iostream>
using namespace std;
int main() {
int lastScore = 1;
int sum = 0;
int status;
while (cin >> status) {
if (status == 0)
break;
else if (status == 1) {
lastScore = 1;
sum++;
}
else if (status == 2) {
if (lastScore == 1) {
lastScore = 2;
sum += 2;
}
else {
lastScore += 2;
sum += lastScore;
}
}
}
cout << sum << endl;
return 0;
}
CSP