Solutions

题目大意 有 $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

题面 有 $n$ 个数，第 $i$ 个数是 $a_i$ ，Bob 可以从第 $1$ 个数开始，依次考虑这些数选不选。 如果 Bob 同时选择了 $i,j(i<j)$ 两数则应该有 $a_i\le a_j$ 。 如果 Bob 不选择 $i$ , 并且这是连续第 $k$ 场没有选择的数，他将丢失 $k$ 点分数。 Bob 最终获得的值是所有选择的数 $a_i$ …

Jayun 发布于 2023-10-25 07:26:06

00

The Shortest Statement 题目描述 给你一个有 $n$ 个点， $m$ 条边的无向连通图。有 $q$ 次询问，第 $i$ 次询问回答从 $u_i$ 到 $d_i$ 的最短路的长度。 $1 \le n, m \le 10^5, m - n \le 20$ 题目大意 注意到 $m - n \le 20$ ，那就把它转成树来做，而多出来的边标记两端为特殊点 …

Jayun 发布于 2023-10-24 11:59:05

00

题目大意 一个长度为 $n$ 的序列。现在按照从 $1$ 到 $n$ 的顺序，每个 $i$ 将自己 $a_i$ 中点每个 1 一个一个地随机地分给 $n-1$ 个位置。 问最后每个位置的期望 $a_i$ ，对 998244353 取模。 $n\leq10^6$ 。 题解 简单期望 DP，令 $f_i$ 表示操作到第 $i$ 个数时它的的期望值。 代码 const …

Jayun 发布于 2023-10-24 11:47:48

00

[HAOI2011] problem a 题目描述 一次考试共有 $n$ 个人参加，可能出现多个人成绩相同的情况。第 $i$ 个人说：“有 $a_i$ 个人成绩比我高， $b_i$ 个人成绩比我低。” 请求出最少有几个人没有说真话。 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$ ， $0 \leq a_i, b_i \leq n$ 。 题解 一个 …

Jayun 发布于 2023-10-23 07:54:16

00

[CSP-S 2023] 结构体 题目大意 模拟定义结构体、元素，并查询某个元素的地址或某个地址的元素。 题解 直接模拟，挺难调的。 代码 考场写了个屎山。 inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = get …

Jayun 发布于 2023-10-23 07:34:57

00