SDSC2021

有很多东西还没有写。。。

Day1

测试

\(T1\)

给一个 \(m\) 次的多项式 \(f(x)\) ,令

\(\begin{cases}a_0=a\\a_n=a_{n-1}+f(n)\times a_{\left\lfloor\frac{n+b}{c}\right\rfloor}\end{cases}\)

求 \(a_n\) 对 \(1004535809\) 取模

\(n\le 10^{18},m\le 20\)

PS:zyb不让用lld!!!

\(T2\)

题意:给一张图,每个点的权值 \(w\in\{1,2,3\}\) ,然后对于所有为 \(1\) 的点,选一些特殊点,使得去掉所有 \(2\) 点或者去掉所有 \(3\) 点之后,任何一个 \(1\) 点所在的连通块内都至少有一个特殊点,最小化特殊点的数量,输出方案,对于 \(2,3\) 求同样的东西。 \(n\le10^5,m\le 2\times 10^5\)

\(sol\) :把所有 \(2\) 点删掉会形成若干连通块记作 \(p_1,p_2,p_3...p_k\) ,把所有 \(3\) 点删掉后形成的若干连通块 \(q_1,q_2,q_3...q_l\) ,然后考虑建一个二分图,然后左边是 \(k\) 个点,右边是 \(l\) 个点,两个点之间连边当且仅当有点同时在这两个连通块里,然后问题就变成了最小边覆盖,总点数-最大匹配,构造方案的话,就是先把最大匹配的边都搞了,然后剩下每个点随便找条边就好了/kk

PS:俺考场上yy了一个贪心,然后发现大样例过不去,于是让它按随机顺序遍历每个点,多跑几遍获得了70pts

\(T3\)

题意:交互题,每次询问两个点之间的距离,次数不超过 \(m\) 次,让你构造这棵树。 \(n\le 10^5,m\le 5\times 10^6\)

PS:tyy二轮给过一个 \(n^2\) 的题,然后我就硬搞过来了,然后zyb不讲武德和暴力一个分,但还有点良心给了45

讲课

主要讲题答,讲了模拟退火,原理是最优解附近通常也很优,为了避免陷入局部最优解,需要一定概率跑出去。然后控制一个温度,温度越高就越可以跳出去,过程中不断降温。

然后讲了各种模拟退火和各种造计算机题,没得写。。。

交互

\(T1\) :两个 \(int\) 范围内的数 \(x,y\) ,每次询问可以给两个数 \(z,w\) ,然后会告诉你 \(x\oplus z\) 与 \(y\oplus w\) 的大小,确定 \(x,y\) 。询问次数 \(65\) 。

\(sol\) :首先都异或 \(0\) 确定两个数哪个大,不妨设 \(x<y\) ,那么从第一位开始考虑,先对 \(x\) 第一位取反,再对 \(y\) 第一位取反。两次的结果代表的数字和把这一位都清零之后剩下的数的大小如下。

\(<,<:0,1,x<y\)

\(<,>:1,1,x<y\)

\(>,<:0,0,x<y\)

\(>,>,0,1,x>y\)

\(T2\) :二分,询问次数卡的非常紧,如果你最后要多问一次那你就无了。

\(sol\) :不会,好像是从下往上构建决策树然后随机区间什么的我不会。

\(T3\) :你有 \(n\) 台机器,有好的和坏的,然后好的一定比坏的多,好机器说话一定是真的,坏机器说话不能判断真假,然后你最多 \(2n\) 次问机器 \(i\) ,问他机器 \(j\) 是好的还是坏的。最后判断所有机器的好坏。

\(sol\) :做一个栈,栈里面元素的类型都一样。然后如果栈目前是空就把这台机器扔进去,否则让它和栈顶互问,如果都说对方是好的,那么这两要么都好或者都坏,直接丢进栈就好,否则一定一个好一个坏,那么两个都扔掉,因为好的比坏的多,所以最后栈里面剩下的一定是好机器。然后你过程中那个并查集啥的维护一下什么就好了。

关于这个题zyb提了另外一个题,这个题据zyb研究可以出成交互,一堆数,众数出现次数大于 \(\dfrac{n}{2}\) ,要求你空间 \(\Theta(1)\) 求出众数。类似于这题,两个变量,一个记录目前的众数,另一个记录出现次数,如果目前出现次数为零就把这个数当众数,否则如果这个数和众数一样那么出现次数加一,出现次数减一,因为众数出现次数大于 \(\dfrac{n}{2}\) ,那么最后一定是众数留下。

\(T4\) :竞赛图,每次可以询问一个点与另一个点之间边的方向,然后求这个图中的一条长度为 \(n\) 的链。 \(n\le 10^3,m\le 10^4\)

\(sol\) :考虑增量,如果 \(n\) 指向链头那么做完了,如果链尾指向 \(n\) 那么做完了,否则中间一定有个位置 \(x\) 使得 \(x\rightarrow n,n\rightarrow x+1\) ,这个可以二分,以前紫书上做到过,虽然它没有什么单调性。。。考虑最后一定是一堆指着 \(n\) 的,所以有解是肯定的。那么你二分一个位置,如果它也指着你后面也指着你,那么它肯定在一堆指着你的区间里面,那么前面到这里肯定有个位置复合,如果在一堆被指着的区间里面,那么后面肯定有个位置符合。

\(T5\) :一棵二叉查找树的权值是点的编号,然后你 \(2n\) 次询问一个点是否是另一个点的祖先,让你确定这棵二叉查找树

\(sol\) :模拟建一棵笛卡尔树即可。

通信

\(T1\) :给一棵 \(n\le 70\) 个点的树,然后程序 \(A\) 要输出一个 \(128\) 位的 \(01\) 串,\(B\) 要根据这个串把树复原出来。

\(sol\) :因为一棵树 \(dfs\) 的时候,进入加一个左括号,出来加一个右括号,除了根以外都这样做,那么形成的 \(2n-2\) 的括号序列是唯一的,然后卡特兰数 \(C(69)\) 恰好比 \(2^{128}\) 小点,然后你只需要求字典序第 \(k\) 大的括号序列,\(oiwiki\) 上有,这个过程可逆。

\(T2\) :给一个 \(10^{18}\) 以内的非负整数,然后你输出一棵不超过 \(100\) 个结点的树,然后根据这棵树复原这个非负整数。

\(sol\) :考虑一条链上挂不超过 \(2\) 个点总共有 \(4\) 种情况,那么你每种情况代表一个树,然后就是 \(4^{30}\) 左右的数都可以表示,多用几个点可以表示更大的,tyy有一个组合数的东西貌似可以把这个数据范围翻倍但我不会。

上一篇:cdq分治


下一篇:POJ 2488