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

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有一个组合数的东西貌似可以把这个数据范围翻倍但我不会。