浪在ACM集训队寒假集训第一场 部分题解

临时出了点意外情况导致本场比赛unrated。所以这更加增长了我想要A掉B题的勇气(指当场切掉计算几何)。。后续发现,我还不如去做E题,可能还有得救。。。


C - Function Height(CodeForce1036A)

原题地址:https://vjudge.net/contest/279588#problem/C

题意很简单,在坐标系上x轴正半轴位置有2n+1个点,他们都是整数点,编号是从0到2n,现在可以把任意奇数位置的点的y坐标抬高任意高度,这样它就会和两边的偶数点组成三角形,可以求出它的面积。现在给你点的个数还有需要达到的面积,问三角形最低的高度是多少。

可以这样想,既然要高度最低,那显然最合理的做法就是同等增长,让所有可以动的点都向上动一个单位。因为显然动一个单位面积就会增加1。

那就好办了。首先判断一下要求的面积大小是否小于点的个数,如果是,那显然是完成这个要求绰绰有余的,甚至还可能有用不着操作的点,这样答案显然就是1。而如果所有点都往上提高了1,一直面积提高了n,还是不满足要求,怎么办?再提高一层呗。依此类推。可以用目标面积除以点的个数,然后判断是否有剩余,如果有剩余则答案+1。就这么简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdlib>
#define maxn 2333
using namespace std;
long long int n, p;
int main() {
cin >> n >> p;
if (p < n)
cout << "1" << endl;
else {
long long int ans = p / n;
if (p % n != 0)
ans++;
cout << ans << endl;
}
return 0;
}

D - Diagonal Walking v.2(CodeForces1036B)

原题地址:https://vjudge.net/contest/279588#problem/D

题意说,一个人要从(0,0)移动到(n,m),他最多移动k次,并且是想尽量沿着对角线走。这个人想知道他要走到目标位置按照走对角线的方式最多需要走几步。也就是说要尽量让对角线步数最大化。这个人是可以对任何位置(包括终点)访问任意次的。

既然是对角线步数最大化,那就把所有能走的对角线都走完就可以了。首先可以明确的是,走对角线应该是比较近的道路,并且这是存在无解情况的。比如说对于输入的目标点(n,m),假设我们知道其中较大值为m,那么先判断m与k的关系,如果k连m的大小都不够显然是怎么跑都跑不到的,毕竟最短路就这么长了,不可能有答案比这再短。所以此时应该输出-1。下面的情况比较难找也比较难想,考虑走完了对角线,如果能到达目的地那好说,答案就是k,因为你完全可以走到终点后随便浪,所以答案就是k。如果仍然到达不了目的地,该怎么办?说明我们不能这么浪,我们会有走一些直步,向上或者向右是一个道理。我们考虑(n,m)的值,假设m较大,不难想到,如果m-n是一个奇数,那么显然是只有一步不能走对角线的。

啥?你问我要是差了十万八千里还是只走一步吗?螺旋上升懂不懂?(滑稽),可以左上一步右上一步这样啊,最后一步一定是直走的,因为你一定走到了终点附近。

还有一种可能,还是假设m比较大,当k-m是奇数的时候。一定是有两步是直走或横走的。可以画个图康一康(滑稽,所以此时的答案就是k-2。

论 证 完 毕

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdlib>
#define maxn 2333
using namespace std;
long long int n, m, k;
long long int q;
int main() {
cin >> q;
while (q--) {
cin >> n >> m >> k;
if (n > m)
swap(n, m);
if (m > k)
cout << "-1" << endl;
else {
if ((m - n) % 2 == 1)
k--;
else if ((k - m) % 2 == 1)
k -= 2;
cout << k << endl;
}
}
return 0;
}

很惭愧,只做了一些微小的工作。

PS:B题我在赛场上以为这是个计算几何,结果出来题目标签你告诉我这是个FFT。。。。。有毒。。。


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


本文标题:浪在ACM集训队寒假集训第一场 部分题解

文章作者:Shawn Zhou

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

最后更新:2019年01月22日 - 16:01

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

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

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