第184章 附加题(1 / 2)
请关闭浏览器的阅读/畅读/小说模式并且关闭广告屏蔽过滤功能,避免出现内容无法显示或者段落错乱。
这是一道没有标准套路的附加题。
至少第一眼看上去没有。
林辰把题目从头到尾读了一遍。
又读了一遍。
题目给出一个九宫格式的点阵。
每个格点上可以填入一个整数。
要求满足横向、纵向若干局部关系,同时证明,无论初始数字怎样选,只要经过题目规定的三种变换,最终都能判断某个目标状态是否可达。
乍看和第一题的状态问题有点像。
真正往下看,又完全不是一回事。
第一题至少告诉了每一步怎么变。
这题却只给了几条局部关系。
剩下的东西像被藏在格子里面。
林辰盯了半天。
没有公式。
没有明显模型。
甚至连“证明某某不变量”这种暗示都没有。
他第一反应是往苏晚晴平时教过的方向找。
奇偶。
和。
差。
对称。
全试了一遍。
没找到。
时间已经不到二十分钟。
旁边答题卡最后一块区域还是空的。
按正常考试策略。
这题完全可以放掉。
反正附加题不计基础预选成绩。
可题目刺。
不是因为想被老师点名。
恰恰相反。
林辰很怕被点。
但最近几天训练的东西,刚好全部挤在这道题面前。
没有现成答案。
没有苏晚晴给公式。
也没有必须拿满分的要求。
那自己会怎么想?
林辰把草稿纸转了九十度。
不再盯着题目里的字母。
他把九个格点重新画了一遍。
三个一排。
一共三排。
然后看了几秒。
“九宫格……”
他心里念了一遍。
突然想起小时候小区楼下铺地砖。
不是数学题。
就是几块颜色不同的方砖。
工人铺的时候,一排一排放。
如果某一块高了。
旁边就得跟着调。
再往旁边。
整个局部关系会像波纹一样传出去。
林辰的笔动了一下。
题目里的三种操作,其实也都只改相邻位置。
一次只动两格或者四格。
那如果不看具体数字。
只看“某个位置被改变了几次”呢?
他先在九个格点旁边写上零。
模拟第一种操作。
两个位置加一。
第二种。
四个角变。
第三种。
中间十字变。
算了两轮。
乱。
再算一轮。
还是乱。
林辰皱眉。
这条路似乎不对。
正常情况下,他现在很容易陷进去。
已经算了三遍。
不甘心扔。
总想证明自己前面没白写。
可苏晚晴最近一直逼他练一件事。
发现路走不通,就停。
不是坚持越久越值得。
林辰在那堆零和一外面画了一个大叉。
重新来。
具体次数不行。
那只看奇偶?
改一次算一。
改两次相当于没改。
他把所有变化全部压成奇偶。
纸面立刻少了一半东西。
第一种操作改变两个格点的奇偶。
第二种改变四个。
第三种也是四个。
每次变化的格点总数都是偶数。
林辰停住。
总数?
不是数字总和。
是和初始状态相比,“发生奇偶变化的位置数量”。
每一次操作都让偶数个位置翻转。
所以这个数量的奇偶性……
不会随便变。
他盯着草稿。
有点像。
但还不够。
目标状态要求九个格点里恰好有一个位置与其他八个满足不同的奇偶关系。
那意味着从某些初始状态出发,需要翻转奇数个位置。
可题目允许的每一次操作,影响的都是偶数个位置。
多个偶数次局部翻转叠加以后,整体翻转数量的奇偶……
林辰写到这里,又停。
不对。
同一个位置可能被重复翻转。
不能直接把每次影响的位置数相加。
会抵消。
他差点又把刚刚的答案全部划掉。
笔抬起来。
却没立刻落下。
如果把每个位置是否翻转,当成零和一。
所有操作本身都是一个九位的零一向量。
目标变化也是。
题目问的其实就是:
目标向量能不能由这三类操作组合出来。
这个说法已经开始像苏晚晴会说的话。
林辰自己都觉得有点离谱。
可一想到“向量”,脑子又要回到公式。
他赶紧把这个词先放一边。
换成自己能看的。
他在草稿上写:
“每一种操作都是一张模板。”
“多操作几次,就是模板叠起来。”
然后把三种操作画成三个小九宫格。
变的位置涂黑。
不变的位置留白。
林辰盯着三个黑白图。
突然发现,每一种模板的每一行、每一列,黑格数量都存在一个很规律的关系。
更重要的是。
如果把三条对角线其中一条与中间十字一起看。
某几个固定位置的黑格总数永远是偶数。
林辰重新检查。
第一种。
偶数。
第二种。
偶数。
第三种。
还是偶数。
只要这三种基本操作每一种都保持这个性质。
无论叠多少次。
这个性质都不会变。
而目标状态——
是奇数。
入口找到了。
林辰心跳忽然快了一下。
不是共感。
就是那种卡了十分钟以后,忽然看见门缝的兴奋。
他没有时间把证明整理得特别漂亮。
先把那几个关键位置圈起来。
定义它们的奇偶和。
再逐一验证三类操作都只会改变其中零个或两个位置,因此这个奇偶和保持。
初始状态的值是什么。
目标状态又是什么。
不同。
所以不可达。
写到最后。
林辰的笔停了两秒。
答案已经成立。
至少他自己能解释。
问题是草稿里的过程太难看。
三个九宫格。
一堆黑点。
还有一句:
“把操作当模板叠。”
如果按照苏晚晴以前的习惯。
应该全部删掉。
把它整理成一个简洁的不变量证明。
甚至可以直接定义一个模二量。
四五行解决。
林辰也知道那样更漂亮。
可他看着自己那几张小格子,迟迟没擦。
这是他真正找到答案的路。
如果删掉以后,只剩一段标准语言。
老师真问“为什么想到”。
他又只能回答:
就这么想到的。
那跟以前背公式没有区别。
林辰最后只做了一件事。
把最乱的试算划掉。
三个模板保留。
圈出的关键位置也保留。
旁边补上正式说明。
不漂亮。
但完整。
后排。
苏晚晴同样在做这道附加题。
她比林辰更早看出这是一个模二状态问题。
也更早意识到可以寻找线性不变量。
如果完全按照她自己的能力。
她有至少两种方式写。
一种用奇偶不变量。
另一种把操作写成零一向量,讨论生成空间。
后者更短。
也更“竞赛”。
可她现在用的是林辰的身体。
旁听卷的意义不是展示她能做到什么程度。
苏晚晴把第二种方法压下去。
↑返回顶部↑