The Site of laekov

BZOJ3301 [USACO2011 Feb] Cow Line

新年第一题哈哈。虽然没有成功拿到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];...

BZOJ3823 定情信物

解锁成就：半夜过题。（其实是因为在搞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;...

BZOJ1367 [Baltic2004]sequence

退役了之后智商下降严重啊。今天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;...

BZOJ1171 大sz的游戏

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

BZOJ3821 玄学

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 == '-') \...

BZOJ2738 矩阵乘法

全局二分的经典题。最初试图用持久化线段树和分块，然后欢快地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;...

BZOJ1633 [Usaco2007 Feb]The Cow Lexicon 牛的词典

本来想做点英语作业的。想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;...

BZOJ1933 [Shoi2007]Bookcase 书柜的尺寸

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

20141222

不久之后要会考了，再过不久要期末了。教育部在放风，大概以后如果noi拿不到金牌的话就得和别人一样地高考了。一直在oi里面坚持也没有怎么想过高考的事，一直只是当作一个额外的好处。如果让我不上大学给我一次ioi的机会，我想我也不会犹豫的。本来，上什么大学，也不是什么重要的事情。作为oier，我知道，只向上看，是个很好的品质，但是不是什么好的策略。如果你非要落魄到拿着期末成绩去让大学收你，那你该考虑换个差点的大学了。因为做过鸡头，所以对做凤尾产生了抵触吧。当然，显然，学校，老师都不这么想。虽然我来这里的目的也完全不是因为高考，但是既然穿上这身校服，你也没有办法。背起包走回教室的感觉真的很像退役了。大本的崭新的练习册让人很压抑。如何在两周内补完一个学期的内容是一个很艰巨的问题。也许多看书多刷题是个不错的选择。既然有人要来挑战，那就让他们看看。

BZOJ3809 Gty的二逼妹子序列

好一道卡常数。不仅卡时间，还卡空间。堪称丧心病狂的极致。首先因为空间小所以得用莫队。然后不知为何树状数组没有直接分块跑得快。没有救啦。 #include <cstdio> #include <cctype> #include <cmath> #include <cstring> #include <algorithm> usingnamespacestd; structqry { intl, r, a, b, n; }; int_d_; #define readInt(_x_) { \ int& _s_ = _x_; \ while(!isdigit(_d_ = getchar())); \ _s_ = 0; \ while((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \ } constintmaxn = 100009; constintmaxm = 1000009; intn, m, bsz, a[maxn], c[maxn], w[maxn], b[maxn], ans[maxm];...