[原创]KCTF第二题 Nepnep题解-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]KCTF第二题 Nepnep题解

2023-9-4 21:54 7854

[原创]KCTF第二题 Nepnep题解

Zuni-W

2023-9-4 21:54

7854

姗姗来迟，且没有电脑，开始写题的时候就已经有了四个解，好在没延误太久。

书归正题

本题是一个蕴含信息论模型的题目，考察点主要在于理解天平称重寻找次品的称量模型，并将其转化为一个线性表达。

天平称重

天平称重问题由来已久，主要是进行t次称重，在n个产品中有1个次品，次品或轻或重。注意到天平称重一次具有三个状态，于是共有 $3^t$ 种状态，而次品情况共有2n种，于是我们有 $2n\le 3^t$ 即 $n\le \frac{3^t}{2}$ 取整数可知，最多可以秤取 $\frac{3^t-1}{2}$ 个物品并选出次品。
另一方面，观察常见的相关脑筋急转弯，我们可以发现最常见的模式反而是t=3,n=12的情况，这和我们估计的上界n=13不同，但这符合题设的t=4,n=39。通过对这类题目试做可以发现，n取上界的情况并不是不能选到，但是要通过对某次选择的情况做分类讨论再执行，这跟本题中提供的矩阵逻辑看起来很不相符；而另一方面，通过将n三等分的方式进行分组上称，使得编码方案更加整洁。注意到 $\frac{3^t-1}{2}-1=\frac{3^t-3}{2}=\frac{3^{t-1}-1}{2}\times 3$ 为3的倍数，于是三等分在数学上是可行的，那么我们合理猜想，在模型扩充的过程中，进行三等分一定是必须的一步，所以我们获得第一个矩阵信息：每行012的个数一致，这在4*39的矩阵上也刚好可以成立。

另一方面，考虑在现实中，如果一个球出现问题，那么称量时一定是其所在的组不平衡，且偏转方向相反。这个性质在线性表达时我们可以看到重要性。

线性表达

接着我们考虑问题，假如一个球有问题，那么必然是其被选中时天平的平衡性被打破，而其轻与重的区别会导致天平倾向的角度完全相反。注意到从模型中抽离出后，某个球有问题即代表某一位被选中，于是某个列向量便被选出作为特征向量，根据过轻或过重得到两个相反的特征向量；而不同的问题球应当对应不同的特征向量，因而不同的列向量不应该是相同或相反；因此注意到共 $3^4-3=81=78$ 个向量，两两分组得到39组向量，每组中二选一，正好对应39个列向量。

复杂度优化1-分块

注意到这里题目为列向量整体规定了一个递增排序，所以每选定39个向量，都有唯一一个排列方案，这时复杂度为 $2^{39}$ 。

注意到还有前文提供的其他一些约束条件：
1.每行012的个数一致；
2.不同的列向量不应该是相同或相反；

由条件1和递增：第一行应为“0”*13+“1”*13+“2”*13，而对于以第一行分类后三行构成的三个3*13矩阵升序排列。

由条件2， $3^3-1=26$ 个向量，能分成13组，正好符合3*13的矩阵。

将三个矩阵分类讨论，对于0开头的（0）矩阵：
由于0的相反还是0，所以两个三长向量相反，他们呢在（0）矩阵里对应的四长向量也相反，这跟条件2是不符合的，所以这部分的复杂度是 $2^{13}*O(sort())$ ；

对于（1）矩阵，注意到某个向量被选择，都会在矩阵（2）里淘汰掉一个他的相反向量，每个块共有26种可能，其中((1),0,0,0)对应((2),1,1,1)，((1),2,2,2)对应((2),0,0,0)，那么每选择13个（1）矩阵的三长列向量，在（2）矩阵里能淘汰掉13个向量，剩下13个向量就唯一确定。这时复杂度为 $2^{13}*C(26,13)=2^{36}$

复杂度优化2-互斥

注意到((1),0,0,0)对应((2),1,1,1)，((1),2,2,2)对应((2),0,0,0)，这两组必须是二选一的，所以复杂度变为 $2^{13}*2*C(24,12)=2^{36}$
复杂度好像没有变化，但这提醒了我们，对于某些情况，似乎可以做些额外的预处理来进行下一步处理。

复杂度优化3-预处理

好像已经没有什么条件可以用了，两个条件+排序都用过了。但是注意到整个处理过程我们分成了两步走，在这个过程中实测发现两步中0的个数是稳定的，但是1和2不平衡，如果可以提前限制1和2平衡，那么其实就是第一步和第二步的数据要结合，这里1和2平衡就是桥梁。
我们可以预处理出2*C(24,12)的情况里三个向量维度里1的个数，然后在 $2^{13}$ 里每个维度确定还差多少个1，进行查表，这时保证每个结果都是合法的，且没有遗漏，达到了最优解。
分析复杂度，表中最多有 $18536=2^{15}$ 个可能的情况，将排序看作常数时间，于是最坏复杂度达到 $2^{13+1+15}=2^{29}$ ，表的平均大小约为1092，平均复杂度向上估计达到 $2^{13+1+11}=2^{25}$ ，还在可承受范围内。