ultmaster edited 7 年，7 月前
题意：求匀加速直线运动每一点的时间。
题解：一种做法是二分（强行多个 $O(\log n)$ 美滋滋），还有一种当然是公式代入咯。
题意：求一个全是 6 的数能被 $x$ 整除。
题解：真的有勇夫大力写高精度！一定是被 CCCC 那道题搞坏了。其实用一下同余性质，易得：只要每次乘 10 加 6 模一下看看是不是 0 就好了。至于无解的情况嘛，判环？类似 BFS 的做法？或者打个表也很容易发现规律啊……
题意：有 $n$ 个楼房，为了满足相邻的 $r$ 个中至少有两户人家装了摄像头，还要装多少个摄像头。
题解：贪心。发现不满了就往里面加。或许用代码会比较清晰一点：
for (int i = 1; i <= k; ++i) {
int x;
scanf("%d", &x);
a[x] = 1;
}
int cur = 0;
for (int i = 1; i <= n; ++i) {
cur += a[i];
if (i >= r) {
cur -= a[i - r];
while (cur < 2) {
int j = i;
while (a[j]) j--;
a[j] = 1;
ans++;
cur++;
}
}
}
题意：求帕斯卡金字塔底层出现的数形成的集合。
题解：先把底层 $(x_1, x_2, \ldots, x_D)$ 会出现哪些情况搜出来，然后依次求这些值。求的时候又是搜索，直接记忆化搜索就好了。但是不加任何优化状态量显然太大了，注意运用对称性，就是存的时候对 $x_1, x_2, \ldots, x_D$ 进行排序。存状态用 map 还是哈希无所谓，用 vector 还是数组也无所谓。然后水水就过了。
题意：对于每一个节点，求子树中 key 比它小的 value 之和。
题解：我们对树进行后序遍历。用树状数组累计权值。每一个节点的答案等于遍历这个节点子树后的累计权值减去遍历前的累计权值（累计是指对 key 比它小的部分进行累计）。
题意：求 $K$ 的二进制表示的后 $N$ 位是不是都是 1。
题解：如题。
题意：有很多人去上洗手间，都插空站，问最后的情况。
题解：用优先队列可以水过 Easy，不讲了。用优先队列不能过 Hard，主要是因为做了太多重复的操作。可以用一个 multiset 来维护，使得重复的操作只做一次。具体实现看代码：
map<ll, ll> M;
scanf("%lld%lld", &n, &k);
M[n] = 1;
acc = 0;
for (auto iter = M.rbegin(); iter != M.rend(); ++iter) {
cur = iter->second;
fl = (iter->first - 1) / 2;
ce = iter->first - 1 - fl;
M[iter->first] = 0;
M[fl] += cur;
M[ce] += cur;
acc += cur;
if (acc >= k) break;
}
printf("Case %d: %lld %lld\n", kase, ce, fl);
题意：构造一个矩阵使得横、竖、斜恰好出现指定数量的 O/I。
题解：真的是有点难……而且似乎一言难尽……直接给 Google 官方的题解吧。
One surprisingly viable approach for the Small dataset is to create random grids of random sizes and count the numbers of I/Os in them until we happen to find a grid with the desired number. Even if we only try square grids with a random size and random contents, this is easily fast enough to pass. Other optimizations are possible — we can vary the frequencies of I, /, and O, or try to edit grids that are close — but not necessary.
Another possibility is to directly construct a grid with the desired number of I/Os. Better yet, we can construct one grid with at least 287 I/Os, and then use it in every test case, eliminating I/Os individually until we have the desired number. To ensure that I/Os do not interfere with each other, let’s space them out in a field of Os like this:
I/OOI/OOI/OO...
OOOOOOOOOOOO...
I/OOI/OOI/OO...
OOOOOOOOOOOO...
I/OOI/OOI/OO...
...
If we extend this pattern to fill a 50 by 50 grid, we will have 25 rows with 12 I/Os each; 25 × 12 = 300, which is more than enough. We can eliminate an individual I/O by changing its / into another O. With this grid setup, that change cannot possibly affect other existing I/Os or create new ones. Other similar strategies are possible.
The particular construction strategy above cannot produce enough I/Os when each of our grid dimensions is capped at 15. Nor will random generation help; we would be lucky to get a random 15 x 15 grid for N = 80, let alone 287. We need to pack as many I/Os into the grid as possible. Let’s start with a single row; we can fit many I/Os in, overlapping forward ones with backward ones:
I/O/I/O/I...
If we stack these rows on top of each other, we will also form many diagonal I/Os:
I/O/I/O/I...
I/O/I/O/I...
I/O/I/O/I...
...
How many I/Os are in the 15 by 15 version of this grid? Let’s count by looking only at the /es. Any / in the top or bottom row is part of exactly one I/O, running horizontally. Any other I/O is part of exactly three I/Os: one horizontal and two diagonal. There are 7 /es in each row; the 14 in the top and bottom row contribute 14 I/Os, and the 13 × 7 = 91 in the other rows contribute 91 × 3 = 273. That’s a total of 287, which is conveniently exactly the maximum number of I/Os we could be asked to produce. Note that we do not need to prove that this arrangement packs in as many I/Os as possible; we only had to find a way to fit at least 287 in.
Now, in each test case, we only need to whittle the number of I/Os down from 287 to N. As we do this, we must be careful not to create any new I/Os or destroy more I/Os than we want to. One safe strategy is to change /es into Os, as in the Small strategy above. Changing a / in the top or bottom row eliminates one I/O, and changing any other / eliminates three. We can reach any value of N by first removing as many “threes” as possible (without going below N) and then removing as many “ones” as possible (without going below N). For example, for N = 280, we remove two “threes” and one “one”. For N = 4, we remove everything except for four of the “ones”. Since there are only 288 possible test cases, we can even precompute answers to all of them before downloading the dataset (but this is not necessary).