题意简述一个字符串是“优秀”的，定义为：存在两个非空的字符串 $A,B$，满足这个字符串 $S=AABB$，那么这个 $S$ 就是优秀的。 给定一个串，计算它有多少子串是“优秀”的。相同的子串出现在不同的位置也被算两次。 长度 $\le 3e4$ 思路对于每个位置，我们维护 $pre[i]$ 表示以 ...

考场上想出了思路，但是没能写出来代码，实在可惜 题意简述有 $n\le 1e5$ 个正整数，每个数值域都是 $[1,10^6]$，并且最多有 $7$ 个因数。 请你求出最少选多少个数能使得乘积是平方数。 思路最多 $7$ 个因数 $\leftrightarrow$ 最多两个质因数 而且对于一个质因数 ...

题意简述$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} \operatorname{lcm}(i,j)$ $n\le 10^{10}$ （简短题意，恶臭规模） 思路总的来说，就是先把式子变一变，然后巧妙的用欧拉函数 $\varphi$ 加上杜教筛和整除分块来算 ...

题意简述给定 $n$ 个点 $m$ 条边的无向连通图，边带权。$q$ 次询问，每次问你 $u,v$ 之间的所有路径中，边权最大值最小是多少。 $n\le 7\times10^4,m\le 10^5,q\le 10^7$ （询问会用种子生成方式给你，具体见原题，不会影响输入时间） 思路首先跑一遍 Kr ...

题意简述有 $n$ 个人，$k$ 轮比赛。每次如果淘汰了 $x$ 个人，还剩下 $m$ 个人，得分增加 $\dfrac{x}{m}$ 的奖金。。假设你能控制每次淘汰多少人，最大化得分。 思路设 $dp[i]$ 表示现在还剩下 $i$ 个人的最优方案 （先不考虑轮数）。 那么 $dp[i]=max(d ...

题意简述你有一个字符串，仅由 A,B 两种字符构成。长度 $n\le 10^5$。维护 $Q$ 次操作，格式为：1 L R 区间 $[L,R]$ 中，$A$ 变成 $B$，$B$ 变成 $A$。2 L R A B 你有两个数，初始是 $A$ 和 $B$。从 $L$ 遍历到 $R$ ，如果这一位是字 ...

题意简述一个图有 $n$ 个点 $m$ 条边，每个边是白色或黑色。生成一棵树使得白边的数量恰好是 $k$，并且边权和最小。输出最小的边权和。 $1\le n,m\le 10^5$，边权在 $[1,100]$ 之间 思路我们在跑朴素的 Kruskal 的时候，把每个白边都调的贵一点，或者便宜一点。把白 ...

算法概述点分治用来统计树上满足某种条件的路径个数，一般具有可合并答案的性质（比如是否存在路径长度 $=k$等）。 算法步骤首先我们考虑经过根节点的满足条件的路径有多少。那比如我们就拿长度为 $k$ 举例，先从根节点 $DFS$ 一遍，求出每个节点的 $dis$。然后对于一个节点的 $dis[i]$， ...

题意简述给定一个 $n\le 10^5$ 个点带权的树，初始根为 $1$。支持三种操作：1 r 把根换成 $r$2 u v x 把 $LCA(u,v)$ 的子树整体加 $x$3 u 查询 $u$ 的子树点权和 操作数$\le 10^5$。每个点权 $\le 10^8$ 。 思路如果没有 $1$ 操作 ...

题意简述给定 $n$，求 $\sum\limits_{i=1}^{n} 2\sigma_2(i)+3\sigma_1(i)+5\sigma_0(i)$ $n<=1e9$ 其中 $\sigma_k(x)=x$ 所有因数的 $k$ 次方和。 思路我们反过来想，枚举每个因数对答案产生了多少贡献。 显 ...