https://ac.nowcoder.com/acm/contest/120563
本文给出代码在 nowcoder 使用 pypy3 环境均可 AC

A 宙天

题目分析

给定一个正整数 $x$ $(1 \leq x \leq 100)$，判断是否存在自然数 $k$，满足 $x = k \times (k+1)$，即 $x$ 能表示为两个连续自然数的乘积。如果是则输出 YES，否则输出 NO。

解题思路

由数据范围 $x \in [1, 100]$，$k$ 最大取到 $9$（因为 $9 \times 10 = 90$，$10 \times 11 = 110 > 100$）。

直接枚举 $k$ 从 $1$ 到 $9$，检查 $k \times (k+1)$ 是否等于 $x$ 即可。

Code

import sys
input = sys.stdin.readline

def solve():
    x = int(input())
    for i in range(1, 10):
        if i * (i+1) == x:
            print('YES')
            return
    print('NO')

solve()

G スピカの天秤

题目分析

天平左侧有 $n$ 个砝码（重量为 $a_1, a_2, \ldots, a_n$），右侧有 $m$ 个砝码（重量为 $b_1, b_2, \ldots, b_m$）。天平有三种状态：左重、平衡、右重。要求拿走最少数量的砝码，使天平状态发生改变。

解题思路

关键在于拿走最少砝码使天平状态改变。分情况讨论：

1. 两侧重量相等：随便拿走任意一个砝码即可打破平衡，答案为 $1$。
2. 左侧更重（$\text{sumL} > \text{sumR}$）：需要从左侧拿走总重量 $\geq \text{sumL} - \text{sumR}$ 的砝码（改变天平状态）。为了拿走最少个数，贪心地优先拿最重的。
3. 右侧更重：同理，从右侧贪心取。

贪心策略：将较重一侧的砝码降序排序，依次取出，直到累计取出重量 $\geq$ 差值。取出的个数即为答案。

Code

import sys
input = sys.stdin.readline

def greed(a: list, target: int):
    s = 0
    cnt = 0
    arr = sorted(a, reverse=True)
    for i in arr:
        s += i
        cnt += 1
        if s >= target:
            return cnt

def solve():
    n, m = map(int, input().split())
    arrl = list(map(int, input().split()))
    arrr = list(map(int, input().split()))
    suml = sum(arrl)
    sumr = sum(arrr)
    if suml == sumr:
        print(1)
    elif suml > sumr:
        print(greed(arrl, suml-sumr))
    elif suml < sumr:
        print(greed(arrr, sumr-suml))

T = int(input().strip())
for _ in range(T):
    solve()

B Random

题目分析

给定一个长为 $n$ 的数组 $a_1, a_2, \ldots, a_n$（元素在 $[1, 10^9]$ 范围内独立均匀随机生成），从中选出两个不同位置的元素，使得它们的最大公约数（gcd）大于 $1$。如果不存在输出 $-1$，否则输出这两个元素的值。

解题思路

由于笔者不懂概率论，故推理思路：

• 判末尾是不是 2 的倍数，WA
• 用 2 试除，找到两个 break，WA
• 用小范围质数表质因分解，WA
• 用质数筛取出 $[1, \sqrt{10^9}]$ 范围质数做质因分解，AC

核心思路：对每个元素做质因数分解，记录每个质因子第一次出现在哪个元素中。当某个质因子再次出现时，说明两个元素共享该质因子，gcd 必然大于 $1$。

由于 $a_i \leq 10^9$，任何合数 $a_i$ 至多有一个大于 $\sqrt{10^9} \approx 31623$ 的质因子。因此先用欧拉筛预处理 $[2, 31623]$ 的质数表，对每个元素先用小质数试除，剩余部分若大于 $1$ 则为大质因子，同样记录即可。

Code

import sys
input = sys.stdin.readline

def euler_sieve(n):
    is_p = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if is_p[i]:
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            is_p[i * p] = False
            if i % p == 0:
                break
    return primes

# sqrt(1e9) ≈ 31623
primes = euler_sieve(31623)

def solve():
    n = int(input())
    arr = list(map(int, input().strip().split()))
    res = {}
    
    for i in arr:
        if i == 1:
            continue
        t = i
        for p in primes:
            if p * p > t:
                break
            if t % p == 0:
                if p in res:
                    print(res[p], i)
                    return
                res[p] = i
                while t % p == 0:
                    t //= p
        if t > 1:
            if t in res:
                print(res[t], i)
                return
            res[t] = i
    print(-1)

T = int(input().strip())
for _ in range(T):
    solve()

赛后分析

在随机均匀分布条件下，任取两个数 gcd > 1 的概率约为 $1 - 6/\pi^2 \approx 39\%$。因此暴力枚举相邻窗口为 30 的所有 pair 取 gcd，在概率上必然能找到答案（若存在的话）。

详细证明参考官方题解：https://ac.nowcoder.com/discuss/1609142

更简代码：

def solve():
    n = int(input())
    arr = list(map(int, input().strip().split()))
    
    for i in range(n):
        for j in range(i + 1, min(n, i + 31)):
            if math.gcd(arr[i], arr[j]) > 1:
                print(arr[i], arr[j])
                return
    print(-1)

J Branch of Faith

题目分析

一棵 $n$ 个节点的完全二叉树，$1$ 号为根，$i$ 号节点的左儿子编号 $2i$，右儿子编号 $2i+1$。给定 $q$ 次查询，每次给一个节点编号 $x$，求与 $x$ 深度相同的节点有多少个（包含 $x$ 本身）。

解题思路

因为题目给了大段的二叉树背景信息，所以这道题一定不是用二叉树搜索。（doge）只需要了解完全二叉树的编号规律就可以了。

简单罗列各层节点编号：

• 第 0 层（根）：$[1, 1]$
• 第 1 层：$[2, 3]$
• 第 2 层：$[4, 7]$
• 第 3 层：$[8, 15]$

规律：深度为 $d$ 的节点编号范围为 $[2^d, 2^{d+1}-1]$。

已知节点编号 $x$，求深度 $d$：$d = \lfloor \log_2(x) \rfloor$

$\lfloor x \rfloor$ 为 $x$ 向下取整。此处注意尽量不要在算法题中使用浮点计算。例如本题 $x$ 范围为 $[1, 10^{18}]$，浮点 log2 存在精度问题。应使用位运算：d = x.bit_length() - 1。

得到 $d$ 后，该层的满编号范围为 $[\text{left}, \text{right}] = [2^d, 2^{d+1}-1]$。但完全二叉树最后一层右侧可能存在空位，实际节点编号不超过 $n$。因此：

• 若 $n < \text{left}$（即整层都不存在），答案为 $0$
• 否则答案为 $\min(n, \text{right}) - \text{left} + 1$

Code

import sys
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    for _ in range(q):
        x = int(input())
        d = x.bit_length() - 1
        left = 2 ** d
        right = 2 ** (d+1) - 1
        if n < left:
            print(0)
        else:
            print(min(n, right) - left + 1)

T = int(input().strip())
for _ in range(T):
    solve()

C++ 中需要使用 1 << d 代替 2 ** d，否则可能整形溢出。

H Tic Tac DREAMIN’

题目分析

在二维平面上有两个关键点 $A(x_a, y_a)$ 和 $B(x_b, y_b)$。需要在 $x$ 轴上找一个锚点 $O(x, 0)$，使得以 $A, B, O$ 为顶点的三角形面积恰好等于 $2$。如果存在则输出 $x$（误差不超过 $0.001$），否则输出 no answer。

解题思路

根据提示：向量叉积的绝对值等于两个向量围成的平行四边形的面积，三角形面积为其一半。

设 $O(x, 0)$，则：

• $\vec{OA} = (x_a - x,\ y_a)$
• $\vec{OB} = (x_b - x,\ y_b)$

三角形面积公式： $S = \frac{1}{2} |\ \vec{OA} \times \vec{OB}\ | = \frac{1}{2} |\ (x_a - x) \cdot y_b - y_a \cdot (x_b - x)\ |$

展开： $S = \frac{1}{2} |\ x_a y_b - x \cdot y_b - y_a x_b + y_a \cdot x\ |= \frac{1}{2} |\ (x_a y_b - y_a x_b) + x(y_a - y_b)\ |$

令 $C = x_a y_b - y_a x_b$（常数），则： $S = \frac{1}{2} |\ C + x(y_a - y_b)\ | = 2$

即 $|\ C + x(y_a - y_b)\ | = 4$。

分情况讨论：

1. $y_a = y_b$：此时 $x$ 的系数为 $0$，等式变为 $|C| = 4$。若恰好成立则任意 $x$ 均可（输出 $0$ 即可），否则无解。
2. $y_a \neq y_b$：解方程 $|\ C + x(y_a - y_b) \ | = 4$（绝对值方程有两解，此处取一解即可），得 $x = \frac{4 - C}{y_a - y_b}$。

此题若使用 C++，需注意浮点输出精度，使用 setprecision(10)。

Code

import sys
input = sys.stdin.readline

def solve():
    xa, ya = map(int, input().split())
    xb, yb = map(int, input().split())

    C = xa * yb - ya * xb
    if ya == yb:
        if abs(C) == 4:
            print(0)
        else:
            print('no answer')
    else:
        x = (4 - C) / (ya - yb)
        print(x)

solve()