首页 > 代码库 > hdu 5100 Chessboard

hdu 5100 Chessboard

2024-08-01 02:11:39   220人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5100

在比赛时没看懂题就没看，结束之后，看了解题报告才知道怎么做。

解题报告：

首先，若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<stdio.h> 2  3 int main() 4 { 5     int t,n,k; 6     while(scanf("%d",&t)!=EOF) 7     { 8         while(t--) 9         {10             scanf("%d%d",&n,&k);11             if(n<k)12             {13                 printf("0\n");14             }15             else16             {17                 int x=n%k;18                 if(x<=k/2)19                 {20                     printf("%d\n",n*n-x*x);21                 }22                 else23                 {24                     printf("%d\n",n*n-(k-x)*(k-x));25                 }26             }27         }28     }29     return 0;30 }
View Code

 

 

hdu 5100 Chessboard


联系
我们