2020-team1-C001

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 8/12  dirt: 20%
rank: 22
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
在路上了
== 题解 ==
A: 任何一个数初始位置和结束位置不连通->No，否则找一棵dfs树从叶子往根一个点一个点调整
B: AC自动机+矩阵快速幂
C: 最小生成树
D: BSGS，预处理每次跳65536步后的结果（题面有锅，实际上0~2^32^-2互不相同）
E: 回文树上dp
F: 拆分数大约几千，爆搜或者dp（需要足够剪枝，辣鸡题目）
G: 来自朱老大的做法：随机10个排列，每次从10个里面随机选一个修改m个位置，如果返回的答案差别不足m个就忽略这次询问，否则可以确定某些数一定在某些位置。
这样下去使得每个数都被确定过O(1)（3~4?）次就可以确定唯一的位置，取m=sqrt(n)/2可以180次询问左右得到答案
H: 李超树
I: 暴力（OOP一下会好写很多）
J: 二维偏序算一下SG函数，因为偏序关系具有传递性所以mex=max+1，最后线性基+输出方案
K: 题目给定一个匹配，再构造一个(1,2),(3,4),...,(2n-1,2n)的匹配，两个匹配的并是二分图，二分图染色
L: 辣鸡计算几何 一个corner case是直线恰好是双曲线渐近线

[/wiki/2020-team1 返回]

概述

solved: 8/12 dirt: 20%

rank: 22

流水账

总结

在路上了

题解

A: 任何一个数初始位置和结束位置不连通->No，否则找一棵dfs树从叶子往根一个点一个点调整

B: AC自动机+矩阵快速幂

C: 最小生成树

D: BSGS，预处理每次跳65536步后的结果（题面有锅，实际上0~232-2互不相同）

E: 回文树上dp

F: 拆分数大约几千，爆搜或者dp（需要足够剪枝，辣鸡题目）

G: 来自朱老大的做法：随机10个排列，每次从10个里面随机选一个修改m个位置，如果返回的答案差别不足m个就忽略这次询问，否则可以确定某些数一定在某些位置。

这样下去使得每个数都被确定过O(1)（3~4?）次就可以确定唯一的位置，取m=sqrt(n)/2可以180次询问左右得到答案

H: 李超树

I: 暴力（OOP一下会好写很多）

J: 二维偏序算一下SG函数，因为偏序关系具有传递性所以mex=max+1，最后线性基+输出方案

K: 题目给定一个匹配，再构造一个(1,2),(3,4),...,(2n-1,2n)的匹配，两个匹配的并是二分图，二分图染色

L: 辣鸡计算几何 一个corner case是直线恰好是双曲线渐近线

附加文件