以前觉得不会，仔细想想觉得还是挺水。 manacher找出所有中心回文串，然后用单调队列扫一下每个位置往左最长和往右最长就行。找位置比较烦不过还是比较好写的。 重点是写出了在windows下拿for循环对拍，虽然异常丑。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 200009; int n, l[maxn], q[maxn], vx[maxn], vy[maxn]; char a[maxn]; void manacher() { l[0] = 1; for (int i = 1, j = 0; i < (n << 1) - 1; ++ i) { int r = ((j + 1) >> 1) + l[j] - 1; int p = i >> 1, q = i - p; l[i] = (r >= q) ? min(r - q + 1, l[(j << 1) - i]) : 0;...
昨天就考完了不过今天还是讲了一天的课。 上午是罗翔宇的杂题。感觉好多题他上次都讲过不过就是记不得怎么做了。看来听课效率有待提高。 下午是讲icpc的题加各种神奇的玩意。感觉比较好玩，不过有点偏题啊。然后做表去了也没大听。 毕竟我还是太年轻对吧，七天就水过去了。还被学军的大爷们虐成狗了。
最初以为是splay维护Hash的简单题。顺手开心地敲了个splay还是指针版的。 然后发现tle了。 然后知道了可以暴力重新建串。 然后拿splay暴力重新建串。 然后又tle了。 然后不得已改成了随机线性存取表，过之。 我还是太naive了啊。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long qw; #define _l (long long int) const int maxn = 200009; const int base = 233; struct str { char a[maxn]; int len; inline str() { len = 0; } inline void read() { scanf("%s", a + 1); len = strlen(a + 1); } inline char operator [](const int& x) const {...
昨天是day3明天是day4所以今天是day3.5。 讲了一天课。 上午+晚上是图论。感觉图论的东西比较神。好像基本都是cf原题吧。好多东西要和其它的诸如数据结构和dp之类的东西结合，还有数学也比较重要。 下午是fft相关。先讲了一下fft的原理，虽然我觉得讲得除了好玩以外没什么特点，也没有用最好理解的方式来讲。然后期待的例题好像也不杂。然后怎么就扯到牛顿迭代上去了。不过这玩意以前没用过感觉还挺神奇的，改天找道题试试。 晚上无聊的时候写了个后缀数组，这种东西还是要不时写写不然都要忘了。然后后缀自动机的构建依然不太能理解。看来我还是太弱了WUW 然后明天是最后一天了。我虽然年轻，但是还是要努力一点的。
最初以为是水题，直接写个dq交上去不对。 看了下题解才知道是后缀数组。好久不写都快不会写了。 把原串倒过来扔一起排一下就行了。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int maxn = 60009; int n; int sa[maxn], rk[maxn], ro[maxn], w[maxn], o[maxn]; char a[maxn]; void sufixArray(int n) { memset(w, 0, sizeof(w)); for (int i = 0; i < n; ++ i) ++ w[(int)a[i]]; for (int i = 1; i < 123; ++ i) w[i] += w[i - 1]; for (int i = 0; i < n; ++ i) sa[-- w[(int)a[i]]] = i;...
既然明天考试是day2，那么今天就叫day1.5好了。 上午下午都在听讲。 上午讲构造。题都比较神奇。我觉得比较重要的是思想吧。以后看到这类题可以稍微有些套路，不过更多的还是要靠智商了。 下午讲字符串。后缀树和后缀自动机前几天就在看，虽然一直不太理解怎么构造出来的。讲得我也有点晕。还是要自己努力消化了。然后在bzoj上看到好多例题都有jiry的不久前的ac记录，orz。 晚上bc做了a和c之后就不想做了。b没想出来，d知道是分块+主席树，不过也懒得敲了。晚上大概吃得有点多。 所以我啊，还是太年轻了。
今天上课讲的题。 做法就直接枚举约数，或者说分解质因数。后者可以预处理到log。 判循环也比较开心。直接用一些奇奇怪怪的字符串的性质就好了。 看来字符串很博大精深啊。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long qw; typedef pair <int, qw> hstrv; #define _l (long long int) int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } const int maxn = 500009; const int base = 257; const int hmod = 1000000093;...
昨天晚上被那道usaco的题玩坏了于是没写日记。 来到了帝都。第二次去80ms了。好像没啥好写啊。 这回没下雪不过风吹上去还是挺冷。 晚上去家乐福吃汉堡，然后走回去。外面好冷。（这绝对不是伏笔） 想到明天要考试也是比较开心。和zhx聊了聊人生，然后写了道usaco发现把题看错了不会。然后就弃疗了。
好久没做过数据范围这么小的题了。 看来我是有点偏科了。 这么前面的题居然都不做。 dp就好。状态是前面男-女的最大值和最小值还有现在有多少男。然后滚动。 我毕竟太年轻。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 159; const int maxk = 49; const int kbase = 23; const int mod = 12345678; int n, m, c, f[2][maxn][maxk][maxk]; #define incm(_x_,_b_) { \ int& _a_ = _x_; \ _a_ += _b_; \ if (_a_ >= mod) \ _a_ %= mod; \ } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif scanf("%d%d%d", &n, &m, &c); if (c == 0) { puts("0"); } else {...
前两天还在YY动态DFS序呢，这就冒了一个出来。 动态DFS序的郁闷之处在于不好维护dfs序上的end。而把反括号建出来正好能解决这个问题。 然后就splay写得飞慢不知道怎么回事。 用两个栈就可以迭代做出括号序列，自己YY出来的给自己赞一个。 然后是目前最长的代码和倒数第二慢的时间。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_; #define readInt(_x_) { \ int &_s_ = _x_; \ while (!isdigit(_d_ = getchar())); \ _s_ = 0; \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } #define readOpt(_x_) { \ while (!isupper(_d_ = getchar())); \ _x_ = _d_; \ } typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif struct edge { int t;...