机房杂题
机房杂题
奇怪通信题
通信题1 [线性基] [随机化] [构造]
A程序输入 $x\le 10^18$ 和最多40个位置, 要求编码长为150的01串给B, 其中给定的位置必须为0, B从这长150的串里恢复信息.
法1: 每3个分一块, 若一块内有两个位置必须为0则全填0, 否则按照如下方式编码:
1 | 块编码 -> 实际信息 |
构造满足不管是哪个位置挂了, 都可以用一种编码表示它, 最坏情况下我们也能有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)$, 然后直接枚举倍数即可.
Project Eular 427
容易想到数长度不超过 $k$ 的, 即把序列划分成 $i$ 段极长相同颜色段, 每段长不超过 $k$ 的方案数, 一段的GF是 $G(x)=\dfrac{x-x^{k+1}}{1-x}$, 则这个方案数是 $[x^n] \dfrac{n}{n-1}\dfrac{1}{1-(n-1)G(x)}=[x^n] \dfrac{n}{n-1}\dfrac{1-x}{1-nx+(n-1)x^{k+1}}$.
暴力拆分母:
$$
[x^n]\dfrac{1}{1-nx+(n-1)x^{k+1}}\
=[x^n]\sum_j (n-1)^jx^{j(k+1)}(1-nx)^{-1-j}(-1)^j\
=\sum_j (n-1)^jn^{n-j(k+1)}(-1)^j\binom{-1-j}{n-j(k+1)}
$$
注意到暴力枚举 $j$ 是调和级数 $n\ln n$, 做完了.