Solutions

题面 有 $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

[CSP-S 2023] 消消乐 题目 有一个长度为 $n$ 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。 其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。 求这个字符串的所有非空连续子串中，有多少个是可消除的。 $1 \le n \le 2 \times 10^6$ ，且询问的字符串仅 …

Jayun 发布于 2023-10-23 07:28:26

00

题意 给定一个长度为 $n$ 的非负整数序列 $[a_1,…,a_n]$ ，求它的一个子序列 $[{a_i}_1,{a_i}_2,…,{a_i}_k]$ $(1≤i_1<i_2<⋯<i_k≤n)$ ，使得 $\sum^{k−1}_{j=1}({a_i}_j\text{and} {a_i}_{j+1})$ 最大。你只需要输出这个最大值即可。 $n\leq2\tim …

Jayun 发布于 2023-10-20 15:35:28

00

口胡 这个网格图求最小割即求对偶图上最短路。对于任意两个附加点之间的空间都是一个点（同色边权为 0），然后两两配对，如果存在路径有交集的，一定不是最优的（这里在思考时花的时间多，我也不知道为啥……），那么 $\mathcal{O}\left(\left(\sum k\right)nm\log nm\right)$ 建二分图，其中对数是跑最短路的时间。对这个二分图跑最优匹配即可。

Jayun 发布于 2023-10-19 19:39:31

00

题面 给出一个长度为 $n$ 的序列 $s$ ， $q$ 组询问。 每次给定区间 $[l,r]$ 。 如果 $i,j \in [l,r]$ ， $s_i|s_j$ 则 $i$ 得一分。 问有多少个没有得到满分，即 $r-l$ 。 题解 考虑能整除区间内所有数的数的个数。可简单证明即为求区间内区间最大公因数的个数。 代码 const int N = 1e5 + 5; inli …

Jayun 发布于 2023-10-18 19:49:46

00

Mushroom Gnomes 题面 很久以前，在蘑菇森林的灌木丛中生活着蘑菇地精。它们以神奇的蘑菇而在邻居中闻名。它们的神奇特性使得它们每分钟可以在相邻的两个蘑菇之间长出另一个蘑菇，而该蘑菇的重量等于两个相邻蘑菇的重量之和。 蘑菇地精喜欢一切都井井有条的，这就是为什么它们总是按照重量递增的顺序将蘑菇种成一行。 地精们种下蘑菇后就去吃饭了。 $x$ 分钟后，他们返回，发现新的蘑菇长大了，因此打 …

Jayun 发布于 2023-10-18 17:06:14

00