娱乐 数学算法挑战 [构造] 斯芬克斯之谜

[刁刁茶茶丸]

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]

17 小时前，挼挼说道:

①1 0 0

②0 1 0

③0 0 1

④1 1 1

⑤1 1 1

①错了时，④-②-③，⑤-②-③对比即得

②、③同理

④、⑤错了，①+②+③比较也能得出

这应该没问题吧？

不是很自信

有哦 ④⑤值相同可以确定前三个有错 但是怎么确定前三个错的是哪个呢

[Nemakori]

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]

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

[Nemakori]

题解已出 欢迎捧场哦 顺带敬请期待下一期

@hentai14 @IOPU  @U咩 @挼挼

题解链接：

https://sstm.moe/topic/358970-【题解】数学算法挑战-斯芬克斯之谜/

[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] 那就肯定没法编码到三维了，那还是线代吧

应该是只要满足任选三个向量均线性无关即可

这样任意三个都能解出一组解，并且错误的解的组数小于正确的组数

七月 24，由Muriya Tensei修改

[Prism]

总算升级了能回复了

看上去应该可以看成一个线性方程组解问题（

每一次提问都可以构造一个向量，构成一个 5 * 4 的矩阵，总共可以取出 5 个 4 阶方阵，因为有一个结果是错误的，所以仅有一个方阵是有解的

八月 6，由Prism修改
数学好难

[Nemakori]

7 小时前，Prism说道:

总算升级了能回复了

看上去应该可以看成一个线性方程组解问题（

每一次提问都可以构造一个向量，构成一个 5 * 4 的矩阵，总共可以取出 5 个 4 阶方阵，因为有一个结果是错误的，所以仅有一个方阵是有解的

是的 但是为了解出结果方便的话 大多数是我给的通解范围内的构造

[Nemakori]

于 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