我的SAM第一题。按照惯例几乎是照着std抄的OVO。本来以为是要在SAM上DP，后来发现好像是并列的，于是比较开心。 SAM这个东西主要就是用来匹配子串用的。建法详见clj的课件，然后现在我还处于消化状态中。 SAM匹配多个串的话也比较好弄，直接在串末再加一个字符集里没有的元素就好了。 现在假设已经用SAM匹配出了第i个位置往左ml[i]个位置都是可以匹配的，那么可以二分一个答案，然后用单调队列来DP判断。写法比较简单，虽然我急着去写SAM所以这部分也是蒙过去的。 然后网上的2个std就有2种不同的答案还和我不一样。最后还是wd学长的代码靠谱orz。 现在我可以说我是写过SAM的人了哈哈。
很早之前就看过的题。一直被数据范围吓到，然后感觉也比较难写所以都没写。后来发现还是挺好的。 就重链dfs序维护一下每个位置的和，然后可持久化一下就完了。然后一个常数优化是如果这个点是在这次修改的时候建的，那么就直接覆盖而不是新建点。然后跑得就比较快了。
上课讲的神题。构造公式。本来用HTML写了一堆公式的。然后天杀的网就断了要我重新开然后就没了。很想骂人。那就不写了呗，自行翻课件或者yy。
比较基础的dp。不过因为权限的原因好像做的人不多。 首先肯定先泡便宜的茶再泡贵的茶。 然后记一下上一种茶是啥，连续泡了几次。 于是用f[i][j][k][l]表示泡了i个红茶，j个绿茶，上一种茶是k，连续泡了l次的最小花费。转移是O(1)的。然后后两个反正都要手拆开，所以干脆压下来了。 似乎很水的样子。
水水的cdq。久了不写练一下手。然后发现犯了一堆逗错。幸好没过样例不然就do big die了。
多年之前讲过的最小割。 比较好想啦。 把每一位拆开。然后单独跑一遍最小割。各种连边。然后以答案为高位，数字和为低位跑就行了。 好像也没说清楚怎么建图啊。 对于原图中已经确定的点，如果它是1，就从源连过来，否则连向汇。对于每一个未知的点，把所有边建出来。然后再向汇连个1的边来表示它如果选1的话就要产生贡献。然后就差不多了吧。脑补一下。
原来备案还没过。那之前是怎么成功访问的囧。 写了一晚上。教训还是之前那个，写之前要想清楚。写完再去改就很烦。自己yy了很久，虽然最初是听了mhy的一句提醒。好有危机感。 首先这个东西可以离线。之前一直在想在线怎么做然后也觉得没法做。 把询问按右端点排序之后问题就转化成了左端点在一个范围里的时候的最大子段。 然后用一个线段树表示从i到current right的时候的和，这个玩意可以直接区间加。然后再去维护这个东西的历史最大值。于是就变成了每个位置上接了一个add序列，要找它的前缀最大值。那么只需要存两个东西：当前的和以及当前的最大前缀和，就可以合并了。 然后线段树上维护两个add序列，分别是对整个线段的lazy tag of add和max value of son。就可写了。 然后好像跑得很慢啊TT。
<div class="post_brief"><p> 题目名字好长。</p> 当年在考场上只会分块打表的题。 前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。 于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。 考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久） 然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。 然后还是没有原版跑得快。OTL。 #define PROC "shop" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 53; const int maxm = 509; const int mb = 253; dint l, r; int n, m, bs, a[maxn];...
<div class="post_brief"><p> 在一道usaco的题上wa了三次。我也是厉害。</p> 其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。 对于一个平面图上的点的曼哈顿最小生成树，一定存在一种方案，使得每个点的度数至多为8。也就是说以斜率为0,inf,1,-1的四条直线分出来的八个区域里各有一个点就行了。然后是可以保证的。 于是就是拿俩树状数组扫四遍就行了。 #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; struct point { int x, y, i; point() { x = -inf, y = -1; } point(int xo, int yo) { x = xo, y = yo; } inline void init(int ix) { scanf("%d%d", &x, &y); i = ix; } }; inline bool operator <(const point& a, const point& b) { return (a....
<div class="post_brief"><p> 插头dp的练手题么。虽然之前还没写过哈密顿回路的题。</p> 学习了一下广义括号法。发现状态数比之前记连通性的方法要少。仔细想想发现，两个连通的插头的顺序有关。不能存在1212这种东西。所以连通性的方法记了很多废状态。那把连通性方法改进一下会不会变得更快呢？可以研究一下。我觉得应该是等效了吧。 今天的debug时间明显缩短了。虽然还是debug了老半天。然后怎么代码还是那么长。想起我每次都觉得把东西挤到一起看起来很不雅观，于是去写一堆找转移的函数。晕。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 15; const int maxst = 50009; #define mbit(x,y) ((x)<<((y)<<1)) #define gbit(x,y) (((x)>>((y)<<1))&3) #define cbit(x,y) ((x)&(~(3<<((y)<<1)))) int n, m, tots, slst[maxst]; bool mp[maxn][maxn]; dint f[2][maxst]; void dfsState(int l, int c, int z) { if (l == m + 1) { if (!...