Views

idy又开坑辣.居然开的是虚树. 然后发现我好像还是不会ovo我太弱了ovo而且idy自带常数优化+代码长度优化根本打不过ovo 这个题算是相对比较容易的虚树吧.强行模拟一遍缩掉所有没有用的边之后的dfs就好了.中间要讨论一下几个点的祖先关系.yy起来还比较清晰. 然后似乎就没有啥要说的了ovo Upd:早上起来脑洞一开发现似乎不需要讨论当前的点已经在栈里的情况啊ovo

#include #include #include using namespace std; struct edge { int t, v; edge *next; }; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxn = 250009; const int maxl = 19; const int inf = 0x3f3f3f3f; const dint dinf = 0x3f3f3f3f3f3f3f3fll; int n, m; int d[maxn], dfb[maxn], dfe[maxn], dfo[maxn]; int ut[maxn][maxl], uv[maxn][maxl]; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn];...

gui vfk. 在hdsdfz听讲过的题. 可持久化seg tree优化建边.好像一句话就能说清楚啊. 然后证明了我的网络流的姿势严重不科学ovo 然后bzoj上样例居然是图片ovo于是附上手打的样例ovo 10 0 1 7 3 9 2 7 4 0 9 10 5 1 0 4 2 10 2 7 9 1 5 7 2 6 3 5 3 6 2 6 6 4 1 8 1 6 1 6 0 6 5 2 2 5 0 9 3 5 1 3 0 2 5 5 6 7 1 1 2

#include #include #include using namespace std; struct seg { int id; seg *ls, *rs; }; struct block { int b, w, p, l, r, a; int lid, rid, mid; inline void read() { scanf("%d%d%d%d%d%d", &a, &b, &w, &l, &r, &p); } }; struct edge { int t, c; edge *next, *rv; }; const int maxn = 5009; const int maxnd = 90009; const int maxe = 400009; const int inf = 0x3f3f3f3f;...

有点像xyz在wc的时候讲的动态图连通性问题.不过这个看上去要水些啊. 考虑建一棵生成树,那么所有剩余的边覆盖了的边就不是桥.如果没有被覆盖就是桥. 于是这个题可以倒过来,支持加边和查询两点间没有被覆盖的边数. 似乎挺水. 完了.

#include #include #include #include using namespace std; typedef pair <int, int> epr; typedef set erbt; struct seg { int s, z, l, r; seg *ls, *rs; }; struct edge { int t; edge *next; }; struct oper { int t, u, v, s; }; const int maxn = 30009; const int maxq = 40009; const int maxe = 100009; int n, m, q, r[maxn]; int fa[maxn], d[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn]; seg sbuf_arr[maxn « 2], *sbuf(sbuf_arr), *rt[maxn]; oper o[maxq]; erbt re; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn];...

被虐暴了.看来我还是太年轻. 去年的uestc校赛过了3道,今年过了4道ovo虽然很挫. a题水水的虽然还是写错了几次还因为数据出错坑了几次. b题随机水过去了. c题最开始想错了,然后就放弃了.其实还能做. d题0阶aha. e题鹰蛋么.不过看到期望题之后就不想再想了.知道是dp,不过最后没有推对. f题数据结构.最初都想到点分了,但是被队友坑了去想线段树,于是就再见了.其实点分+dfs序挺好写的.浪费了诶. g题好神. h题常数优化老久水过去了. i题算几.队友写到结束没有成功. j题后缀数组构造.其实都想到一半了.然后就没有再想下去了. 所以我还是太弱了啊怎么办啊.

#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; } const int maxn = 209; const int inf = 0x3f3f3f3f;...

下午写的东西被奇妙地吞掉了ovo 最小直径生成树,一定不要用sort,否则会tle. 首先考虑一个绝对中心的概念.既在生成树上它是所有直径的严格中心.它有可能在点上,也有可能在边上. 于是我们枚举边,试图让这个绝对中心在这条边上.那么每个点都选择到这条边的最短路树来生成.如果两个端点的最长链的差距不是很大,那么就有可能在这条边上找到最小直径生成树的绝对中心. 考虑绝对中心对一个端点的距离,会对每个点形成一个峰形的函数.要找的答案就在相邻两个峰之间.于是可以利用两边直线k相同,把b排序之后直接做.总复杂度O(n3). 然后如果每个边强行排序只会多个log,但是会tle.

这么早就开始写总结了ovo 其实已经玩了一个上午了.写完是9点的事. 感觉今天题比较顺手,于是就ak了一发ovo 第一题似乎是做过,虽然我不记得了.水水的最小割模型.差点就忘了处理0和9的情况.幸好最后检查的时候发现了. 第二题似乎是我当年想过的费用流建边优化啊,开心ing.于是就敲上去了.于是就过了.然后发现yjq居然写的是segtree优化dp.好强. 第三题思考了一下,发现转移可以变成旋转45度的最长上升子序yeah. 所以我还是太弱了.