【计数原理】【UVA11538】 Chess Queen
Description
给你一个n*m的棋盘,在棋盘上放置一黑一白两个皇后,求两个皇后能够互相攻击的方案个数
Input
多组数据,每组数据包括:
- 一行,为n和m
输入结束标志为n=m=0。
Output
对于每组数据,输出:
- 对应的放置方案数
Sample Input
Sample Output
Hint
n,m≤1e6,n和m不全为1。保证最终答案在long long int范围之内
两个皇后能相互攻击,当且仅当他们在同一列,同一行,或同一斜线上。
黑白两个皇后位置相反算两种不同的方案。
Solution
考虑两个皇后相互攻击的情况,显然相互之间没有包含关系,故而可以使用加法原理,分别求出方案数后相加。
对于在同一列上的方案数,设这个棋盘是m行n列的,不妨设n≤m,先考虑放置一只皇后,那么对于这n列,每一列都有m种放置方法,即共有n*m种放置方法。再考虑放置另一个皇后,对于每一种方案,两个皇后相互攻击当且仅当后放的皇后在先放的皇后的那一列上的除先放的皇后所在位置之外的m-1个位置上。也就是对于每种放置第一只皇后的方案共有m-1个满足题意的方案。使用乘法原理,那么在同一列上的方案数就是n*m*(m-1)。
同理易得,在同一行上的方案数是n*m*(n-1)。
对角线上的元素同理。不同的是,对于一个n*m的棋盘,不妨设n≤m,其对角线长度如下:
1,2,3,……n,n,n,……,3,2,1。其中共有(m-n+1)个n。
只考虑一条斜线,那么这样的方案数就是(∑(i:1 to n-1) i*(i-1)) + n*(m-n+1)*(n-1)。化简这个式子。以下省略sigma后i的范围
∑i*(i-1)=∑i2-∑i。其中∑i=n(n-1)/2。对于∑i2,有如下结论:
∑n(i=1)i2 = n(n+1)(2n+1)/6
证明?能吃嘛?
那么对于本题i∈[1,n-1],∑i2=(1/6)*n*(n-1)*(2n-4)。
因为是两条对角线,所以需要×2。带入方案数的式子,斜线上的方案数就是
2n(n-1)(3m-n-1)/3。
将上面几种情况相加即得答案
Code
#include<cstdio>
#define rg register
#define ci const int
#define LL unsigned long long int namespace IO {
char buf[];
} inline void qr(LL &x) {
char ch=getchar(),lst=' ';
while(ch>''||ch<'') lst=ch,ch=getchar();
while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
if (lst=='-') x=-x;
} inline void write(LL x,const char aft,const bool pt) {
if(x<) {putchar('-');x=-x;}
int top=;
do {
IO::buf[++top]=x%+'';
x/=;
} while(x);
while(top) putchar(IO::buf[top--]);
if(pt) putchar(aft);
} template <typename T>
inline T mmax(const T &a,const T &b) {if(a>b) return a;return b;}
template <typename T>
inline T mmin(const T &a,const T &b) {if(a<b) return a;return b;}
template <typename T>
inline T mabs(const T &a) {if(a<) return -a;return a;} template <typename T>
inline void mswap(T &a,T &b) {T temp=a;a=b;b=temp;} LL n,m; int main() {
qr(n);qr(m);
while(n||m) {
if(n>m) mswap(n,m);
write(n*m*(n-+m)+*n*(n-)*(*m-n-)/,'\n',true);
n=m=;qr(n);qr(m);
}
return ;
}
Summary
1、∑n(i=1)i2 = n(n+1)(2n+1)/6
2、看到1e6的题,如果因为答案大小限制了输入的大小,不妨往数学上想想,万一是O(1)的呢= =
最新文章
- HTML kbd键盘元素
- Spring Boot -- Start Up
- AutoHotkey 使用笔记
- 【Unity3D基础教程】给初学者看的Unity教程(四):通过制作Flappy Bird了解Native 2D中的RigidBody2D和Collider2D
- iOS面试题 02
- [SAP ABAP开发技术总结]动态语句、动态程序
- 3)Javascript设计模式:Observer模式
- new/delete和malloc/free的比较
- 清晰讲解SQL语句中的外连接,通用于Mysql和Oracle,全是干货哦
- SqlSever 使用 CROSS APPLY 与 OUTER APPLY 连接查询
- Docker基础-使用Dockerfile创建镜像
- PHP从入门到精通(三)
- MySQL数据库SQL修改数据规范
- Appium典型问题处理
- 为DOM节点添加或者删除class
- Redis持久化之RDB&;&;AOF的区别
- html5 &; upload files
- freetds设置超时
- shiro缓存
- photoswipe图片滑动插件使用