白天讲课讲到的题。感觉比较有意思于是就去写了。然后这也是我超过于教授的题。感觉还是挺有意义的。 之前遇到过这个题。不过没有想出比较靠谱的方法。然后就用黑暗水过了。这回算是来对地方了。 做法比较简单。二分一个xo，看x=xo这条直线上有没有一部分被所有圆覆盖。如果有就ok。没有的话，如果有圆完全在它左或者它右，那么可以确定二分往哪边走或者无解。否则去随便找两个不相交的圆。如果它们在不同侧那就没有解了。在同一侧也可以确定方向。虽然我觉得没解这个地方需要再想想严格的证明。 不过反正填了2个点分之后终于写了道有意思的题，开心ing。
#include #include #include using namespace std; struct edge { int t, v; edge *next; }; typedef pair <int, int> dpr; struct seg { dpr d; int l, r; seg *ls, *rs; }; struct ptrec { dpr d; int l, r, du; seg *rt; }; inline bool operator <(const ptrec& a, const ptrec& b) { return a. d. first < b. d. first; } const int maxn = 50009; const int maxl = 17; const int maxbuf = maxn * maxl;...
又是idy开的坑。感觉回去要被他吊打致残。 树分治。最开始想用二分，然后直接去每个分治点上查询。这样的总复杂度是O(n*log3n)的。不过感觉常数比较小而且绝对省代码，只用二分不用数据结构。然后发现要输出所有的边。这个算法要用容斥一样的东西来减，根本搞不定。 于是向mhy学习。使用类似noi那个超级钢琴的思路，每次把最大的一条路径找出来，然后找它的替代品。树分治后，对于每一个树上的团，算出它的dfs序。默认一个点与dfs序在它前面的区间中最深的连边。这样就可以保证不重，也比较好写。然后用堆来维护。堆中一个点需要记录的信息是这个点的答案，线段树的根，左右端点，这个点到分治团的根的距离。然后每次找出一个最大的之后把它的区间再折成两半扔回堆里就好啦。 比较神的做法。感觉我自己是想不出来的。要是考场上遇到还真会出事呢。郁闷ing。
没有五笔好烦。 无语的期望题。AC第一页最长。 首先用像借教室一样的做法去求每个位置被覆盖了多少次。然后一个下降的序列需要求导再积回来。然后发现要加回来，这个东西是不能积的。于是坑了我好久。 最后期望就是∑1-Pim。其中Pi表示第i个点被任意一个区间覆盖的概率。 水过去啦。
#include #include #include #include using namespace std; typedef long long dint; const int maxn = 1000009; int n, m, l, r; dint a[maxn], b[maxn], ss[maxn], sv[maxn], sa[maxn], sr[maxn], tot; double ans; int main() { #ifndef ONLINE_JUDGE freopen(“in.txt”, “r”, stdin); #endif scanf("%d%d%d%d", &n, &m, &l, &r); memset(sv, 0, sizeof(sv)); memset(sa, 0, sizeof(sa)); tot = 0; for (int i = 1; i + l - 1 <= n; ++ i) { int li(i + l - 1), ri(min(n, i + r - 1)); tot += ri - li + 1; sv[i] += ri - li + 1; sv[ri + 1] -= ri - li + 1; if (li < ri) { sa[li + 1] -= 1; sa[ri + 1] += 1; sr[ri + 1] += ri - li; } } a[0] = b[0] = 0; dint ad(0); for (int i = 1; i <= n; ++ i) { ad += sa[i]; a[i] = a[i - 1] + sv[i]; b[i] = b[i - 1] + ad + sr[i]; } for (int i = 1; i <= n; ++ i) a[i] += b[i]; ans = 0; for (int i = 1; i <= n; ++ i) ans += 1....
迷一样的欧拉序列的题。然后似乎只有岛君的题解能看啊233。 其实就是在欧拉序列上，两点u,v之间的距离=(dfb[u], dfe[v]]之间未匹配的括号数（左开右闭）。其中dfb表示左括号的位置，dfe表示右括号的位置。 然后就是写一个线段树去维护了。写得比较丑，把所有数对都记下来了。其实只用记和跟差就行了。然后要强制如果一端是空的那么这个点就不能作为端点。完了。 然后dfs这一步越写越短了，开心hhh。 于是代码巨长还巨丑还巨慢。
#include #include #include #include #include using namespace std; const int buf_len = 4567; char buf[buf_len], *bufb(buf), *bufe(buf + 1); #define readBuf() { if (++ bufb == bufe) bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); } #define readInt(x) { register int s(0); do { readBuf(); } while (!isdigit(*bufb)); do { s = s * 10 + *bufb - 48; readBuf(); } while (isdigit(*bufb)); x = s; } #define readOpt(x) { do { readBuf(); } while (*bufb !...
考试。然后是膜拜已久的vfk神牛牛牛牛亲自讲课。比较感动。 上午的题是原题大战。的确是。 第一题感觉bzoj上见过，虽然花了一中午也没有找到。然后写了60分。其实100分和60分也差得不多了。只不过想不到嘛。这种做法还是比较通用的。要记下来。 第二题感觉是个数学题啊。推出式子去优化。不过最后也没有能把∑里的n给拿出来。原来正解需要结合原问题去化简。这个嘛，orz烂的感觉。然后一堆式子最后还得用fft去求1~n的所有第二类斯特林数。要用取模的fft。这个东西以前都不会。可以学习一下。 第三题是bzoj上原题啊。虽然还是不会做。然后写的时候有地方没有想对，所以连10分都没有拿到。比较郁闷。正解是一个分很多种情况讨论的贪心。唯一的想法是vfk真的好神。 然后还讲了一道thu集训的文学。发现demi guo早就过了，而且还只有她一个人过了。感觉又orz了。然后过了一会机房的山东同学把她给hack掉了。这个就更orz了。这题讲了之后感觉还是可以一做的吖。 最近发生了一些事情吧。关于sctsc的。据说时间推前了，而且还加上了一段时间的集训。其实也没有什么好抱怨的，因为在这件事情上我没有话语权。hbw倒是显得比较烦躁，感觉好像就是不想退役一样。其实也要有自信吧。要相信付出总是会有回报的。这么年就这样过来了。从noip完开始每一场都是最后一场了。似乎我也没有过机会让它不是。总之觉得这么些年搞OI没有让我后悔过，就已经很好了吧。好多东西都已经预习过了。现在是时候去创造自己的辉煌了。 也看到消息说no4的某wc金牌同学被挖角去了ns。好像因为作风啥的no7的同学一直和ns就走得很远，总有一种淡淡的鄙视的感觉。就算人家去年四块金牌只能引起仇恨。然而我觉得还是应该良性竞争吧。至少不是一种互相敌视的感觉。人总是要有自己的选择的。祝该君在ns愉快。虽然我知道他看不到我些文字的。或者也许这个博客就不会再被人看到。不过无所谓吧。只是一个说说话的地方而已。 所以我还是太年轻了，赶紧去刷题吧。
来到长沙的第二天。昨天晚上感觉被子没有被晒干？ 今天早上先考一发试。开始的时候感觉这个读题复杂度略高啊。然后每个题都是一堆东西套起来，根本不会做。 于是第一题先放一放。于是第二题和第三题可以暴力。赶紧先拿。第三题本来以为要写最小圆覆盖，几何类的模板都打好了然后发现不用写，直接输出就能30。开心。 第二题过了一会发现hbw在swap，于是知道了那些矩阵是出题人的诡计。是可以交换的。于是直接朴素维护就行了。懒得写平衡树了，反正跑得挺快。 然后去写第一题。yy了一会发现可以简单地搞出每个图形。于是敲，改，过。然后发现没有办法找点。于是想了一会想到一个O(n3)的东西。不管了先扔上去。然后发现和起点没有关系，虽然也不会，于是把平方的朴素又扔上去了。然后一看，原来50%的数据是x,y≤1000而不是n,m≤1000。那玩ball啊。不管了交了。 下午看成绩，20+100+30。第一题好像拿得到分的人都不多。感觉还是挺值。虽然也只是一小步。然后后面的找点的做法比较神。等会去敲risk去。第二题被抽上去讲了hhhhhhh。第三题原来有个啥东西可以把期望降下来。然后那个矩阵还有特别的规律，行列式推起来很简单，直接乘还会乘着乘着就变成0。晕。 然后讲的题感觉虽然少但是都很有营养。然后刚过了一道虽然被网络把题解给吞掉了。不知道有没有保存表单这种功能。 据说同学们在南充很厉害orz。毕竟我还是太弱，
#include #include #include using namespace std; #define _l (long long int) struct node { int l; node *pr, *t[3]; node() { l = 0; pr = 0; memset(t, 0, sizeof(t)); } }; const int maxn = 1100009; node nbuf_arr[maxn « 1], *nbuf(nbuf_arr), *srt, *scur; int n, m, f[maxn], ml[maxn]; char a[maxn]; void samIns(int w) { node *np(nbuf ++), *p; np-> l = scur-> l + 1; for (p = scur; p && !...