April Fools 2025 TANG

2095 A.Piecing It Together

【汤立祥 物院】我的 tag: Jigsaw https://codeforces.com/contest/2095/problem/A

思路：我们需要仔细观察题干，可以发现题干是一个拼图游戏。首先我们给位置命名，横向为 1,2,3，纵向为 A,B。可以先根据颜色分类，A1,B2 都是蓝色，应该是一起的，A2,A3,B1,B3 都是绿色，应该是另一块区域。

我们将这张图打印下来之后进行拼图的尝试，最后得到如下拼接方式。

• 第一行：B2 - A3 - B3
• 第二行：A1 - A2 - B1

时间复杂度 $\mathcal{O}(\mathrm{打}\mathrm{印}\mathrm{机}\mathrm{打}\mathrm{印}\mathrm{时}\mathrm{间}+\mathrm{剪}\mathrm{刀}\mathrm{裁}\mathrm{剪}\mathrm{时}\mathrm{间})$（注：拼接时间远小于前两者）

代码：

print("puzzling")

2095 B. Plinko

我的 tag: Chance https://codeforces.com/contest/2095/problem/B

【汤立祥 物院】思路：我们注意到这是一个道尔顿钉板的游戏，题目要求我们能够连续获胜10次。我从 0 ~ 16 之间扔下去最好的记录是 Wrong answer on test 8，你也快来试试看吧。

实际上由于题干只要求输出一个整数，因此只需要输出-1即可。

代码：

print(-1)

2095 C. Would It Be Unrated?

我的 tag：binary search, brute force https://codeforces.com/contest/2095/problem/C

【汤立祥 物院】思路：如果你现在直接去做这道题目，Verdict 里面可以直接看到一行 Answer，但如果要模拟当时比赛的过程，你是看不到 Answer 的。那究竟应该是怎么做的呢？答案是利用二分查找，但不是代码上二分。

当时比赛时主办方让某一个小号提交了一个正确的答案，这使得 Status 里面出现了一个 Accept。由于题目要求输出测试的数量，我们可以直接利用 Status 里的筛选功能（即筛选通过测试数量 $\ge$ 某个值的提交记录）利用二分法即可轻松找到。

代码：

print(143)

2095 D. Where Am I?

我的 tag: GeoGuessing https://codeforces.com/contest/2095/problem/D

【汤立祥 物院】思路：仔细观察图片，映入眼帘的就是两个大大的 New York，但如果我们再定睛一看，湛蓝的天空，沿街矗立的棕榈树，这显然不是纽约的气候。

注意到图片中的一处路牌，上面写着

由此我们锁定这张图在拉斯维加斯。那么有什么特殊的建筑能够让我们直接找到这是在拉斯维加斯的哪里呢？注意到图片最右侧大大的 Dolby 字样，这是拉斯维加斯的杜比影院，简单搜索之后我们可以找到拍摄的位置：

代码：

print(36.104299, -115.172916)

2095 E. Pair Count

我的 tag：Wordle, number theory

【汤立祥 物院】思路：这道题还是一道不错的数论题。https://codeforces.com/contest/2095/problem/E

• 第零步：点开 bitwise XOR operation. 发现这道题目的 XOR 是 MULTIPLY 的意思。

• 第一步：预处理与频数统计

  由于我们只关心 $a_i^3$ 在模 $p$ 意义下的值，首先对数组进行预处理：计算每个元素的立方：$x_i=a_i^3(\mathrm{mod}p)$。使用 Counter 统计每个 $x_i$ 出现的频率。这可以将搜索空间从 $O(n^2)$ 降低到 $O(\text{unique values})$。

• 第二步：分类讨论 $k=0$ 的特殊情况

  当 $k=0$ 时，只要 $x_i$ 或 $x_j$ 至少有一个为 $0$，积就为 $0$。设 $zeros$ 为 $x_i=0$ 的个数，$non\mathrm{\_}zeros$ 为非零个数。组合情况为：两个都是 $0$（$\frac{zeros\times (zeros-1)}{2}$） + 一个是 $0$ 一个不是（$zeros\times non\mathrm{\_}zeros$）。

• 第三步：利用逆元处理 $k\ne 0$

  对于 $x_i\ne 0$，我们需要寻找 $x_j$ 使得 $x_i\cdot x_j\equiv k(\mathrm{mod}p)$。变形方程：$x_j\equiv k\cdot (x_i{)}^{-1}(\mathrm{mod}p)$。费马小定理：由于 $p$ 是质数（愚人节题通常默认或给出），可以使用 $x_i^{p-2}(\mathrm{mod}p)$ 快速求得逆元。计数逻辑：如果 $x_i\ne x_j$，则数对数量为 $count(x_i)\times count(x_j)$。注意这种情况下 $(x_i,x_j)$ 和 $(x_j,x_i)$ 会各被计算一次，最后需除以 2。如果 $x_i=x_j$（即 $x_i^2\equiv k(\mathrm{mod}p)$），则数对数量为 $count(x_i)\times (count(x_i)-1)$。

代码：

from collections import Counter
n, p, k = list(map(int, input().split()))
an = list(map(int, input().split()))

cubed = list(map(lambda x: x**3 % p, an))
counted = Counter(cubed)

def fast_recipical(a, p):
    # a * b === 1 mod p
    return pow(a, p-2, p)

if k == 0:
    zeros = counted[0]
    non_zeros = n - zeros
    print(zeros * (zeros - 1) // 2 + zeros * non_zeros)

else:
    total = 0
    for i in counted:
        if i != 0:
            recipical = fast_recipical(i, p)
            j = recipical * k % p
            
            nums_of_ai = counted[i]
            nums_of_aj = counted[j]
            
            if i != j:
                total += nums_of_ai * nums_of_aj 
                # Notice the double counting with (i, j) & (j, i)
            else:
                total += nums_of_ai * (nums_of_aj - 1)
    print(total // 2)

2095 F. ⅓ оf а Рrоblеm

https://codeforces.com/contest/2095/problem/F

【汤立祥 物院】思路：阅读题干之后，我们得到了一个不完整的表达式：

$$a4+-+-)2$$

那么剩下 2/3 的题干在哪里呢？打开俄语版本，我们得到了 $$ 12 \quad +1\quad ab\quad |a\quad b|\quad (a \quad 3b\quad b+ $$ 也就是剩下 2/3 的题干，因此我们最后得到 $$12a+14ab+|a-b|+(a-3b)b+2$$

代码：

a, b = list(map(int, input().split()))
print(12 * a + 14 * a * b + abs(a - b) + (a - 3 * b)*b + 2)

2095 G. Definitely a Geometry Problem

我的 tag: geometry https://codeforces.com/contest/2095/problem/G

【汤立祥 物院】思路：题目要求我们寻找给定平面上 $N$ 个点之后，能够包住其中至少 $k$ 个点的圆最小是多少。这道题看起来十分复杂，并且要求我们在 $\mathcal{O}(n)$ 的时间复杂度内完成。但若我们仔细阅读，会发现条件：任意三点都不在一圆上，这意味着所有点都共线。只需一个简单的双指针，扫描排序后第 $i$ 与 $i+k-1$ 个点的最小距离，即可计算最小的圆面积。

代码：

from math import pi

n, k = list(map(int, input().split()))
points = [list(map(int, input().split())) for _ in range(n)]

on_the_line = []

def dsq(x, y):
    return (x[0] - y[0])**2 + (x[1] - y[1])**2

if n == 1:
    print(0)
else:
    on_the_line = sorted(points)
    ptr1 = 0
    ptr2 = k - 1
    width = dsq(on_the_line[ptr2],on_the_line[ptr1])

    while ptr2 < len(on_the_line):
        curr_width = dsq(on_the_line[ptr2], on_the_line[ptr1])
        if width > curr_width:
            width = curr_width
        ptr2 += 1
        ptr1 += 1

    print((width / 4) * pi)

2095 H. Blurry Vision

我的 tag: fft, Wiener https://codeforces.com/contest/2095/problem/H

【汤立祥 物院】思路：这道题目给我们提供了一个若干字符模糊后的图片，需要我们去辨认图片。看起来这是一个不可能的任务，但如果你仔细思考，模糊的过程相当于某一个像素的值和周围的像素值发生了线性叠加，本质上相当于进行了一个巨大的线性变换。求解初始的图片就相当于求解这个巨大的线性方程组，这个过程应当是可逆的。

图片模糊化的过程可以理解为一个卷积的过程，不同的模糊方法使用不同卷积核进行计算。比如一个最简单的模糊方法：取平均，它的卷积核就长：

$$\frac{1}{25}\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1\end{array}\right)$$

它的含义就是在计算 $a[i][j]$ 这一点模糊后的值 $a^{\prime }[i][j]$ 时，需要计算 $$\frac{1}{25} \sum_{2\le \Delta_x,\Delta_y \le 2} a[i+\Delta_x][j+\Delta_y] $$ 这个卷积核给出的就是一个格点周围元素对格点影响的权重。

我们记原始图像为 $f(x,y)$，原始卷积核为 $h(x,y)$，变换后包含噪声 $n(x,y)$，因此观测到的模糊图像为 $ g(x,y)=h(x,y)*f(x,y)+n(x,y) $，利用卷积定理，作傅里叶变换可以得到 $$ G(u,v)=H(u,v)F(u,v)+N(u,v) $$

如果我们想要复原出 $f$，我们可以尝试找到卷积核 $w$，使得 $\hat{f}=w\ast g$，在频域中可以写为 $$\hat{F}(u,v)=W(u,v)G(u,v)$$

我们的目标是让 $\hat{f}$ 与 $f$ 足够接近，我们不妨最小化 $ \mathbb E[|\hat{f}-f|^2]$，对应频域上 $$ \mathbb E[|\hat{F}-F|^2]=\mathbb E[|WHF+WN-F|^2] $$ 注意到由于噪声是随机的，那么 $\mathbb{E}[N{F}^{\ast }]=0$，因此可以得到 $$\mathbb E[|\hat F -F|^2]=(1-WH)(1-W^H^)\mathbb E[|F|^2]+WW^\mathbb E[|N|^2]$$ 分别设原信号和噪音信号的强度为 $S_f,S_n$，则有 $\mathbb{E}=|1-WH{|}^2{S}_f+|W{|}^2{S}_n$，对$W^{\ast }$求导可以得到 $$ \frac{\partial\mathbb E}{\partial W^}=S_f (1-WH)(-H^*)+WS_n=0 $$ 解得 $W=\frac{H^{\ast }}{|H{|}^2+S_n/S_f}$ 其中 $S_n/S_f$ 表示的就是信噪比。对 $W$ 再进行傅里叶逆变换即可得到 $w$，由此卷积即得 $\hat{f}$。

使用 $(25,25)$ 大小，$\sigma =7$ 的高斯卷积核，阅读可以得到 CODEFORCES EYE TESTING SYSTEM APRIL FOOLS YOU READ POORLY GET EYEGLASSES

代码：

words = "CODEFORCES EYE TESTING SYSTEM APRIL FOOLS YOU READ POORLY GET EYEGLASSES".split()
n = int(input())
print(words[n-1])

去模糊代码：(Mathematica)

img = Import["blurred.png"];
ImageDeconvolve[img, GaussianMatrix[{12, 7}], Method -> {"Wiener", 5*10^-6}, MaxIterations -> 100]

2095 I. Mysterious Script

我的 tag: Linguistic, expression parsing, number theory https://codeforces.com/problemset/problem/2095/I

【汤立祥 物院】思路：我们的任务是破译外星语言的数字。在破译数字前，我们首先要明确的是外星人用的进制体系，注意到外星人只有9根手指，因此外星人大概率使用的是9进制。

很快我们对比题目中所提供的字符与9进制下数字的表示方法，得到：

$$\begin{array}{ccc}0& 1& 2\\ 3& 4& 5\\ 6& 7& 8\end{array}\iff \begin{array}{ccc}\mathtt{?}& \mathtt{le}& \mathtt{lon}\\ \mathtt{sha}& ?& \mathtt{shon}\\ \mathtt{ta}& \mathtt{te}& ?\end{array}$$

容易观察到，通过拼接元音和辅音，我们可以得到 0,4,8 对应的符号

$$\begin{array}{ccc}0& 1& 2\\ 3& 4& 5\\ 6& 7& 8\end{array}\iff \begin{array}{ccc}\mathtt{la}& \mathtt{le}& \mathtt{lon}\\ \mathtt{sha}& \mathtt{she}& \mathtt{shon}\\ \mathtt{ta}& \mathtt{te}& \mathtt{ton}\end{array}$$

最后你只需要记得写完数字之后加一个 "s" 即可。

代码：

dictionary = {
    "la": "0",
    "le": "1",
    "lon": "2",
    "sha": "3",
    "she": "4",
    "shon": "5",
    "ta": "6",
    "te": "7",
    "ton": "8"
}

keys = list(dictionary)
a, b = input().split()
a = a[:-1]
b = b[:-1]

def translate(string: str):
    curr = ""
    final = ""
    for i in range(len(string)):
        curr += string[i]
        if curr in dictionary:
            final += dictionary[curr]
            curr = ""
    return final

def write(num: int):
    if num == 0:
        return "las"
    res = "s"
    while num > 0:
        res = keys[num % 9] + res
        num //= 9
    
    return res

numa = int(translate(a), base=9)
numb = int(translate(b), base=9)

sumation = numa + numb
print(write(sumation))

注意2025年考试还有一个 J 问，不过懒得做了。