主题

主题

 
   

12633 - Super Rooks on Chessboard

原题:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4358

题目为pdf,就不搬题面了。


题目大意:

一个n*m的地图上有一些格子里有骑士,每个骑士可以攻击到它所在行,所在列以及所在的从左上到右下的对角线的所有格子,问有多少格子没被任何一个骑士攻击到。


个人解法:

首先我们把这张棋盘的左下角第一个格子视为(0,0)。

先不考虑对角线的影响。

接下来我们发现,如果x没有被占据,y也没有被占据,这个格子就对答案有1的贡献。

那么我们生成两个多项式A与B,分别表示行与列。

如果一行没有被占领,那么在多项式A中,这一行置为1,否则这一行置为0。

那么A与B的卷积就是答案。

考虑对角线的影响之后,我们发现在我们建立的坐标系中,对角线的x+y相同。

那么我们在统计答案的时候不统计被占领的x+y即可。


代码如下:

https://code.csdn.net/snippets/2252074

我这辈子都不想在UVa上做题……对这个OJ表示深深的烟(yan)雾(wu)。

 
 
评论