Solutions

题面 给出 $n$ 个数字 $a_1 , a_2 , \ldots , a_n$ ，每次操作可以给其中一个数加上 $2$ 的非负整数次幂。求最少的操作次数，使得这 $n$ 个数相等。 题解 令 $a_i$ 升序，记 $\text{bit}(i)$ 表示 $i$ 二进制中 1 的个数，则要求一个 $x$ 使得 $$\sum_{i=1}^n\text{bit}(x+a_ …

Jayun 发布于 2023-10-08 15:51:13

00

题目描述 定义：如果字符串 A 是字符串 B 的后缀，那么称 B 是 A 的 XQ 串。 小奇有 n 个只包含小写字母的字符串，编号为 1-n，表示为 Si。 接下来对于每个串 Si，小奇想知道：对于小奇拥有的 n 个字符串，所有是 Si 的 XQ 串的编号集合(包括 i）中第 Ki 小的编号。 对于 100%的数据 n<=100000，字符串总长<=300000。 题解 考虑处理 X …

Jayun 发布于 2023-10-08 11:57:18

00

题面 题目描述 著名的植物学家 Alice 经过多年的探索，终于找到了传说中的璀璨花。璀璨花的生长速度非常迅猛，如果不加以合适的控制，璀璨花会因为过度内耗而死亡。璀璨花的生长趋势可以用序列 $a$ 表示，Alice 在研读前人对璀璨花的研究后总结出了一个控制序列 $b$ 。Alice 需要让璀璨花的生长趋势尽可能贴合控制序列，这样璀璨花就能尽可能快且安全地生长，以让更多人能欣赏到传说花卉的美 …

Jayun 发布于 2023-10-01 09:10:31

00

题目大意 在平面直角坐标系中，有 $n$ 个圆。需要找到一个方向，使得从原点按该方向射出的一条射线，每隔距离 $d$ 为一个点，这些点落在圆的个数最大（同一个圆可以贡献多次）。 $n\leq2\times10^4,5\leq d\leq10.$ 思路 考虑一个圆被以原点为圆心、半径为 $k\cdot d$ 的若干个圆交。如下图。 发现每一个在圆内的弧线的贡献都是 $1$ ，那么 …

Jayun 发布于 2023-09-17 16:26:59

00

题目大意 记 $m_i=\underbrace{1\cdots1}_{i\text{ times}}$ ，即十进制下 $i$ 个连续的 $1$ 。 现在给定一个正整数 $n$ ，找到一个无限长的整数序列 $(x_1,x_2,\cdots)$ 满足： $\sum_{i=1}^\infty m_ix_i=n$ 。 最小化 $\sum_{i=1}^\infty i|x_i|$ 。 …

Jayun 发布于 2023-09-17 16:22:39

00

题意 求字符串字典序第 $k$ 大子串（本质不同或位置不同）。 $n\leq 5\times 10^5$ 题解 DP 求得结点大小（size），再 DP 求 DAG 子树（或子图？）的大小，像平衡树那样转移即可。 代码 const int N = 1e6 + 10; inline ll Read() { ll x = 0, f = 1; char c = getchar(); wh …

Jayun 发布于 2023-04-24 17:11:49

11

题意 给定一个长为 $n$ 的字符串 $s$ 和 $m$ 个问题，每个问题均有 $a,b,c,d$ 四个参数，求子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。 $1\le n,m\le 100,000$ 。 题解 SAM 例题。直接算长度太难，考虑二分长度：若二分到长度为 $\mathrm{len}$ ，接着查询子串 …

Jayun 发布于 2023-04-24 11:53:49

00

题目描述 一个 $n\times m$ 数独是一张包含 $m\times n$ 个区域的网格，其中每个区域包含 $n\times m$ 个格子，因此一个 $n\times m$ 数独共有 $nm\times nm$ 个格子。 $n\times m$ 数独的每行、每列、每个区域都恰好包含 $[1,nm]$ 的所有整数。 对于某行或某列，从某个方向开始，依次列出这行（列）的 …

Jayun 发布于 2023-03-27 18:25:59

00

题意 定义一个无向图的权值为所有结点度数的 $k$ 次方之和（规定 $0^0=1$ ）。 求所有 $n$ 个点的简单无向图的权值之和。 答案对 998244353 取模。 $n\leq10^9,0\leq k\leq5\times10^5$ 。 题解 可以对于每个点的贡献然后乘 $n$ 。考虑每个点贡献的组合意义，相当于是 $k$ 个有标号点放进 $d$ 个有标号桶里，并且可 …

Jayun 发布于 2023-01-28 07:53:08

00

题意 给定一棵 $n$ 个点的有根树，其中 $1$ 号点是根，定义 $f(x)=\sum_{i\leq j,\mathrm{LCA}(i,j)=x}(w_i+w_j)$ 。 现在你需要支持两种操作： 1 x v：对于所有 $x$ 子树内和 $x$ 距离不超过 $2$ 的点 $y$ ，令 $w_y\leftarrow w_y+v$ 。 2 x：询问 $f(x)$ 的值。 …

Jayun 发布于 2023-01-28 07:52:57

00