Solutions

题目大意 在平面直角坐标系中，有 $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

题意 一个长度为 $n$ 的整数序列 $\{h_i\}$ ， $m$ 种操作，每种操作为花费一定的代价将一段长度为给定值的连续子区间加一或减一，每种操作都可以使用任意多次。 求把 $\{h_i\}$ 变成单调不降的最小代价，或者判断无解。 $n,m\leq200$ 。 思路 区间加一减一，用差分维护，设差分数组 $a_i=h_i-h_{i-1}$ 。那么目标就是要使所有 $a_i …

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

00

大意 给定长度为 $n$ 的系数数组 $a_i$ 和 $l,r$ ，求出长度为 $n$ 的数组 $x_i(x_i\in\mathbb{N})$ 使得： $$l\leq \sum_{i=1}^na_ix_i\leq r $$ 问 $x_i$ 数组有多少个。 $n\leq 12,1\leq l\leq r\leq 9\times10^{11},1\leq a_i\leq5\ti …

Jayun 发布于 2022-11-25 16:58:52

00

题目 阿申准备报名参加 GT 考试，准考证号为 $N$ 位数 $X_1,X_2,…,X_n$ ，他不希望准考证号上出现不吉利的数字。 他的不吉利数字 $A_1,A_2…A_m$ 有 $M$ 位，不出现是指 $X_1,X_2,…,X_n$ 中没有恰好一段等于 $A_1,A_2,…,A_m$ ， $A_1$ 和 $X_1$ 可以为 $0$ 。阿申想知道不出现不吉利数字的号码有 …

Jayun 发布于 2022-11-21 17:17:04

00