Views

镇海题…考试的时候内心的绝望ovo 第一题只想到了朴素的做法.完全没想到网络流那边去.没想到启发了半天骗来80还是挺开心的.但是居然花了那么多时间在debug上比较郁闷. 第二题最初根本没有思路啊.最后1小时的时候突然发现,咦,基环内向树?那直接判断在不在一个连通块里就行了吧?整体二分+并查集?写写写.40分钟的时候,写完辣,咦过不到样例?maya哪是内向树是外向树.应该是判祖先关系啊.然后?整体二分+ett?去noi吧半小时肯定写不完.后来听说其实根本不用整体二分啊…所以可以搞成静态的啊…撞死ing…听上去也不难写嘛…更奇妙的是居然我那个错误的内向树写法交上去60… 剩下的时间都在想第三题了…然后发现一个式子似乎可以推一推构造答案?咦似乎能过?然后证明…我想的和标解根本不是一个东西…(咦今天为啥那么喜欢打\dots)转化成基环树(又是基环树wtf)的做法好神奇好开心. 于是因为奇怪的数据我就不小心拿了rank1整个人都是虚的ovo 下午讲题好快于是留了几乎2个小时来颓,然后只过了1个题好无语. 晚上更颓更无语ovoovo 毕竟我还是太年轻了.这个样子怎么考noi啊不开心TT

之前感觉是sg函数.不过不会.在wulala神犇的指点下找来题解看了一下.太神辣.自己肯定想不出来… 设以点u为根的子树的局面的sg值为sgu.设以u为根的子树中先手先hack掉v后的sg函数为gu,v. 那么gu,v = f[v] xor ∑ fu到v路径上所有点的非主干儿子. 然后fu = mex{gu,v} 这个转移得转移是O(n2)的样子吧. 然后发现某棵子树的g其实每次都是异或了一个相同的值.而且会合并. 咦可以用trie来优化一下.打下标记啥的.然后根据主席的论文这个东西是O(log n)的?虽然感觉复杂度证明没有说清楚啊ovoovo 然后就在trie树标记上卡了好久啊火冒三丈ing

#include #include #include using namespace std; struct edge { int t; edge *ne; }; struct node { int sz, rv; node *ch[2]; }; const int maxn = 100003; const int maxnd = maxn * 46; const int maxl = 19; int n, vo[maxn], f[maxn], sp[maxn], tsp; node nbuf_arr[maxnd], *nbuf(nbuf_arr), *rt[maxn]; edge ebuf_arr[maxn « 1], *ebuf(ebuf_arr), *head[maxn]; #define szof(p) (p?p->sz:0) inline void pushDown(node* q, int l) { if ((q-> rv » l) & 1) swap(q-> ch[0], q-> ch[1]); if (q-> ch[0]) q-> ch[0]-> rv ^= q-> rv; if (q-> ch[1]) q-> ch[1]-> rv ^= q-> rv; q-> rv = 0; }...

#include #include #include using namespace std; struct mov { int x, y, d; mov() { x = y = d = 0; } void rot(); }; const int maxl = 33; int le[maxl], t; mov a[maxl], b[maxl]; void mov :: rot() { int xo(x), yo(y); y = xo, x = -yo; d = (d + 1) & 3; } mov operator +(mov a, mov b) { mov r; for (int i = 0; i < a....

上课题.之前只有5个人过5个人交.我成功地拉低了这题的通过率yeah. 其实就是考虑Si序列走完之后对x和y的贡献以及对方向的改变就好了. 比较烦的是中间那一个东西是哪个方向.然后发现如果在上一层的左边就是1否则是0.和更上层没有关系不能直接异或往下传. 代码越写越丑了TAT

hn集训day1…感觉炎热的天气要把我的智商烧焦了…所有题都没想到啊ovovo 早上考试…第一题根本没想到高消那边去.于是直接欺负随机数据居然就过了ovovoovo 第二题嘛…昨天在飞机上还在思考vfk的论文来着.但是还没吃透所以就gg了.然后也没有想到变换之后可以直接找根. 第三题比较ovo想到的启发式合并的思路几乎是对的.然而sbt里插入的时候没有给当前点的size++导致了一场悲剧.撞死的心都有了…然后当时的我居然还傻傻地以为是做法的复杂度没算对于是就弃疗了ovovo 所以我还是太弱了然后跪ak爷mhy… 下午听讲似乎没啥事…中午看sdfz几个同学在研究4399的flash版cf.只想说黑得漂亮啊.然而空间站这图重力调回去之后就不好玩了啊… 然后下午讲题也就那样呗ovoovo感觉还比较能听… 晚上发现一个人在房间里会更颓啊ovovo 所以我还是太年轻了.

在家里的windows上用机械键盘的感觉真不一样呢。 于教授的题，教我做人orz。 第一题没有想到利用向量加减和相对速度。于是想了一些奇怪的自适应算法去骗分。然而效果不怎么理想。 第二题是ommy老师的题，于是比较开心地很快过掉了。其实一年前zhx就出过此题的弱化版ovovoo 第三题一直在想能不能转成线性的。最后居然是个玩矩阵的题啊太神了。想过高消自由元不过没想到会有那么神。看来我还是太弱了一点啊。 下午讨论的时候发现为啥sf那么多问题ovovovo 走的时候收拾了东西。把显示器还给学校。把机械键盘背回家。也许以后就没有机会回来了呢。唉。若干年的oi生涯走到了一个分水岭。Fight for dream or beg for survival? All on myself. 所以啊，我还是太弱了ovovoo 明天还要会考啊ovovov感觉啥都不会啊一股要跪的感觉。

原来是yali的题…我一看到fft就想到魏总… 第一题原来是那样做的…感觉我的做法没啥不好只是常数大了点,嘛. 第二题fft不过之前一直不知道它自带了多项式取模.毕竟我还是naive 第三题神题啊ovoovo 所以我还是太 弱了.

#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) const int maxl = 103; int bi[maxl], le; dint f[maxl], g[maxl][2]; dint digDP(dint n) { le = 0; for (; n; n »= 1, ++ le) bi[le] = n & 1; bi[le ++] = 0; memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); g[0][0] = g[0][1] = 1; for (int i = 1; i < le; ++ i) { g[i][0] = g[i - 1][0] + g[i - 1][1]; g[i][1] = g[i - 1][0]; } f[0] = 1; for (int i = 1; i < le; ++ i) if (bi[i] == 1) { if (bi[i - 1] == 1) f[i] = g[i - 1][0]; else f[i] = f[i - 1]; } else { if (bi[i - 1] == 1) f[i] = f[i - 1] + g[i - 1][0]; else f[i] = f[i - 1]; } return f[le - 1] - 1; }...

还不错的题ovoovo 发现其实要求x的二进制表示中没有相邻的1就行了. 第一问水水的数位dp.从未写得如此愉快. 第二问就是前面的g.然后发现是fib数列.矩阵快速幂搞定.