oi

最初觉得挺麻烦的一道题没思路。有点像并查集直接搞但是不好维护直径。 然后发现树上到任意一点的最远点一定是直径的两个端点之一。于是直接把直径是哪俩点记下来就好了。然后按点权从大到小往树里插。 然后莫名其妙地抢到了第二快。这么老的题也是蛮欣慰的。大概是读入优化2333 #include <bits/stdc++.h> using namespace std; void setRand() { FILE* pf = fopen(".rs", "r"); int hsv; if (pf) { fscanf(pf, "%d", &hsv); fclose(pf); } srand(hsv); printf("Seed = %d\n", hsv); pf = fopen(".rs", "w"); fprintf(pf, "%d", (hsv << 1) | (rand() & 1)); fclose(pf); } #define readArg(a,b) { if (argc > a) sscanf(args[a], "%d", &b); } void mklr(int m, char s) { int l, r; do l = rand() % m + 1, r = rand() % m + 1; while (l > r); printf("%d %d%c", l, r, s); }...

orz jason_yu提醒了我一句“最简单的优化”，才想起来。 如果d合法的话那么b/d-(a-1)/d>0。然后用整除优化到sqrt就可过。虽然比较慢。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main() { int t, a, b, c, d, s, e; scanf("%d", &t); while (t --) { scanf("%d%d%d%d", &a, &b, &c, &d); -- a; -- c; s = 1; e = min(b, d); for (int i = 1, j; i <= e; i = j + 1) { j = min(b / (b / i), d / (d / i)); if (a / i) j = min(j, a / (a / i)); if (c / i)...

树型贪心orz 写丑了。调了半个晚上，然后发现是起点最耗时的时候的情况搞错了，只用走n-1条路而不是n条。晕。 对于每个节点贪心按f[p]-2*sz[p]排序或者用原式也行。不过巨慢。 #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())); \ } struct edge { int t; edge *next; }; const int maxn = 500009; int n, v[maxn], t, f[maxn], sz[maxn], dfo[maxn], st[maxn]; edge *ep, *head[maxn]; inline void addEdge(int u, int v) { ep-> t = v;...

一血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;...

签到题。表示今天虽然废了一天但是还是坚持写了题的。 单调栈搞定。 因为打球把小指头打残了所以不想敲include所以写了pascal，然后发现include不用小指。 const maxn = 100009; var n, i, t: longint; a, st, ans: array[0 .. maxn] of longint; begin readln(n); for i := 1 to n do readln(a[i]); t := 0; for i := n downto 1 do begin while (t > 0) and (a[i] >= a[st[t]]) do dec(t); if t = 0 then ans[i] := 0 else ans[i] := st[t]; inc(t); st[t] := i; end; for i := 1 to n do...

英语阅读题。做完去翻译题面然后写英语作业了。 就维护一下区间里的距离和and忽略一个点的收益的最大值。完了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct seg { int l, r; int s, v; seg *ls, *rs; }; const int maxn = 100009; int n, m, x[maxn], y[maxn], d[maxn], v[maxn]; seg *rt, *sp; inline void upDis(int i) { if (i < n) d[i] = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]); else d[i] = 0; } inline void upVal(int i) { if (i > 1 && i < n) v[i] = d[i - 1] + d[i] - abs(x[i + 1] - x[i - 1]) - abs(y[i + 1] - y[i - 1]);...

新题么。略水。 就一个序列，如果起点单增的话只要终点单增就不会冲突。 然后最少单增子序列覆盖=最长不降子序。 #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;...