Ants
题意
有一棵树，从0时刻开始，有两只蚂蚁分别从树的左右两侧出发遍历这棵树。左蚂蚁从一条边的下方爬到上方需要2秒，从上方爬到下方需要1秒，右蚂蚁的爬行速度是左蚂蚁的两倍。蚂蚁如果碰到对方就会立刻调头继续爬行，蚂蚁如果返回地面也会调头继续爬行。计算两只蚂蚁第二次相遇的时间。
Ants
输入
t 组数据，每组数据包含一个整数 n 代表边数和一个 n/2 个字符的字符串。这个字符串本质上是一个大十六进制数，如果转化为二进制数就可以表示这棵树的信息，具体表示方法为假设右蚂蚁不动的情况下左蚂蚁的运动轨迹，当当前位置为1时表示蚂蚁向上爬，否则表示蚂蚁向下爬。
输入数据量不超过 50 MB。注意空间限制为 6 MB，远远小于输入数据量。
输出
输出一个最简分式 p/q ，表示答案。如果答案为整数，q = 1
样例
1 28 fb1da30d1b7230
282/5
样例解释
转化为二进制即为上图的树。
1111 1011 0001 1101 1010 0011 0000 1101 0001 1011 0111 0010 0011 0000
解法
首先我们观察到，显然，左边的蚂蚁将在第一次相遇后首先回到地面，因为右蚂蚁需要向上爬的比率总是较高。
于是就可以轻松嘴出算法的大概流程：
- 读入树的大小。于是我们就知道了有n条上升的边和n条下降的边。
- 当读入树的信息时，我们就可以计算出左蚂蚁的行动轨迹和需要的时间。由于上升和下降边的个数是已知的，所以右蚂蚁走到当前位置的时间也是可以算出来的。所以当两只蚂蚁第一次相遇的时候，我们就可以知道。
- 当两只蚂蚁第一次相遇后，按照右蚂蚁的行动轨迹继续模拟，直到左蚂蚁回到地面。左蚂蚁回到地面的时间是可以计算出来的，而根据我们先前的观察，此时右蚂蚁还没有回到地面。
- 然后继续模拟右蚂蚁的运动，直到两只蚂蚁在此相遇。
听上去真的非常轻松啊？现在来形式化地描述一下这个流程。
用实数 表示左蚂蚁目前经过了多少条边，用实数 表示左蚂蚁目前的高度，用 表示左蚂蚁向上爬需要的时间， 表示左蚂蚁向下爬需要的时间。于是有到达某个点的总时间的公式： 于是就可以列出两只蚂蚁第一次相遇的方程 如前所述，我们可以在读入的时候判断相遇点是否会发生在当前这条边上。当蚂蚁处在节点 的时候，令 表示这是一条上升边， 表示这是一条下降边，于是上式就满足： 如果 , 我们就找到了第一个相遇的位置。于是就可以求出相遇的时间： 然后，我们让左蚂蚁回头，它将在 秒回到树根。此时，右蚂蚁的位置为： 于是我们可以知道，左蚂蚁的确会比右蚂蚁回到树根。
我们继续模拟右蚂蚁的运动，右蚂蚁从 开始，到 的运动满足： 如果 , 那么我们就找到了第二个相遇点。这个时间就是 所以，从0秒开始到第二次相遇的总时间为： 注意到 总是 的倍数。于是 是 。所以 都是 的倍数。于是，所有数字都可以用实际数值的 800 倍在 64 位整数的限制下表示。
算法的时间复杂度为 ，空间复杂度为 。
代码
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
| #include <iostream>
#include <algorithm>
#include <string>
using ll = long long;
ll T, n, x;
ll hextooct(char a) {
if (a <= '9' && a >= '0') {
return ll(a-'0');
}
return 10+ll(a-'a');
}
ll gcd(ll a, ll b) {
ll t;
while(b != 0) {
t = a%b;
a = b;
b = t;
}
return a;
}
int main(int argc, char *argv[]) {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> T;
while (T--) {
std::cin >> n;
ll nn = n * 800;
ll k = 0, a = 0, eps, eps2, a1, k1, a2, k2;
ll t1 = -1, t2 = -1, t;
std::cin.get();
for (int i = 0; i < n/2; i++) {
x = hextooct(std::cin.get());
for (int j = 0; j < 4; j++) {
ll b = ((x >>(3-j) & 1ll)?1:(-1));
if (t1 < 0) {
eps = (6*nn-9*a-k)/(9+b);
if (eps < 800 && eps >= 0) {
a1 = a+eps, k1 = k+eps*b;
t1 = (3*a1+k1)/(2);
}
} else if(t2 < 0) {
eps2 = (12*nn-9*(a-a1)+(k-k1))/(9-b);
if (eps2 < 800 && eps2 >= 0) {
a2 = a+eps2, k2 = k+eps2*b;
t2 = (3*(a2-a1)+(k2-k1))/(4);
}
}
k += 800 * b;
a += 800;
}
}
t = t1 + t2;
ll divisor = gcd(t, 800);
std::cout << t/divisor << '/' << 800/divisor << '\n';
}
}
|
吐槽
打算开个新栏目整点有趣的算法题！
感觉自己还是需要写一点算法题获得一点虚假的成就感... 但是老年选手 codeforces 手速跟不上，project euler 又做不动，leetcode 又觉得无聊... 有点... 尴尬啊
然后最近找到了清晰版本的 Looking for a challenge? 的拍照pdf，打算做一做... 因为这个题解质量和题目质量好像很高... 而且基本都是思维题（真的吗），适合我这种数据结构废物
其实 AGC 也不错，但是 AGC 太多了，做不动...
以及图书馆的荐购功能是真的牛逼...
Screen Shot 2020-12-15 at 9.44.29 PM
我现在在 szkopul 上的题均 dirt 数肯定超过 20 了...
代码细节还挺多的...
不会一个字符一个字符读入错了一万遍
不会位运算又错了一万遍（读入16进制数之后我竟然从后往前用2模它 真的老了
这个 k 和 a 应该在算 eps 之后更新，又错了一发
最后一共交了 14 发才过...
这个东西在 cf 叫 2014-2015 CT S02E07: Codeforces Trainings Season 2 Episode 7 ，找了一年
后来牛逼网友教了我怎么在 gym 按题目名字搜题 然后我发现我笔记里其实有这个链接（
我搜 amppz 题解，搜到一篇英文博客，我一看怎么这么眼熟，结果是我今年一月自己写的，可能是什么垃圾站自动翻译成英文了...
写这种东西比写 Leetcode 快乐多了...