Views

成功被吊打. 花了五个小时去写第三题.然后证明是我太弱了. 第一题知道可以写.计划花2小时写第三题2小时写第一题的.晕啊ovo 第二题太神了ovo 第三题ovo正解用上了平面图的性质.然而我没有想到怎么正确地利用这个性质.于是只好去写lct+ett.其实是最后30分钟才想到ett的于是成功地没有写出来.郁闷ing 所以我太弱啦.

听说比一个月之前的策爷高ovo感觉今天什么奇怪的东西也没用啊. 第一题kd-tree居然是正解.我还以为会被卡ovo 第二题差不多想到了直线的交,但是没有想到三维空间去,于是觉得此题不可做然后只好最大团了.然后我的最大团又不是mhy那种优越的最大团ovo 第三题想了一会想出了正解感觉比较trick啊ovo 然后配cena的时候装了dev搞忘配到cena里了.幸好后来去看了一下,不然就身败名裂了ovo 所以我还是太弱.

n = int(raw_input()); gl = raw_input().split(’ ‘); a = []; a.append(0); s = 0; iz = 0; for i in range(0, n): a.append(int(gl[i]) - 1); s = s + a[i + 1]; if (a[i + 1] < 0): iz = 1; if (n == 1): if (a[1] == -1): print 1; else: print 0; elif (s != n - 2 or iz): print 0; else: fac = []; fac.append(1); for i in range(1, n + 1): fac....

网没救啦.然后发现看电影居然看得无聊了.于是去愉快地刷题了ovo 来复习一下一个叫prufer序列的东西.它是用来做生成树计数的.考虑一棵有标号的树,每次把叶子中编号最大的一个节点的唯一一条边的另一边扔进序列尾部,然后把它扯了,直到只剩俩点.然后发现这个序列对于一棵树是唯一的,且一个序列对应唯一的树.且这个序列的取值全都是1到n的数,无相互限制.这也是为啥完全图的生成树个数是nn-2. 然后这个题是给定度数嘛,于是就是对于每个点要求在prufer序列中出现次数一定.那也很好做的啦. 然后要注意的是有一堆无解的情况要先判断一下.然后听说写c++要小心暴long long.我强行python无压力啦ovo

#include #include #include #include using namespace std; struct doll { int w, v, e; inline void read() { scanf("%d%d%d", &w, &v, &e); } }; const int maxn = 1009; const int tv = 1000; int n, q, bsz, fa[maxn][maxn], fr[maxn][maxn], f[maxn][maxn]; doll d[maxn]; void sglDP(int* f, doll d) { int e(d. e); for (int i = 1; i <= e; i «= 1) { e -= i; for (int j = tv; j >= i * d....

似乎是去年省选集训的时候见过啊ovo还记得当年因为把背包写错了所以被唱歌了ovo 比较有意思的题.这个题询问数是骗人的ovo其实是预处理然后O(1)询问. 把如果强行预处理的话时间是O(n3)的.于是考虑一些奇怪的黑暗.把物品强行分块.对于每一个块,可以知道它左边的总答案,右边的总答案.这个是可以O(n2)的.(二进制背包的log就忽略了)然后把左边和右边合并一下,这个是平方的.然后对于块内的每个物品,把其它的物品拿来强行跑一遍背包,这个对于一个物品的复杂度是O(n1.5)的.于是就奇妙地少了O(n0.5)的复杂度.然后就可过了ovo 我当年是怎么想到的ovo还是我当年黑暗过去了ovo

后缀数组的基础题ovo好久没写sa了还自己yy了半天ovo 为啥感觉每次写sa写得都不一样ovo 求出height数组之后,如果一个位置的height大于上一个位置的,那么高出来的这一截都是新的一个答案.那么直接朴素地去找它出现了多少次就好了.我相信出题人没有办法构造数据把我卡到三方. 所以各种题都要再复习一下ovo

#include #include #include using namespace std; const int maxn = 3009; int n, a[maxn], sa[maxn], rk[maxn], hi[maxn], ho[maxn]; char g[maxn]; inline bool equStr(int a, int b, int l) { if (rk[a] > rk[b]) return 0; else if (a + l >= n && b + l >= n) return 1; else if (a + l >= n || b + l >= n) return 0; else return rk[a + l] == rk[b + l]; }...

#include #include #include #include using namespace std; const int buf_len = 4567; char buf[buf_len], *bufb(buf), *bufe(bufb + 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; } typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)...

继续填idy的坑ovo 这个题就是比sdoi那个题要麻烦一些.于是我决定把虚树建成真正的树来跑dp.然后这个树形dp似乎没啥麻烦的东西.就是给你一棵有关键点的树求所有点对的距离和,距离min和max. 常数又被吊打ovo无语喽.