蒟蒻求助站外题(CF1717B)!!!!很简单的
  • 板块题目总版
  • 楼主Haron
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/5 09:19
  • 上次更新2023/10/27 12:29:52
查看原帖
蒟蒻求助站外题(CF1717B)!!!!很简单的
239716
Haron楼主2022/9/5 09:19

就是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)以外的其他格子应该放什么字符为什么可以通过这个式子决定呢? 蒟蒻真的很不理解!!!希望有大佬能帮忙下!

2022/9/5 09:19
加载中...