CF 264B(质因数分解)

Posted on 20 1 月, 2013 by nike0good

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

问删后序列最长长度.

Input

第一行 n (1 ≤ n ≤ 10⁵)
第二行序列 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵; a_i < a_i + 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 20 1 月, 2013 by nike0good

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| ≤ 10⁶).
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 20 1 月, 2013 by nike0good

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

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

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

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

Input

第一行为 n (1 ≤ n ≤ 10⁵)
.

接下来n行为序列 h_i (1 ≤ h_i ≤ 10⁴)
.

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;
}

CF 265A(彩石简化版)

Posted on 20 1 月, 2013 by nike0good

有一排彩色的石头，用字符串 s 表示，第i个为"R",
"G", or "B"表示颜色。

Liss接到操作符，用"R",
"G",
or "B"表示，当Liss所在的彩石与操作符相同时，Liss向前走一格，否则不动。(Liss一开始在彩石1处)

现给定操作序列 t.

请输出Liss最后所占的彩色编号(假设Liss不会走出彩石)

Input

第一行 s (1 ≤ |s| ≤ 50). 第二行 t (1 ≤ |t| ≤ 50).

Output

输出一行Liss最后所占的彩色编号.

Sample test(s)

input
RGB
RRR

output
2

input
RRRBGBRBBB
BBBRR

output
3

input
BRRBGBRGRBGRGRRGGBGBGBRGBRGRGGGRBRRRBRBBBGRRRGGBBB
BBRBGGRGRGBBBRBGRBRBBBBRBRRRBGBBGBBRRBBGGRBRRBRGRB

output
15

模拟题，各种做

注意 scanf("%s%s",&s,&t); s和t都是从0开始的

字符串长度函数为strlen(s)

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (50+10)
char s[MAXN],t[MAXN];
int main()
{
	scanf("%s%s",&s,&t);
	int j=0;
	for (int i=0;i<strlen(t);i++)
	{
		if (t[i]==s[j]) j++;
	}
	cout<<1+j<<endl;


}

POJ 2007(卷包裹算法(Gift Wrapping Algorithm)+ostream)

Posted on 20 1 月, 2013 by nike0good

Language:

Scrambled Polygon

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 5602		Accepted: 2664

Description

凸包求法如图：

Input

点数不超过 50.每行输入的坐标为整数且范围在 -999..999. 数据以(0,0)开头,保证所有点必能构成凸包,除第1个点外没有点在坐标轴上或第二象限,没用三点共线.

Output

每行输出一个坐标(x,y)，以(0,0)开头,逆时针输出.

Sample Input

Sample Output

(0,0)
(-30,-40)
(-30,-50)
(-10,-60)
(50,-60)
(70,-50)
(90,-20)
(90,10)
(80,20)
(60,30)

Source

Rocky Mountain 2004

注意istream和ostream的写法

它必须是友元函数（如果是成员函数，则必须以const P为开头，这显然不行）

它返回一个指向ostream的指针，前面可以接ostream(cout<<a<<b;)，还有一个元素（要输入的）

friend ostream& operator<<(ostream& cout,P &a)

{
cout<<"("<<a.x<<','<<a.y<<')'<<endl;
//把要输出的内容推进输出流
return cout;
}

接下来讲卷包裹算法：

我们先找到一个在凸包上的点，然后卷过去

伪代码如下：

初始化st[]=0,j=0,endpoint=P0

{

将endpoint加入队列st.

找到任意从P0点出发，转向最右的点P

endpoint=P

}until endpoint=P0

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (50+10)
struct P
{
    int x,y;
    P(){}
    P(int _x,int _y):x(_x),y(_y){}
    friend ostream& operator<<(ostream& cout,P &a)
	{
		cout<<"("<<a.x<<','<<a.y<<')'<<endl;
		return cout;

	}
}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){}
};
int operator*(V a,V b)
{
    return a.x*b.y-a.y*b.x;
}
int n,st[MAXN];
int main()
{
//	freopen("poj2007.in","r",stdin);
    int n=1;
	while (scanf("%d%d",&a[n].x,&a[n].y)!=-1) n++; //scanf读入失败返回-1
    n--;

    int endpoint=1,j=1;
	do
	{
		cout<<a[st[j++]=endpoint];
		int k=(endpoint+1)%n+1;
		for (int i=1;i<=n;i++)
			if (endpoint!=i&&V(a[endpoint],a[i])*V(a[endpoint],a[k])>0) k=i;
		endpoint=k;
	//	cout<<endpoint<<' ';
	}while (endpoint!=1);


    return 0;
}

一	二	三	四	五	六	日
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

nike0good

有所作为是人生的最高境界

Daily Archives: 20 1 月, 2013

CF 264B(质因数分解)

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

CF 265B(行道树简化版)

CF 265A(彩石简化版)

POJ 2007(卷包裹算法(Gift Wrapping Algorithm)+ostream)