关于『JROI-2』Summer Fun Round T2
  • 板块学术版
  • 楼主幽云蓝萌萌JS式神
  • 当前回复18
  • 已保存回复18
  • 发布时间2021/8/2 20:39
  • 上次更新2023/11/4 12:12:15
查看原帖
关于『JROI-2』Summer Fun Round T2
149196
幽云蓝萌萌JS式神楼主2021/8/2 20:39

作为本题的出题人,蓝向大家谢罪,蓝向大家承诺以后再次出题时会准备足够严谨的理论证明并且做好充分的验题工作,希望大家能轻 D。

  1. 关于数据:蓝仅仅给出了题解和 std,事先并没有拿到数据并对其强度进行检验,这在一道强调思维的题目中是绝对不可取的,这也导致了赛时的事故,向大家道歉。

  2. 关于 std 的正确性:感谢 Forever_Pursuit 大佬可以给出 hack 数据,在此之前,蓝并没有试图构造这样高强度的数据对 std 进行检验,再次向大家道歉。

  3. 关于该题是否是假题:目前蓝不能下定论,作为一道新题,蓝认为还没有人对其有充分的研究,但是可以确定的是蓝给出的解法并不一定能得到正确的答案(只能得到一个近似的答案)。蓝对于此题有三个疑问:① 最优的冰冻策略是否一定保证每一时刻被冻住的青蛙形成一个连通块;② 如果使用蓝的 dp 解法并且枚举根节点,最后将所有算出的结果取 min\min 值是否能得到正确答案,这样做的时间复杂度是 O(n2)O(n^2),但蓝只想要知道正确性/kel;③ 本题是否存在多项式复杂度的解法,是否有论文提到类似问题的解法。

如果有任何人能帮助蓝解决上述问题,请私信蓝或者在帖子下方回复并@蓝。对于该题有任何意见 or 建议也可以直接留言。希望可以让更多的人看到该问题,最好可以置顶(当然啦,这只是蓝的奢望)。最后为该题的质量问题再次向大家道歉,蓝保证以后不会出如此低质量或者没用经过充分准备的题目。

2021/8/2 20:39
加载中...