• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day18 J (Catalan数+单调队列)

admin

11月 28, 2021

题目链接在这里:Problem – J – Codeforces

这是一个Catalan数的应用,关于Catalan数的推导以及其他应用可以看这个博客:(7条消息) n个节点的二叉树有多少种形态(Catalan数)_garrulousabyss的博客-CSDN博客_n个节点的二叉树有多少种

回到这题,我们每次需要把最小的数统计出来,然后一步步的递归下去。

这是官方题解:

 这里学会了一种方法,当统计一段区间里一个数的个数且这个区间与该数的大小有关的时候,可以考虑单调队列的解法。

有一个要注意的地方,在数列的末尾要加一个-1,保证数列的每个数最后都能从单调队列里面取出来。

参考博客:(7条消息) CF gym102501 J. Counting Trees(Catalan数、dfs/单调队列)_小鱼yn的博客-CSDN博客

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=1e6+5;
 5 const int MOD=1000000007;
 6 LL n,m,a[MAX],jie[MAX<<1],q[MAX],cnt[MAX],ans;
 7 void init(){
 8     LL i,j;jie[0]=1;
 9     for (i=1;i<=2*n;i++) jie[i]=i*jie[i-1]%MOD;
10 }
11 LL ksm(LL x,LL y){
12     LL an=1;
13     while (y){
14         if (y&1) an=an*x%MOD;
15         x=x*x%MOD;
16         y>>=1;
17     }
18     return an;
19 }
20 int main(){
21     freopen ("j.in","r",stdin);
22     freopen ("j.out","w",stdout);
23     LL i,j;
24     scanf("%lld",&n);
25     for (i=1;i<=n;i++)
26         scanf("%lld",a+i);
27     a[n+1]=-1;
28     init();
29     LL head,tail;
30     head=1,tail=0;ans=1;
31     memset(cnt,0,sizeof(cnt));
32     for (i=1;i<=n+1;i++){
33         while (head<=tail && a[i]<q[tail]){
34             m=cnt[tail];
35             ans=ans*jie[2*m]%MOD*ksm(jie[m],MOD-2)%MOD*ksm(jie[m+1],MOD-2)%MOD;
36             tail--;
37         }
38         if (head<=tail && a[i]==q[tail])
39             cnt[tail]++;
40         else{
41             tail++;q[tail]=a[i];
42             cnt[tail]=1;
43         }
44     }
45     printf("%lld",ans);
46     return 0;
47 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注