Daily Archives: 23 1 月, 2013

BZOJ 1088(mine)

Posted on by

1088: [SCOI2005]扫雷Mine

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 659  Solved: 386
[Submit][Status][Discuss]

Description

相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

Input

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

Output

一个数，即第一列中雷的摆放方案数。

Sample Input

2

1 1





Sample Output

2

Dp扫雷题：
一开始居然没有想出方程…天生不敏感？

显然方程为f(i,x,x_r) 表示第i格时，中间x和右边x_r是否有雷
轻易得到递归方程：
这题的教训是，方程果断列，另当前状态确定差1，由前面得到。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<cmath>
using namespace std;
#define MAXN (10000+10)
int n,a[MAXN];
int f[MAXN][2][2]={0}; //Middle and 1
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	switch (a[1])
	{
		case 2:f[1][1][1]++;break;
		case 0:f[1][0][0]++;break;
		default:f[1][0][1]=f[1][1][0]=1;
	}
	for (int i=2;i<=n;i++)
	{
		switch (a[i])
		{
			case 3:f[i][1][1]=f[i-1][1][1];break;
			case 0:f[i][0][0]=f[i-1][0][0];break;
			case 2:f[i][1][0]=f[i-1][1][1];f[i][0][1]=f[i-1][1][0];f[i][1][1]=f[i-1][0][1];break;
			case 1:f[i][1][0]=f[i-1][0][1];f[i][0][1]=f[i-1][0][0];f[i][0][0]=f[i-1][1][0];break;
		}
	}
	cout<<f[n][1][0]+f[n][0][0]<<endl;

	return 0;
}

HDU 1465(错排公式)

Posted on by

不容易系列之一

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9829    Accepted Submission(s): 4115



Problem Description
大家常常感慨，要做好一件事情真的不容易，确实，失败比成功容易多了！
做好“一件”事情尚且不易，若想永远成功而总从不失败，那更是难上加难了，就像花钱总是比挣钱容易的道理一样。
话虽这样说，我还是要告诉大家，要想失败到一定程度也是不容易的。比如，我高中的时候，就有一个神奇的女生，在英语考试的时候，竟然把40个单项选择题全部做错了！大家都学过概率论，应该知道出现这种情况的概率，所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语，我们可以这样总结：一个人做错一道选择题并不难，难的是全部做错，一个不对。

不幸的是，这种小概率事件又发生了，而且就在我们身边：
事情是这样的——HDU有个网名叫做8006的男性同学，结交网友无数，最近该同学玩起了浪漫，同时给n个网友每人写了一封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！

现在的问题是：请大家帮可怜的8006同学计算一下，一共有多少种可能的错误方式呢？

 


Input
输入数据包含多个多个测试实例，每个测试实例占用一行，每行包含一个正整数n（1<n<=20），n表示8006的网友的人数。
 


Output
对于每行输入请输出可能的错误方式的数量，每个实例的输出占用一行。
 


Sample Input
2
3
 


Sample Output
1
2
 


Author
lcy
 


Source
ACM暑期集训队练习赛（九）
 


Recommend
lcy
 

难得的中文题。

n错排公式：F[n]=(n-1)*(F[n-1]+F[n-2])

证明：

1.当前n-1个错排时：将其任意一封信与n对调,共(n-1)*F[n-1]

2.当前n-2个错排，1个不错排时,将不错排的那封信与n对调,共(n-1)*F[n-2]

3.当前≤n-3个错排，≥2个不错排时,显然无解.

∴F[n]=(n-1)*F[n-1]+(n-2)*F[n-2]

证毕


记得用long long，不然会爆

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
#define MAXN (20+10)
int n;
long long f[MAXN]={0,0,1};
int main()
{
	for (int i=3;i<=20;i++) f[i]=(i-1)*f[i-1]+f[i-2]*(i-1);
	while (cin>>n) cout<<f[n]<<endl;
}

POJ 2954(Pick公式)

Posted on by
Language:
Triangle
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4203   Accepted: 1858

Description

求出一个已知3点坐标的格点三角形的里面(边上的不算)有多少点.

Input

多组数据。每一行输入x1, y1, x2, y2, x3,y3, 表示格点三角形 (x1, y1), (x2, y2),
(x3, y3), −15000 ≤ x1, y1, x2, y2, x3, y3 ≤ 15000. 数据以6个0结尾.

Output

每组数据输出一行，表示格点三角形里面的点数.

Sample Input

0 0 1 0 0 1
0 0 5 0 0 5
0 0 0 0 0 0

Sample Output

0
6

Source

Stanford Local 2004

Pick定理：S=I+E/2-1 (E表示格点多边形边上的点,I表示格点多边形内的点)

Pick推论：格点多边形S=0.5k (k是正整数)


边上格点数公式：线段(x1,y1)-(x2,y2)的格点数=gcd(abs(x1-x2),abs(y1-y2))+1


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXX (15000)
int n;
int gcd(int a,int b){if (a<b) swap(a,b);if (b==0) return a;else return gcd(b,a%b);}
struct P
{
	int x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream& cin,P &a){cin>>a.x>>a.y;return cin;	}
	friend bool operator||(bool b,P &a){return b||a.x||a.y;}
}a[3];
struct S
{
	P s,t;
	S(){}
	S(P _s,P _t):s(_s),t(_t){}
	friend bool operator||(bool b,S &a){return b||a.s||a.t;}
	friend bool operator||(S &a,S &b){return 0||a||b;}
	int dx(){return abs(t.x-s.x);}
	int dy(){return abs(t.y-s.y);}
	int E(){return gcd(dx(),dy())+1;}
};
struct T
{
	S c[3];
	S& operator[](int i){return c[i];}
	friend istream& operator>>(istream& cin,T &c){cin>>a[0]>>a[1]>>a[2];c[0]=S(a[0],a[1]);c[1]=S(a[1],a[2]);c[2]=S(a[2],a[0]);return cin;}
	friend bool operator&&(bool b,T &a){return b&&(a[0]||a[1]||a[2]);}
	int area2(){return c[0].s.x*c[1].s.y+c[1].s.x*c[2].s.y+c[2].s.x*c[0].s.y-c[1].s.x*c[0].s.y-c[2].s.x*c[1].s.y-c[0].s.x*c[2].s.y;}
	int E(){return c[0].E()+c[1].E()+c[2].E()-3;}
	double _S(){return (double)abs(area2())/2;}
	int I(){return _S()-E()/2+1;}
}c;
int main()
{
	while (cin>>c&&c)
	{
		cout<<c.I()<<endl;
	}
	return 0;
}