浅念づ昔夜's Blog

传送门

Solution

对于 $1\le a_i \le 10^6$，不超过 6 次操作可将一个 $a_i$ 变为 $1$ 或 $2$。有 $O(n\log n)$ 的方法预处理出 $1\sim 10^6$ 的正约数个数。

传送门

Solution

倒序染色使得每个点被染色后，可从序列中删去。使用单向链表，设 $nxt_i$ 为点 $i$ 在链表中指向的下一个点。设当前染色区间为 $[L,R]$，点 $i$ 染色结束后，令 $nxt_i=nxt_R$。

传送门

Solution

对物品以过期时间（从小到大）为第一关键字，价格（从大到小）为第二关键字进行排序，然后开一个按照物品价值排序的小根堆。

传送门

Solution

每个 $10$ 都是由一对 $2$、$5$ 相乘而得。设 $F_{i,j,0}$ 为点 $(1,1)$ 到 $(i,j)$ 路上最少 $2$ 的数量，$F_{i,j,1}$ 为最少 $5$ 的数量。答案即为 $ans=\min\{F_{n,n,0},F_{n,n,1}\}$。

传送门

Solution

观察到 $a_i\le 10^6 <2^{20}$，拆位后数组变成 20 条长度为 $n$ 的 01 串。开二十棵线段树分别维护这些串的区间和。

传送门

Solution

设当前待合并的串为 $A$，已合并的串为 $B$。若 $|A|\ge |B|$，则 $C=A+B$。否则 $C$ 等于 $A$ 与 $B$ 长度为 $|A|$ 的后缀拼接而成的字符串。对 $C$ 进行 KMP，求出最大相同前后缀长度 $nxt_{|C|}$。把 $A$ 的相应长度后缀并入 $B$ 后面即可。

传送门

Solution

设第 $i$ 个序列最小没出现的非负整数为 $v_i$，次小没出现的非负整数为 $u_i$。从 $u_i$ 向 $v_i$ 连有向边。由于 $u_i>v_i$，最后得到的是一张有向无环图，且每个点之间不一定连通。

传送门

Solution

注意数据范围。用桶记录某数是否在数组内出现。从 $10^6$ 枚举 $x$ 到 $1$，检查是否能生成 $x$。若所有在数组内的 $x$ 的倍数的最大公约数等于 $x$，则可生成 $x$。

设数组内最大的数为 $N$，时间复杂度 $O(N\log N)$

传送门

Solution

若设 $F_a$ 为选择付款的商品的 $t_i$ 之和为 $a$ 时，支付的最小金额，$k$ 为这些商品的数量。那么只有 $a\ge n-k$ 时，$F_a$ 才为一种合法的答案。

传送门

Solution 1

考虑使用 Z 函数（exkmp）且设 $S$ 长度为 $n$，下标从 $0$ 开始。