杂题选讲

目录区间dp入门选讲合并果子括号匹配PalindromeAgainPalindromeStringpainter搬寝室配对区间dp入门选讲合并果子传送门设\(f_{i,j}\)表示合并区间\([i,j]\)的最小代价，\(\begin{aligned}s_i=\sum^{i}_{k=1}a_k\end{aligned}\)，显然有\(\begin{aligned}f_{i,j}=\min(f_{......

计数P6672[清华集训2016]你的生命已如风中残烛题意给你一个长度为\(m\)的序列\(W\)，其中\(n\)个\(w_i\geq1\)，\(\Sigmaw_i[w_i\geq1]=m\)，拿到一个\(w_i\)可以往后拿\(w_i\)个数，求在\(m!\)中有多少种排列可以拿到第\(m+1\)的数。简化我们将每个数减一，原......

CF1548EGregorandtheTwoPainters计数。一个很棒的思想找代表元。一个联通块由多个格子组成不好计数，因此我们给每个连通块找一个代表元，就找\((a_i+b_j,i,j)\)的最小的吧。我们考虑一个格子\((x,y)\)何时成为代表元：\(a_x+b_y\leqk\)。\(a_x\)是\([la,ra]\)中最......

CF11DASimpleTask题意给定一个\(n\)个点\(m\)条边的简单无向图，询问里面有多少个简单环。\(n\leq19\)解法对于每一个环，用唯一确定的方法去标记他。（寻找另一种更容易统计的对象，让这种对象可以唯一对应一个环）我们可以找到这个环里面编号最小的点，分别从这个点的左侧和......

【S-C1】是啥意思？？01.CF1858E2Rollbacks(HardVersion)维护一个初始为空的序列\(a\)，支持以下操作：\(\texttt{+}x\)：在序列末端插入\(x\)；\(\texttt{-}k\)：在序列末端删除\(k\)个数（\(k\)不超过当前序列长度）；\(\texttt{?}\)：查询序列中不同的数字个数；\(\texttt{!}\)：撤回前......

\(CF1839E\)DecreasingGame考虑两个数的情况。显然，若两数不等，先手胜；否则，后手胜。不妨直接猜结论:如果能找出一个集合，使得集合中元素的和恰为总和的一半，则后手胜；否则先手胜。充分性很显然，每次先手选择一个数，后手只要在另一个集合中也选一个数即可。这样两个集合减少的值......

BronzeT1CowCollege暴力扫一遍，更新最大值。提交记录：Submission-LuoguT2FeedingtheCows贪心放，维护一个能分别被\(\texttt{G}\)和\(\texttt{H}\)覆盖到的最远位置，如果当前位置\(i\)覆盖不到就在\(i+k\)放一个新的。由于\(i\)各不相同，这样放置除了可能在\(n\)......

CF1855BLongestDivisorsInterval对于任意一个区间\(\left[l,r\right]\)，一定有\(\foralli\in\left[1,r-l+1\right]\)，都\(\existsj\in\left[l,r\right]\)，使得\(i\midj\)。因为模\(i\)意义下的正整数每\(i\)个一循环，由于\(i\)小于区间长度，所以在这个......

UOJ21缩进优化题目链接记\(M=\max(a_i)\)从反面考虑，考虑\(x\)让答案减小的量。即为$\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor\times(x-1)=(x-1)\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor$。只需要快速计算$S=\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor$。可以......

大概会把博客当草稿纸用（当然写出正解还是会把正解贴出来。[ARC080E]YoungMaids（待补代码）给定正偶数\(N\)。给定\(N\)元排列\(p=(p_1,p_2,...,p_N)\).Snuke打算根据下述步骤构造一个\(N\)元排列\(q\)。首先，令\(q\)为空。接下来，执行下述操作直到\(p\)为空......