dp

<div class="post_brief"><p> 什么鬼。</p>   很好想的dp。f[i][j]表示深度不超过i且大小为j的二叉树的个数。转移是f[i][j] = ∑(f[i - 1][k] * f[i - 1][j - k - 1])。   然后直接暴力是O(n3)的。在spoj上能过在bzoj上不能过。在bzoj上得用记忆化搜索来减掉一些无用的东西。虽然我觉得很烦。   然后试图用fft，发现fft比暴力还慢。然后试图用fnt，然后发现fnt好像不能对1e9+7这种质数用。因为1e9+6只有来一个2。真悲伤。我还是太弱啊。   #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 609; const int mod = 1000000007; #define _l (long long int) int f[maxn][maxn]; int getf(int i, int j) { if (i == 0) return j <= 1; else if (j == 0) return 1; else if (f[i][j] == -1) { f[i][j] = 0; for (int k = 0; k < j; ++ k) f[i][j] = (f[i][j] + _l getf(i - 1, k) * getf(i - 1, j - k - 1)) % mod; } return f[i][j]; }...

<div class="post_brief"><p> 立杰出的题，orz。</p>   一个时间比较微妙的状压DP。用一个二进制状态表示0~k中哪些数已经可以被表示出来了，然后大于k的数直接乘，因为对状态不产生影响。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define pow2(x) (1<<(x)) #define _l (long long int) const int maxn = 21; const int maxb = pow2(maxn) + 9; const int mod = 1e9 + 7; int n, k, l, f[2][maxb], zu, va; #define incm(a,b) { a += b; if (a >= mod) a %= mod; } int sov() { int prv(0), cur(1); memset(f, 0, sizeof(f)); va = max(0, l - k) + 1; zu = pow2(k + 1) - 1; f[cur][1] = 1; for (int ti = 0; ti < n; ++ ti) { swap(cur, prv); for (int i = zu; i; – i) f[cur][i] = 0; for (int i = zu; i; – i) if (f[prv][i]) { for (int j = 1; j <= k; ++ j) { int zn((i | (i << j)) & zu); incm(f[cur][zn], f[prv][i]); } incm(f[cur][i], _l f[prv][i] * va % mod); } } int ans(0); for (int i = zu, e = pow2(k); i >= e; – i) incm(ans, f[cur][i]); return ans; }...

<div class="post_brief"><p> 决心写一道usaco之外的题，于是就挑中了这道。</p>   为啥这编辑器有BUG，每次按回车要向下跳？   发现可以预处理DP。f_i表示第i个数被砍完需要最少多少刀。对于每一个i，设p_i是它的质因子里最大的一个在给定集合里的，那么它可以转移到(i+1,i+p_i)这个范围。然后f_i显然不减，所以用单调队列之类的玩意。   然后卡着时间限制过了。不知道前面那些秒跑的人是怎么搞的。   #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 10000009; const int maxm = 100009; int k[maxn], f[maxn], n, m, q, p[maxm], v[maxm]; void pre(int n) { sort(p, p + m); memset(k, 0, sizeof(k)); for (int i = 0; i < m; ++ i) if (!i || p[i] != p[i - 1]) for (int j = 0; j <= n; j += p[i]) k[j] = p[i];...

题号是3851，题目名称是2048。 比较厉害的DP。最初没有想到怎么表示状态。其实就是一个≤2048的自然数就可以表示状态了。 然后转移不能一个一个来，每个值要一起来， 然后拿组合数来算。然后就行了。 虽然hdu上还是过不到。好慢的说。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int maxn = 100009; const int mod = 998244353; int n, f[2][2051], c[2051]; int fac[maxn], finv[maxn], p2[maxn]; int modPow(int a, int x) { int s(1); for (; x; x >>= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s;...

一血yeah yeah。 第一眼觉得是比较麻烦的单调队列。 然后发现转移的时候只会加1或者不加。 那么取的时候只用取队首，队里首先fi单不降然后hi单减。那么一定没有方案比取队首差。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; int _d_;  #define readInt(_x_) { \ int& _s_ = (_x_ = 0); \ while (!isdigit(_d_ = getchar())); \ while (_s_ = _s_ * 10 + _d_ - 48, isdigit(_d_ = getchar())); \ } const int maxn = 1000009; int n, m, a[maxn], f[maxn], q[maxn]; int getTrans(int l, int r) { int v0 = f[q[l]]; while (l < r) { int mid = (l + r + 1) >> 1;...

大概是今天不宜刷题来着。应该好好做作业。 用线段树套单调队列可以把复杂度降到O(nlogn)。然后deque严重不靠谱，得用list才行。 然后还是跑得巨慢。前面的人是排序搞定的么？表示不明觉厉。 #include <cstdio> #include <cctype> #include <cstring> #include <deque> #include <list> #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())); \ } //typedef deque <int> dque_i; typedef list <int> dque_i; struct seg { int l, r; dque_i u, d; seg *ls, *rs; }; const int maxn = 250009;...

老早之前就听说过的题。好像讲过不只一遍。不过才从bzoj上翻出来。 记得是神奇的dp优化。为啥这年头卡常数的题这么多。 首先肯定这玩意多项式可解。六维状态肯定能搞定。然后会mle+tle。 首先考虑从高到低放书，那么后面的如果不新开一行的话对高度没有影响。瞬间少了3维状态。 然后发现只要知道两维的总宽度和当前是第几位，就能知道第三维的宽度。于是一维2100缩70，开滚动可过。 当然还是需要一些常数优化的技艺。比如用宽度直接判断这一行有没有书。这样可以省下不少时间，而且好像只能这样才存得下。64MB太紧了点。另外把函数里的int改成const int&会变慢，不知为何。 居然花了这么久才搞出来。我太年轻了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct book { int w, h; }; inline bool cmpBook(const book& a, const book& b) { return a. h > b. h; } const int maxn = 71; const int maxw = 2109; const int inf = 0x3f3f3f3f; int n, f[2][maxw][maxw], sw; book a[maxn]; inline void upmin(int& _a_, int _b_) { if (_a_ > _b_) _a_ = _b_;...

乍一看矩阵水题，然后发现不能走回头路。 于是改一下把边当做点，把点当作转移，转移的时候就可以避免走过去就走回来的情况了。 说好的复习会考呢？ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define _l (long long int) const int mod = 45989; const int maxn = 123; class matrix { public: int n, a[maxn][maxn]; inline matrix() { } inline matrix(int n0, bool one = 0) { n = n0; memset(a, 0, sizeof(a)); if (one) for (int i = 0; i < n; ++ i) a[i][i] = 1; } void operator =(const matrix& x) { n = x....

好久没做过数据范围这么小的题了。 看来我是有点偏科了。 这么前面的题居然都不做。 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 {...

考场上只想到暴力。 如果只是一条链的话怎么乱搞一搞？ 如果没有深度限制的话简单的斜率优化+链剖就行了。 有深度限制就把hull扔到线段树里用可持久化栈来维护一下。DFS的时候塞进线段树里，然后完了再扔出来。总的复杂度O(n*log^2(n))， 代码也不怎么复杂。 #include <cstdio> #include <cctype> #include <memory.h> #include <vector> #include <algorithm> using namespace std; struct edge { int t; edge* next; }; typedef long long qw; typedef long double exf; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct oper { int p, v, t;...