月度归档:2017年01月

BZOJ 1089: [SCOI2003]严格n元树(dp+python)

Description

  如果一棵树的所有非叶节点都恰好有n个儿子,那么我们称它为严格n元树。如果该树中最底层的节点深度为d
(根的深度为0),那么我们称它为一棵深度为d的严格n元树。例如,深度为2的严格2元树有三个,如下图:

给出n, d,编程数出深度为d的n元树数目。

Input

  仅包含两个整数n, d( 0   <   n   <   =   32,   0  < =   d  < = 16)

Output

  仅包含一个数,即深度为d的n元树的数目。

Sample Input

【样例输入1】
2 2
【样例输入2】
2 3

【样例输入3】
3 5

Sample Output

【样例输出1】
3
【样例输出2】
21

【样例输出2】
58871587162270592645034001

今天下午花了一点时间看了一些py的东西,然后上网查了查py这东西在oj上给怎么交题以及注意事项之类的。感谢韩司机教我了一下py的基本知识。。。
 因为OJ上py都是按照字符串来读入数据的,所以我们需要用相应的字符串函数把数据切分出来。比如读入了整数n。我们就需要:

strip()是把字符串的左右空格去掉,split是按照空格或者tab来切分。

回到这道题目,一开始想直接计算答案,看有没有什么规律。发现不会做。。。问了一下别人,发现计算前缀和就可以了。

设dp[i]为高度小于等于i的所有严格n元树的方案数。我们想一下怎么计算出dp[i+1]来。高度不超过i+1的严格n元树一定是由n棵不超过i的严格n元树加上一个根节点组成的。那么很明显dp[i+1]=dp[i]^n了。但是这样的话我们只考虑了有子树的情况,但是只有一个根节点的情况也是合法的。dp[i+1]=dp[i]^n+1.

不过需要特判一下d=0的情况,因为dp[-1]貌似是变成了dp数组里的最后一个数字。

然后py直接水过。。。的确是比Java好用很多。

 

BZOJ 1067: [SCOI2007]降雨量(ST表)

Description

  我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意
Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,
则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自2002年以来最多的”由于有些年份的降雨量未
知,有的说法是可能正确也可以不正确的。

Input

  输入仅一行包含一个正整数n,为已知的数据。以下n行每行两个整数yi和ri,为年份和降雨量,按照年份从小
到大排列,即yi<yi+1。下一行包含一个正整数m,为询问的次数。以下m行每行包含两个数Y和X,即询问“X年是
自Y年以来降雨量最多的。”这句话是必真、必假还是“有可能”。

Output

  对于每一个询问,输出true,false或者maybe。

Sample Input

6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008

Sample Output

false
true
false
maybe
false

HINT

100%的数据满足:1<=n<=50000, 1<=m<=10000, -10^9<=yi<=10^9, 1<=ri<=10^9

一个分类大讨论加上ST表维护区间最大值就可以了。。。

如果是真话的要求是十分严格的,必须要X和Y已知而且已知X到Y的任意一年的信息,而且num[Y]>=num[X],num[X]还得大于Y+1~X-1中的任意一年。

 

SPOJ DRUIDEOI – Fata7y Ya Warda!(破环成链+单调栈)

Druid (AKA Amr Alaa El-Deen) and little EOIers have finished their training and they are playing “Fatta7y ya warda!”. It’s a kids game when everyone holds hands with two other kids forming a circle, and they keep saying “Fatta7y ya warda!” (Flourish, flower!) (moving away from each other, while still holding hands, to form a huge circle), then “2affely ya warda!” (Die, flower!) (moving back as close to each other as possible, while still holding hands, to form a tiny circle, i.e. a point). That’s it!

Anyway the point is…

While Eagle (AKA Mohamed Ahmed) was watching them playing he was wondering, who’s the first person taller than Druid on his left? Similarly, who’s the first person taller than Druid on his right? Help Eagle find the answer for each person not just Druid.

Input

The input starts with an integer T (1 ≤ T ≤ 20), the number of test cases.

Each test case contains two lines. The first line contains a single integer N (1 ≤ N ≤ 105), the number of persons playing the game. The second line contains N integers hi (1 ≤ hi ≤ 109) the height of the i-th person. They are numbered 1 to N starting from Druid.

Output

For each test case print N lines, in the i-th line print 2 numbers, the index of the first person taller than the i-th person on his left, and the index of the first person taller than the i-th person on his right. If no one is taller than the i-th person print -1 -1.

Example

碰到这种问题,就是先把环拆开,然后弄个单调栈维护一下。从左向右扫一次,再从右向左扫一次。