题目链接

CF

题意简述

有一个字符串 $S[1..n+2]$，告诉你 $\forall 1\le i\le n, S[i..i+2]$（所有长为 $3$ 的子串），求任意一个满足条件的 $S$。

$1\le n\le 2\cdot 10^5$，字符集为大小写字母 + 数字。

题目链接

CF

题意简述

给你一张二分图：左边 $t$ 个位置，第 $i$ 个位置上有 $a_i$ 个点；右边 $n$ 个带权的点，第 $i$ 个点与位置在 $[l_i, r_i]$ 之间的所有左边的点有连边；匹配权值为匹配中右边点的权值之和；求最大权匹配。

$1\le n,t\le 3\cdot 10^5$，保证 $l_i\le l_{i+1}$, $r_i\le r_{i+1}$。

题目链接

CF

题意简述

对于一个数列，每次操作可以将相邻的两个数 $x$ 和 $y$ 合并成一个数 $x+2y$，定义一个数列的权值为进行操作直至只剩一个数能得到的最大值。

多组询问，每次给定一个区间，求这个区间的权值。

数列值域 $-10^9\sim10^9$，数列长度和询问个数不超过 $10^5$。

作为一个刚刚上线两周就回滚了无数次数据的 OJ，备份自然是很重要的~

程序员就是代码重用的艺术家（

题目链接

洛谷

LOJ

BZOJ

题意简述

一个数列是“可删除的”，当且仅当可以通过这种操作将其清空：将数列中等于这个数列长度的数删去。

如，$[1, 2, 4, 4]$ 是“可删除的”，第一次操作删成 $[1, 2]$，第二次操作删成 $[1]$，第三次操作清空。

定义一个数列的权值为至少需要进行的单点修改数目，使得这个数列变成“可删除的”。

现在给你一个数列 $a_{1..n}$，以及 $m$ 次修改操作，你需要在每次修改后回答这个数列的权值。

修改操作有三种：

1. 单点修改。
2. 全局加一。
3. 全局减一。

$1\le n,m\le 150000$，数列初始值以及单点修改成的值在 $[1,n]$ 内，但全局修改可能使数列中的元素超过这个范围。

题目链接

CF

题意简述

给你一张 $n$ 个点 $m$ 条边的无向连通图，一条路径的权值是路径上的边的编号（十进制）顺次连接而成的数字。求 $1$ 到每个点的最短路，输出 对 $10^9+7$ 取模。

$2\le n\le10^5$, $n-1\le m\le10^5$。

题目链接

CF

洛谷

题意简述

给定一棵 $n$ 个点带边权的树，定义 $d(u)$ 为树上离它最远的点到它的距离，$q$ 次询问，每次询问给定 $l$，求一个最大的树上连通块 $V'$ 的大小，满足 $\forall u, v\in V'$，$|d(u)-d(v)|\le l$。

$1\le n\le 10^5$, $1\le q\le 50$。

题目链接

LOJ

洛谷

题意简述

你需要给 $n$ 颗珠子的项链染 $m$ 颗黑色，$n-m$ 颗白色，不能有连续的一串黑色珠子长度超过 $k$，求旋转同构下本质不同的染色方案数。

$1\le m,k\le n\le10^5$

题目链接

LOJ

题意简述

求长度为 $n$ 逆序对数为 $k$ 的排列个数。

$1\le n, k\le 10^5$，$k\le \binom n 2$