给定 $n$ 和数字串 $a_1,a_2,\cdots,a_n$，$b_1,b_2,\cdots,b_n$。 定义一次操作为：将一个等长且不相交的前缀和后缀对应位置交换。举例：${1,2,3,4,5,6}$ 交换长度为 $2$ 的前后缀变为 ${5,6,3,4,1,2}$。 可以对 $a$ 进行任意次操作，问是否能变成 $b$。多组数据。 $1\l…

给定一个 $n$ 个点 $m$ 条边的无向图。有 $q$ 个人，第 $i$ 个人要从 $s_i$ 到 $t_i$。 现在你要给无向图的每条边定向。问是否存在一种定向方法使得所有人都能够到达目的地。 $n,m,q\leq 2\times 10^5,u_i\neq v_i,s_i\neq t_i$ sol 我的做法（186ms） 可以发现，对于一个边双…

给定 $n$ 个数字 $a_1,a_2,\cdots,a_n$。 $m$ 次询问，每次询问给定 $x$，求 $\oplus_{i=1}^n (a_i+x)$ 的值。 强制在线。 $1\leq n,m\leq 2.5\times 10^5,0\leq a_i,x\lt 2^{60}$。 sol 由于每个 $a_i$ 加的都是 $x$，所以向第 $w$…

设一个由小括号和中括号组成的串 $S$ 的权值为 $\sum_{S_i\in{\texttt{'(',')'}}} A_i+\sum_{S_i\in{\texttt{'[',']'}}} B_i$。 求所有的合法的由小括号和中括号组成的长度为 $N$ 的串中最大的权值是多少。 $2\leq N\leq 10^5,2\mid N,1\leq A_i,…

给你 $N,L$ 和序列 $0=A_0<A_1<A_2<\cdots<A_n\leq A_{n+1}=L+1,0=B_0<B_1<B_2<\cdots<B_n\leq B_{n+1}=L+1$。 每次可以选择一个数 $x(1\leq x\leq N)$，使得 $A_x=A_{x-1}+1$ 或 $A_…

如果 $max(a_1,a_2,\cdots,a_m)\cdot min(a_1,a_2,\cdots,a_m)\geq a_1+a_2+\cdots+a_m$，则整数序列 $a_1,a_2,\cdots,a_m$ 被称为好的。 如果 $a$ 的每个非空子序列都是好的，则整数序列 $a_1,a_2,\cdots,a_n$ 被称为完美的。 给定两个整…

给定一个 01 串 $s$，要求你找到一个与 $s$ 长度相等的 01 串 $t$ 并满足以下条件： 对于任意的 $l,r(1\leq l\leq r\leq n)$，$s[l:r]$ 和 $t[l:r]$ 的最长不下降子序列长度相同； $t$ 中 $0$ 的数量尽可能多。 有多解输出任意一种。$|S|\leq 10^5$。 sol 这个题非常有意…

给定 $n$ 个数字 $a_1,a_2,\cdots,a_n$，每次操作可以给某个 $a_i$ 加上 $2$ 的非负整数次幂。 求最少的操作次数使得 $n$ 个数相等。 $1\leq n\leq 10^5,0\leq a_i\leq 10^{17}$ sol 不妨先将 $a$ 从小到大排序。 设最后每个数都等于 $a_n+x(x\geq 0)$。那…

给定一个小写字母组成的字符串 $S$，每次操作可以交换相邻两个字符。 问最少需要多少次操作，使得 S 的字典序严格大于 atcoder，无解输出 -1。 有 $T$ 组数据，$1\leq T\leq 100,1\leq |S|\leq 1000$。 sol ```cpp include using namespace std; const char…