机房杂题

奇怪通信题

A程序输入 $x\le 10^18$ 和最多40个位置, 要求编码长为150的01串给B, 其中给定的位置必须为0, B从这长150的串里恢复信息.

法1: 每3个分一块, 若一块内有两个位置必须为0则全填0, 否则按照如下方式编码:

块编码  ->  实际信息
001     ->  1
010     ->  0
101     ->  00
100     ->  01
110     ->  10
111     ->  11

构造满足不管是哪个位置挂了, 都可以用一种编码表示它, 最坏情况下我们也能有40个坏了的和10个没坏的, 其中没坏的可以表示2位, 坏了的表示至少1位, 就能表示 $2^40*4^10=2^60$ , 正好表示 $10^18$

法2: 每2个分一块, 如果有一个位置挂了就全0, 否则可以编码3种信息, 那么能表示 $3^35$ 个信息, 发现 $3^38$ 才行, 发现这种最坏情况仅当每个数单独占一块, 这时可以两个程序选用同一个种子把位置随机打乱, 则极大概率就会有些0跑到同一块, 然后就能过了

法3: 使用科技, 随机150个数每个位置表示一个, 用线性基看是否满秩能表示出来, 编码就是直接把每一位当成这个数是否选, 最后异或起来.

A程序输入一棵有 $n\le 2. 5\times 10^5$ 个点的树, 要为每个位置定一个点权 $w\le 2^28$ , B程序有许多询问, 每次给两个你定的点权, 问两点关系(谁是祖先或并非祖先关系)

解法: 用dfs序判断关系, 那么就要存自身的dfs序号和子树大小, 这两个东西大小都是 $n$ 的存不下, 做法是通过加儿子把每个子树的大小都补成一个数 $a$ 的幂, 那么此时子树大小就只有 $\log_a{n}$ 种, 通过调节 $a$ 就能卡进去了.

给一个网格图, 每两个格子间有一条边, 求每个点能到达的点的个数和

因为是平面图, 如果扶着边走一圈其中包含的点就是所有能到达的点

然后再用一个dp, f[i][0/1]表示从i开始沿着哪一侧的墙走的结果, 转移是走一步

给 $m$ 个点, 点有权值 $w_i$ , 其有 $n$ 个点在凸包上, 求凸包上三点最大化它们形成的三角形内点的点权和.
$n\le 600, m\le 10^5$

$n^3$ 枚举, 预处理每两个点连线向外里面的点数(对每个点跑一遍极角排序即可).

求 $1\ldots n$ 内有多少个数可以被唯一的表示成 $c^2-a^2-b^2$ , 其中 $a, b, c\in Z^+, c-b=b-a, a<b<c$ .
$n\le 10^10$

todo

给定 $n\times n$ 矩阵 $A$ , 求不断求二维前缀和(膜2意义下的二维前缀和), 最少几次让 $A$ 变会自己.

$n\le 1000$

前缀和变成差分, 倒着找规律.

给定数列对每个数求左边第 $k$ 近的比他大的数

考虑倒着扫, 维护 $k$ 级单调栈, 一个数被弹了就进入下一级, 那么每个数在每一级被弹的时候, 正在插入的那个数就是它左边最近的比它大的数之一

求区间最大异或对. 值域 $10^9$. 数据随机.

考虑对于一个固定的数, 每个数异或这个数得到的数是均匀的, 所以前/后缀max只有 $\log n$ 个, 只要用可持久化字典树求出 $n\log n$ 个可能贡献的对然后数点即可.