Solutions

口胡 设 $f_{i,j}$ 表示 $i$ 是第 $j$ 个邮局，有 $$f_{i,j}=\min_{k<i,g\text{二分得到}}\left\{f_{k,j-1}+\sum_{h=k+1}^{g-1}(a_h-a_k)+\sum_{h=g}^{i-1}(a_i-a_h)\right\} $$ 后面那一串满足四边形不等式。

Jayun 发布于 2023-10-30 19:16:33

00

题意 $n$ 个数，每个数 $a_i$ ，选 $k$ 个数，一个选取方案的值是异或和。求所有选取方案值的和。 $n\leq10^5,a_i<2^{31}$ 。 题解 加法和异或本质相同。 考虑每一位的贡献，简单组合计数。 代码 const int N = 3e5 + 5, mod = 998244353; inline ll Read() { ll x = 0, f = 1; …

Jayun 发布于 2023-10-30 19:02:53

00

题面 有一颗 $n$ 个点的树，第 $i$ 个点有点权 $a_i$ 。 现在要断掉一些边，记一个连通块的权值为连通块中所有点的点权和，一个断边方案的权值为所有连通块的权值的乘积的平方。 求所有不同的断边方案的权值和对 $10^9+7$ 取模后的结果。 $n\leq5\times10^5$ 题解 直接组合意义：每个连通块 $\sum a_i$ 个球，对每个连通块选两个球（放回） …

Jayun 发布于 2023-10-30 18:48:18

00

题目大意 给一个 $2n$ 结点的二分图，左边的点 $i$ 连向 $i+n$ 并且有值 $LE,LF,E,F$ 分别表示经过此边需要多少 $e,f$ 、经过此边后会使 $e\leftarrow e+E,f\leftarrow f+F$ ，右边的点连向任意左边点无值无条件。现在可以从任意点出发，一笔画遍历图，问起始时可以带最小的 $e,f$ 是多少。 $n\leq10^5$ …

Jayun 发布于 2023-10-30 18:23:46

00

题目大意 给定 $n$ 个数，求出这 $n$ 个数的一个非空子集，使得这个子集中的数的和能被 $n$ 整除，无解输出 -1。 $n\leq 10^5$ 。 口胡 一眼鸽笼，算上 0 位前缀和有 $n+1$ 个，而最多 $n$ 个余数，此处鸽笼。

Jayun 发布于 2023-10-30 15:56:31

00

题目大意 有 $n$ 个点，它们的位置分别在 $x_i$ ，它们有值 $a_i$ 。现在给 $T$ 秒钟时间，要求选定的一个 $i$ 从它出发，在这 $T$ 秒内可以花 $1$ 秒时间移动， $0$ 秒时间拿取某个点的 $1$ （ $a_j\leftarrow a_j-1$ ）、放在某个点（ $a_j\leftarrow a_j+1$ ）并且手里最多只有 $1$ ，求 …

Jayun 发布于 2023-10-29 22:15:12

00

[ZJOI2013] 防守战线 题目描述 战线可以看作一个长度为 $n$ 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第 $i$ 号位置上建一座塔有 $C_i$ 的花费，且一个位置可以建任意多的塔，费用累加计算。有 $m$ 个区间 $[L_1, R_1], [L_2, R_2], \cdots, [L_m, R_m]$ ，在第 $i$ 个区间的范围内要建至少 $D_i …

Jayun 发布于 2023-10-27 11:47:36

00

Destinations 题目大意 在一棵有 $n$ 个结点的树上，有 $m$ 个人从 $s_i$ 出发，可以选择三个目的地 $e_{i,[1,3]}$ ，分别花费 $c_{i,[1,3]}$ 。现在求一种方案使得每个点只被一个人走过且花费最小。 题解 一个人的路径是共起点的，又有每条路径没能经过相同点，那么就可以把人给忽略，直接考虑 $3m$ 条路经的选择。即简化题意：选择 …

Jayun 发布于 2023-10-26 16:47:21

00

题面 给出一个长度为 $n$ 的序列 $a$ ，有 $m$ 次操作，格式如下： 1 x y k 对于所有满足 $(i-1)\bmod x\le y$ $i$ 的 ，将 $a_i$ 的值加 $k$ 。 2 l r 求 $\sum_{i=l}^r a_i$ 。 数组下标从 1 开始。 $n,m\leq2\times10^5$ 。 题解 分块维护差分数组。特别地，对于所有小于块 …

Jayun 发布于 2023-10-26 08:11:29

00

meirin 题目大意 在和积和的基础上加个区间增加 $b_i$ 的值，每次操作完询问和积和。 题解 推式子，发现加的数和原本的 $a_i,b_i$ 是独立的。然后没了，推个式子即可。 代码 const int N = 5e5 + 5, mod = 1e9 + 7; inline ll Read() { ll x = 0, f = 1; char c = getchar(); wh …

Jayun 发布于 2023-10-26 08:03:20

00