看题
\(\rm{T1}\)
神 tm zcy 和 jmr , what's up
至少看懂题了(雾)
\(\rm{T2}\)
也是看懂题了, 怎么也应该比 \(\rm{T1}\) 难
\(\rm{T3}\)
这个类型的题 \(100\%\) 不会的呀
看看能不能骗点算了
\(\rm{T4}\)
神秘计数, 这个类型的题 \(100\%\) 不会的呀
看看能不能骗点算了
正序开题
\(\rm{T1}\)
容易注意到, 没有参过赛的一定看做小号, 可以不管
每一次比赛相当于告诉我们, 比赛中的人不是同一个人, 最后询问有多少个号可能是同一人
问题转化为,
对于 \(k\) 个点集, 构造最小的 \(k\) , 使得每一个点集之中的点不在一场比赛中出现
将每个点向没有约束条件的点连边 (这一步可以用并查集处理), 最后会出现一张图
我们注意到, 问题转化成, 找图中最大的完全分量, 最后统计剩下多少个点
\(30 \rm{min}\) 过去了还是不会, 暴力都不会打, 寄
是不是题目 \(\rm{swap}\) 了一下, 去看 \(\rm{T3}\) , 也不会啊?
过 \(20 \rm{min}\) 想到了一个抽象二分答案做法, 看下是不是对的?
错误的
完啦啦啦啦啦啦啦寄寄积极急急急
不能啊
只能先跳过了, 确实想不出来, 这个题确实一点思路没有
发现暴力还是能打的, 框框 \(\rm{dfs}\) 即可, 有 \(35 \rm{pts}\)
\(\rm{T2}\)
有感觉能做?
但是复杂到爆炸
容易想到把相关的字符串全部加到字典树中
然后操作只有两种嘛
- 键盘输入
- 按
tab
显然有一个 \(\rm{dp}\)
1.对于每一个点, 都可以从前一个点按键盘 \(+1\) 推过来, 这是显然的
2.对于文件名的最后一个点, 可以从上一个文件名按 tab 过来 \(+1\)
3.对于文件名的最后一个点, 可以从自己的祖宗节点按 tab 过来 \(+1\)
4.对于第一个文件名, 特判一下可以从最后一个文件名按 tab 过来 \(+1\)
但是实现上非常困难
关键问题是我不知道字典树怎么 \(\rm{dfs}\) 啊, 而且第一个需要最后一个还有后效性
感觉确定 \(\rm{dp}\) 顺序之后应该还好, 考虑刷表法
对于每一个点, 转移:
- 后一个点
- 按
tab之后的点
转移顺序不会, 写不了一点
\(\rm{T3}\)
约束条件又多又杂, 完全想不出
对于 \(n \leq 7 \sim 20\) , 应该可以 \(\rm{dfs}\)
但是 \(a_i \leq 0\) 还是可以想一想
观察到这种情况下, 问题转化成
转化不出来, \(\rm{dfs}\) 不出来, 特殊性质做不出来, 鉴定为滚回文化课
\(\rm{T4}\)
\(\rm{dfs}\) + 剪枝暴力是显然的, 不想打, 大概有 \(15 \rm{pts}\)
考虑高一点的暴力
观察到每一次我们可以记录小米需要在 \(x, y, z\) 上运动的路程, 记为 \(dx, dy, dz\)
当 \(N = dx + dy + dz\) 时, 每一步必须是有效的, 答案即为
\[\frac{N!}{dx! \times dy! \times dz!} \]否则, 答案分为两种情况
-
\(N - (dx + dy + dz)\) 为奇数
显然的, 这种情况无解, 偶数之和必不可能为奇数 -
\(N - (dx + dy + dz)\) 为偶数
显然的, 这种情况我们需要让某一个维度分到偶数次操作, 令其为 \(2k\)
这样会在原来基础上多一个 \(k\) , 还需要 \(k\) 次撤回操作
我们先考虑分配
利用插板法, 现在有 \(k + 1\) 个插板位置, 要插两个板, 可能性显然有 $ \frac{k(k + 1)}{2}$
现在显然有一种朴素做法, 直接枚举 \(O(n ^ 2)\) 分配的操作数, 然后计算即可
具体的, 答案应该为$ \displaystyle \frac{N!}{(dx + kx)! \times (dy + ky)! \times (dz + kz)! \times kx! \times ky! \times kz!}$
这样我们就有了 \(45 \rm{pts}\)
正解只能考完之后补了
标签：一个点,赛时,11.19,times,dz,dx,dy,rm,CW From： https://www.cnblogs.com/YzaCsp/p/18554858