比赛链接

Chef and Proxy - PROXYC

题目描述

给定一个由字符 $A,P$ 构成序列 $S$

你可以把一些位置上的值变成 $B$,如果 $S_i$ 能变成 $B$,当且仅当:

  • $3 \le i \le n-2$
  • $S_i=A$
  • $([S_{i-1}=P] \lor [S_{i-2}=P]) \land ([S_{i+1}=P] \lor [S_{i+2}=P])$

你的目标是把尽可能少的 $A$ 变成 $B$,之后需要满足 $ \frac{\sum_{x \in S}[x \ne A]}{|S|} \ge \frac{3}{4}$

数据范围:$1 \le |S| \le 1000$

题解

设有 $x$ 个位置可以变成 $B$,有 $y$ 个位置是 $P$,至少需要 $z$ 个非 $A$ 的位置

如果 $y \ge z$,那么就直接可行了,否则需要 $z-y$ 个位置放 $B$,判断一下即可

Guddu on a Date - KS2

题目描述

定义圆数为十进制下个位数字之和为 $10$ 的倍数的正整数,求第 $n$ 个圆数

数据范围:$1 \le n \le 10^{18}$

题解

首先圆数的位数不会小于 $2$,而且个位是由个位前的数位之和唯一确定的

也就是所有圆数去掉个位后互不相同,且构成正整数集

也就是只需要输出 $n \cdot 10+((10-m \bmod 10) \bmod 10)$ 即可,其中 $m$ 为 $\left\lfloor \frac{n}{10} \right\rfloor$ 的各个数位之和

Road Signs - RSIGNS

题目描述

$Marichka$ 在去大厨国的途中看到了 $10^K$ 个路牌(编号为 $0 \sim 10^K-1$)

编号为 $i$ 的路牌一面写了数字 $i$,另一面写了数字 $10^K − i − 1$

$Marichka$ 想知道,有多少块路牌正反两面的数字中,一共只有两种不同的数位?

由于答案可能很大,请求出其对 $10^9 + 7$ 取模的结果

数据范围:$1 \le K \le 10^9$

题解

显然答案就是 $10 \times 2^{K-1}$

Chef and Ingredients - CHFING

大厨想要做一顿满汉全席,为此,他需要各种各样的食材

每种食材都有自己的美味程度,可以是任意正整数

初始时,对于 $[K, K + N − 1]$ 内的每种美味程度,大厨都有无限量的食材

食材有个独特的性质:任意两种食材经过混合,都可以得到一种新食材

设原本两食材的美味程度分别为 $x$ 和 $y$,那么新食材的美味程度就是 $x + y$

混合得到的新食材也可以再次被混合,大厨可以以任意方式混合任意多次

如果无论如何都无法得到美味程度为 $v$ 的食材,那么我们称美味程度 $v (v > 0)$ 是不可达成的

否则,就是可达成的

大厨要做出每种可达成的美味程度的食材,因此他想知道有多少种不可达成的美味程度

由于种数可能很多,请你求出其对 $10^9 + 7$ 取模的结果

注:可达成美味程度有无穷多种,但可以证明对于 $N \ge 2$,不可达成的美味程度一定只有有
限种

数据范围:$2 \le N \le 10^{18},1 \le K \le 10^{18}$

题解

设你能使用的数字为 $a,a+1,a+2,\cdots,b$,那么 $1 \sim a-1$ 一定无法达成

如果 $b \ge 2a$,则所有数字都可以构成

否则 $b+1 \sim 2a$ 是无法构成的,把 $[a,2a]$ 当作一块,所有块的 $b+1 \sim 2a$ 部分都无法构成

于是答案就是:
$$
\sum_{i=0}^{K+N-3}\left\lfloor \frac{i}{N-1} \right\rfloor
$$

Sum and GCD - SUMAGCD

题目描述

大厨有一个正整数序列 $A_1, A_2, \cdots , A_N$

他想要将这个序列分成两个非空的(未必连续的)子序列 $B$ 和 $C$,使得 $\gcd(B) + \gcd(C)$ 尽可能大

请你求出这一最大值

数据范围:$2 \le N \le 10^5, 1 \le A_i \le 10^9$

题解

首先重复的数字是没用的,先去重一下

猜想最优解一定是某个数单独作为一个集合,剩下的数字另作一个集合

然后写一下,发现它过了

Lent Money - LENTMO

题目描述

大厨借了些钱给 $Chefexim$

大厨讨债讨了好一阵子了,但 $Chefexim$ 总是能找到一些理由拖着

这次,大厨真的生气了,他自己想做点印度点心都没钱买食材了

看到大厨这么生气,$Chefexim$ 终于决定还钱了

他知道大厨喜欢做题,因此还钱的同时还送了大厨一道题,让他消消气

$Chefexim$ 把借来的钱分装进了 $N$ 个袋子(编号为 $1 \sim N$),第 $i$ 个袋子里有 $A_i$ 块钱

他把所有 $N$ 个袋子都给了大厨,然后告诉了他两个整数 $K$ 和 $X$

大厨可以任意次(包括零次)进行下面的操作:

  • 选择 $K$ 个不同的袋子,编号分别为 $i_1, i_2, \cdots , i_K (1 \le i_j \le N)$
  • 改变选择的袋子里装的金额,对于 $1 \le j \le K$,编号为 $i_j$ 的袋子里的钱从 $A_{i_j}$ 变为 $A_{i_j} \text{ xor } X$

每个袋子可以在任意多次操作中被选择

假设大厨按照最优策略操作,最后所有袋子里的金额之和最大可以是多少?

数据范围:$1 \le N \le 10^4, 1 \le K \le N, 0 \le A_i \le 10^9, 0 \le X \le 10^9$

题解

首先题意可以转化为,给定 $n$ 张牌,每张牌正面是 $0$,反面是 $b_i$

每次你可以选择 $k$ 张牌并把它们翻面,最大化最终所有牌朝上面的数字之和

首先如果 $k=n$ 可以特判掉

否则,如果 $k$ 是奇数,则可以把任意多张牌都翻面

如果 $k$ 是偶数,则只能把任意偶数张牌翻面

那么从大到小排序后贪心即可

Intersecting Paths - INTRPATH

题目描述

给定一棵 $N$ 个节点的树(无向无环连通图),节点编号为 $1 \sim N$

对于每对节点 $u$ 和 $v$,记它们之间的简单路径为 $(u, v)$

这些路径都是没有方向的,因此 $(u, v)$ 与 $(v, u)$ 等价

你需要回答 $Q$ 个询问,每个询问给定两个节点 $u$ 和 $v$

对于树中每一条简单路径 $(a, b)$,我们定义完美相交如下:

  • 记路径 $(u, v)$ 和 $(a, b)$ 途经的节点(包括端点)集合分别为 $S_1$ 和 $S_2$
  • 如果 $|S_1 \cap S_2|=1$(即两条路径只有一个公共节点),那么 $(a, b)$ 与 $(u, v)$ 完美相交

询问的回答即与 $(u, v)$ 完美相交的简单路径条数

数据范围:$1 \le Q \le 3 \cdot 10^5,1 \le u,v \le N \le 250000$

题解

只需要对于每个链上的点考虑一下经过它的路径条数即可

设 $s_u$ 表示 $u$ 的子树大小,$f_u$ 表示 $u$ 的子树中经过 $u$ 的路径条数,考虑链上的边 $u \to v$,那么交点为 $u$ 的路径条数为 $f_u-s_v(s_u-s_v)$,预处理后前缀和即可解决

之后特殊考虑一下 $\text{lca}$ 处的答案即可

Chef and His Dish - COOLCHEF

题目描述

大厨在厨房里做实验

他有 $N$ 种香料(编号为 $0 \sim N − 1$),类型分别为 $S_0, S_1 , \cdots, S_{N−1}$

你需要回答 $Q$ 个询问,每个询问给定两个整数 $L$ 和 $R$

大厨想使用编号在 $[L, R]$ 中的所有香料来做一道菜

不过,大厨不知道应该以什么顺序放这些香料

因此,他想知道一共有多少种不同的可能

即,序列 $S_L, S_{L+1}, \cdots , S_R$ 共有多少本质不同的排列方案

由于答案可能很大,请输出答案对 $10^9 + 7$ 取模的结果

我们认为两种排列本质不同,当且仅当存在下标 $i$,且两个排列的第 $i$ 位不同

你需要在线回答所有询问,输入已经过加密

数据范围:$1 \le N,Q \le 3 \cdot 10^5, 1 \le S_i \le 10^9, 0 \le L, R < n$

题解

分块模板题,卡卡常就过了

Count Arrays - COUNTIT

题目描述

考虑所有仅包含 $[1, K]$ 中的整数的 $N$ 行 $M$ 列矩阵(行列均从 $1$ 开始编号)

对于每个这样的矩阵 $A$,按下述规则构造序列 $L_1, L_2, \cdots , L_{N+M}$:

  • 对于 $1 \le i \le N$,$L_i$ 为 $A$ 第 $i$ 行中元素的最大值
  • 对于 $1 \le i \le M$,$L_{i+N}$ 为 $A$ 第 $i$ 列中元素的最大值

请求出有多少种不同的序列,由于答案可能很大,请输出其对 $10^9 + 7$ 取模的结果

数据范围:$1 \le K\ le 10^9, 1 \le N,M \le 10^5$

题解

猜想这个序列只需要满足前 $n$ 个位置和后 $m$ 个位置的最大值相同即可

不难得到答案为:

$$
\begin{aligned}
\sum_{x=1}^{k} \left(x^n-(x-1)^n\right) \left( x^m-(x-1)^m \right)
\end{aligned}
$$

至多是个 $n+m+10$ 次多项式,暴力插值即可

另一个没法做的想法:

定义 $0^0=1$,答案为:

$$
\begin{aligned}
&\sum_{x=1}^{k} \sum_{i=1}^{n} {n \choose i} (x-1)^{n-i} \sum_{j=1}^{m} {m \choose i} (x-1)^{m-j} \\
=&\sum_{x=1}^{k} \sum_{i=0}^{n-1} {n \choose n-i} (x-1)^{i} \sum_{j=0}^{m-1} {m \choose m-i} (x-1)^{j} \\
=&\sum_{x=1}^{k} \sum_{i=0}^{n-1} {n \choose i} (x-1)^{i} \sum_{j=0}^{m-1} {m \choose i} (x-1)^{j} \\
=&\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} {n \choose i} {m \choose j} \sum_{x=1}^{k} (x-1)^{i+j} \\
=&\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} {n \choose i} {m \choose j} \sum_{x=0}^{k-1} x^{i+j} \\
=&\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} {n \choose i} {m \choose j} f_{i+j}(k) \\
=&\sum_{T=0}^{n+m-2}f_T(k) \sum_{i=0}^{T} {n \choose i} {m \choose T-i}[i<n][T-i<m] \\
=&\sum_{T=0}^{n+m-2}f_T(k) \left({n+m \choose T}-{m \choose T-n}-{n \choose T-m} \right)
\end{aligned}
$$

其中 $f_T(k)=\sum_{i=0}^{k-1}i^T$

然而这个玩意不太能做,还是算了

Forgotten Tree 9 - FGTREE

SnackDown 99 - SNCK99