杂题选讲

今天的题目没有那么难，挑一些不蛮板的题目来讲。建议不要光看，打个草稿画一下图，这个是解字符串题的关键。[POI2005]SZA-Template题目描述你打算在纸上印一串字母。为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。同一个位置的相同字符可以......

           ......

        ......

                       ......

arc124_e一种方案的权值为\(\prod\limits_{1\leqi\leqn}b_i\)，考虑其组合意义，就是每个人在自己最终的球中选一个。可以发现要么拿自己原来的球，要么拿上一个人传来的球。定义状态：\(f(i,0)\)为第\(i\)个人拿自己的球，考虑前\(i-1\)个人的答案。\(f(i,1)\)为第\(i\)个......

          ......

目录区间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\)解法对于每一个环，用唯一确定的方法去标记他。（寻找另一种更容易统计的对象，让这种对象可以唯一对应一个环）我们可以找到这个环里面编号最小的点，分别从这个点的左侧和......