首页 > 代码库 > BestCoder17 1001.Chessboard(hdu 5100) 解题报告

BestCoder17 1001.Chessboard(hdu 5100) 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5100

题目意思:有一个 n * n 的棋盘,需要用 k * 1 的瓷砖去覆盖,问最大覆盖面积是多少。

  比赛时不会做.............

hdu 题解:

    首先,若n<k,则棋盘连一个1×k的矩形都放不下,输出0。

    我们只需要考虑n≥k的情况。将棋盘类似于黑白染色,按(i+j)模k划分等价类,给每个格子标一个号。

标号之后,会注意到每条从左下到右上的斜线数字都是相同的,那么对于s×s的格子,其内部数字有且恰好有2s−1种,所以当s<=k2的时候,内部数字有floor(k2)∗2−1<k种,所以不能有更佳的方案。

从而证明最优的方案一定是仅剩下一个s×s的正方形区域没有被覆盖到,其中s ≤k2。

而令l = n mod k之后,根据l大小的不同,可以构造出中心为l×l或(k−l)×(k−l)的风车形图案,又通过上面证明这个l(或k−l)就是之前的s,所以是最优的。

所以令l = n mod k,如果l≤k2,最多可覆盖的格子数即为n2−l2,否则为n2−(k−l)2,显然这样的方案是可以构造出来的(风车形)。

     其实我觉得这个题解更好看,热烈推荐下面这个:

    http://www.matrix67.com/blog/archives/5900

 1 #include<iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7  8 int main() 9 {10     int T, n, k;11     while (scanf("%d", &T) != EOF)12     {13         while (T--)14         {15             scanf("%d%d", &n, &k);16             if (n < k)17                 printf("0\n");18             else19             {20                 int area = n * n;21                 int remain = n % k;22                 printf("%d\n", remain <= k/2 ? area-remain*remain : area-(k-remain)*(k-remain));23             }24         }25     }26     return 0;27 }
View Code

 

BestCoder17 1001.Chessboard(hdu 5100) 解题报告