社区讨论

你们怎么都会D呀/流泪，求助该如何想到抽屉或证明合法

2024/07/19 08:51学术版参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复: 1 条
当前快照: 1 份
快照标识符: @lyrzk0tv
此快照首次捕获于: 2024/07/19 08:52
此快照最后确认于: 2024/07/19 10:04

你们怎么都会D呀/流泪

怎么想到抽屉原理的呀？

对D的心路历程大概是：

尝试找高复杂度的确定性做法
未果，考虑如何判断非法。
如果乱选的话需要反悔，但又感觉这题不应该这么难。（尝试往贪心上想）
考虑仿照 kru，以某种顺序访问边权，顺序和质数个数有关（尝试往数论上走），需要用并查集维护（很符合div2D的特点对吧）
未果，观察样例。发现都是深度为 $3$ 的菊花，考虑构造成这种类型（雾）
罚坐一个小时依旧得不到确定性做法。
发现完全没有用到图的性质，再考虑从图上思考。（此时已经摆了）

各位朋友们，我也感觉不出问题出在哪一步上。但我认为，想不到抽屉就不能确定必然合法，那是应该先想到抽屉，还是应该先用其他方法归纳证明必然合法？如果是后者的话应该怎么想？如果是前者的话该如何想到？还是说根据样例/题目位置来推出。

感觉是很有价值的题目，至少对于我而言。谢谢大家/玫瑰。

回复

共 1 条回复，欢迎继续交流。

正在加载回复...