Monthly Archives: 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;
}

CF 18A(近似直角三角形判断+向量直角公式+switch+istream&(..&P a))

Posted on by
A. Triangle
time limit per test

2 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

判断一个格点三角形是直角三角形,近似直角三角形,还是都不是.

Hint:近似直角三角形是指把一个三角形的一个点移动1个单位长度(移动后仍为格点三角形)，其能变成直角三角形的非直角三角形

Input

 x1, y1, x2, y2, x3, y3 表示3点坐标（都在格点上），不超过
100.

Output

I直角三角形输出 RIGHT,

近似直角三角形输出 ALMOST, 都不是输出 NEITHER.

Sample test(s)
input
0 0 2 0 0 1
output
RIGHT
input
2 3 4 5 6 6
output
NEITHER
input
-1 0 2 0 0 1
output
ALMOST

各种判断…

注意格点三角形在移动完可能出现点重合（0向量）

仍满足向量直角公式a X b
= |a||b|

以及switch-case-default的用法。

△：default打错不会提示.

PS:istream& operator<<的重载中 输入的struct 如果不加&，是读不进的。


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
#include<cmath>
using namespace std;
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;	}
	void move(int d)
	{
		if (d==1) x++;
		if (d==-1) x--;
		if (d==2) y++;
		if (d==-2) y--;
		return;
	}
}a[3];
struct V
{
	int x,y;
	V(){}
	V(int _x,int _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend int operator*(V a,V b){return a.x*b.y-a.y*b.x;}
	int dis2(){return x*x+y*y;	}
	friend bool right_angle(V a,V b){return pow(a*b,2)==a.dis2()*b.dis2();	}
}c[3];
void res_c()
{
	for (int i=0;i<3;i++) c[i]=V(a[i],a[(i+1)%3]);
}
bool is_r_trangle()
{
	res_c();
	for (int i=0;i<3;i++) if (!c[i].dis2()) return 0;
	for (int i=0;i<2;i++)
		for (int j=i+1;j<=2;j++) if (right_angle(c[i],c[j])) {/*cout<<i<<' '<<j<<endl;*/return 1;}
	return 0;
}
int solve()
{
	if (is_r_trangle()) return 1;
	for (int i=0;i<3;i++)
	{
		for (int j=-2;j<=2;j++)
		{
			if (j==0) continue;
			a[i].move(j);
			if (is_r_trangle()){/*cout<<i<<' '<<j<<endl;*/ return 2;}
			a[i].move(-j);
		}
	}
	return 0;
}
int main()
{
	for (int i=0;i<3;i++) cin>>a[i];

	switch (solve())
	{
		case 1:cout<<"RIGHT";break;
		case 2:cout<<"ALMOST";break;
		default:cout<<"NEITHER";
	}
	cout<<endl;

	return 0;
}

POJ 2398(二分点集)

Posted on by
Language:
Toy Storage
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 8137   Accepted: 3848

Description

在长方形 (x1,y1) (x2,y2) 中有n块板（保证与上下边相交），和m个点。
现给出板和点的位置，求拥有相同点数的区域数、
 
 

Input

多组数据.每组数据开头为 n m x1 y1 x2 y2. n (0 < n <= 5000) m (0 < m <= 5000). (x1,y1)为左上角坐标 , (x2,y2)为右下角坐标. 
接下来 n 行有2个数 Ui Li,表示第i块板为 (Ui,y1) (Li,y2). （保证两两不交）.
接下来m 行为点的坐标 Xj Yj （保证不在板上）
数据以 0 结束.

Output

每组数据给出同点数的区域数
点数: 区域数
…(点数1→n，区域数为0不输出)
请按这个格式输出。
每组数据开头输出“Box”。 

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
 5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

Hint

落在长方形边上的点也算.

Source

Rocky Mountain 2003

基本同POJ 2318

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (1000+10) //Board
#define MAXM (1000+10) //Toy
struct P
{
	double 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;	}
}a[MAXM];
struct V
{
	double x,y;
	P s;
	V(){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y),s(a){}
	friend int operator*(const V a,const V b)
	{
		return a.x*b.y-a.y*b.x;
	}
}c[MAXN];
int n,m,x1,y1,x2,y2,f[MAXM];
int cmp(V a,V b)
{
	return a.s.x<b.s.x;
}
void binary(int L,int R,int l,int r)
{
	if (R-L==1)
	{
		f[r-l+1]++;
		return;
	}
	int i=l,j=r,m=(l+r)>>1;
	V &M=c[(L+R)>>1];
	do
	{
		while (i<=r&&V(M.s,a[i])*M<0) i++;
		while (j>=l&&V(M.s,a[j])*M>0) j--;
		if (i<=j) {swap(a[i],a[j]);i++;j--;	}
	}while (i<=j);

	i--;j++;
	binary(L,(L+R)>>1,l,i);
	binary((L+R)>>1,R,j,r);

}
int main()
{
//	freopen("poj2398.in","r",stdin);

	while (scanf("%d%d",&n,&m)==2)
	{
		cout<<"Boxn";
		memset(f,0,sizeof(f));
		cin>>x1>>y2>>x2>>y1;
		for (int i=1;i<=n;i++)
		{
			int u,l;
			cin>>u>>l;
			c[i]=V(P(l,y1),P(u,y2));
		}
		c[0]=V(P(x1,y1),P(x1,y2));c[n+1]=V(P(x2,y1),P(x2,y2));
		sort(c+1,c+1+n,cmp);
		for (int i=1;i<=m;i++) cin>>a[i];
		binary(0,n+1,1,m);
		for (int i=1;i<=m;i++)
			if (f[i]) cout<<i<<": "<<f[i]<<endl;
	}
	return 0;
}

POJ 2318(点集二分)

Posted on by
Language:
TOYS
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 8137   Accepted: 3848

Description

在长方形 (x1,y1) (x2,y2) 中有n块板（保证与上下边相交），和m个点。
现给出板和点的位置，求各区域点数、
 
 

Input

多组数据.每组数据开头为 n m x1 y1 x2 y2. n (0 < n <= 5000) m (0 < m <= 5000). (x1,y1)为左上角坐标 , (x2,y2)为右下角坐标. 
接下来 n 行有2个数 Ui Li,表示第i块板为 (Ui,y1) (Li,y2). （保证两两不交，且板从左至右给出）.
接下来m 行为点的坐标 Xj Yj （保证不在板上）
数据以 0 结束.

Output

每组数据给出各区域点数（最左边区域编号0）
区域编号: 点数
…(区域编号0→n)
请按这个格式输出。
不同组数据间输出一空行。 

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
 5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2

Hint

落在长方形边上的点也算.

Source

Rocky Mountain 2003

直接枚举点超时，

所以枚举中间那块板，二分查找（注意Qsort性质,[1, i-1]  和 [ j+1,n]即为所求范围）

但是由于中间那块板并不“计入点集”，所以 i 和 j 可能 越界，要特判。

由于用int会乘越界（这题没给范围），所以稳妥的用double.



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (5000+10) //Board
#define MAXM (5000+10) //Toy
struct P
{
	double 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;	}
}a[MAXM];
struct V
{
	double x,y;
	P s;
	V(){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y),s(a){}
	friend int operator*(const V a,const V b)
	{
		return a.x*b.y-a.y*b.x;
	}
}c[MAXN];
int n,m,x1,y1,x2,y2;
void binary(int L,int R,int l,int r)
{
	if (R-L==1)
	{
		cout<<L<<": "<<r-l+1<<endl;
		return;
	}
	int i=l,j=r,m=(l+r)>>1;
	V &M=c[(L+R)>>1];
	do
	{
		while (i<=r&&V(M.s,a[i])*M<0) i++;
		while (j>=l&&V(M.s,a[j])*M>0) j--;
		if (i<=j) {swap(a[i],a[j]);i++;j--;	}
	}while (i<=j);

	i--;j++;
	binary(L,(L+R)>>1,l,i);
	binary((L+R)>>1,R,j,r);

}
int main()
{
//	freopen("poj2318.in","r",stdin);
	scanf("%d%d",&n,&m);
	while (1)
	{
		cin>>x1>>y2>>x2>>y1;
		for (int i=1;i<=n;i++)
		{
			int u,l;
			cin>>u>>l;
			c[i]=V(P(l,y1),P(u,y2));
		}
		c[0]=V(P(x1,y1),P(x1,y2));c[n+1]=V(P(x2,y1),P(x2,y2));
		for (int i=1;i<=m;i++) cin>>a[i];
		binary(0,n+1,1,m);
		if (scanf("%d%d",&n,&m)==2) cout<<endl; else break;
	}
	return 0;
}

POJ 1228(稳定凸包)

Posted on by
Language:
Grandpa's Estate
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 8990   Accepted: 2383

Description

Kamran the Believer继承了祖母的一个凸多边形庄园. 庄园外围用绳子和木桩围起. 但一些绳子和木桩缺失了.帮忙看一下用剩余木桩围起的庄园是否是稳定凸包（即剩下的钉子能确定一个唯一的凸包）.

Input

第一行一个数据组数 t (1 <= t <= 10). 
对于每组数据，第一行为 n (1 <= n <= 1000) 表示木桩数. 接下来n行，每行为木桩坐标(x,y)，保证整数.

Output

 对每组数据输出YES 或 NO ，表示其是否稳定.

Sample Input

1
6
0 0
1 2
3 4
2 0
2 4
5 0

Sample Output

NO

Source

Tehran 2002 Preliminary

要想让一个凸包稳定，当且仅当凸包上任意一条边有3个以上的木桩（包括端点）

证明：


只要在建完凸包后，枚举，边上的第3点即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXT (10+10)
#define MAXN (1000+10)
//#define sqr( x ) (x*x)
int sqr(int x){return x*x;}
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 double dis(P a,P b)
	{
		return sqrt(double(sqr(a.x-b.x)+sqr(a.y-b.y)));
	}
}a[MAXN];
struct V
{
	int x,y;
	V(){}
	V(int _x,int _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend int operator*(V a,V b)
	{
		return a.x*b.y-a.y*b.x;
	}
};
int cmp(P A,P B)
{
	int temp=V(a[1],A)*V(a[1],B);
	if (temp>0) return 1;
	else if (temp==0&&dis(a[1],A)<dis(a[1],B)) return 1;
	else return 0;
}
int t,n,st[MAXN];
bool solve()
{
	int size=1;st[0]=1;
	st[1]=1;
	int j=2;
	while (j<=n)
	{
		if (size<2||V(a[st[size-1]],a[st[size]])*V(a[st[size]],a[j])>0)
		{
			st[++size]=j++;
		}
		else size--;
	}
	a[++n]=a[1];
	st[++size]=n;

	for (int i=1;i<size;i++)
	{
	/*
		int k=st[i-1]+1;
		for (;k<st[i+1];k++)
			if (k!=st[i]&&V(a[st[i]],a[st[i+1]])*V(a[st[i]],a[st[k]])==0) break;
		if (k==st[i+1]) return 0;
	*/
		int k=1;
		for (;k<n;k++)
			if (k!=st[i]&&k!=st[i+1]&&V(a[st[i]],a[st[i+1]])*V(a[st[i]],a[k])==0) break;
		if (k==n) return 0;
	}
	return size>=4;
}
int main()
{
//	freopen("poj1228.in","r",stdin);
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++) cin>>a[i];
		if (n<6)
		{
			cout<<"NOn";
			continue;
		}
		int p=1;
		for (int i=2;i<=n;i++) if (a[i].x<a[p].x||(a[i].x==a[p].x)&&(a[i].y<a[p].y)) p=i;
		swap(a[1],a[p]);
		sort(a+2,a+1+n,cmp);
//		cout<<dis(P(0,0),P(1,0))<<dis(P(0,0),P(1,0));
		if (solve()) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}

备注：不知为何，将sqr替换成define 结果会输出"nan"……彩蛋？



CF 264B(质因数分解)

Posted on by
D. Good Sequences
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

数列 n 有 a1, a2, ..., an 个数（严格递增），请从中任意删去一些数，使序列相邻2数都不互质。

问删后序列最长长度.

Input

第一行 n (1 ≤ n ≤ 105)
第二行序列 a1, a2, ..., an (1 ≤ ai ≤ 105; ai < ai + 1).

Output

删后序列最长长度.

Sample test(s)
input
5
2 3 4 6 9
output
4
input
9
1 2 3 5 6 7 8 9 10
output
4
Note

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

错解：枚举开头即可。X

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN];
bool b[MAXN]={0};
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);};
int main()
{
	scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int ans=0;
	for (int i=1;i<=n;i++)
	if (!b[i])
	{
		int len=1;
		b[i]=1;
		int head=i,tail=i+1;
		while (tail<=n)
		{
			if (gcd(a[tail],a[head])==1) tail++;
			else {b[head]=1;head=tail;tail++;len++;	}
		}
		ans=max(ans,len);
	}
	cout<<ans<<endl;

	return 0;
}

更正：

枚举开头不行，因为一个开头可能跟有多个序列（2，6，9）/（2，4）←选这个不忧

故枚举质因数，证明下：

若a和b不互质,则必存在质数k，使k|a&&k|b

故Dp如下:

 f[i,j]=max(f[i-1,k]+1) (k| a[i] 且j|a[i] ) 最大值len=f[i,j] 

//  f[i,j]  表示到第i个数为止，结尾是质数 j 的倍数的最大长度。

+上滚动数组后，得到如下的Dp方程

计算： len=max(f[k])+1 (k| a[i] )

更新：f[j]=max(f[j],len) (j|a[i]) 


注意质因数的分解中 先分解到√n，若此时未除尽，那一部分也要算进去（肯定是质数，否则必能再分）

eg：14=2*7（7=√49>√14）


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
int n,a[MAXN],f[MAXN]={0},st[MAXN],size;
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);};
void fac_prime(int x)
{
	size=0;
	for (int j=2;j*j<=x;j++)
	{
		if (x%j==0)
		{
			while (x%j==0) x/=j;
			st[++size]=j;
		}
	}
	if (x>1) st[++size]=x;
}
int main()
{
	scanf("%d",&n);
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if (a[i]==1) {ans=max(ans,1);continue;}
		fac_prime(a[i]);
		int len=0;
		if (st[1]==a[i]) {len=1;f[a[i]]=1;}
		else
			for (int j=1;j<=size;j++)
				len=max(len,f[st[j]]+1);

		for (int j=1;j<=size;j++) f[st[j]]=max(f[st[j]],len);
		ans=max(ans,len);
//		for (int j=1;j<=a[i];j++) cout<<f[j]<<' ';
//		cout<<endl;
	}
	cout<<ans<<endl;
	return 0;
}



CF 264A(向内的双向队列)

Posted on by
C. Escape from Stones
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Squirrel Liss lived in a forest peacefully, but unexpected trouble happens. Stones fall from a mountain. Initially Squirrel Liss occupies an interval [0, 1]. Next, n stones
will fall and Liss will escape from the stones. The stones are numbered from 1 to n in order.

The stones always fall to the center of Liss's interval. When Liss occupies the interval [k - d, k + d] and a stone falls to k,
she will escape to the left or to the right. If she escapes to the left, her new interval will be [k - d, k]. If she escapes to the right,
her new interval will be [k, k + d].

You are given a string s of length n. If the i-th
character of s is "l" or "r",
when the i-th stone falls Liss will escape to the left or to the right, respectively. Find the sequence of stones' numbers from left to right after all
the n stones falls.

Input

The input consists of only one line. The only line contains the string s (1 ≤ |s| ≤ 106).
Each character in s will be either "l" or "r".

Output

Output n lines — on the i-th line you should print
the i-th stone's number from the left.

Sample test(s)
input
llrlr
output
3
5
4
2
1
input
rrlll
output
1
2
5
4
3
input
lrlrr
output
2
4
5
3
1
Note

In the first example, the positions of stones 1, 2, 3, 4, 5 will be , respectively. So you should print the sequence: 3, 5, 4, 2, 1.

不能用模拟double+除法，会爆精度啊！！（long double 也不行）

其实只要根据性质，在序列前后添加即可。

靠，人生中的处女Hack，竟然是被Hack…(受？）


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (1000000+10)
//pair<double,int> a[MAXN];
char s[MAXN];
int n,a[MAXN];
int main()
{
	scanf("%s",&s);
	n=strlen(s);
	int l=1,r=n;
	for (int i=0;i<n;i++)
	{
		if (s[i]=='l') a[r--]=i+1;
		else a[l++]=i+1;
	}



	for (int i=1;i<=n;i++) cout<<a[i]<<endl;



}

CF 265B(行道树简化版)

Posted on by
B. Roadside Trees (Simplified Edition)
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

 从西向东有 n 棵树，编号 1 到 n ，树顶有nuts.第 i 棵树高 hi.
Liss 想吃所有的 nuts.

Liss 在第1棵树的高度为1的地方. Liss 做下列任意一件事情耗时1s:

  • 向树的上方或下方移动1格.
  • 吃树顶的 nut .
  • 向东边那棵树跳(不能向西跳),高度不变，注意Liss不能从高的地方往低跳。

算出Liss吃掉所有nuts最短时间.

Input

第一行为 n (1  ≤  n ≤ 105)
.

接下来n行为序列 hi (1 ≤ hi ≤ 104)
.

Output

算出Liss吃掉所有nuts最短时间.

Sample test(s)
input
2
1
2
output
5
input
5
2
1
2
1
1
output
14

注意不能往西跳（一开始以为可以，看题仔细啊！）


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define MAXHi (10000+10)
int n,h[MAXN];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>h[i];h[0]=1;
	int ans=0;
	for (int i=1;i<=n;i++) ans+=abs(h[i]-h[i-1]);
/*
	int hmin=h[n];
	for (int i=n-1;i>=1;i--)
	{
		ans=min(ans,ans-abs(h[i]-h[i-1])-abs(h[i+1]-h[i])+abs(h[i-1]-h[i+1])+n-i+abs(hmin-h[i])+abs(hmin-h[n]));
	}
*/
	ans+=2*n;
	cout<<ans<<endl;
	return 0;
}