欢迎来到 Siyuan 的博客!
Siyuan 的博客
繁华落尽。「Codeforces 1174F」Ehab and the Big Finale
题目链接:Codeforces 1174F
这是一道交互题。
给定一棵有 $n$ 个点的树,节点 $1$ 为根节点。
我们选择一个隐藏节点 $x$,你需要进行以下三种操作来找到这个节点 $x$ 的编号。
d u
:你会得到节点 $u$ 和 $x$ 之间的距离。两个节点之间的距离定义为最短路径上的边数。s u
:你会得到节点 $u$ 到 $x$ 的最短路径上的第二个节点。但是如果 $u$ 不是 $x$ 的祖先,你会直接得到Wrong answer
的结果!! u
:回答隐藏节点 $x$ 的编号为 $u$。
你需要在 $36$ 次询问(不包括回答)内找到 $x$ 的编号。这个隐藏节点 $x$ 不会根据你的询问而改变。
数据范围:$2 \le n \le 2 \times 10 ^ 5$。
「Codeforces 1189F」Array Beauty
题目链接:Codeforces 1189F
我们定义一个序列 $b_{1}, b_{2}, \dots, b_{n} (n > 1)$ 的「美丽值」为 $\min_{1 \le i < j \le n} \lvert b_{i} - b_{j} \rvert$。
我们给定一个序列 $a_{1}, a_{2}, \dots, a_{n}$ 个一个数字 $k$。请计算出所有长度恰好为 $k$ 的子序列的「美丽值」之和,答案对 $998244353$ 取模。
数据范围:$2 \le k \le n \le 1000$,$0 \le a_{i} \le 10 ^ {5}$。
「Codeforces 1189D2」Add on a Tree: Revolution
题目链接:Codeforces 1189D2
你有一个棵 $n$ 个点的树,初始所有的边上的数字都是 $0$。对于每次操作,你可以选择两个不同的叶子节点 $u,v$ 和一个任意整数 $x$ 并把 $u - v$ 这条简单路径上的边加上 $x$。
每条边都有一个目标状态,用一个两两不同的非负偶数表示。你需要判断这个目标状态是否可以通过有限次操作达到。如果可行则输出 YES
和构造的方案;否则输出 NO
。
注意叶子节点的定义为度数为 $1$ 的点。
数据范围:$2 \le n \le 10 ^ {5}$。
「Codeforces 1189D1」Add on a Tree
题目链接:Codeforces 1189D1
你有一个棵 $n$ 个点的树,初始所有的边上的数字都是 $0$。对于每次操作,你可以选择两个不同的叶子节点 $u,v$ 和一个任意实数 $x$ 并把 $u - v$ 这条简单路径上的边加上 $x$。
我们令 $w_{i}$ 表示最终第 $i$ 条边上的实数,是否对于所有的 $w_{i} \in \mathbf{R}, 1 \le i < n$,都存在有限的操作使得所有的边都满足条件?如果可行则输出 YES
否则输出 NO
。
注意叶子节点的定义为度数为 $1$ 的点。
数据范围:$2 \le n \le 10 ^ {5}$。
「Luogu 4173」残缺的字符串
题目链接:Luogu 4173
很久很久以前,在你刚刚学习字符串匹配的时候,有两个仅包含小写字母的字符串 $A$ 和 $B$,其中 $A$ 串长度为 $m$,$B$ 串长度为 $n$。可当你现在再次碰到这两个串时,这两个串已经老化了,每个串都有不同程度的残缺。
你想对这两个串重新进行匹配,其中 $A$ 为模板串,那么现在问题来了,请回答,对于 $B$ 的每一个位置 $i$,从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配?
数据范围:$1 \le m \le n \le 3 \times 10 ^ {5}$。
「Codeforces 1199E」Matching vs Independent Set
题目链接:Codeforces 1199E
给定一个由 $3 \cdot n$ 个点、$m$ 条边组成的图。你需要找到一组大小为 $n$ 的边的匹配,或者找到一组大小为 $n$ 的独立集。
一组边的匹配表示不存在两条边拥有一个共同的点。
一组独立集表示不存在两个点被同一条边相连。
如果能找到一组边的匹配,输出 Matching
和方案;如果能找到一组独立集,输出 IndSet
和方案;否则输出 Impossible
。
本题有 $T$ 组数据。
数据范围:$1 \le \sum n \le 10 ^ {5}$,$0 \le \sum m \le 5 \times 10 ^ {5}$。
「Codeforces 1199F」Rectangle Painting 1
题目链接:Codeforces 1199F
有一个大小为 $n \times n$ 的网格图。其中一些格子是黑色的,其余格子都是白色的。你每次操作可以任意选择一个大小为 $h \times w$ 的矩形并把它全部染成白色,花费为 $\max(h, w)$。现在你想把所有格子都染成白色,请求出最小花费。
数据范围:$1 \le n \le 50$。
「WC 2011」最大 XOR 和路径
题目链接:BZOJ 2115
考虑一个包含 $n$ 个点和 $m$ 条边的无向连通图,节点编号为 $1$ 到 $n$,第 $i$ 条边的边权为非负整数 $D_{i}$。试求出一条从 $1$ 号节点到 $n$ 号节点的路径,使得路径上经过的边的全是的 $\text{XOR}$ 和最大。
路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 $\text{XOR}$ 和时也要被计算相应多的次数。
数据范围:$1 \le n \le 5 \times 10 ^ {4}$,$1 \le m \le 10 ^ {5}$,$0 \le D_{i} \le 10 ^ {18}$。
「AHOI / HNOI 2017」礼物
题目链接:LOJ 2020
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 $n$ 个装饰物,并且每个装饰物都有一定的亮度。
但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$(可能是负数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。
在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 $1, 2, \dots, n$,其中 $n$ 为每个手环的装饰物个数,第一个手环的 $i$ 号位置装饰物亮度为 $x_i$,第二个手环的 $i$ 号位置装饰物亮度为 $y_i$,两个手环之间的差异值为:
$$ \sum_{i = 1} ^ {n} (x_{i} - y_{i}) ^ {2} $$
麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小,这个最小值是多少呢?
数据范围:$1 \le n \le 5 \times 10 ^4$,$1 \le a_{i} \le m \le 100$。