转跳到内容

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


推荐贴

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值了....

 

(数零数到头昏)

 

,由刁刁茶茶丸修改
链接到点评
17 小时前,挼挼说道:

①1 0 0

②0 1 0

③0 0 1

④1 1 1

⑤1 1 1

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

②、③同理

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

这应该没问题吧?

不是很自信

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

链接到点评
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的值。

其实 构造思路完全正确 但是 注意审题哦 提问的值需要是自然数 不包括负数 不过无所谓啦 算你对了

链接到点评
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

链接到点评

才看到题,第一反应是想到一个简单的思路

基础思路是通过哈希把三个值编码到三个不同的维度,那么每次询问相当于同时校验三个值

但是存在一个可能的问题就是因为不知道值域,因此无法确定出无冲突的哈希,那么可以先通过询问确定值域

如先询问两次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] 那就肯定没法编码到三维了,那还是线代吧

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

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

,由Muriya Tensei修改
链接到点评
  • 2 周后...

总算升级了能回复了

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

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

,由Prism修改
数学好难
链接到点评
7 小时前,Prism说道:

总算升级了能回复了

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

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

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

链接到点评
于 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

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款