新题么。略水。 就一个序列，如果起点单增的话只要终点单增就不会冲突。 然后最少单增子序列覆盖=最长不降子序。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define _l (long long int) const int maxn = 100009; int n, m, a[maxn], t[maxn], s; dint v[maxn], v0[maxn]; int btQry(int p) { int s = 0; for (; p; p -= (p & -p)) s = max(s, t[p]); return s; } void btChg(int p, int v) { for (; p <= n; p += (p & -p)) t[p] = max(t[p], v); }...

2015，嗯，还习惯性地敲2014。一年就过去了，好快。 2014年1月1号已经是一年前的事情了，略恐怖。 感觉不只过了一年啊。 这一年我都在干啥？ 寒假的时候去wc打个酱油，骗分的结果还不错。然后感觉讲课完全像在冬眠。好多课根本听不懂没法听。是我太弱吧。 开学之后就一直在教室和机房两边跑。对省队还怀有一丝幻想。直到，见到省选题。然后就以能拿的分没拿到不能拿的分也没拿到的分再见了。当时安慰自己太年轻，现在想来，也真是。 然后看到学长们填thu的自招表，也去跟着填了一个表。然后，当然肯定被毫无疑问地打了回来。令人触目惊心的是要填各次大考的成绩。半期缺考+垫底的我心中一惊啊。 然后期末的调研考试考得不好但是也比半期进步了不少。毕竟半期是停课裸考还没考完。 然后暑假很荣幸地去参观noi。结果自己再次犯傻把最简单第一题写错然后抱着AG哭。记得第一天估分的时候信心满满地报了个200+然后看到第一题60的时候。唉。 暑假回来感觉愉快不少，毕竟终于可以不上课了。 然后就全力准备noip，虽然常常刷题不小心就打开了bzoj。 然后就去了noip。然后再次犯傻的bird。于是没拿到省rank1。 然后半期经过三天“认真”复习之后真的垫底了。文化课看来是废了。 然后就又去学习thu集训的题了。然后跟着去了bj80ms。然后发现在诸如jiry和dzy大神的眼里我也只是根草而已，连菜都算不上。 然后回来了，然后被告愉快的停课生涯结束了。然后愉快地直接在月考中勇夺rank1还是倒数的。 老师问一年里收获是啥？学会了放弃吧。有多少付出才会有多少回报。然后当你面对你付出后血淋淋的伤口的时候，你会是怎样一种心情？也不见得能用愉快来形容吧。 管他去死。 既然都这样了，也只能继续了。人在矮桅下，不得不低头。等哪天离开矮檐了，再考虑去把让我低头的人的头给砍下来当夜壶。然后再深情地表达尊敬，还能写出一篇不错的议论文。 虽然也不是没有道理。有些事情总是要面对的。 不要忘了本，然后该干啥干啥吧。

新年第一题哈哈。虽然没有成功拿到fb。 所谓阶乘进制数么。略水。只不过加一减一啥的得小心些。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long dint; #define pow2(x) (1<<(x)) #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif const int maxn = 21; dint fac[maxn]; int n, k, t, x[maxn]; dint a; void sovPerm() { t = 0; for (int i = n; i; -- i) { int r = (a - 1) / fac[i - 1] + 1, c = 0; a -= (r - 1) * fac[i - 1];...

解锁成就：半夜过题。（其实是因为在搞bsd） 仔细看下题推一下发现第n维中m维元素的个数为2^(n-m)*C(n,m)。 然后组合数好像得nlogn用逆元？恭喜tle。 然后yy了一个用线性筛的办法，只是素数用快速幂，这样大约可以降低复杂度，然后就能过了。好神奇。 代码好长TT。 #include <cstdio> #include <cstring> #define _l (long long int) const int maxn = 10000009; int tp, pn[maxn], inv[maxn]; bool pr[maxn]; int n, mod, s, c, p; 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;...

退役了之后智商下降严重啊。今天bc死惨了。这比较水的题也是去看了题解才反应过来的。 先把序列改成不降。 然后把原来的序列分成一些段，每段的中位数递增。   考虑新加入一个ai，如果它比前一段的中位数小，那么就把它和前一段合并，再拿合并之后的段去和再前一段比较一下。其实我也不能证明为啥是这样，只是感觉比较有道理。我肯定是没救了。 中位数的话用可合并的堆来维护比较方便。orz各种神级堆，然后我还是用的左偏树。 以后树要拿指针写所以代码巨长。 #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 sof(p) ((p)?(p->s):0) struct node { int v, s; node *ls, *rs; inline void init(int x) { v = x; s = 1; ls = 0; rs = 0;...

大概是今天不宜刷题来着。应该好好做作业。 用线段树套单调队列可以把复杂度降到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;...

zhx+主席出的题，恐怖至极。 写此题需要极高的常数优化技巧+耐心。 本地跑到50s才在bzoj上压80s跑过。 其实思路就是拿线段树套AVL把询问的时间复杂度优化到O(logn)。 然后首先用treap会t爽+mle爽。 然后avl需要各种常数优化。 然后要在xxxxx地方优化。 加上zhx牌读入优化+块状内存+抄std的AVL+.....终于在81s过了。 orz比我快一倍的wangyisong神犇。 #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> #include <algorithm> using namespace std; const int BUF_SIZE = 300; char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1; #define PTR_NEXT() \ { \ buf_s ++; \ if (buf_s == buf_t) \ { \ buf_s = buf; \ buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \ } \ } #define readInt(_n_) \ { \ while (*buf_s != '-' && !isdigit(*buf_s)) \ PTR_NEXT(); \ bool register _nega_ = false; \ if (*buf_s == '-') \...

全局二分的经典题。 最初试图用持久化线段树和分块，然后欢快地tle+mle了。看到jason_yu和mhy过了，只能说自己的常数优化还不过关啊。 第一次写这种二分。就是把所有东西扔进来快速排序，顺便考虑每个询问应该被扔到哪边。然后加树状数组来统计就好了。 代码巨丑。 #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> using namespace std; struct query { int x1, y1, x2, y2, k, n; }; 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 = 509; const int maxq = 310009; int n, m, t, maxa, a[maxn][maxn], b[maxn][maxn], ttm;...

本来想做点英语作业的。想10分钟把这题搞定的。结果傻了去写trie树dp又傻了没有考虑终点也可以有子结点。 我真是无药可救了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int tcnt; struct trie_node { int d, e, t[26]; inline trie_node(int d0 = 0) { e = 0; d = d0 + 1; memset(t, 0, sizeof(t)); } inline int ins(char c) { if (!t[c - 97]) t[c - 97] = ++ tcnt; return t[c - 97]; } inline int trans(char c) { return t[c - 97]; } }; const int inf = 0x3f3f3f3f; const int maxs = 15009;...

老早之前就听说过的题。好像讲过不只一遍。不过才从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_;...