【题解】TJ monthly 图灵姬月赛 2020.10

winsoul 2020-10-01 20:51:23 2020-10-05 19:12:57

1001. 2020

注意 " 的输出和不要忽略 ;
cout << "SET date=\"7/23/2021\";" << endl;printf("SET date=\"7/23/2021\";")

1002. 水滴 💧

按照题目计算即可。

double a = 3.6, b = 2.81, g = 9.8;
double r, gamma, rho;
cin >> r >> gamma >> rho;
printf("%.2f\n", r * r * r * pow(a * gamma/rho/g/r/r, 3/b));

1003. 再次相遇

模拟题,根据题目进行模拟。
ans 表示总天数,N 表示今天需要扣除的思念值,now 表示今天在 N 思念值中的天数。

int x, N = 0, now = 0, ans = 0; 
cin >> x;
while (x > 0) {
if (now == N) N++, now = 0;
    x -= N;
    now++;
    if (x > 0) ans++;
}
cout << ans << endl;

1004. 达拉崩吧

(宽度优先搜索) 由于经过传送门传送不花费时间,自由活动花费 1 个单位时间,楼层传送器花费 2 个单位时间。因此使用简单的普通队列进行广搜,上述的转移过程会破坏队列的层次性,使得队头所到达的位置不一定是最早到达。
为了保证队列的分层性,可以考虑使用优先队列(priority_queue)维护宽搜,使得队列按照到达时间分层。最后再判断不同类型的点,分别执行各自的宽搜操作。

1005. 秃头程序员

(二分答案) 可以想到,对第一天程序员所写的 bug 数目 x 进行二分,如果以当前 x 写出来的总 bug 数少于 A ,则增大 x ,否则减小 x
重点在于如何计算第一天写 x 个 bug 的情况下,写出总 bug 的数目。

暴力情况

一般的,我们可以直接使用暴力求解。

bool check(LL x) {
    LL ans = 0;
    for (int i = 1; x/i != 0; i++) {
        ans += x/i;
    }
    return ans >= A;
}

优化情况

但是可以发现,本题的数据高达 10^{12} 。因此上述 check 函数极有可能超时,因此需要寻求优化方法。

整除分块
首先我们可以想到的是 \sum_{i = 1}^{n}{\lfloor\frac{n}{i}\rfloor} 里面,有很多项是重复的。
例如在 n = 10 的情况下, 1 10 项分别是 10,5,3,2,2,1,1,1,1,1
而整除分块的任务就是 \sum_{i = 1}^{10}{\lfloor\frac{10}{i}\rfloor} = 10\times1+5\times1+3\times1+2\times2+1\times5

\sum_{i = 1}^{n}{\lfloor\frac{n}{i}\rfloor} 的性质:

  1. 不同的项最多只有 2\sqrt{n} 项。
  2. \lfloor\frac{n}{i}\rfloor 相等的最大的 i' \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor

因此,我们可以尝试使用整除分块进行优化。

bool check(LL x) {
    LL ans = 0;
    for (LL l = 1, r; l <= x; l = r + 1) {
        r = x/(x/l);
        ans += (r - l + 1) * (x/l);
    }
    return ans >= A;
}

1006. 数列补全

(单调队列/线段树/树状数组/RMQ/...) 只要手动演算一下,就可以发现,只要把 b 从小到大依次取用即可(当然,也不难验证)。
问题在于对于当前需要填充的 a_i 取出了 b_j ,如何查询 max\{a_k - k|b_j \le k \lt i\} 的值。
当前问题转换为在区间 k\in [b_j, i) 的数列 a 中查询最大的 a_k-k 。只要复杂度在要求范围内能解决最大值查询的算法都欧可。

关于数列 b 的讨论

  1. 考虑当前需要填充 a_i ,且已经选取了一个 b_j ,即 a_i = max\{a_k - k|b_j \le k \lt i\}
  2. 考虑某次需要填充 a_p(p > i) ,且已经选取了一个 b_q ,即 a_p = max\{a_k - k|b_q \le k \lt p\} ,其中 \{a_k-k | b_q \le k \le n\} 由输入给定,而 \{a_k-k | n \lt k \lt p\} 为算法填充。
    为满足题目要求的 max(\sum_{i=1}^{2n}a_i) ,应当使 max\{a_k-k | n \lt k \lt p\} 尽可能大,即 (1.) 中 a_i - i = max\{a_k - k|b_j \le k \lt i\} - i 尽可能大,而索引 i 是不变的,则应当让区间 [b_j, i) 尽可能大,因此每次需要选取最小的 b_j

恭喜

共 5 条回复

Leiyuxuan

qpcz!恭喜港佬紫名!

winsoul

qpcz!恭喜港佬紫名

Leiyuxuan

T5其实还可以维护一个 f(n) 代表 n 的因数个数,找到最小的 i 满足 \sum_{j=1}^{i} f(j) >= A 就是答案了。

诡异做法来源QwQ

13917772823a

qpzc

cww970329

恭喜港佬紫名!

AMAZE UI
Hello world!