就是CF818 DIV.2的B题:Madoka and Underground Competitions
在网上看到的题解:
题意:给定n,k,n是k的倍数。你需要在n * n的矩阵中的每个位置填充'.','X'使得任意一个1*k或者k *1的子矩阵都至少有一个X。你要让X的数量尽量少,并且在(r,c)位置,必须为X。
题解: 构造。可以先考虑一个k * k的子矩阵,发现至少需要k个X,每行/列各一个。让n * n分割成k * k的小矩阵,每个kk矩阵都同样填充就能保证满足第一个条件。为了满足第二条件,我们只需让位置((r - 1) % k + 1, (c - 1) % k + 1) 为X。你可以填充第一个kk矩阵,然后复制到其他位置。不过更好的办法是,你只需让|i + j - r - c | %k == 0的位置为X。
然后给的代码里面,只需要对每个格子判断|i + j - r - c | %k == 0就行了,但是我不理解的是这个不是拿(r,c)去平移吗,那在单独一个k*k的矩阵里面除了(r,c)以外的其他格子应该放什么字符为什么可以通过这个式子决定呢?
蒟蒻真的很不理解!!!希望有大佬能帮忙下!