[bzoj] 3193: [JLOI2013]地形生成

发表于   |   分类于   |  

刚刚听说小米与微软合作,将要出小米4上的WIN10ROM,我想说,会有多少人主动去刷机呢?Orz

题意

给定一些山,每座山都有一个高度height与限制limit,表示这座山的高度为height,这座山之前高度大于它的山的数量不能超过limit,求合法的标号序列数量和高度序列数量

传送门

分析

　　对于第一问来说,高度较小的山放在哪里不会影响到高度较大的山(因为高度较大的山的只有对高度比他还要大的山的数目的限制).那么我们就按高度的从大到小来枚举山,每座山在摆放时,由于比它大的山已经被放好了,所以它此时的可选位置可以求出来.那么第一问就是所有这些位置的乘积
　　第二问与第一问不同的是,可能会有两个合法的标号序列的高度序列相同.我们按高度排序后枚举的话,我们需要处理的就是高度相等的山.显然,完全相等的山,交换它们对高度序列无影响.我们可以将limit作为第二关键字来排序.我们不妨让关键值较小的山排在关键值较大的前面.这样每一座山的限制范围都有一个限制范围,用这个限制范围来做类似格子中每一行格子从1开始到limit的图形上从左下到右上角的方案数.

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <cstring>

#define  maxn    1010LL
#define  ansmod  2011LL
#define  inc(a,b) {a+=b;if(a>=ansmod)a-=ansmod;}
#define  mul(a,b) {a*=b;a%=ansmod;}

struct Mount {
trueint hei , lim ;
truebool operator < (const Mount& b) const
true{ return hei==b.hei ? lim<b.lim : hei>b.hei ; }
} m[maxn] ;

int n , f[maxn] ;
int ans1 = 1 , ans2 = 1 ;

int main() {
int i , j , k , tmp , limit ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
trueRep (i,1,n)
truetrueread(m[i].hei) , read(m[i].lim) , m[i].lim -- ;
truestd::sort(m+1 , m+n+1) ;
truefor (i = 1 ; i <= n ; i = j ) {
truetruememset(f , 0 , sizeof f) ;
truetruetmp = 0 ; f[0] = 1 ;
truetruefor (j = i ; j<=n && m[j].hei==m[i].hei ; j ++ ) {
truetruetruelimit = std::min(m[j].lim,i-1) ;
truetruetruemul(ans1 , limit+j-i+1) ;
truetruetrueRep (k,1,limit)
truetruetruetrueinc(f[k] , f[k-1]) ;
truetrue}
truetrueRep (k,0,limit)
truetruetrueinc(tmp , f[k]) ;
truetruemul(ans2,tmp) ;
true}
trueprintf("%d %d\n", ans1 , ans2) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章