UOJ748

UOJ751

找出所有二进制有 log2n2\frac{\log_2 n}{2}(因为要求是偶数,所以取 142\frac{14}{2},202{\frac{20}{2}}) 个 1 的数,把每条边依次用这些数分配一个编号,数量一定是够的。

Read more »

一个给 B 层的模拟赛,感觉题选的不错(?

只改了题面、写了题解和删掉题目来源

Read more »

E 类,(100) + (100+15+0) + (100+8+0) = 323,Ag

感觉这届 NOI 各方面体验特别好。

Read more »

引理:有两个线性基 A,BA,B , 设 BB 中能被 AA 表示的集合为 WW,且 (BW)A(B\setminus W)\cup A 线性无关,则 WWA,BA,B 所表示张成的空间的交的一组基。

Read more »

模拟赛 T1 ddtt

http://47.92.197.167:5283/contest/258/problem/1

一个点集为原图,边集极小的强连通图一定可以从一个只包含一个点的强连通分量,每次加一条两端在当前强连通分量里,而中间不在的链或环扩展而成(容易发现这样加入后仍然是强连通分量)。

Read more »

草莓蛋糕

赛时写了两个 log 的线段树分治+平衡树上二分的做法,没有前途(毕竟线段树分治就一个 log 了,O(1) 计算不太可能)。

Read more »

CF1369F

发现当所有点权值小于度数时一定无解,考虑最后一条删的边,当删除它时它的两个端点权值一定都是 0。

于是找到一个权值大于等于度数的点,发现即使所有连到它的边都依靠它来删,也是一定合法的,于是把它的所有连接它的边删掉,因为这个点已经发挥了最大可能的贡献,所以如果原图有解,删后的图也一定有解。

Read more »

2022.7.15 模拟赛 T1

http://47.92.197.167:5283/contest/241/problem/1

考虑在序列上怎么做,对于每一个数 x 设 viv_i 表示 i 是否在 x 左面出现,存在一组解的条件显然就是存在一个 a 使得 vxavx+av_{x-a} \neq v_{x+a},这个不太好处理,于是考虑没有界的条件,就是不存在一个 a 满足上述条件,也就是原串以 x 为中心回文,而回文串可以用正反哈希相等来判断,于是可以线段树维护 vv 的区间哈希值。

Read more »

模拟赛 T2

http://47.92.197.167:5283/contest/240/problem/2

首先求出一棵 dfs 树,把要割的变分成树边和非树边两类,存在一个结论:

如果存在一个割掉的边的子集,使所有没被割掉的非树边都覆盖了偶数条在这个集合内的树边,那么这种割边方案可以使原图不连通。

Read more »
0%