https://ac.nowcoder.com/acm/contest/10662
J
题意：
给定 (n) 个点的一棵树。
构造 (a_1, a_2, ..., a_n)。
若 (a_i ~ ext{or}~ a_j = 2 ^ {60} - 1)，则 (i, j) 连边，反之不连边。
连出来的图满足树的形态。
思路：黑白染色
构造题的一些套路：
- 增量
- 倍增
- 随机
- 染色
- 特化
- 换思路
顺便又练了一两个构造题。
-
给定 (n, k)，构造 (n) 元排列，使 (|a_i - a_{i + 1}|) 有恰好 (k) 种取值
思路：特化，换思路 -
题意：lpy决定在实验课上抄dzc大佬的实验数据,已知dzc大佬的数据共有n个,其中最大值与最小值之差最多为2, lpy要魔改这n个数据满足数据的平均值和dzc的平均值一样,且最大值最小值分别不大于不小于dzc的最大值最小值。在此前提下魔改出两个人相同数据最少的方案。
思路：分析
K
题意：给定长度为 n 的序列 a[1..n]，Q次询问，每次给定 L, R, K，询问对所有 L <= S <= R，【a[i] xor S 的第 K 小值】 的最大值。
思路：Trie树的每一个结点预处理 S 的选法任意的情况下，第 1, ..., size 小的最大值。
对于数位题，只需要考虑没有限制的数位问题，然后再套上按数位枚举的爆搜。这个框架我得弄明白。
场上不会做就离谱，好烦啊。