20230922NOIP训练赛#13总结

Timeline

07:40-08:10

通看题目，好好好，3 道构造是吧，A 又双叒叕是性质题，BCD 还没头绪，先把 A 题 $\mathcal{O}(n)$ 卡时暴力打了

08:10-08:45

写了 B D 的暴力

08:45-09:25

C 写了一些莫名其妙的代码，开始罚坐

Result

$60+50+0+30$

Summary

1. 有时间多想想前面的题，别在后面死磕拼包。

Problem

T1

给出一个数 $a$，找出另外两个整数 $b,c$ 使得这三个数为勾股数。

$1\leq a\leq 10^9$

Solution

$a\geq 3$ 时绝对有整数解。

先选个好推的式：$a^2+b^2=c^2=a^2=c^2-b^2=(c-b)(c+b)$

设 $c-b=1$，则 $c+b=a^2$，解方程组得：

$$c=\frac{a^2+1}{2}=\frac{a^2-1}{2}+1\\ b=\frac{a^2-1}{2}$$

$a^2-1$ 为奇数怎么办？此时 $a$ 为偶数，因为对于勾股数来说 $(\frac{a}{2})^2+(\frac{b}{2})=(\frac{c}{2})^2$ 依旧成立，故将 $a$ 一直除以 $2$ 直到 $a$ 为奇数，特别处理 $a=2^k$ 的情况，此时将三数设为 $3,4,5$，因为此时 $a$ 会除为 $1$，则 $b=0$。

时间复杂度 $\mathcal{O}(\log a)$。

T2

给出 $n$ 个节点的树，$q$ 次操作：

1. 删除第 $x$ 条边。

2. 查询 $x$ 所在连通块内的以 $x$ 为起点的最远距离。

$n,q\leq 2\times 10^5$

Solution

把操作离线下来并倒序处理，把删边转化为逐步加边，最远点一定在直径上，用并查集维护连通块的同时维护直径，且新直径一定在原先两条直径的四个点中。

时间复杂度 $\mathcal{O}(n\log n+q\log n)$。

T3

有 $n$ 个数对 $(val_i,mask_i)$，设 $k$ 为最初的 $\sum val_i$，对于一个数 $s$ 和一个数对来说，若 $s\operatorname{AND} mask_i$ 的二进制表示下有奇数个 $1$，则 $val_i$ 会变为 $-val_i$，找出这个 $s$ 使得 $\sum val_i$ 和 $k$ 正负性互异。

$n\leq 3\times 10^5,|val_i|\leq 10^9,mask_i\leq 2^{62}-1$

Solution

将题目中的 “有奇数个 $1$” 改为 $val_i\times (-1)^p$，其中 $p$ 为操作次数。

$\operatorname{AND}$ 操作只与最高位的 $1$ 之后有关，故枚举 $mask_i$ 的最高位，所做更改不会影响前面的决策。

对于每一位，若当前位为最高位的所有数对的 $\sum val_i$ 和原正负性相同，则说明将此位变为 $1$ 有意义，并将所有影响到的数变为 $-val_i$。

时间复杂度 $\mathcal{O}(n\log \max mask_i)$。

T4

设 $f(i)$ 为 $i$ 的数位和，给定 $a$，构造 $l,r$ 使得 $(\sum_{i=l}^{r}f(i))\bmod a=0$。

$1\leq a\leq 10^{18}$

Solution

设 $F(l,r)$ 为 $\sum_{i=l}^{r}f(i)$。因为 $\forall k < 10^{18},F(k+1,k+1+10^{18})=F(k,k+10^{18})+1$，令 $F(1,10^{18})\bmod a=p$，那么 $l=1+(a-p),r=10^{18}+(a-p)$。

$p$ 就好比 $18$ 个空位中放 $10$ 个物品，那么 $p=F(1,10^{18})=\sum_{i=1}^{18}C_{18}^{i}\times 9^{18-i}=81\times 10^{18}$。

时间复杂度 $\mathcal{O}(1)$。