曹轩鸣的博客

比赛传送门 A. Larger Score 因为只需要增加而不限制增加量，所以找到一对前小后大的数对，设法将它们交换即可。具体来说，所以对于 k+1k+1k+1 到 nnn 的一个位置 iii，找到在前 kkk 个当中离它最近的（最后的）、比它小的位置 jjj（取后缀 min⁡\minmin 后用 lower_bound 找出），用 k−jk-jk−j 次操作将 jjj 移到位置 kkk，用 i−k−1i-k-1i−k−1 次操作将 iii 移到位置 k+1k+1k+1，再用一次操作交换即可，总操作数为 (k−j)+(i−k−1)+1=i−j(k-j)+(i-k-1)+1=i-j(k−j)

在这个直角三角形中，我们设以 ccc 为底的大三角形面积为 ScS_cSc​，以 a,ba,ba,b 为底的两个小三角形的面积分别为 Sa,SbS_a,S_bSa​,Sb​。 显然，Sc=ch2=c2⋅h2cS_c=\frac{ch}{2}=c^2\cdot\frac{h}{2c}Sc​=2ch​=c2⋅2ch​。令 m=h2cm=\frac{h}{2c}m=2ch​，则有 Sc=mc2S_c=mc^2Sc​=mc2。 同理，Sa=a2⋅ha2aS_a=a^2\cdot\frac{h_a}{2a}Sa​=a2⋅2aha​​（其中 hah_aha​ 表示三角形 BPCBPCBPC 中以 aa

01背包 由于01背包太过经典，所以一定要把每一个细节理解透彻！ 有 nnn 个物品和一个容量为 mmm 的背包，每个物品有体积 wiw_iwi​ 和价值 viv_ivi​，求用这个背包所能装下的最大价值。 设 fi,jf_{i,j}fi,j​ 表示只考虑前 iii 个物品，体积不超过 jjj 的最大价值。如果我们算完了前 i−1i-1i−1 个物品的所有结果，那么第 iii 个物品有选和不选两种情况。如果不选，则结果为 fi−1,jf_{i-1,j}fi−1,j​；如果买，则：由于选了 iii 后体积不超过 jjj，那么选 iii 之前体积就不能超过 j−wij-w_ij−wi​，而选了

比赛传送门 赛时做出来五道题，涨大分（开心） A. First Grid problem 有一个两行两列的矩阵，每个格子有黑和白两种颜色，至少有两个黑色格子，问黑色格子是否构成一个连通块（四连通）。 显然，如果左上、右下都是白色或右上、左下都是白色，那么不能构成，否则能。 B. Hard Calculation problem 有两个正整数 aaa 和 bbb 做加法，问是否需要进位。 大水题，一位一位地判断即可。 C. Cheese problem 有 nnn 种奶酪，第 iii 种奶酪每千克能提供 aia_iai​ 的美味度，但最多能使用 bib_ibi​ 千克。你

引入 有很多题的答案可能会很大，这时候通常会让我们输出模一个数的结果。当我们的计算中只用到了加法，可以边加边模；只用到了乘法，可以边乘边模。但如果有除法，就不能边除边模了。这时候就要用到乘法逆元：a×inv(b)×inv(c)%mod=ab×c%moda\times inv(b)\times inv(c)\%mod=\frac{a}{b\times c}\%moda×inv(b)×inv(c)%mod=b×ca​%mod。 有了乘法逆元，在过程中想怎么模就怎么模，非常方便。 计算 我们都知道，当模数为质数时，可以用快速幂求 amod−2a^{mod-2}amod−2，否则可以用扩展欧几里

众所周知，Tarjan 可以用来求有向图的强连通分量，我们就不扯那些 dfs 生成树，前向边、返祖边之类的东西，直接步入正题。 准备工作 Tarjan 算法本质上是一次 dfs 的过程，我们用 dfn[u]dfn[u]dfn[u] 记录 uuu 结点被 dfs 到的顺序，用 low[u]low[u]low[u] 记录 uuu 能到达的所有结点中最小的 dfndfndfn（包括自己）（详细定义：能够回溯到的最早的已经在栈中的结点。设以 uuu 为根的子树为 subtreeusubtree_usubtreeu​，则 low[u]low[u]low[u] 定义为以下结点的 dfndfndfn 的

比赛传送门 做出来五道题。 A. AB Balance problem 给你一个只含有 a 和 b 的字符串，问怎样通过修改尽可能少的字符，使得 ab 的数量和 ba 的数量相等。 显然，ab 的数量和 ba 的数量最多差 111，而当开头字母和结尾字母相同时，ab 的数量等于 ba 的数量。如果不同，修改开头或结尾字母使它们相同即可。 B. Update Files problem 有 nnn 个电脑和 kkk 个数据线，其中一个电脑上有一个文件，每次可以通过数据线将文件从一个电脑传到另一个电脑上，耗时 111 小时。问至少需要几个小时才能让所有电脑都有文件。 设当前有 x

比赛传送门 赛时AC三道，补题做出一道。 A. Mathematical Addition Problem 给你两个正整数 u,vu,vu,v，求一对合法的 x,yx,yx,y 使得 xu+yv=x+yu+v\frac{x}{u}+\frac{y}{v}=\frac{x+y}{u+v}ux​+vy​=u+vx+y​。 解方程。 vx+uyuv=x+yu+v(vx+uy)(u+v)=uv(x+y)uvx+u2y+v2x+uvy=uvx+uvyu2y+v2x=0\begin{array}{c} \frac{vx+uy}{uv}=\frac{x+y}{u+v} \\ (vx+uy)(u+

这道题是线性筛的模板题，所以我们考虑怎么不用线性筛。 我们都知道有一种筛法叫埃拉托色尼筛，简称埃氏筛，它比线性筛好写，也更好理解，但它过不了这道题，那怎么办呢？我们可以用 bitsetbitsetbitset 代替 bool 数组来进行优化，这造成的常数优化非常显著，以至于开了 ios::sync_with_stdio(false) 之后能轻松过掉这道题，和线性筛的时间总差距只有 0.5s0.5s0.5s，可以说是非常优秀了。 AC 代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

A. Diverse Substring ProblemProblemProblem 定义一个字符串为多变的，当且仅当字符串中没有一个字符的出现次数严格大于 n/2n/2n/2。给定一个只由小写字母构成的字符串，问是否能找出一个多变的字串，如果能，任意输出一个。 n≤1000n\le 1000n≤1000 SolutionSolutionSolution 只有两个不同字符的字符串时多变的，所以只要给定的字符串中包含至少两个字符就一定可以，输出相邻两个不同字符即可。 B. Vasya and Books ProblemProblemProblem 有一摞书，从上到下依次编号为 a1