sort 这题题意就是给定有 nnn 个数的数组 aaa，每次将 aaa 划分为多个连续的下降区间，将每个有至少两个数的区间翻转。问让 aaa 排好序需要至少多少次翻转。 O(n2)O(n^2)O(n2) 的做法很显然，就按题意模拟即可，考虑优化。 假设第一次数组 aaa 划分成了 [1,2,…,p1],[p1+1,p1+2,…,p2],…,[ps−1+1,ps−2+1,...,ps](ps=n

一道字符串&DP好题。 题意 给你一个字符串 sss，还有 kkk 组字符串，问你从每组字符串中只选一个字符串，且按顺序排列后连接起来的串为 sss 的子串的选择种数有多少个，对 1e9+71\text{e}9+71e9+7 取模。 题解 显然是道 DP。 定义 fi,jf_{i,j}fi,j​ 表示按顺序选到第 iii 组串且连接起来的字符串匹配到 sss 的第 jjj 个位置的种数

前言 卡特兰数是初赛中比较重要的数学知识，所以写篇博客总结一下。 定义 用 CnC_nCn​ 表示从 (0,0)(0,0)(0,0) 出发，每次只能向右或向上走 1 步，且 xxx 轴的值始终不小于 yyy 轴的值，到 (n,n)(n,n)(n,n)的方案种数。 通项+证明 Cn=1n+1(2nn)C_n=\dfrac{1}{n+1}\left(\begin{matrix}2n \\ n\

题目 30pts\text{30pts}30pts 显然就是这道题。 100pts\text{100pts}100pts 肯定要跑最短路的。令 did_idi​ 表示 iii 到 nnn 的最短路长度。 fu,if_{u,i}fu,i​ 表示从 uuu 到 nnn 长度为 du+id_u+idu​+i 的路径个数。 disdisdis 数组显然可以建反图然后跑源点为 nnn 的最短路。 考

赛时想了一下就过了 一个显然的结论：给定一个正整数 nnn，很多个与 nnn 互质的正整数的积与 nnn 互质。 由于这题要求的数的乘积被 nnn 除余 111，所以这些数都是与 nnn 互质的。 所以长度 ≤\leq≤ nnn 的既约剩余系长度（指的就是 1∼n1\sim n1∼n 与 nnn 互质的数的个数）。 由于这些数的乘积  mod n\bmod nmodn 不一定为 111，所以要考虑

很明显这题要拆点，因为蜥蜴跳上去的个数是有限的。 超级源点直接向左边那一堆点连流量为 111 的边即可（只可能遍历一次）。 处理蜥蜴跳来跳去的情况只需要用拆出来的点向最开始没拆的点连流量为 ∞\infty∞ 的边就行（顺序要搞对）。 然后右边那一堆点如果能跳到图外，就向超级汇点连流量为 ∞\infty∞ 的边（注意：这里是可以经过多次的，因为上面蜥蜴可以从一个点跳到另一个点）。 代码。

刚学网络流，记一篇题解。 题意 给你两堆卡片，分蓝的和红的，分别有 nnn 个和 mmm 个，然后每个卡片上都有一个数。一个人要拿很多张卡片，每次只能从两堆中各取一个，而且这两个卡片上的 gcd⁡>1\gcd>1gcd>1，问：最多能拿多少个。 思路1 这不就是个二分图板子吗，暴力建图然后跑EK不就可以过了吗？ 然后： 稍微想一下发现建图就 O(nm)O(nm)O(nm

赛时调了半天没调出来，赛后又调了半天还发帖询问后才过的。。。 题意 给定两个 010101 串 a,ba,ba,b，定义操作规则： 对于一个 010101 串，每次只能选择串中从 1∼i1\sim i1∼i 的数字进行翻转（000变111，111变000），而且这 iii 个数字 000 的个数与 111 的个数是相同的。 问你能否对 aaa 操作后变成 bbb。 思路 这题我是从后往前考虑的

这题一眼看上去是一道树形DP的题目，然后后面一想好像可以用二分图来做（虽然是教练提醒的），故产生了此份题解。 题目大意 给定一个无根树，每个节点可以“管制”一堆给定点，求选择最少的点数来覆盖这棵树。 Solution 这题的“覆盖”看起来有那么亿点点像最小点覆盖，所以可以想想如何用二分图来解。 如何建立二分图？ 注意到这是一棵树，则每层之间肯定不会有连接，而且没有跨越两层的边，所以我们可以把

Trie树 Trie树（字典树），是一种查询快速，省空间（相对而言）的一种数据结构。 引入 上百度搜东西，我们发现搜索“洛谷”会出现二十多页的结果。我们知道，百度是一个十分强大的搜索引擎，而且信息量巨大，但我们搜索东西总会非常快得搜索出结果，而且还十分准确。而他们就是运用了Trie实现的。 Trie思想 我们发现，“洛”、“洛谷”、“洛谷强”都有共同的前缀，这时候我们就将前缀“洛”存储成一