hrbust寒假训练赛水题题解

一次非常不愉快的做题体验。。


A - Taymyr is calling you(CodeForces764A)

Comrade Dujikov is busy choosing artists for Timofey’s birthday and is recieving calls from Taymyr from Ilia-alpinist.

Ilia-alpinist calls every n minutes, i.e. in minutes n, 2n, 3n and so on. Artists come to the comrade every m minutes, i.e. in minutes m, 2m, 3m and so on. The day is z minutes long, i.e. the day consists of minutes 1, 2, …, z. How many artists should be killed so that there are no artists in the room when Ilia calls? Consider that a call and a talk with an artist take exactly one minute.

Input
The only string contains three integers — n, m and z (1 ≤ n, m, z ≤ 104).

Output
Print single integer — the minimum number of artists that should be killed so that there are no artists in the room when Ilia calls.

Examples
Input
1 1 10
Output
10
Input
1 2 5
Output
2
Input
2 3 9
Output
1

Note
Taymyr is a place in the north of Russia.

In the first test the artists come each minute, as well as the calls, so we need to kill all of them.

In the second test we need to kill artists which come on the second and the fourth minutes.

In the third test — only the artist which comes on the sixth minute.

开幕诉讼,有毒这题。题意是说这个人每隔n分钟打一次电话,但是会有一些人每m分钟来拜访他一次,这个人不想打电话时被打扰,所以他打算干掉一些人,一天有z分钟,问需要干掉多少人。

显然能看出来,这就是求最小公倍数啊。比赛前还专门看了一下gcd怎么求,这下好,写完能派上用场了。

然后tnnd吃了一个WA。。怒而暴力模拟A之。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#define maxn 23333
using namespace std;

int gcd(int a, int b) {
return a % b ? gcd(b, a%b) : b;
}

int call[maxn];

int main() {
int n, m, z;
cin >> n >> m >> z;
for (int i = n; i <= z; i = i + n) {
call[i] = 1;
}
int ans = 0;
for (int i = m; i <= z; i = i + m) {
if (call[i] == 1)
ans++;
}
cout << ans;

return 0;
}

B - Timofey and cubes(CodeForces764B)

Young Timofey has a birthday today! He got kit of n cubes as a birthday present from his parents. Every cube has a number ai, which is written on it. Timofey put all the cubes in a row and went to unpack other presents.

In this time, Timofey’s elder brother, Dima reordered the cubes using the following rule. Suppose the cubes are numbered from 1 to n in their order. Dima performs several steps, on step i he reverses the segment of cubes from i-th to (n - i + 1)-th. He does this while i ≤ n - i + 1.

After performing the operations Dima went away, being very proud of himself. When Timofey returned to his cubes, he understood that their order was changed. Help Timofey as fast as you can and save the holiday — restore the initial order of the cubes using information of their current location.

Input
The first line contains single integer n (1 ≤ n ≤ 2·105) — the number of cubes.

The second line contains n integers a1, a2, …, an ( - 109 ≤ ai ≤ 109), where ai is the number written on the i-th cube after Dima has changed their order.

Output
Print n integers, separated by spaces — the numbers written on the cubes in their initial order.

It can be shown that the answer is unique.

Examples
Input
7
4 3 7 6 9 1 2
Output
2 3 9 6 7 1 4
Input
8
6 1 4 2 5 6 9 2
Output
2 1 6 2 5 4 9 6

Note
Consider the first sample.

1.At the begining row was [2, 3, 9, 6, 7, 1, 4].
2.After first operation row was [4, 1, 7, 6, 9, 3, 2].
3.After second operation row was [4, 3, 9, 6, 7, 1, 2].
4.After third operation row was [4, 3, 7, 6, 9, 1, 2].
5.At fourth operation we reverse just middle element, so nothing has changed. The final row is [4, 3, 7, 6, 9, 1, 2]. So the answer for this case is row [2, 3, 9, 6, 7, 1, 4].

某人收到了生日礼物是一排方块(谁会没事闲的送这种东西……),然后这个人把他们按照一定顺序排了起来,但是他哥哥把顺序按照一定规则打乱了,你的任务是按照这个规则再变回来。

我tm简直就是沙雕。这个题其实就是奇换偶不换,奇数位置和对面的奇数位置交换,偶数不交换。原本是水题,结果交上去各种不对,最后发现数组开小了。。。tmd

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 <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#define maxn 233333
using namespace std;
int n;
int a[maxn];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n / 2; i++) {
if (i % 2) {
swap(a[i], a[n - i + 1]);
}
}
for (int i = 1; i <= n; i++)
cout << a[i] << " ";

return 0;
}

D - 钱币兑换问题(HDU1284)

在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。

Input
每行只有一个正整数N,N小于32768。

Output
对应每个输入,输出兑换方法数。

Sample Input
2934
12553
Sample Output
718831
13137761

所以说还是中文题目好懂一些。。。本来以为这题和台阶问题类似,不过后来发现了不同。台阶问题里面存在上楼的先后决策顺序,而这个先后兑换顺序是对答案没有影响的。不得已想一些构造的方法。不难想象,答案显然是一个函数,这里假设三个未知数k1,k2,k3,分别代表兑换一分的数量,兑换二分的数量和兑换三分的数量。这样会得到一个方程:k1 + k2 2 + k3 3 = n,对于三个未知数,我们只需要给他们赋一些合理的值,这就是解的其中之一。那么我们找到所有的合理的值,统计一下就是答案了。

所以要怎么办?暴力枚举吗?显然不行,这样是立方阶的时间复杂度,会爆掉的。考虑优化,我们可以先假定一个k3已知,如果能够推导出k2和k1,那就可以把这个算法进行优化。

那么问题来了,如何根据一个已知的k3去推导k2和k1。由上边的式子,移项可以得到k1 + 2 k2 = n - 3 k3,那么这个式子的左边就代表了当k3已知时的分法。

这一步有点跳。我们需要知道k2的取值范围,根据k1 + 2 k2 = n - 3 k3,可以得到不等式2 k2 <= n - 3 k3,于是有k2∈[0,(n-3 k3)/2]。方案只能取整数,所以k2的取值其实是有限的。这个数值是(n-3 k3)/2+1,也就说当k3已知时k2的方案也就已知了。那怎么算k1呢?其实不用算,当k3和k2确定后,k1便会自动确定(想一想,为什么)。

所以我们只需要枚举k3,每枚举一次k3计算一下有多少个k2,累加一下这个数值,就是最终答案。

最后的小细节,k3并不需要枚举到n,由于k1 + k2 2 + k3 3 = n,可以得到k3 * 3 <= n,于是有k3 <= n/3,所以只需要枚举到n/3就可以了。

这题确实是好题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#define maxn 23333
using namespace std;

int main() {
int n;
while (cin >> n) {
int sum = 0;
for (int i = 0; i * 3 <= n; i++) {
sum += (n - i * 3) / 2 + 1;
}
cout << sum << endl;
}

return 0;
}

E - Mahmoud and a Triangle(CodeForces766B)

Mahmoud has n line segments, the i-th of them has length ai. Ehab challenged him to use exactly 3 line segments to form a non-degenerate triangle. Mahmoud doesn’t accept challenges unless he is sure he can win, so he asked you to tell him if he should accept the challenge. Given the lengths of the line segments, check if he can choose exactly 3 of them to form a non-degenerate triangle.

Mahmoud should use exactly 3 line segments, he can’t concatenate two line segments or change any length. A non-degenerate triangle is a triangle with positive area.

Input
The first line contains single integer n (3 ≤ n ≤ 105) — the number of line segments Mahmoud has.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109) — the lengths of line segments Mahmoud has.

Output
In the only line print “YES” if he can choose exactly three line segments and form a non-degenerate triangle with them, and “NO” otherwise.

Examples

Input
5
1 5 3 2 4
Output
YES
Input
3
4 1 2
Output
NO

Note
For the first example, he can use line segments with lengths 2, 4 and 5 to form a non-degenerate triangle.

给你一个大小为n的线段的集合,从这里头挑出来任意三条线段,问能不能组成非退化三角形。

神tm非退化三角形,竟然还没有给出定义,出题人是默认我们知道这个东西咯?后来我发现,还真的有退化三角形,它指的是指面积为零的三角形。满足下列条件之一的三角形即可称为退化三角形:三个内角的度数为 (180°,0°,0°) 或 (90°,90°,0°);三边其中一条边的长度为0;一条边的长度等于另外两条之和。

这TM还是三角形吗???

好了不扯这么多,反正就是能组成三角形就可以。那就简单了,排个序找就完事了。

那么问题来了,从一堆线段里面选三个出来,答案不是排列组合吗?其实不然。

目前这个线段序列是有序的,考虑贪心,如果当前线段和它的前边那条线段和后边那条线段能组成,那就能组成,如果这个组不成,再往前和再往后找也组不成。

能组成三角形要求任意两边之和大于第三边,假设从第一条线段到第n条线段长度递增,那么在中间的第i条线段,构造a[i] + a[i - 1] > a[i + 1],如果成立则可以构成三角形。

假设此时该式子不成立,那么有a[i] + a[i - 1] <= a[i + 1],我们令a[i]固定,去寻找i-1和i+1之外的可能性。

如果是a[i] + a[i - 2] <= a[i + 2],不等式成立吗?显然成立,由于线段长度的单调性,a[i - 2]不会比a[i - 1]长,而a[i + 2]不会比a[i + 1]短。

推广,到a[i] + a[i - k] <= a[i + k],由数学归纳法可证得a[i] + a[i - k] <= a[i + k]成立,即a[i] + a[i - k] > a[i + k]不可能成立。由于证明太冗长且显然,此处略。

但是注意,如果a[i] + a[i - 1] > a[i + 1]成立,a[i] + a[i - k] <= a[i + k] 不一定不成立。也就是结论的逆命题不一定真。

(证明都是后续的事了,比赛当时谁会bb这么多,看起来显然成立用就完事了。。。)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#define maxn 233333
using namespace std;
int n;
int a[maxn];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
bool succeed = false;
for (int i = 2; i < n; i++) {
if (a[i] + a[i - 1] > a[i + 1]) {
succeed = true;
}
}
if (succeed)
cout << "YES";
else
cout << "NO";

return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:hrbust寒假训练赛水题题解

文章作者:Shawn Zhou

发布时间:2019年01月16日 - 21:01

最后更新:2019年01月18日 - 19:01

原始链接:http://shawnzhou.xyz/2019/01/16/19-01-16-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%