我的SAM第一题。按照惯例几乎是照着std抄的OVO。本来以为是要在SAM上DP，后来发现好像是并列的，于是比较开心。 SAM这个东西主要就是用来匹配子串用的。建法详见clj的课件，然后现在我还处于消化状态中。 SAM匹配多个串的话也比较好弄，直接在串末再加一个字符集里没有的元素就好了。 现在假设已经用SAM匹配出了第i个位置往左ml[i]个位置都是可以匹配的，那么可以二分一个答案，然后用单调队列来DP判断。写法比较简单，虽然我急着去写SAM所以这部分也是蒙过去的。 然后网上的2个std就有2种不同的答案还和我不一样。最后还是wd学长的代码靠谱orz。 现在我可以说我是写过SAM的人了哈哈。
今天考得比较不开心啊。 第一题似乎做过？不敢再写O(nlognsqrt(n))了，想起上回被jcvb怒斥。线段树前几天写过也不难。 第二题似乎也见过？翻了一下原来的代码发现是tarjan然后拓补排序。于是没有想就敲了然后发现环的情况处理错了。晕啊。 第三题直接想到了KM。然后就去写了，然后发现各种bug。打了一堆补丁之后终于能过了，然后常数被卡成和朴素一个分。我还有啥可说的呢。 所以啊，我还是太年轻了。 然后sam继续跪。决定去写一道题。我看有点悬。
很早之前就看过的题。一直被数据范围吓到，然后感觉也比较难写所以都没写。后来发现还是挺好的。 就重链dfs序维护一下每个位置的和，然后可持久化一下就完了。然后一个常数优化是如果这个点是在这次修改的时候建的，那么就直接覆盖而不是新建点。然后跑得就比较快了。
#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) struct edge { int t; edge *next; }; struct seg { dint a, b, s; int t; seg *ls, *rs; }; #define sgt_root 1,n+1 #define midp ((pl+pr)»1) #define pls pl,midp #define prs midp,pr const int maxn = 100009; int n, m, p; int d[maxn], sz[maxn], fa[maxn], tc, fc[maxn], ch[maxn], fs[maxn]; int dfb[maxn], dfe[maxn], dfo[maxn], ci, ti; edge elst[maxn « 1], *ep(elst), *head[maxn]; seg *rt[0];...
其实前几天已经发现状态不好了吧。不过昨天听了hbw一席话所以还是rank1。今天就暴露了。 考试的时候感觉比较晕，也不想写代码。 第一题想到树形DP，想到链剖，想到几种似乎可以维护的方式。然后又都否掉了。最后听说正解就是我否掉的解法中的一种。 第二题想到了枚举环算树。不过对那个prufer序列并不熟悉，所以根本没有想到正确的东西。然后朴素打表还打错了。 第三题在学军见过啊。不过当时只会指数dp现在也只会指数dp。似乎是一个很神奇的容斥？no save。 所以我太弱了。 每年春天似乎都会遇到这样一段日子，感觉整个人都不太顺。是不是应该想些什么办法去抵抗？我不是一个服输的人啊。嗯。
上课讲的神题。构造公式。本来用HTML写了一堆公式的。然后天杀的网就断了要我重新开然后就没了。很想骂人。那就不写了呗，自行翻课件或者yy。
#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) #define mInc(a,b) { a += b; if (a >= mod) a -= mod; } const int maxn = 40009; dint n; int k, mod; struct matrix { static const int n = 2; int a[n][n]; matrix() {} void init() { memset(a, 0, sizeof(a)); } void setOne() { memset(a, 0, sizeof(a)); for (int i = 0; i < n; ++ i) a[i][i] = 1; } void operator =(const matrix& b) { memcpy(a, b....
#include #include #include 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 = 1009; const dint inf = 0x3f3f3f3f3f3f3f3fll; int n, m, ca[maxn], cb[maxn], ta, tb; dint f[maxn][maxn][5]; #define upMin(a,b) { if (a > b) a = b; } dint dp() { memset(f, 0x3f, sizeof(f)); if (ta) f[1][0][0] = ca[0] * n; if (tb) f[0][1][2] = cb[0] * n; for (int i = 0; i <= ta; ++ i) for (int j = 0; j <= tb; ++ j) if (n - i - j > 0) { int cc(n - i - j); if (f[i][j][0] < inf) { if (i < ta) upMin(f[i + 1][j][1], f[i][j][0] + ca[i] * cc); if (j < tb) upMin(f[i][j + 1][2], f[i][j][0] + cb[j] * cc); } if (f[i][j][1] < inf) { if (j < tb) upMin(f[i][j + 1][2], f[i][j][1] + cb[j] * cc); } if (f[i][j][2] < inf) { if (i < ta) upMin(f[i + 1][j][0], f[i][j][2] + ca[i] * cc); if (j < tb) upMin(f[i][j + 1][3], f[i][j][2] + cb[j] * cc); } if (f[i][j][3] < inf) { if (i < ta) upMin(f[i + 1][j][0], f[i][j][3] + ca[i] * cc); } } dint ans(inf); for (int i = 0; i <= n; ++ i) for (int j = 0; j < 4; ++ j) upMin(ans, f[i][n - i][j]); return ans; }...
比较基础的dp。不过因为权限的原因好像做的人不多。 首先肯定先泡便宜的茶再泡贵的茶。 然后记一下上一种茶是啥，连续泡了几次。 于是用f[i][j][k][l]表示泡了i个红茶，j个绿茶，上一种茶是k，连续泡了l次的最小花费。转移是O(1)的。然后后两个反正都要手拆开，所以干脆压下来了。 似乎很水的样子。
#include #include #include #include using namespace std; const int max_buf = 4567; char buf[max_buf], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!isdigit(*bufb)); do { s = s * 10 + *bufb - 48; readBuf(); } while (isdigit(*bufb)); x = s; } struct query { int t, x, y, v; };...