刁刁茶茶丸 发布于七月 18 分享 发布于七月 18 (已修改) · 只看该作者 18 小时前,Nemakori说道: emmmm 因为原题目是来源于算法竞赛中的一道题,有数据范围限制QwQ,所以我可能需要一段时间去消化佬的做法,不过这个思路真的很有意思 不过我有个提问 假如第四次的回答是99980555021 + 10000000000的话 该怎么确定a,b,c的值,此时第四次回答的错误均可能来源于a,b,c,比如a是21+10000000000,b是10000000+555,c是1000+9998或者第四次回答均可以产生错误,那么第五次提问该如何验证 如果斯芬提前知道这样的提问方式,并且有意识地来选择让数据出错的方式来专门干扰这种方式的话 仅凭第四次提问确实没办法独立完成对数据的校对,但我们可以通过拉大第五次提问的位数来对抗这种混淆 例如斯芬给出的第四次回答的位数为1*10^10, 那么第五次提问就将 k1 k2 k3设定为 1 , 1*10^(10+1),1*10^(20+1) 或者将k1 k2 k3的顺序进行调转 例如改成 10000000,1,1000 这样...应该...就能获取足够的信息来确定abc的值了(瘫) 用具体数字来说明的话(我取个小一点的数字吧...) 不出现混淆的情况: a:2 b:3 c:5 d:50302 出现混淆的情况: 混淆a:2 真实a:1000002 b:3 c:5 d:1050302 将间隔调整为1*10^(6+1)后 e:5000000031000002 就可以获取到无混淆的abc值了.... (数零数到头昏) 七月 18,由刁刁茶茶丸修改 链接到点评
Nemakori 发布于七月 18 作者 分享 发布于七月 18 · 只看该作者 17 小时前,挼挼说道: ①1 0 0 ②0 1 0 ③0 0 1 ④1 1 1 ⑤1 1 1 ①错了时,④-②-③,⑤-②-③对比即得 ②、③同理 ④、⑤错了,①+②+③比较也能得出 这应该没问题吧? 不是很自信 有哦 ④⑤值相同可以确定前三个有错 但是怎么确定前三个错的是哪个呢 链接到点评
Nemakori 发布于七月 18 作者 分享 发布于七月 18 · 只看该作者 17 小时前,danielrosen4说道: 由题意,需要构造五个向量kn(k1,k2,k3),并且保证任取3个kn都互相线性无关。 不妨构造(1,0,0)(0,1,0)(0,0,1)(1,1,1)(1,-2,2)为k1、k2、k3的取值, 那么得到如下的五条方程:(Pn为第n次提问时得到的求和答案) ①P1=a ②P2=b ③P3=c ④P4=a+b+c ⑤P5=a-2b+2c 将上述五条方程中任意舍弃一条,将剩余部分构造为方程组,得到包含等式②③④⑤的方程组1、包含等式①③④⑤的方程组2、包含等式①②④⑤的方程组3、包含等式①②③⑤的方程组4、包含等式①②③④的方程组5。 这五个方程组中仅有一个会有解,那个解就是abc的值。 其实 构造思路完全正确 但是 注意审题哦 提问的值需要是自然数 不包括负数 不过无所谓啦 算你对了 链接到点评
Nemakori 发布于七月 18 作者 分享 发布于七月 18 · 只看该作者 1 小时前,刁刁茶茶丸说道: 如果斯芬提前知道这样的提问方式,并且有意识地来选择让数据出错的方式来专门干扰这种方式的话 仅凭第四次提问确实没办法独立完成对数据的校对,但我们可以通过拉大第五次提问的位数来对抗这种混淆 例如斯芬给出的第四次回答的位数为1*10^10, 那么第五次提问就将 k1 k2 k3设定为 1 , 1*10^(10+1),1*10^(20+1) 或者将k1 k2 k3的顺序进行调转 例如改成 10000000,1,1000 这样...应该...就能获取足够的信息来确定abc的值了(瘫) 用具体数字来说明的话(我取个小一点的数字吧...) 不出现混淆的情况: a:2 b:3 c:5 d:50302 出现混淆的情况: 混淆a:2 真实a:1000002 b:3 c:5 d:1050302 将间隔调整为1*10^(6+1)后 e:5000000031000002 就可以获取到无混淆的abc值了.... (数零数到头昏) 暂时没发现问题 佬应该是唯一一个用到提问是一次一次提问这个条件的 点赞w 1 链接到点评
Nemakori 发布于七月 18 作者 分享 发布于七月 18 · 只看该作者 题解已出 欢迎捧场哦 顺带敬请期待下一期 @hentai14 @IOPU @U咩 @挼挼 题解链接: https://sstm.moe/topic/358970-【题解】数学算法挑战-斯芬克斯之谜/ 链接到点评
Muriya Tensei 发布于七月 24 分享 发布于七月 24 (已修改) · 只看该作者 才看到题,第一反应是想到一个简单的思路 基础思路是通过哈希把三个值编码到三个不同的维度,那么每次询问相当于同时校验三个值 但是存在一个可能的问题就是因为不知道值域,因此无法确定出无冲突的哈希,那么可以先通过询问确定值域 如先询问两次a+b+c(由题意三者均非负) 那么单独的a+b+c必然不会超过这个范围 接下来,把之前得到的a+b+c较大者+1作为进制p(当然取更大的素数p 或者直接取位数h 进制取 10^h也是一样的道理) 再次询问 a+b*p+c*p^2 三次(如果前两次不同的话甚至询问两次就够了) 再根据p解码出abc后,取重复出现的即可 --- 去看了眼原题,果然是ICPC啊() 题目限定了系数只能取 [0, 10] 那就肯定没法编码到三维了,那还是线代吧 应该是只要满足任选三个向量均线性无关即可 这样任意三个都能解出一组解,并且错误的解的组数小于正确的组数 七月 24,由Muriya Tensei修改 链接到点评
Prism 发布于八月 6 分享 发布于八月 6 (已修改) · 只看该作者 总算升级了能回复了 看上去应该可以看成一个线性方程组解问题( 每一次提问都可以构造一个向量,构成一个 5 * 4 的矩阵,总共可以取出 5 个 4 阶方阵,因为有一个结果是错误的,所以仅有一个方阵是有解的 八月 6,由Prism修改 数学好难 链接到点评
Nemakori 发布于八月 6 作者 分享 发布于八月 6 · 只看该作者 7 小时前,Prism说道: 总算升级了能回复了 看上去应该可以看成一个线性方程组解问题( 每一次提问都可以构造一个向量,构成一个 5 * 4 的矩阵,总共可以取出 5 个 4 阶方阵,因为有一个结果是错误的,所以仅有一个方阵是有解的 是的 但是为了解出结果方便的话 大多数是我给的通解范围内的构造 链接到点评
Nemakori 发布于八月 6 作者 分享 发布于八月 6 · 只看该作者 于 2024/7/25 于 AM2点59分,Muriya Tensei说道: 才看到题,第一反应是想到一个简单的思路 基础思路是通过哈希把三个值编码到三个不同的维度,那么每次询问相当于同时校验三个值 但是存在一个可能的问题就是因为不知道值域,因此无法确定出无冲突的哈希,那么可以先通过询问确定值域 如先询问两次a+b+c(由题意三者均非负) 那么单独的a+b+c必然不会超过这个范围 接下来,把之前得到的a+b+c较大者+1作为进制p(当然取更大的素数p 或者直接取位数h 进制取 10^h也是一样的道理) 再次询问 a+b*p+c*p^2 三次(如果前两次不同的话甚至询问两次就够了) 再根据p解码出abc后,取重复出现的即可 --- 去看了眼原题,果然是ICPC啊() 题目限定了系数只能取 [0, 10] 那就肯定没法编码到三维了,那还是线代吧 应该是只要满足任选三个向量均线性无关即可 这样任意三个都能解出一组解,并且错误的解的组数小于正确的组数 不过 没有数据范围的限制感觉有更多更有意思的解法 算是意外之喜了w 链接到点评
推荐贴