https://codeforces.com/contest/1849 C. Binary String Copying 题意 给出一个长度为 nnn 的 010101 串 sss 和 mmm 个相同的拷贝 t1,t2,⋯ ,tmt_1,t_2,\cdots,t_mt1​,t2​,⋯,tm​。有 mmm 个操作，第 iii 个操作 [li,ri][l_i,r_i][li​,ri​] 表示将 tit

https://codeforces.com/gym/104369 B. Base Station Construction 题意 现在需要在点 1,2,⋯ ,n1,2,\cdots,n1,2,⋯,n 上建设基站，在点 iii 建设基站的费用为 aia_iai​。有 mmm 个要求，每个要求为区间 [li,ri][l_i,r_i][li​,ri​] 内至少有一个基站。问最小费用是多少。 题解 如果

https://codeforces.com/gym/104417 B. Building Company 题意 有一家建筑公司，一开始你有 ggg 种员工。第 iii 种员工编号为 tit_iti​，有 uiu_iui​ 个。一共有 nnn 项任务，第 iii 项任务有 mim_imi​ 个指标，第 jjj 个指标需要编号为 ai,ja_{i,j}ai,j​ 的员工至少有 bi,jb_{i,j}

https://codeforces.com/gym/104385 D. Stack Out 题意 有 nnn 个数，每次可以将第一个数入栈，或者将栈顶元素出栈。求最大连续出栈次数不小于 kkk 的方案数。 题解 我们这样考虑，每当一个元素压入栈以后，紧跟着就是出栈操作（可能是 000 次），这样每次可能的出栈操作次数只与当前栈内的元素个数有关，由此可以设计状态进行dp。 设 fi,j,0/1f_

https://codeforces.com/contest/1853 E. Ina of the Mountain 题意 给出一个长度为 nnn 的数组 aaa，满足 1≤ai≤k1\leq a_i\leq k1≤ai​≤k。每次操作可以选定一个区间 [l,r][l,r][l,r]，让其中所有的数减 111。当一个数变成 000 后，它会立刻变成 kkk。求最少需要多少次操作，才能让所有的数都变

网络流简介 网络 网络是指一个有向图 G=(V,E)G=(V,E)G=(V,E) 。 每条边 (u,v)∈E(u,v)\in E(u,v)∈E 都有一个权值 c(u,v)c(u,v)c(u,v) ，称之为容量。当 (u,v)∉E(u,v)\notin E(u,v)∈/E 时有 c(u,v)=0c(u,v)=0c(u,v)=0 。 其中有两个特殊的点：源点 s∈Vs\in Vs∈V 和汇点 t∈V,

一些网络流的常见建模方法： 拆点：Luogu P1402 酒店之王、Luogu P2053 [SCOI2007] 修车、HDU7298 Coin 二分图最小点覆盖：UVA11419 SAM I AM 染色法：Luogu P2774 方格取数问题、Luogu P3355 骑士共存问题、Luogu P5030 长脖子鹿放置 划分问题：Luogu P4313 文理分科 平面图最小割转对偶图最短路：Lu

一些零碎的做题记录。 CF1635D Infinite Set 题意 给定一个数组 aaa。构造一个集合 SSS。它里面的元素 xxx 至少满足以下一条： xxx 在 aaa 中； x=2y+1x=2y+1x=2y+1 且 yyy 在 SSS 中； x=4yx=4yx=4y 且 yyy 在 SSS中。 给出 ppp，问 SSS 中小于 ppp 的元素有多少个，答案对 109+710^9+710

这里的题目相对会更难一些。 CF1856D More Wrong 题意 给定一个长度为 nnn 的排列。每次询问一个区间 [l,r][l,r][l,r]，代价为 (r−l)2(r-l)^2(r−l)2，返回该区间内逆序对的数量。要求找出区间内最大元素的下标，总代价不超过 5×n25\times n^25×n2。 数据范围：2≤n≤20002\leq n\leq 20002≤n≤2000。 题解 单

https://codeforces.com/gym/104354 B. Art for Rest 题意 给定一个序列 aaa。定义 aka_kak​ 为将 aaa 划分为 ⌈nk⌉\lceil\dfrac{n}{k}\rceil⌈kn​⌉ 段，每段升序排序后得到的序列。求有多少个 k∈[1,n]k\in [1,n]k∈[1,n] 满足 aka_kak​ 单调不降。 题解 容易想到对每个 kkk