TKK-ICPC Round#7 题解

1、圣诞树

扎实的星号阵列题目,注意反斜杠需要转义后输出。


2、How many bugs?

设置三个变量 a、b、c 分别保存 可用 的 ‘b’、’u’、’g’ 的数量。

每遇到一个 ‘b’,a++。

每遇到一个 ‘u’,b = min(a,b + 1)。

每遇到一个 ‘g’,c = min(b,c + 1)。

也就是说,可用的 ‘u’ 的数量一定小于等于 ‘b’ 的数量,可用的 ‘g’ 的数量一定小于等于 ‘u’ 的数量,最后变量 c 即为答案。


3、积木

用 add 保存目前已经添加了多少积木,每一次操作 2,我们都需要让 add += x。

那么每一次操作 1 我们只要使 a[x] = y – add 就可以了。

最后每一堆的数量其实就是 a[i] + add。


4、高次幂运算

用到了费马小定理:a ^ (p – 1) ≡ 1(mod p),因此我们只需要在读入 a 的过程中对 1e9 + 7 取模,读入 b 的过程中对 1e9 + 6 取模,最后用快速幂跑 a 的 b 次方就可以了。

注意取模完以后 a 和 b 都等于 0 的情况,此时答案为 0。


5、几个部分

先判断两个矩形相离的情况,即相交部分面积为 0 的情况,此时平面总是会被分成三个部分。

再来判断相交的情况,首先明确相交部分一定是一个矩形,那么我们先把相交部分的 xy 坐标提取出来,把它当成一个新的矩形 C,然后把前两个矩形分别命名为 A 和 B。

最后我们去判断 C 与 A 的关系和 C 与 B 的关系。如果 C 把 A 分成一部分(C 与 A 重合),那么 ans += 1;如果 C 把 A 分成两部分,那么 ans += 2;如果 C 把 A 分成三部分,那么 ans += 3。同时 B 也进行相应的判断,最后输出 ans。


6、进制转换

扎实无坑的进制转换题。