CF 264B(质因数分解)

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 ≤ 105ai < 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(向内的双向队列)

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(行道树简化版)

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

CF 265A(彩石简化版)

A. Colorful Stones (Simplified Edition)
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

有一排彩色的石头,用字符串 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)

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

0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10

Sample Output

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

Source


注意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

do

{

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




extern

基本解释:extern可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中提示编译器遇到此变量和函数时在其他模块中寻找其定义。此外extern也可用来进行链接指定。

      也就是说extern有两个作用,第一个,当它与"C"一起连用时,如: extern "C" void fun(int a, int b);则告诉编译器在编译fun这个函数名时按着C的规则去翻译相应的函数名而不是C++的,C++的规则在翻译这个函数名时会把fun这个名字变得面目全非,可能是fun@aBc_int_int#%$也可能是别的,这要看编译器的"脾气"了(不同的编译器采用的方法不一样),为什么这么做呢,因为C++支持函数的重载啊,在这里不去过多的论述这个问题,如果你有兴趣可以去网上搜索,相信你可以得到满意的解释!
    第二,当extern不与"C"在一起修饰变量或函数时,如在头文件中: extern int g_Int; 它的作用就是声明函数或全局变量的作用范围的关键字,其声明的函数和变量可以在本模块活其他模块中使用,记住它是一个声明不是定义!也就是说B模块(编译单元)要是引用模块(编译单元)A中定义的全局变量或函数时,它只要包含A模块的头文件即可,在编译阶段,模块B虽然找不到该函数或变量,但它不会报错,它会在连接时从模块A生成的目标代码中找到此函数。

2 问题:extern 变量
  在一个源文件里定义了一个数组:char a[6];
  在另外一个文件里用下列语句进行了声明:extern char *a;
  请问,这样可以吗? 
  答案与分析:
  1)、不可以,程序运行时会告诉你非法访问。原因在于,指向类型T的指针并不等价于类型T的数组。extern char *a声明的是一个指针变量而不是字符数组,因此与实际的定义不同,从而造成运行时非法访问。应该将声明改为extern char a[ ]
  2)、例子分析如下,如果a[] = "abcd",则外部变量a=0x61626364 (abcd的ASCII码值),*a显然没有意义
  显然a指向的空间(0x61626364)没有意义,易出现非法内存访问。
  3)、这提示我们,在使用extern时候要严格对应声明时的格式,在实际编程中,这样的错误屡见不鲜。
  4)、extern用在变量声明中常常有这样一个作用,你在*.c文件中声明了一个全局的变量,这个全局的变量如果要被引用,就放在*.h中并用extern来声明

3 问题:当方面修改extern 函数原型
  当函数提供方单方面修改函数原型时,如果使用方不知情继续沿用原来的extern申明,这样编译时编译器不会报错。但是在运行过程中,因为少了或者多了输入参数,往往会照成系统错误,这种情况应该如何解决?
  答案与分析:
  目前业界针对这种情况的处理没有一个很完美的方案,通常的做法是提供方在自己的xxx_pub.h中提供对外部接口的声明,然后调用方include该头文件,从而省去extern这一步。以避免这种错误。
  宝剑有双锋,对extern的应用,不同的场合应该选择不同的做法。

4 问题:extern “C”
  在C++环境下使用C函数的时候,常常会出现编译器无法找到obj模块中的C函数定义,从而导致链接失败的情况,应该如何解决这种情况呢?

  答案与分析:
  C++语言在编译的时候为了解决函数的多态问题,会将函数名和参数联合起来生成一个中间的函数名称,而C语言则不会,因此会造成链接时找不到对应函数的情况,此时C函数就需要用extern “C”进行链接指定,这告诉编译器,请保持我的名称,不要给我生成用于链接的中间函数名。
  下面是一个标准的写法:
//在.h文件的头上
#ifdef __cplusplus
#if __cplusplus
extern "C"{
 #endif
 #endif /* __cplusplus */ 
 …
 …
 //.h文件结束的地方
 #ifdef __cplusplus
 #if __cplusplus
}
#endif
#endif /* __cplusplus */ 

5 问题:extern 函数声明
  常常见extern放在函数的前面成为函数声明的一部分,那么,C语言的关键字extern在函数的声明中起什么作用?
  答案与分析:
  如果函数的声明中带有关键字extern,仅仅是暗示这个函数可能在别的源文件里定义,没有其它作用。即下述两个函数声明没有明显的区别:
extern int f(); 和int f();
  当然,这样的用处还是有的,就是在程序中取代include “*.h”来声明函数,在一些复杂的项目中,我比较习惯在所有的函数声明前添加extern修饰。关于这样做的原因和利弊可见下面的这个例子:“用extern修饰的全局变量”

    (1) 在test1.h中有下列声明:
    #ifndef TEST1H
    #define TEST1H
    extern char g_str[]; // 声明全局变量g_str
    void fun1();
    #endif
    (2) 在test1.cpp中
    #include "test1.h"
        char g_str[] = "123456"; // 定义全局变量g_str
        void fun1() { cout << g_str << endl; }
    (3) 以上是test1模块, 它的编译和连接都可以通过,如果我们还有test2模块也想使用g_str,只需要在原文件中引用就可以了
    #include "test1.h"

     void fun2()    { cout << g_str << endl;    }
    以上test1和test2可以同时编译连接通过,如果你感兴趣的话可以用ultraEdit打开test1.obj,你可以在里面找到"123456"这个字符串,但是你却不能在test2.obj里面找到,这是因为g_str是整个工程的全局变量,在内存中只存在一份,test2.obj这个编译单元不需要再有一份了,不然会在连接时报告重复定义这个错误!
    (4) 有些人喜欢把全局变量的声明和定义放在一起,这样可以防止忘记了定义,如把上面test1.h改为
    extern char g_str[] = "123456"; // 这个时候相当于没有extern
    然后把test1.cpp中的g_str的定义去掉,这个时候再编译连接test1和test2两个模块时,会报连接错误,这是因为你把全局变量g_str的定义放在了头文件之后,test1.cpp这个模块包含了test1.h所以定义了一次g_str,而test2.cpp也包含了test1.h所以再一次定义了g_str,这个时候连接器在连接test1和test2时发现两个g_str。如果你非要把g_str的定义放在test1.h中的话,那么就把test2的代码中#include
"test1.h"去掉 
换成:
    extern char g_str[];
    void fun2()   {  cout << g_str << endl;   }
   这个时候编译器就知道g_str是引自于外部的一个编译模块了,不会在本模块中再重复定义一个出来,但是我想说这样做非常糟糕,因为你由于无法在test2.cpp中使用#include "test1.h",那么test1.h中声明的其他函数你也无法使用了,除非也用都用extern修饰,这样的话你光声明的函数就要一大串,而且头文件的作用就是要给外部提供接口使用的,所以 请记住, 只在头文件中做声明,真理总是这么简单

6. extern 和 static

 (1) extern 表明该变量在别的地方已经定义过了,在这里要使用那个变量.
 (2) static 表示静态的变量,分配内存的时候, 存储在静态区,不存储在栈上面.

    static 作用范围是内部连接的关系, 和extern有点相反.它和对象本身是分开存储的,extern也是分开存储的,但是extern可以被其他的对象用extern 引用,而static 不可以,只允许对象本身用它. 具体差别首先,static与extern是一对“水火不容”的家伙,也就是说extern和static不能同时修饰一个变;其次,static修饰的全局变量声明与定义同时进行,也就是说当你在头文件中使用static声明了全局变量后,它也同时被定义了;最后,static修饰全局变量的作用域只能是本身的编译单元,也就是说它的“全局”只对本编译单元有效,其他编译单元则看不到它,如:
    (1) test1.h:
    #ifndef TEST1H
    #define TEST1H
    static char g_str[] = "123456"; 
    void fun1();
    #endif

    (2) test1.cpp:
    #include "test1.h"
    void fun1()  {   cout << g_str << endl;  }
    (3) test2.cpp
    #include "test1.h"
    void fun2()  {   cout << g_str << endl;  }
    以上两个编译单元可以连接成功, 当你打开test1.obj时,你可以在它里面找到字符串"123456",同时你也可以在test2.obj中找到它们,它们之所以可以连接成功而没有报重复定义的错误是因为虽然它们有相同的内容,但是存储的物理地址并不一样,就像是两个不同变量赋了相同的值一样,而这两个变量分别作用于它们各自的编译单元。 也许你比较较真,自己偷偷的跟踪调试上面的代码,结果你发现两个编译单元(test1,test2)的g_str的内存地址相同,于是你下结论static修饰的变量也可以作用于其他模块,但是我要告诉你,那是你的编译器在欺骗你,大多数编译器都对代码都有优化功能,以达到生成的目标程序更节省内存,执行效率更高,当编译器在连接各个编译单元的时候,它会把相同内容的内存只拷贝一份,比如上面的"123456",
位于两个编译单元中的变量都是同样的内容,那么在连接的时候它在内存中就只会存在一份了,如果你把上面的代码改成下面的样子,你马上就可以拆穿编译器的谎言:
    (1) test1.cpp:
    #include "test1.h"
    void fun1()
    {
        g_str[0] = ''a'';
        cout << g_str << endl;
    }

    (2) test2.cpp
    #include "test1.h"
    void fun2()  {  cout << g_str << endl;  }
    (3) void main()     {
        fun1(); // a23456
        fun2(); // 123456
    }
    这个时候你在跟踪代码时,就会发现两个编译单元中的g_str地址并不相同,因为你在一处修改了它,所以编译器被强行的恢复内存的原貌,在内存中存在了两份拷贝给两个模块中的变量使用。正是因为static有以上的特性,所以一般定义static全局变量时,都把它放在原文件中而不是头文件,这样就不会给其他模块造成不必要的信息污染,同样记住这个原则吧!

7. extern 和const

   C++中const修饰的全局常量据有跟static相同的特性,即它们只能作用于本编译模块中,但是const可以与extern连用来声明该常量可以作用于其他编译模块中, 如extern const char g_str[];
    然后在原文件中别忘了定义:     const char g_str[] = "123456"; 

    所以当const单独使用时它就与static相同,而当与extern一起合作的时候,它的特性就跟extern的一样了!所以对const我没有什么可以过多的描述,我只是想提醒你,const char* g_str = "123456" 与 const char g_str[] ="123465"是不同的, 前面那个const 修饰的是char *而不是g_str,它的g_str并不是常量,它被看做是一个定义了的全局变量(可以被其他编译单元使用), 所以如果你像让char*g_str遵守const的全局常量的规则,最好这么定义const
char* const g_str="123456".

auto和static

auto仅在语句块内部使用,初始化可为任何表达式,其特点是当执行流程进入该语句块的时候执行初始化操作,没有默认值。C语言中提供了存储说明符auto,register,extern,static说明的四种存储类别。四种存储类别说明符有两种存储期:自动存储期和静态存储期。其中auto和register对应自动存储期。具有自动存储期的变量在进入声明该变量的程序块时被建立,它在该程序块活动时存在,退出该程序块时撤销。在函数内部定义的变量成为局部变量。在某些C语言教材中,局部变量称为自动变量,这就与使用可选关键字a
u t o定义局部变量这一作法保持一致。

局部变量仅由其被定义的模块内部的语句所访问。换言之,局部变量在自己的代码模块之外是不可知的。切记:模块以左花括号开始,以右花括号结束。对于局部变量,要了解的最重要的东西是:它们仅存在于被定义的当前执行代码块中,即局部变量在进入模块时生成,在退出模块时消亡。定义局部变量的最常见的代码块是函数。 语言中包括了关键字auto,它可用于定义局部变量。但自从所有的非全局变量的缺省值假定为auto以来,auto就几乎很少使用了。

在C或者以前的C++中,auto关键字基本上可以被无视:比如这个局部变量:int a = 100;auto int a = 100;并没有什么区别。

但是在VC2010中,auto已经有了新的含义,它可以对类型进行推断使得我们在使用的时候可以这样auto a = 100;那么a就是int类型,初始值为100。

Static

静态变量作用范围在一个文件内,程序开始时分配空间,结束时释放空间,默认初始化为0,使用时可以改变其值。

    静态变量或静态函数只有本文件内的代码才能访问它,它的名字在其它文件中不可见。
用法1:函数内部声明的static变量,可作为对象间的一种通信机制
    如果一局部变量被声明为static,那么将只有唯一的一个静态分配的对象,它被用于在该函数的所有调用中表示这个变量。这个对象将只在执行线程第一次到达它的定义使初始化。
用法2:局部静态对象
    对于局部静态对象,构造函数是在控制线程第一次通过该对象的定义时调用。在程序结束时,局部静态对象的析构函数将按照他们被构造的相反顺序逐一调用,没有规定确切时间。
 用法3:静态成员和静态成员函数
  如果一个变量是类的一部分,但却不是该类的各个对象的一部分,它就被成为是一个static静态成员。一个static成员只有唯一的一份副本,而不像常规的非static成员那样在每个对象里各有一份副本。同理,一个需要访问类成员,而不需要针对特定对象去调用的函数,也被称为一个static成员函数。
类的静态成员函数只能访问类的静态成员(变量或函数)。

    进一步详细解释如下:

1.先来介绍它的第一条也是最重要的一条:隐藏

     当我们同时编译多个文件时,所有未加static前缀的全局变量和函数都具有全局可见性。为理解这句话,我举例来说明。我们要同时编译两个源文件,一个是a.c,另一个是main.c. 下面是a.c的内容:

char a = 'A'; // global variable

void msg() { printf("Hellon"); }

    下面是main.c的内容:

int main(void) { 

    extern char a; // extern variable must be declared before use

    printf("%c ", a);

    (void)msg();

    return 0;  }

    程序的运行结果是:

A Hello

    你可能会问:为什么在a.c中定义的全局变量a和函数msg能在main.c中使用?前面说过,所有未加static前缀的全局变量和函数都具有全局可见性,其它的源文件也能访问。此例中,a是全局变量,msg是函数,并且都没有加static前缀,因此对于另外的源文件main.c是可见的。

如果加了static,就会对其它源文件隐藏。例如在a和msg的定义前加上static,main.c就看不到它们了。利用这一特性可以在不同的文件中定义同名函数和同名变量,而不必担心命名冲突。Static可以用作函数和变量的前缀,对于函数来讲,static的作用仅限于隐藏,而对于变量,static还有下面两个作用。

2. static的第二个作用是保持变量内容的持久

    存储在静态数据区的变量会在程序刚开始运行时就完成初始化,也是唯一的一次初始化。共有两种变量存储在静态存储区:全局变量和static变量,只不过和全局变量比起来,static可以控制变量的可见范围,说到底static还是用来隐藏的。虽然这种用法不常见,但我还是举一个例子。

#include <stdio.h>

 int fun(void){

static int count = 10; // 事实上此赋值语句从来没有执行过

 return count--;

 }

 int count = 1;

int main(void) {

printf("globalttlocal staticn");

 for(; count <= 10; ++count)

    printf("%dtt%dn", count, fun());

 return 0; }

    程序的运行结果是:

global local static
1  10
2   9
3   8
4   7
5   6
6   5
7   4
8   3
9   2
10  1

3. static的第三个作用是默认初始化为0.其实全局变量也具备这一属性,因为全局变量也存储在静态数据区

注意:

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int& hash(int x)
{
	static int t=x*2;
	return t;
}
int main()
{
	hash(2);
	hash(3);
	cout<<hash(2)<<hash(3);

	return 0;
}

这段代码中,返回值为4,4.

hash(2) 和  hash(3) 表示同一个函数.

想写hash还是老老实实用Map吧~

    在静态数据区,内存中所有的字节默认值都是0x00,某些时候这一特点可以减少程序员的工作量。比如初始化一个稀疏矩阵,我们可以一个一个地把所有元素都置0,然后把不是0的几个元素赋值。如果定义成静态的,就省去了一开始置0的操作。再比如要把一个字符数组当字符串来用,但又觉得每次在字符数组末尾加‘’太麻烦。如果把字符串定义成静态的,就省去了这个麻烦,因为那里本来就是‘’。不妨做个小实验验证一下。

#include <stdio.h>

 int a;

int main(void){

int i;

static char str[10];

printf("integer: %d; string: (begin)%s(end)", a, str);

 return 0;

 }

    程序的运行结果如下integer: 0; string: (begin)(end)

    最后对static的三条作用做一句话总结。首先static的最主要功能是隐藏,其次因为static变量存放在静态存储区,所以它具备持久性和默认值0.

4. 用static声明的函数和变量小结

    static 声明的变量在C语言中有两方面的特征:

1)、变量会被放在程序的全局存储区中,这样可以在下一次调用的时候还可以保持原来的赋值。这一点是它与堆栈变量和堆变量的区别。

2)、变量用static告知编译器,自己仅仅在变量的作用范围内可见。这一点是它与全局变量的区别。

 Tips:
A.若全局变量仅在单个C文件中访问,则可以将这个变量修改为静态全局变量,以降低模块间的耦合度;
B.若全局变量仅由单个函数访问,则可以将这个变量改为该函数的静态局部变量,以降低模块间的耦合度;
C.设计和使用访问动态全局变量、静态全局变量、静态局部变量的函数时,需要考虑重入问题;
D.如果我们需要一个可重入的函数,那么,我们一定要避免函数中使用static变量(这样的函数被称为:带“内部存储器”功能的的函数)
E.函数中必须要使用static变量情况:比如当某函数的返回值为指针类型时,则必须是static的局部变量的地址作为返回值,若为auto类型,则返回为错指针。

    函数前加static使得函数成为静态函数。但此处“static”的含义不是指存储方式,而是指对函数的作用域仅局限于本文件(所以又称内部函数)。使用内部函数的好处是:不同的人编写不同的函数时,不用担心自己定义的函数,是否会与其它文件中的函数同名。

扩展分析:

     术语static有着不寻常的历史.起初,在C中引入关键字static是为了表示退出一个块后仍然存在的局部变量。随后,static在C中有了第二种含义:用来表示不能被其它文件访问的全局变量和函数。为了避免引入新的关键字,所以仍使用static关键字来表示这第二种含义。最后,C++重用了这个关键字,并赋予它与前面不同的第三种含义:表示属于一个类而不是属于此类的任何特定对象的变量和函数(与Java中此关键字的含义相同)。

全局变量、静态全局变量、静态局部变量和局部变量的区别

变量可以分为:全局变量、静态全局变量、静态局部变量和局部变量。

(1) 按存储区域分,全局变量、静态全局变量和静态局部变量都存放在内存的静态存储区域,局部变量存放在内存的栈区。

(2) 按作用域分,  全局变量在整个工程文件内都有效;静态全局变量只在定义它的文件内有效;静态局部变量只在定义它的函数内有效,只是程序仅分配一次内存,函数返回后,该变量不会消失;局部变量在定义它的函数内有效,但是函数返回后失效。

     全局变量(外部变量)的说明之前再冠以static就构成了静态的全局变量。全局变量本身就是静态存储方式,静态全局变量当然也是静态存储方式。这两者在存储方式上并无不同。这两者的区别虽在于非静态全局变量的作用域是整个源程序,当一个源程序由多个源文件组成时,非静态的全局变量在各个源文件中都是有效的。 而静态全局变量则限制了其作用域,即只在定义该变量的源文件内有效,在同一源程序的其它源文件中不能使用它。由于静态全局变量的作用域局限于一个源文件内,只能为该源文件内的函数公用,因此可以避免在其它源文件中引起错误。

    从以上分析可以看出, 把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期。把全局变量改变为静态变量后是改变了它的作用域, 限制了它的使用范围。

(1) static 函数与普通函数作用域不同。仅在本文件。只在当前源文件中使用的函数应该说明为内部函数(static),内部函数应该在当前源文件中说明和定义。对于可在当前源文件以外使用的函数,应该在一个头文件中说明,要使用这些函数的源文件要包含这个头文件

(2) static全局变量与普通的全局变量有什么区别:static全局变量只初始化一次,防止在其他文件单元中被引用;

(3) static局部变量和普通局部变量有什么区别:static局部变量只被初始化一次,下一次依据上一次结果值;
(4) static函数与普通函数有什么区别:static函数在内存中只有一份,普通函数在每个被调用中维持一份拷贝.
(5) 全局变量和静态变量如果没有手工初始化,则由编译器初始化为0。局部变量的值不可知。

5. C++的static

    C++的static有两种用法:面向过程程序设计的static和面向对象程序设计中的static。前者应用于普通变量和函数,不涉及类;后者主要说明static在类中的作用。

(1)、面向过程设计中的static

1)、静态全局变量

在全局变量前,加上关键字static,该变量就被定义成为一个静态全局变量。我们先举一个静态全局变量的例子,如下: 

//Example 1

#include <iostream.h>

void fn();

static int n; //定义静态全局变量

void main()

{

 n=20;

 cout<<n<<endl;

 fn();

}

void fn()

{

 n++;

 cout<<n<<endl;

}

    静态全局变量有以下特点:  

 i )  该变量在全局数据区分配内存;
  ii )  未经初始化的静态全局变量会被程序自动初始化为0(自动变量的值是随机的,除非它被显式初始化);   
  iii ) 静态全局变量在声明它的整个文件都是可见的,而在文件之外是不可见的;

    静态变量都在全局数据区分配内存,包括后面将要提到的静态局部变量。对于一个完整的程序,在内存中的分布情况如下图:

代码区

全局数据区

堆区

栈区

  一般程序的由new产生的动态数据存放在堆区,函数内部的自动变量存放在栈区。自动变量一般会随着函数的退出而释放空间,静态数据(即使是函数内部的静态局部变量)也存放在全局数据区。全局数据区的数据并不会因为函数的退出而释放空间。细心的读者可能会发现,Example 1中的代码中将 

 static int n; //定义静态全局变量

改为 

 int n; //定义全局变量

    程序照样正常运行。的确,定义全局变量就可以实现变量在文件中的共享,但定义静态全局变量还有以下好处: 

1) 静态全局变量不能被其它文件所用;  

2) 其它文件中可以定义相同名字的变量,不会发生冲突; 

您可以将上述示例代码改为如下:

//Example 2

//File1

#include <iostream.h>

void fn();

static int n; //定义静态全局变量

void main()

{

 n=20;

 cout<<n<<endl;

 fn();

}

//File2

#include <iostream.h>

extern int n;

void fn()

{

 n++;

 cout<<n<<endl;

}

    编译并运行Example 2,您就会发现上述代码可以分别通过编译,但运行时出现错误。试着将  

static int n; //定义静态全局变量

改为  

int n; //定义全局变量

    再次编译运行程序,细心体会全局变量和静态全局变量的区别。  

(2)、静态局部变量

     在局部变量前,加上关键字static,该变量就被定义成为一个静态局部变量。 我们先举一个静态局部变量的例子,如下: 

//Example 3

#include <iostream.h>

void fn();

void main()

{

 fn();

 fn();

 fn();

}

void fn()

{

 static n=10;

 cout<<n<<endl;

 n++;

}

  通常,在函数体内定义了一个变量,每当程序运行到该语句时都会给该局部变量分配栈内存。但随着程序退出函数体,系统就会收回栈内存,局部变量也相应失效。但是有时候我们需要在两次调用之间对变量的值进行保存。通常的想法是定义一个全局变量来实现。但这样一来,变量已经不再属于函数本身了,不再仅受函数的控制,给程序的维护带来不便。  静态局部变量正好可以解决这个问题。静态局部变量保存在全局数据区,而不是保存在栈中,每次的值保持到下



POJ 2187(凸包GrahamScan扫描+极角排序+平面最远点对)

Language:
平面最远点对
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 22454   Accepted: 6868

Description

求 N (2 <= N <= 50,000) 个点平面最远点对距离平方. 

Input

* 第1行:N 

接下来每行为点的坐标 x 和 y ,(x,y)(-10,000<=x,y<=10,000的整数). 

Output

输出一行,为平面最远点对距离平方. 

Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

2

Hint

(0, 0) a到 (1, 1) 距离平方为 2 

Source

凸包模版题

先用GrahamScan扫描求凸包,显然最远点对在凸包上。


极角排序:

按照逆时针顺序给平面上的点集到一个点的距离排序,使得排序后所有点正好绕这个点一圈.(按距离远近从小到大排

思路:


GrahamScan扫描:







大致如此.


另补:

该题小Bug-有可能所有点在一条直线上。

这样也能求出:

Ex:

a序列(-1,0) (0,0)    (4,0)   (9,0)

则st序列重复如下操作:

(-1,1),(0,0)入队。

(4,0)入队,不左拐->(0,0)出队

队列元素<2 (4,0)入队

……


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (50000+10)
double sqr(double x){return x*x;}
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
}a[MAXN],st[MAXN];
int dis2(P A,P B)
{
	return sqr(A.x-B.x)+sqr(A.y-B.y);
}
double dis(P A,P B)
{
	return sqrt(double(dis2(A,B)));
}
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P A,P B):x(B.x-A.x),y(B.y-A.y){}
};
double operator*(V a,V b)
{
	return a.x*b.y-a.y*b.x;
}
int cmp(P A,P B) //1:a>b 0:a<=b
{
	double tmp=V(a[1],A)*V(a[1],B);
	if (tmp>0) return 1;
	else if (tmp==0) return (-(dis(a[1],A)-dis(a[1],B))>0)?1:0;
	else return 0;
}
int n;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	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;
	if (p>1) swap(a[p],a[1]);
	sort(a+2,a+1+n,cmp);

	int size=1;
	st[1]=a[1];
	for (int i=2;i<=n;)
		if (size<2||V(st[size-1],st[size])*V(st[size],a[i])>0)
			st[++size]=a[i++];
		else size--;

	int ans=0;
	for (int i=1;i<size;i++)
		for (int j=i+1;j<=size;j++)
			ans=max(ans,dis2(st[i],st[j]));
	cout<<ans<<endl;


	return 0;
}







POJ 1442(Treap)

Language:
Black Box
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 5156   Accepted: 2085

Description

Black Box 代表数据库。(开始为空)
有2种操作
ADD (x): 向库添加一个x; 
GET: 第i次执行时输出数列中第i大的数. 

Example 1 

N Transaction i Black Box contents after transaction Answer

      (elements 升序排列)

1 ADD(3)      0 3

2 GET         1 3                                    3

3 ADD(1)      1 1, 3

4 GET         2 1, 3                                 3

5 ADD(-4)     2 -4, 1, 3

6 ADD(2)      2 -4, 1, 2, 3

7 ADD(8)      2 -4, 1, 2, 3, 8

8 ADD(-1000)  2 -1000, -4, 1, 2, 3, 8

9 GET         3 -1000, -4, 1, 2, 3, 8                1

10 GET        4 -1000, -4, 1, 2, 3, 8                2

11 ADD(2)     4 -1000, -4, 1, 2, 2, 3, 8   

ADD 和 GET 操作数不超过 30000 . 

操作描述如下:
1. A(1), A(2), ..., A(M): Add 序列,|x|≤2 000 000 000 , M <= 30000. 样例中 A=(3, 1, -4, 2, 8, -1000, 2). 

2. u(1), u(2), ..., u(N):GET的询问时间,第i个GET将在第u(i)读完后执行.样例中 u=(1, 2, 6, 6). 

Input

第一行: M, N, 第二行序列A, 第三行序列u.

Output

第i行输出第i个GET的输出

Sample Input

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

Sample Output

3
3
1
2

Source


此题可用二叉搜索树解决。

二叉搜索树的建立:每拿到一个元素,比根小放在左根,比根大放在右根,否则放根上。

t.weight 表示结点上有几个数, t.key表示数的值 ,t.size表示以该点为根的树上有多少数

重点是左旋和右旋!

2个注意:注意把a的父亲结点改掉,注意把a,b的父亲结点改掉


下图转载自http://dongxicheng.org/structure/treap/



#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXM (30000+10)
#define MAXN (30000+10)
struct tree_node
{
	int key,fim,size,weight;
	tree_node *left,*right,*father;
	int l_size()
	{
		return (left==NULL)?0:(left->size);
	}
	int r_size()
	{
		return (right==NULL)?0:(right->size);
	}
	void count_size()
	{
		//size=(left==NULL)?0:(left->size)+(right==NULL)?0:(right->size)+weight;
		size=l_size()+r_size()+weight;
	}
	tree_node():key(0),fim(rand()),size(0),weight(0){left=right=father=NULL;}
	tree_node(int _key):key(_key),fim(rand()),size(1),weight(1){left=right=father=NULL;}
};
tree_node* newnode(int key)
{
	tree_node* p;
	p=new tree_node;
	*p=tree_node(key);
	return p;
}
struct Treep
{
	tree_node *root;
	Treep(){root=NULL;}
	void left_rotaue(tree_node *&a)
	{
		tree_node* b=a->right;
		a->right=b->left;if (a->right!=NULL) a->right->father=a;
		b->left=a;b->father=a->father;a->father=b;
		a->count_size();
		b->count_size();
		if (b->father)
		{
			if (b->father->left==a) b->father->left=b;
			else b->father->right=b;
		}
		a=b;
	}
	void right_rotaue(tree_node *&a)
	{
		tree_node* b=a->left;
		a->left=b->right;if (a->left!=NULL) a->left->father=a;
		b->right=a;
		b->father=a->father;
		a->father=b;
		a->count_size();
		b->count_size();
		if (b->father)
		{
			if (b->father->left==a) b->father->left=b;
			else b->father->right=b;
		}
		a=b;
	}
	void insert(int key)
	{
		if (root==NULL) {root=newnode(key);return;}
		tree_node *now=root;
		while (1)
		{
			now->size++;
			if (key==now->key) {now->weight++;break;}
			else if (key<now->key)
			{
				if (now->left==NULL) {now->left=newnode(key);now->left->father=now; now=now->left; break;}
				else now=now->left;
			}
			else
			{
				if (now->right==NULL) {now->right=newnode(key);now->right->father=now; now=now->right; break;}
				else now=now->right;
			}
		}
		for (;now!=root&&now->father->fim<now->fim;)
		{
			if (now->key<now->father->key) {now=now->father; right_rotaue(now);}
			else {now=now->father; left_rotaue(now); }
			if (now->father==NULL) root=now;
		}

	}
	int gets(int k)
	{
		tree_node* now=root;
		while (1)
		{
			if (now->l_size()>=k) {now=now->left;}
			else if (now->l_size()+now->weight>=k) return now->key;
			else {k-=now->l_size()+now->weight; now=now->right;}
		}
	}
	void print(tree_node *now)
	{
		if (now->left!=NULL)
		{
			cout<<"( ";
			print(now->left);
			cout<<" )";
		}
		cout<<" "<<now->key<<" ";
		if (now->right!=NULL)
		{
			cout<<"( ";
			print(now->right);
			cout<<" )";
		}


	}
}t;
int n,m,a[MAXN],u[MAXM];
int main()
{
//	freopen("poj1442.in","r",stdin);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=m;i++) cin>>u[i];
	for (int i=1,j=1;i<=n;i++)
	{
		t.insert(a[i]);//t.print(t.root);cout<<endl;
		while (j<=m&&i==u[j]) {cout<<t.gets(j)<<endl;j++;}
	}
	return 0;
}