111qqz的小窝

老年咸鱼冲锋!

vimrc备份

codeforces # 317 div 2 B. Order Book(模拟)

B. Order Book
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

In this task you need to process a set of stock exchange orders and use them to create order book.

An order is an instruction of some participant to buy or sell stocks on stock exchange. The order number i has price pi, direction di — buy or sell, and integer qi. This means that the participant is ready to buy or sell qi stocks at price pi for one stock. A value qi is also known as a volume of an order.

All orders with the same price p and direction d are merged into one aggregated order with price p and direction d. The volume of such order is a sum of volumes of the initial orders.

An order book is a list of aggregated orders, the first part of which contains sell orders sorted by price in descending order, the second contains buy orders also sorted by price in descending order.

An order book of depth s contains s best aggregated orders for each direction. A buy order is better if it has higher price and a sell order is better if it has lower price. If there are less than s aggregated orders for some direction then all of them will be in the final order book.

You are given n stock exhange orders. Your task is to print order book of depth s for these orders.

Input

The input starts with two positive integers n and s (1 ≤ n ≤ 1000, 1 ≤ s ≤ 50), the number of orders and the book depth.

Next n lines contains a letter di (either ‘B’ or ‘S’), an integer pi (0 ≤ pi ≤ 105) and an integer qi (1 ≤ qi ≤ 104) — direction, price and volume respectively. The letter ‘B’ means buy, ‘S’ means sell. The price of any sell order is higher than the price of any buy order.

Output

Print no more than 2s lines with aggregated orders from order book of depth s. The output format for orders should be the same as in input.

Sample test(s)
input

output

Note

Denote (x, y) an order with price x and volume y. There are 3 aggregated buy orders (10, 3), (20, 4), (25, 10) and two sell orders (50, 8), (40, 1) in the sample.

You need to print no more than two best orders for each direction, so you shouldn’t print the order (10 3) having the worst price among buy orders.

 

昨天头疼。。然后觉得要掉。。就用小号打的。。。

结果涨了200+rating。。。。

这题就是纯模拟啊。。。

一遍ac。。。

需要注意的地方,如果说有。。。

大概就是,sell的是取最小的s个,要先从小到大排序。。。但是输出的时候又是从大到小排序。。。

昨天40分钟做完前2道题。。然后c题不会搞。。。就水群(求不鄙视> <),好像一堆人wa b wa得特别惨的样子。。。

codeforces #317 div2 A. Arrays (水)

 应该3分钟过的题。。。

结果花了8分钟。。。ssssad

bc #52 div 2 A ||hdoj5417 Victor and Machine (模拟)

傻逼模拟题

我做了半小时….

sssssad

bc #52 div 2 B || hdoj 5418 Victor and World(tsp问题,状压dp)

比赛的时候一看,tsp么

前些天好像刚写过一个clean robot什么的

然后发现n才16,而m很大..

应该有很多重复的.

那么我们取油费最少的.

然后先做一遍 floyd

之后我写了一个dfs…TLE 了…sad

正解是状压dp

虽然没写过状压dp

但是之前写过一道状态压缩的bfs

所以理解起来没有问题.

这道题的做法是: 

用dp[i][j]表示当前访问国家的状态为s,要访问的国家为j的时候的最小费用.i是二进制,i的第p位为1表示第p个国家已经访问过了,否则表示没有访问过.

那么状态转移方程则为:dp[i|(1<

初始化的时候d[i][i] =0,其他为inf

dp[0][0] 表示要访问第一个国家且没有访问国人国家的时候的状态,此时花费为0

然后先枚举访问国家的状态,再枚举访问的国家.

acm输出输出技巧(提交oj不需要改变)

 

这样写比较爽

交OJ什么都不用改

,妈妈再也不用担心我累死在输入样例&调试上了。。。

 

关于ACM的输入输出(一)

关于ACM的输入输出(一)

写给第一次参加现场赛的同学们

一般来说ACM的现场赛会规定输入输出

或者是文件输入标准输出

也可能是文件输入文件输出

如果没有规定的话那么一般就是标准的输入输出了

那说一下输入输出的重定向

一般用下面两种方法

c++常用:

#include

ifstream filein(“data.in”);   // 定义一个文件输入流

ofstream fileout(“data.out”); //cout<< --> fileout<<

filein.eof() //文件到末尾,返回非零值

 

data.in表示输入的数据文件

本地测试的话本来输入的数据就要在这个文件里面测试了

建一个本地的文本data.in,可以用记事本的方式打开

注意:文件输入的话,以后的cin>>都要改成filein>>, cout<<都要改成fileout<<

 

c语言常用:

freopen(“date.in”,”r”,stdin);  //重定向所有标准的输入为文件输入  

freopen(“date.out”,”w”,stdout);//重定向所有标准的输出为文件输出  

fclose(stdout);//输出结束 

freopen(“date.in”,”r”,stdin);  //重定向所有标准的输入为文件输入

freopen(“date.out”,”w”,stdout);//重定向所有标准的输出为文件输出

fclose(stdout);//输出结束

 

第一句的意思就是文件输入,以”读状态”,去替换标准的输入

以上如果只是规定用文件输入输出 的某一种,那么就只用其中的一种

 

 

 

 

 

 

 

 

关于ACM的输入输出(二)

 

ACM题目特点: 由于ACM竞赛题目的输入数据和输出数据一般有多组(不定),并且格式多种多样,所以,如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。 ACM的输入输出要求严格按照规定来,所以你不需要输出像”Please input the data”这类的提示语。否则将会被判Wrong Answer。 
1、输入 
初学者一般有个误区:如果题目包含多组测试数据,他们就会把输入的内容全部保存起来,然后再依次处理。
其实程序的输入/输出是相互独立的,因此,每当处理完一组测试数据,就应当按题目要求进行相应的输出操作。而不必将所有结果储存起来一起输出。 
下面来介绍一下ACM中常见的一些输入情况。 

只有一组测试数据 
这类题目是最简单的,比如第1000题。参考代码:
#include 
int main(void)
{
int a, b; 
scanf(“%d %d”, &a, &b);
printf(“%d/n”, a + b); 
return 0;

没有明确指出输入什么时候结束 
如果是这种情况,我们默认是以“文件结束”(EOF)为结束标志。
这是ACM的默规,例如1076题。参考代码: 

#include 
int main(void)
{
int a, b; 
while (scanf(“%d %d”, &a, &b) != EOF)
printf(“%d/n”, a + b); 
return 0;

指定数据量 
有时会在数据的第一行提供数据量大小,比如第一行是100,则表示有100组数据。比如第1077题。参考代码: 

#include 
int main(void)
{
int n, a, b; 
scanf(“%d”, &n);
while (n–)
{
scanf(“%d %d”, &a, &b);
printf(“%d/n”, a + b);

return 0;

以特定元素作结束符 
这种输入和第一种类似。常见的是规定以0作为结束符。
比如第1078题。参考代码:
 
#include 
int main(void)
{
int a, b; 

while (scanf(“%d %d”, &a, &b), a || b)
printf(“%d/n”, a + b); 

return 0;

输出 

输出格式统一 
这种比较简单,只要按要求来就没问题的。
比如每组输出占一行,或者每组输出后面加一个空行。比如1000题。 

数据之间有空行 
对于这种输出,有时候还会告诉你有几组输入,这样你就可以自己判断一下是不是最后一组。是就不输出空行,否则多输出一个空行。而有时候连共有几组数据都不会告诉你。其实不论知不知道有几组数据,我们都可以这样处理。

第一组数据后面不加空行。 
第二组开始,每组前面加空行。 比如第1079题,参考代码:

#include 
int main(void)
{
int a, b, i = 0; 
while (scanf(“%d %d”, &a, &b), a || b)
printf((i++? “/n%d/n”: “%d/n”), a + b); 
return 0;
}

 

 

 

关于ACM的输入输出(三)

 

在线判决系统是机器判题系统,也就是俗称的OJ(Online Judge),机器判决的一个特点就是必须100%的吻合才能判为正确,否则要么WA,PE。同时对于提交的程序还有一定的时间限制,如果超过时间则会判超时。OJ一般采用的是标准输入输出,所以提交的时候我们不必要使用文件读入输出(这与高中的信息学是不同的),机器判决只针对程序结果,不针对程序,所以很多时候直接提交数据也是可以的,俗称打表。
 

下面介绍常用的处理输入的方法

几种常用的处理输入方法(C语言) 
感觉新人对于处理输入输出存在一些问题,这里写出几个常用到的处理方法: 
1.知道输入数据组数n 
  scanf(“%d”,&n); 
  whlie(n–){ 
      这里处理每一组输入.然后直接按格式输出,没必要开数组存储答案. 
  } 
2.没有数据总数,以EOF结束 
  可能用的几个函数: 
  scanf(): 
  while(scanf(“%s|%d”)!=EOF){ 
    处理每一组数据,并输出. 
  } 
  getchar():读入一个字符 
  whlie((ch=getchar())!=EOF){ 
      
  } 
  gets():读入一行 
  while(gets(buf)!=NULL) { 
  
  } 
  用getchar,gets注意读入换行符. 
3.以0或-1结束的输入. 
  while(scanf(“%d”,&n),n!=0) { 
  
  }

 

 

 

 

 

 

 

 

关于C++的输入输出处理:

cin读字符串时遇到空白符(空格,换行等)结束 
char str[BUFFER]; 
while (cin >> str) { 

getline读字符串时遇到换行符结束,用于读一整行 
char str[BUFFER]; 
while (cin.getline(str, BUFFER)) { 

string str; 
while (getline(cin, str)) { 

cin/cout要比scanf/printf慢一些,尽可能使用scanf/printf以避免测试大量数据时因为输入输出慢而导致TLE. putchar/getchar要比scanf/printf更快 

关于java的输入输出处理:

如果使用BufferedReader(jdk1.1或以后的版本,一次读一整行字符串,类似于gets) 
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in)); 
String s; 
while ((s = stdin.readLine()) != null) { 
    可以用StringTokenizer st = new StringTokenizer(s);来按空格切词 
    int n = Integer.parseInt(st.nextToken()); 
    double b = Double.parseDouble(st.nextToken()); 

如果使用Scanner(仅限于jdk1.5或以后的版本,一般用于从字符串中切词,类似于cin) 
Scanner stdin = new Scanner(System.in); 
while (stdin.hasNext()) { 
    String s = stdin.next(); 
    int n = stdin.nextInt(); 
    double b = stdin.nextDouble(); 

    至于输出,很多新手总会选择先将答案存储在一个数组里,等程序运行完再输出,其实这是没有必要的,机器判决是逐个字符匹配,所以完全可以处理一组输入后,便输出结果。

 

 

 

 

ACM技巧 使用文件输入输出方便测试的方法

把下面两块宏语句分别嵌在main函数的开始和结束,这样在本地调试的时候,cin/cout和scanf/printf直接对应到指定的文件流,但提交到OJ时,此两句不被编译,所以仍为标准I/O流,因此不用提交前改代码。 

后面一块宏不用也可以,前面一块宏根据自己的输入文件改变”in.txt”,”out.txt”,也可以只用其一。 

#include  
#include  

using namespace std; 

#ifndef ONLINE_JUDGE 
    freopen(“in.txt”,”r”,stdin); 
    freopen(“out.txt”,”w”,stdout); 
#endif 

#ifndef ONLINE_JUDGE 
    fclose(stdin); 
    fclose(stdout); 
#endif 

用这种方法,cin/cout和scanf/printf都可以转化为文件流

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C语言输入输出函数详解

C语言中基本的输入输出函数有:
putchar ():把变量中的一个字符常量输出到显示器屏幕上;
getchar ();从键盘上输入一个字符常量,此常量就是该函数的值;
printf  ();把键盘中的各类数据,加以格式控制输出到显示器屏幕上;
scanf   ();从键盘上输入各类数据,并存放到程序变量中;
puts    ():把数组变量中的一个字符串常量输出到显示器屏幕上;
gets    ():从键盘上输入一个字符串常量并放到程序的数组中.
sscanf(); 从一个字符串中提取各类数据。
   

putchar() 和 getchar() 顾名思议就是从输入流中获取一个字符和输出一个字符,比较简单,不再多讲。
例子如下:
char c = getchar();
putchar(c);

 

格式化输入输出scanf()和printf()是最有用的,所以重点讲一下。
printf():
一般形式:
printf(“格式控制”.输出列表);  
eg : printf(“a=%d,b=%f,c=%c/n”,a,b,c);
1;格式控制.
格式控制是用双引号括起来的字符串,也称”转换控制字符串”,它包含以下两部分信息.
格式说明:由”%”和格式字符组成,如%d,%f,%c,他的作用是把输出数据转换为指定格式输出,格式的说明总是由”%”字符开始的.
普通字符:需要原样输出的字符,或者是一些有特殊含义的字符,如/n,/t。
2;输出列表
就是需要输出的一些数据,也可以是表达式,如果在函数中需要输出多个变量或表达式,则要用逗号隔开.

一些特殊字符的输出:
单引号,双引号,和反斜杠的输出在前面加转义字符”/”
如:”/’”  ,  “/””   ,  “//”
%的输出用两个连在一起的%%,即printf(“%%”);

 

常用的格式说明如下:
格式字符
d  以十进制形式输出带符号整数(正数不输出符号) 
o  以八进制形式输出无符号整数(不输出前缀O) 
x  以十六进制形式输出无符号整数(不输出前缀OX) 
u  以十进制形式输出无符号整数 
f  以小数形式输出单精度实数 
lf以小数形式输出双精度实数
e  以指数形式输出单、双精度实数 
g  以%f%e中较短的输出宽度输出单、双精度实数 
c  输出单个字符 
s  输出字符串 

    这里强调一下:网上很多文章都说f 和lf是一样的,即不管单精度,双精度浮点数,都可以用f, 但我在POJ上做过测试,输出Double时用f确实也可以 ,但读入时,用f就报WA,所以大家如果对Double进行读写的话,都用lf吧。说到Double,再啰嗦一句,建议大家要用到浮点数时都用Double,不要用float,因为在很多情况下,float精度不够会导致WA。
特殊:
对64位整数的输入输出,在POJ上的C++环境下(即VC),64位整数是:
__int64    (注意int前面是两个下划线)
输入输出格式为”%I64d”.
在G++环境下(即Dev C++) 64位整数是
long long
输入输出格式为”%lld”.

 

输出宽度

  用十进制整数来表示输出的最少位数。 注意若实际位数多于定义的宽度,则按实际位数输出, 若实际位数少于定义的宽度则补以空格或0。
精度
  精度格式符以“.”开头,后跟十进制整数。意义是:如果输出数字,则表示小数的位数;如果输出的是字符, 则表示输出字符的个数;若实际位数大于所定义的精度数,则截去超过的部分。
标志格式字符 
–  结果左对齐,右边填空格 
+  输出符号(正号或负号)空格输出值为正时冠以空格,为负时冠以负号
例如:
double c=24212345.24232;
printf(“%020.4”);  表示输出精确到小数点后4位,输出占20位,若有空余的位补0.
scanf:
scanf的很多用法都是和printf对应的,故不再赘述。
说一下scanf一个特别好用的地方,就是可以滤去一些不想要的东西。
举例说明如下:
比如输入为日期 yyyy-mm-dd,就可以这样写:
int year,moth,day;
scanf(“%d-%d-%d”,&year,&moth,&day);
再比如:
scanf(“%3d %*3d %2d”,&m,&n);      输入113 118 69回车(系统将113赋予m,将69赋予n,因为*号表示跳过它相应的数据所以118不赋予任何变量)
puts()用的不多,且基本都能用printf()代替,故不再多说。
gets()是从输入流中获取一行字符串放入字符数组中:
char in[100];
gets(in);
大家可能最容易出错的地方就是字符串的输入,所以强调一下:
能进行字符,字符串输入的有:
getchar(), scanf(“%c”); scanf(“%s”), gets()
其中getchar() 和 scanf(“%c”)的功能是一样的。
需要注意的是,这两个函数读入的是输入流中当前位置的字符,
比如:
    scanf(“%d”,&n);
    c = getchar();
假设输入 67/ (假设“/”代表回车),则第一个scanf读入一个整数67后,当前输入流的位置是67之后,即指向回车符,所以第二个getchar()读入的就是一个回车符了,即 c = ‘/n’。
同样,gets()也是从当前位置读入一行字符串。
比如:
scanf(“%d”,&n);
gets(str);
此时读入字符数组中的字符串就是“/n” 了
所以通常在用scanf读入一个非字符串的类型之后,如果要读入字符,或字符数组,都用一个额外的getchar()把回车符读掉,若后面跟的不止一个回车符,可能还有多余的空格的话,就用gets()读掉。
    和以上不同的是,scanf(“%s”) 读入的时候是会忽略掉空格,回车和制表符的。并且以空格,回车和制表符作为字符串结束的标志。
    经常会有这样的题,输入第一行是一个整数,接下来每行的第一个是一个字符,用来表示某种操作,后面再跟一些数据,比如:
4
A 100 2
B 23
A 23 89
B 34
像这种输入就需要小心,读入字符时不要读成回车符。
为了防止意外,我一般是这样处理这类输入的:
char model[2];
Scanf(“%d”,&n);
for(…,…,…){
    scanf(“%s”,model);
    if(model[0] == ‘A’){
}
else{
}
}
    sscanf():
sscanf()经常用来分解字符串,功能非常强大,但很多功能都需要正则表达式的知识,所以就介绍一下最简单的几种用法,大家如果想了解更多的话,自己去网上找吧。
1、
char str[100],str1[100],str2[100];
gets(str);
sscanf(str,”%s%s”,str1,str2);
将读入的一整行字符串按空格,制表符或回车符分割成两个字符串。
2、
取指定长度的字符串。如在下例中,取最大长度为4字节的字符串。
  sscanf(“123456 “, “%4s”, str);
    对于C++的输入输出就不再详细的讲了,因为cin,cout的速度实在太慢,不推荐使用,我一般都是到万不得已时才用。比如当你要读入字符串到string 对象中时,就只能用cin了,这时候还有一个常见的问题,就是如何将一整行字符串读入一个string 中,这就要用到getline函数了。
用法为:
getline(cin, str);
第一个参数就是标准输入流cin ,第二个参数是接收读入数据的string对象,本来还有第三个参数,是结束符的标志,但通常用它默认的就可以了,所以不用管。
注意区分这个getline和cin.getline的区别:
cin.getline的用法如下:
char str[20]; 
cin.getline(str,20); 表示从读入的一行字符串中,取最多20各字符放入字符数组str中,注意此处的str是字符数组,而上面的str是string对象。
    另外需要注意的是,千万不要把cout和printf混用,因为cout是带缓冲的而printf不带,所以会使得输出的数据顺序混乱。

 

 

 下面是几个比较大的在线提交系统(Online Judge)里面有大量历年的竞赛题目,注册一个ID,然后用自己熟悉的语言(一般有Pascal/C/C++/Java)写好源代码提交即可,会实时返回信息告诉你是否正确。采用黑箱测试,系统里有一套标准的输入输出数据(对外保密,而且通常数据很多很怪),你的程序的输出和标准输出完全符合即可。常见的返回信息有AC(Accepted,通过)WA(Wrong Answer,输出有错误)TLE(Time Limit Exceeded,超时)MLE(Memory Limit Exceeded,内存溢出)RE(Runtime Error,发生实时错误)等,只有AC了才算做对一题。这里只是一个简要介绍,请大家在做题时先看看各网站上的FAQ,Enjoy it~~~

 浙江大学 Online Judge(ZOJ)http://acm.zju.edu.cn

 国内最早也是最有名气的OJ,有很多高手在上面做题。特点是数据比较刁钻,经常会有你想不到的边界数据,很能考验思维的全面性,现在我主要在这个OJ上做题

 北京大学 Online Judge(POJ)http://acm.pku.edu.cn/JudgeOnline/

 建立较晚,但题目加得很快,现在题数和ZOJ不相上下,特点是举行在线比赛比较多,数据比ZOJ上的要弱,有时候同样的题同样的程序,在ZOJ上WA,在POJ上就能AC

 同济大学 Online Judge http://acm.tongji.edu.cn/index.php

 这个OJ题数上不能与上两个相比,推荐这个OJ的原因是它是中文的,这对很多对英文不太感冒的兄弟是个好消息吧。它也因此吸引了众多高中的OIer,毕竟他们的英文还差一些呵呵,上面的题目也更偏向高中的信息学竞赛一些。

 西班牙Valladolid大学 Online Judge(UVA)http://online-judge.uva.es/problemset/

 世界上最大最有名的OJ,题目巨多而且巨杂,数据也很刁钻,全世界的顶尖高手都在上面。据说如果你能在UVA上AC一千道题以上,就尽管向IBM、微软什么的发简历吧,绝对不会让你失望的。

 俄罗斯Ural立大学 Online Judge(URAL)http://acm.timus.ru/

 也是一个老牌的OJ,题目不多,但题题经典,我在高中的时候就在这上面做题的。 

 UsacoGate Online Judge(USACO)http://ace.delos.com/usacogate

 全美计算机奥林匹克竞赛(USACO)的训练网站,特点是做完一关才能继续往下做,与前面的OJ不同的是测试数据可以看到,并且做对后可以看标准解答,所以如果大家刚开始的时候在上面那些OJ上总WA却找不到原因的话,可以试着来这里做做,看看测试数据一般是从什么地方阴你的。

POJ【数论/组合/博弈论】题目列表

转载自:http://www.cnblogs.com/vongang/archive/2013/03/10/2952978.html

POJ【数论/组合/博弈论】题目列表

原来的列表比较水,今天换了一个难一些的列表,重新开始做~

 

博弈论

POJ 2234 Matches Game
POJ 2975 Nim
POJ 2505 A multiplication game
POJ 1067 取石子游戏  威佐夫博弈,奇异局势(必败局)为ak = [k*(1 + sqrt(5))/2], bk = ak + k;
POJ 2484 A Funny Game  这题真欢乐
POJ 2425 A Chess Game
POJ 2960 S-Nim    sg函数
POJ 1704 Georgia and Bob 阶梯博弈转化成Nim,当N为奇数时将p[1]与0绑定
POJ 1740 A New Stone Game
POJ 2068 Nim
POJ 3480 John    Anti-SG问题 贾志豪的论文Chapter2

POJ 2348 Euclid’s Game
POJ 3710 Christmas Game
POJ 3533 Light Switching Game
POJ 3537 Crosses and Crosses

数论/组合

 

 

1.burnside定理,polya计数法
    这个大家可以看brudildi的《组合数学》,那本书的这一章写的很详细也很容易理解。最好能完全看懂了,理解了再去做题,不要只记个公式。
    *简单题:(直接用套公式就可以了)
    pku2409 Let it Bead   
    pku2154 Color
    pku1286 Necklace of Beads
    *强烈推荐:(这题很不错哦,很巧妙)
    pku2888 Magic Bracelet
2.置换,置换的运算

    置换的概念还是比较好理解的,《组合数学》里面有讲。对于置换的幂运算大家可以参考一下潘震皓的那篇《置换群快速幂运算研究与探讨》,写的很好。
    *简单题:(应该理解概念就可以了)
    pku3270 Cow Sorting
    pku1026 Cipher
    *置换幂运算:
    pku1721 CARDS
    pku3128 Leonardo’s Notebook
    *推荐:(不错的应用)
    pku3590 The shuffle Problem
3.素数,整数分解,欧拉函数

    素数是可能数论里最永恒,最经典的问题了(我们的队名就叫PrimeMusic^-^)。素数的判断,筛法求素数,大素数的判断···还有很多其他问题都会用到素数。
    *最水最水的:(心情不爽时用来解闷吧)
    pku1365 Prime Land
    pku2034 Anti-prime Sequences
    pku2739 Sum of Consecutive Prime Numbers
    pku3518 Prime Gap
    pku3126 Prime Path
    pku1595 Prime Cuts
    pku3641 Pseudoprime numbers
    pku2191 Mersenne Composite Numbers
    pku1730 Perfect Pth Powers
    pku2262 Goldbach’s Conjecture
    pku2909 Goldbach’s Conjecture
    *筛法:
    pku2689 Prime Distance(很好的一个应用)
    *反素数:
    zoj2562 More Divisors
    *素数判断,整数分解:
    这两题都要用到miller_rabin的素数判断和pollard_rho的整数分解,算法书上都会有,应该是属于模板题吧,不过最好看懂自己敲一遍。
    pku1811 Prime Test
    pku2429 GCD & LCM Inverse

    *欧拉函数:
    数论里很多地方都能用到欧拉函数,很重要的。
    pku1284 Primitive Roots (关于原根的定理:p的原根为euler(euler(p)),本题中当p为奇素数时euler(p)=p-1,故答案为euler(p-1))
    pku2407 Relatives (很水)
    pku2773 Happy 2006
    pku2478 Farey Sequence (快速求欧拉函数)
   pku3090 Visible Lattice Points (法雷级数)
    *推荐:(欧拉函数,费马小定理)
    pku3358 Period of an Infinite Binary Expansion
    *整数分解
    这个也很重要的耶,包括大数的表示方法。
    pku2992 Divisors
    pku3101 Astronomy (分数的最小公倍数)
4.扩展欧几里得,线性同余,中国剩余定理

    这应该是数论里比较重要的一个部分吧,这类的题目也挺多,具体的内容最好先看看数论书,我也整理过一些,可以参考参考:
    *简单题:
    pku1006 Biorhythms
    pku1061 青蛙的约会
    pku2891 Strange Way to Express Integers
    pku2115 C Looooops
    pku2142 The Balance
    *强烈推荐:
    sgu106 The equation
    pku3708 Recurrent Function (经典)
 5.约瑟夫环问题

    这个问题还是比较有意思的,不是很难。
    *简单题:
    pku3517 And Then There Was One
    pku1781 In Danger
    pku1012 Joseph
    pku2244 Eeny Meeny Moo
    *推荐:
   pku2886 Who Gets the Most Candies?
6.高斯消元法解方程

    其实解方程并不是很难,就是按线性代数中学的那种方法,把系数矩阵化成上三角矩阵或数量矩阵,不过有些题目要判断是否有解,或枚举所有解。不过这类题目我认为比较难的还是怎么去建立这个方程组,这个理解了,就没什么大问题了。
    *简单题:
    pku1222 EXTENDED LIGHTS OUT
    pku1681 Painter’s Problem
    pku1830 开关问题
    *推荐:
    pku2947 Widget Factory
    pku2065 SETI
    *强烈推荐:
    pku1753 Flip Game
    pku3185 The Water Bowls
    *变态题:
    pku1487 Single-Player Games
  
7.矩阵
    用矩阵来解决问题确实很常见,但我现在用到还不是很好,很多难题我还不会做。建议大家可以去看Matrix67的那篇关于矩阵的十个问题,确实很经典,但不太好看懂。
    *简单:
    pku3070 Fibonacci
    pku3233 Matrix Power Series
    pku3735 Training little cats
8.高次同余方程

    有关这个问题我应该是没什么发言权了,A^B%C=D,我现在只会求D和B,唉,很想知道A该怎么求。就先推荐几道题目吧,这里涉及到了一个baby-step,giant-step算法。
    pku3243 Clever Y
    pku2417 Discrete Logging
9.容斥原理,鸽巢原理

    很有用的两个定理,但好像单独考这两个定理的不是很多。
    *鸽巢原理:
    pku2356 Find a multiple
    pku3370 Halloween treats
    *容斥原理:
    hdu1695 GCD
    hdu2461 Rectangles
10.找规律,推公式

    这类题目的设计一般都非常巧妙,真的是很难想出来,但只要找到规律或推出公式,就不是很难了。我很多都是在参考别人思路的情况下做的,能自己想出来真的很不容易。
    *个人感觉都挺不错的:
    pku3372 Candy Distribution
    pku3244 Difference between Triplets
    pku1809 Regetni
    pku1831 不定方程组
    pku1737 Connected Graph
    pku2480 Longge’s problem
    pku1792 Hexagonal Routes
11.排列组合,区间计数,计数序列

    这些题目可能需要一些组合数学知识,基本上高中的知识就够了。区间计数问题一般不难,但写的时候需要仔细一些,各种情况要考虑到位。至于像卡特兰数,差分序列,斯特灵数···都还挺有意思,可以去看看《组合数学》。
    *简单题:
    pku1850 Code
    pku1150 The Last Non-zero Digit
    pku1715 Hexadecimal Numbers
    pku2282 The Counting Problem
    pku3286 How many 0’s?
    *推荐:
    pku3252 Round Numbers
    *计数序列:
    pku1430 Binary Stirling Numbers
    pku2515 Birthday Cake
    pku1707 Sum of powers
12.二分法

    二分的思想还是很重要的,这里就简单推荐几个纯粹的二分题。
    *简单:
    pku3273 Monthly Expense
    pku3258 River Hopscotch
    pku1905 Expanding Rods
    pku3122 Pie
    *推荐:
    pku1845 Sumdiv
13.稳定婚姻问题

    无意中接触到这个算法,还蛮有意思的,《组合数学》中有详细的介绍。
    pku3487 The Stable Marriage Problem
    zoj1576 Marriage is Stable
14.数位类统计问题

    在航点月赛中第一次接触到这类问题,scau大牛little龙推荐我看了一篇论文,09年刘聪的《浅谈数位类统计问题》,这篇论文相当精彩,也相当详 细,每道题都有详细的分析和作者的参考代码。所以我也没什么可说的了,这些题的代码我博客里也就不贴了,大家直接去看论文吧。
    简单:
    ural1057 Amount of degrees
    spoj1182 Sorted bit squence
    hdu3271 SNIBB
    较难:
    spoj2319 Sequence
    sgu390 Tickets

 

poj 2909 Goldbach’s Conjecture (哥德巴赫猜想)

 水题

写一遍的目的是。。。复习一下快速筛的写法 喵呜

poj 1305 (毕达哥拉斯三元组,构造勾股数)

题意是说,能构造多少本元勾股数和勾股数,要求构造的数<=n

所谓本元勾股数,就是三个勾股数没有公因数,两两互质。

由本元勾股数扩大k倍,就可以得到其他勾股数。

而构造本元勾股数的方法如下:

a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2

其中s>t>=1是任意没有公因数的奇数!

 

引用一段构造正确性的证明:

本原勾股数组(PPT)是一个三元组(a,b,c),其中a,b,c无公因数,且满足a² +b² =c²。

很明显存在无穷多个勾股数组(abc同乘以n),下面研究abc没有公因数的情况,先写出一些本原勾股数组:

case:(3,4,5) (5,12,13) (8,15,17) (7,24,25) (20,21,29)(9,40,41)(12,35,37)(11,60,61)(28,45,53) (33,56,65) (16,63,65)

观察可以看出a,b奇偶性不同且c总是奇数。(用一点技巧可以证明这是正确的)

3² = 5² – 4² = (5-4)(5+4) = 1 × 9

15² = 17²-8² = (17-8)(17+8) = 9 ×25

35² = 37² – 12² = (37-12)(37+12) = 25 ×49

……

很神奇的是似乎c-b与c+b总是平方数,并且c-b与c+b木有公因数。证明一下下:假设有公因数,设d是c-b与c+b的公因数,则d也整除(c+b)+(c-b)=2c, (c+b)-(c-b) = 2b,所以d整除2c,2b,但是b,c木有公因数,又假设了(a,b,c)是本原勾股数组,从而d等于1或2,又因为d整除(c-b)(c+b)=a².a²是奇数,所以d = 1,c-b与c+b木有公因数。,又因为(c-b)(c+b)=a²,所以c-b与c+b的积是平方数,只有二者都是平方数才会出现(可以把二者分解成素数乘积直观地看出),令c+b = s²,c-b=t²,解得

c=(s²+t²)/2, b=(s²-t²)/2,a = √(c-b)(c+b) = st.这就得出了勾股数组定理:

每个本原勾股数组(a,b,c)(a为奇数,b偶数)都可由如下公式得出:a=st,b=(s²-t²)/2, c = (s²+t²)/2, 其中s>t>=1是没有公因数的奇数。

当取t=1时就可以得到上面的许多例子。


poj 3370 Halloween treats (剩余类,抽屉原理)

昨天那道签到的数学题没搞出来不开心.
是时候刷一波数学了
这题题意是说,从n个数中任选m个,使得m个的和为c的倍数.
如果有解,输出选的数的下标,否则输出无解字符串.
抽屉原理的原始描述是,如果有n+1个物品,有n个抽屉,那么至少有一个抽屉有2个物品.
抽屉原理我们可以退出一个结论,对于任意 n个自然数,一定有连续的一段和为n的倍数.
证明如下:
  设这n个自然数分别为a1,a2,a3,a4….an
  处理一个前缀和sum[i] = (sum[i-1] + a[i])%n
  因为n的剩余类有n种,分别为0,1,2…n-1
  所以sum[1],sum[2],sum[3]..sum[n]
  那么sum[1],sum[2],sum[3]…sum[n]最多也有n种.
  我们分情况讨论:
    (1)sum[1],sum[2],sum[3]…sum[n]互不相同,那么一定存在sum[i]=0,也就是前i个数的和为n的倍数.
    (2)情况(1)的反面,也就是存在sum[i]==sum[j]  (i<j),那么 从a[i+1] 到 a[j]的和就是n的倍数.
因为题目中的数据 c<=n ,所以解一定存在.
具体做法就是处理出来一个前缀和%c
然后如果有0,则为解,输出.
否则记录sum[i]%d出现的位置,存在一个数组里
如果sum[i]%d第二次出现,就输出这段下标.
嘛,大括号换风格了….
都写开代码太长了==

HUST team contest #E A Mountain Road||poj 3846 (dp)

比赛的时候以为是贪心…

想了好久.

不过最后没敢写,因为没办法证明正确性,只是直觉==

最后剩下的时间给队友改另一道题了..

果然明智…

蠢的人的直觉真心不靠谱..

这题是dp

我们可以把车按照方向的不同分为A车和B车

dp[i][j][0..1]表示已经经过了a方向的i辆车,经过了b方向的j辆车,并且最后一辆车是a/b方向的情况的离开道路的时间.

 

似乎问题不大.

然后就一直wa…

wa到怀疑人生好么!!!

最后发现

问题出在!

dp数组初始化赋值成正无穷的时候,溢出啦!

然后我搜了下,发现0x7fffffff果然不是什么好东西!

以后正无穷用0x3f3f3f3f

这东西>1E9,相加不超过int

而且最重要的是,如果定义 inf = 0x3f3f3f3f

0x3f3f3f3f的每个字节都是0x3f!所以要把一段内存全部置为无穷大,我们只需要memset(a,0x3f,sizeof(a))

不要使用0x7fffffff!

不要使用0x7fffffff!

不要使用0x7fffffff!

0x3f3f3f3f…编程中无穷大常量的设置技巧

如果问题中各数据的范围明确,那么无穷大的设定不是问题,在不明确的情况下,很多程序员都取0x7fffffff作为无穷大,因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较(比如求最小值时min变量的初值),那么0x7fffffff确实是一个完美的选择,但是在更多的情况下,0x7fffffff并不是一个好的选择。

  1. 很多时候我们并不只是单纯拿无穷大来作比较,而是会运算后再做比较,例如在大部分最短路径算法中都会使用的松弛操作:
    if (d[u]+w[u][v]我们知道如果u,v之间没有边,那么w[u][v]=INF,如果我们的INF取0x7fffffff,那么d[u]+w[u][v]会溢出而变成负数,我们的松弛操作便出错了,更一般的说,0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”,它变成了一个很小的负数。
  2. 除了要满足加上一个常数依然是无穷大之外,我们的常量还应该满足“无穷大加无穷大依然是无穷大”,至少两个无穷大相加不应该出现灾难性的错误,这一点上0x7fffffff依然不能满足我们。

所以我们需要一个更好的家伙来顶替0x7fffffff,最严谨的办法当然是对无穷大进行特别处理而不是找一个很大很大的常量来代替它(或者说模拟它),但是这样会让我们的编程过程变得很麻烦。在我读过的代码中,最精巧的无穷大常量取值是0x3f3f3f3f,我不知道是谁最先开始使用这个精妙的常量来做无穷大,不过我的确是从一位不认识的ACMer(ID:Staginner)的博客上学到的,他/她的很多代码中都使用了这个常量,于是我自己也尝试了一下,发现非常好用,而当我对这个常量做更深入的分析时,就发现它真的是非常精巧了。

  1. 0x3f3f3f3f的十进制是1061109567,也就是10^9级别的(和0x7fffffff一个数量级),而一般场合下的数据都是小于10^9的,所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
  2. 另一方面,由于一般的数据都不会大于10^9,所以当我们把无穷大加上一个数据时,它并不会溢出(这就满足了“无穷大加一个有穷的数依然是无穷大”),事实上0x3f3f3f3f+0x3f3f3f3f=2122219134,这非常大但却没有超过32-bit int的表示范围,所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。
  3. 最后,0x3f3f3f3f还能给我们带来一个意想不到的额外好处:如果我们想要将某个数组清零,我们通常会使用memset(a,0,sizeof(a))这样的代码来实现(方便而高效),但是当我们想将某个数组全部赋值为无穷大时(例如解决图论问题时邻接矩阵的初始化),就不能使用memset函数而得自己写循环了(写这些不重要的代码真的很痛苦),我们知道这是因为memset是按字节操作的,它能够对数组清零是因为0的每个字节都是0,现在好了,如果我们将无穷大设为0x3f3f3f3f,那么奇迹就发生了,0x3f3f3f3f的每个字节都是0x3f!所以要把一段内存全部置为无穷大,我们只需要memset(a,0x3f,sizeof(a))。

所以在通常的场合下,0x3f3f3f3f真的是一个非常棒的选择。

 

HUST team contest #2 C Divisible Subsequences ||poj 3844 (剩余类)

算是签到帖,竟然卡住了。

我数学还是太差了。。

然后去找题解。。竟然看不懂!

我数学真的有这么差嘛。。。

然后多亏了队友 @zcy 妹子的讲解。。

其实很好理解啊。。。

不过数到底还是数学太差了==

今天七夕,废话有点多==

 

这道题的题意是,找序列中连续的一段,使得和 可以整除d

我们观察到数列中的数的范围是1..1 000 000 000 的

而d只有1 000 000

我们考虑余数相同,读入的时候就可以直接先 % 掉 d

因为只会和余数有关。

我们可以先处理出来一个前缀和数组sum[i],表示前i个元素的和。

如果有一段序列从a[i] 到 a[j] 满足题意

根据题意那么这段序列的和一定%d=0

a[i] 到 a[j]的和为 sum[j]-sum[i-1]

也就是(sum[j]-sum[i-1] )%d==0

也就是sum[j] 和 sum[i-1] 关于 d 同余

如果我们在处理得到前缀和的时候就%dshuxue

那么就是sum[j]==sum[i-1]

所以我只要对于d的每一个剩余类有多少个统计出来。

然后对于每个剩余类,只需要任意取出两个,就是一种答案。

需要注意的是如果只有一个0,也是一种答案。

我们可以定义sum[i] = 0

还有一个需要注意的是要开long long

HUST team contest #2 A An Industrial Spy ||poj 3842 (筛)

蠢了。

这道题显然可以搜。。

然后自己搜索的姿势果然还是不怎么地。。

最后是蔡大神过掉的。

他的思路是枚举素数,然后把素数的各位拆开,看这些数字是否在给出的字符串中出现过。

一开始TLE掉了。

后来又预处理出来一个标记数组,如果字符串中没有数字2,那么20w+的素数就可以直接跳过去,然后A掉了。

 

其实因为数字的位数最多才7位。。

暴力也不是不可以。。。。

STL中求全排列的那个函数我也不是没用过。。。比赛的时候怎么就没想到==

再开个map判重

然后素数打表部分。

队友是打了个30000+行的表。。。。

说起来。。。我好像还没用C++写过筛法求素数。。。

说来惭愧啊。。。。

pascal的时候倒是写过几次呢。

再复习下。。。

http://blog.csdn.net/dinosoft/article/details/5829550

写的是快速筛。