社区讨论

我好像 hack 了一道题的题意...

李李宇涵
学术版参与者 4已保存回复 5

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@lo2y2w2p
此快照首次捕获于
2023/10/23 21:39
2 年前
此快照最后确认于
2023/10/23 21:39
2 年前
查看原帖

讨论区 LaTeX\LaTeX 挂了（似乎和剪贴板的不一样），看这个剪贴板

题目：P8273 [USACO22OPEN] Pair Programming G
USACO 官方题面：题面
USACO 官方题解：题解
USACO 官方题解与洛谷题解（以下统称“题解”）均能通过 USACO 给出的所有测试点并 AC\color{lime}\texttt{AC} 本题。但是所有题解都不能按照题面的意思对一些 hack 数据给出正确的结果。
所有题解都是基于 dp 来实现的本题，并考虑了以下几点：
  • ×0\times 0 之前的全部无效
  • ×1\times 1 没有任何效果
  • ×a\times a ×b\times b 等效于 ×b\times b ×a\times a（乘法交换律）
  • +a+ a +b+ b 等效于 +b+ b +a+ a（加法交换律）
可以看到，题解在 dp 时预处理了前两点，并去掉了后两点引起的重复——也就是考虑了交换律带来的重复。
但是，除了交换律会带来重复，还有一种情况会引起重复：质因数分解（以及质因数同构）
即：×2\times 2 ×3\times 3 等效于 ×6\times 6（质因数分解）
×2\times 2 ×6\times 6 等效于 ×3\times 3 ×4\times 4（质因数同构）
对于下面的 hack 数据，所有题解给出的结果都是 99，而实际的结果应该是 88（实际结果通过手动模拟题意得出）
hack：
CPP
1
3
23+
+6+
下表中，“组合”一栏表示，在这一栏中的位置填入第一个程序 23+，不在的填入第二个位置 +6+。例如 1,4,61,4,6 代表了 2+63++:
1 2 3 4 5 6\texttt{{\color{red}1} 2 3 {\color{red}4} 5 {\color{red}6}}
2 + 6 3 + +\texttt{{\color{red}2} + 6 {\color{red}3} + {\color{red}+}}

这个表格炸了

题解给出的结果是 99 种，比实际情况 88 种多了一种，那么是哪里多了呢？
可以发现，第 1111 种和第 2020 种分别为 +23+6+ 和 +6+23+。两者结果相同，不是交换律的作用，而是因为一个 ×2\times 2 ×3\times 3 合并成了 ×6\times 6，一个 ×6\times 6 被拆分成了 ×2\times 2 ×3\times 3。
事实上，如果把 ×6\times 6 换成 ×7\times 7，也就是 +23+7+ 和 +7+23+，计算结果将分别为 42x+7y+z42x+7y+z 和 42x+6y+z42x+6y+z，是两个不同的结果。题解结果算出来的第 99 种就是这两种其中的一个。
然而，由于我太蒻了，我并不会写出完全符合题意的程序，而且 USACO 官方题解的做法也忽略了这一点，说明出题人很有可能并不希望题目包含这一点，因为考虑这一点会使难度大大增加，以至于不适合 USACO G 组。
但是对于一道题目，其正解必须对于所有合法输入给出对应的符合题面意义的输出，而不是通过其所有测试数据。在题面里面使用的大家都知道的背景（如本题的程序算术运算）时，也必须完整地引入该背景的所有规则（例如引入交换律、结合律，就要引入 2×3=62\times 3=6 这种基本的“算术规则”）。因此，我的建议是：
重新设定一个题面规则，规定 a×b=b×aa\times b=b\times a，a+b=b+aa+b=b+a，但是 2×3≠62\times 3\neq6，2×6≠3×42\times 6\neq 3\times 4。换句话说，也就是把原先的数字 2 到 9 看成 p2p_2 到 p9p_9，其中对于任意两个不同的可重集 {pa1,pa2,…,pak}\{p_{a_1},p_{a_2},\dots,p_{a_k}\}，都有不同的乘积。
一个便捷且符合认知的办法是，把 pip_i 设为不同的素数。例如下面的表格中，把 0 到 9 看成 ×p0\times p_0 到 ×p9\times p_9。

这个表格也炸了

以上内容仅代表个人建议，本人并没有否认 USACO 官方以及洛谷的权威性和严谨性，也没有任何恶意，违规紫衫，不喜轻喷。

回复

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

正在加载回复...