最初以为是水题，直接写个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;...

优化方法暑假的时候zhx讲过，我居然还记得好感动。 Mobius反演加些奇异的东西。（不会用公式编辑器是不是已经落伍了） 两个优化-> sqrt(n)^2 == n。 跑得飞慢 。而且中间那坨又长又丑。 久了不写都快忘了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #define _l (qw) const int maxn = 10000009; const int mod = 20101009; int pn[maxn], mu[maxn], smu[maxn], tp; bool pr[maxn]; void pre(int maxn) { memset(pr, 0, sizeof(pr)); tp = 0; mu[1] = 1; for (int i = 2; i <= maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; mu[i] = -1; } for (int j = 0; j < tp && i * pn[j] <= maxn; ++ j) {...

题意：求n!在b进制下的位数（n<=2^31）。 好像要高精！？好像会TLE！？根本不会做！ 然后想到answer=∑log(k,i) 然后积分？∫ln(x) dx = xln(x) - x 小数据直接跑，过之。试个极限数据，差了3！？ 仔细一想，对数函数是凹的，这样算答案当然会偏小。 百度了一下，发现有个公式：n!≈√(2*π*n)*(n/e)^n。 拆开之后发现就是比原来的积分多了个ln(2*π*n) #include <cstdio> #include <cmath> const double pi = asin(1) * 2.0; double calc(double n, double k) { double ans = 0; if (n < 100000) { for (int i = 1; i <= n; ++ i) ans += log(i); ans /= log(k); } else { ans = (0.5 * log(pi * n * 2) + log(n) * n - n) / log(k); } return ans + 0.5; }...

好像数学都退化了。 其实一直没有用过中国剩余定理。虽然好像也不是太麻烦，不过要记住。 然后这题也比较裸吧。把C(n,m)中的阶乘分解成t*p^k的样子就好了。ORZ JASON_YU #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #define _l (qw) const int mod = 999911659; const int pn[4] = {2, 3, 4679, 35617}; const int maxb = 50009; int n, g, fac[maxb], tf, s[4]; int t[maxb]; int modPow(int a, int x, int mod) { int s = 1; for (a %= mod; x; x >>= 1, a = _l a * a % mod)...

异常欢乐的并查集。馒头染色法。均摊O(n)的时间。 离线，先把每个染色操作会染黑哪些边算出来，把黑色子节点并到白色父节点里。 然后倒着处理，询问就直接用并查集问白色子节点顶上的黑色父节点最近是谁。染色操作再染回来。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct edge { int t, i; edge *next; }; struct query { int t, v, ans; int *b; }; int _d_; #define readInt(_x_) { \ int& _s_ = _x_; \ _s_ = 0; \ while (!isdigit(_d_ = getchar())); \ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } const int maxn = 1000009; int n, m, d[maxn], fa[maxn], v[maxn], c[maxn], r[maxn];...