机房杂题

奇怪通信题

通信题1 [线性基] [随机化] [构造]

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

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

1
2
3
4
5
6
7
块编码  ->  实际信息
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个数每个位置表示一个, 用线性基看是否满秩能表示出来, 编码就是直接把每一位当成这个数是否选, 最后异或起来.

通信题2 [构造] [思维]

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

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

神仙题1 [思维] [平面图]

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

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

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

POI某题

给 $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

奇怪数学题2

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

$n\le 1000$

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

VUQProblem

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

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

Problem?

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

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

蓝桥杯某题

给定 $l, r$, 求 $(i, j)$ 数量满足 $i^2+j^2\in [l, r]$ 且 $p\vert (i^2+j^2), p=2^3\times 3^3\times 53^2\times (10^6+3)$.

$l, r\le 10^{28}$

判定 $a$ 在模 $p$ 存在二次条件的要求是 $a^{\dfrac{p-1}{2}}\equiv 1$, 发现 $2^3, 3^3, (10^6+3)$ 都没有 $-1$ 的二次剩余, 则因为 $(\dfrac{i}{j})^2+1\equiv 0$ 只有 $i=j=0$ 一组解, 则枚举 $i$ 模 $53^2$ 的值, 放到哈希表可以求出所有 $\bmod p$ 意义下的 $(i, j)$, 然后直接枚举倍数即可.