太子参部落

[Sdoi2010]土精部落

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 1643  Solved: 1025
[Submit][Status][Discuss]

1925: [Sdoi2010]人葠部落

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 1519  Solved: 952
[Submit][Status][Discuss]

Description

传说以前到现在,大地上位居着一种神秘的浮游生物:西洋参。
移山参喜欢住在连绵不绝的深山中。具体地说,一座长度为 N 的山体 H可分
为从左到右的 N 段,每段有八个无比的莫大 Hi,其中Hi是1到N 之间的正
整数。
如若一段山脉比全数与它相近的群山都高,则这段山脉是三个山峰。位于边
缘的深山独有一段左近的山体,别的都有两段(即侧面和左边)。
类似地,假设一段山脉比有所它周围的山峰都低,则这段山脉是二个峡谷。
太子参们有一个一齐的珍视——吃酒,饭店可以设置在山里之中。沙参的小吃摊
不论白天黑夜总是热热闹闹,鬼盖美酒的川白芷能够飘到方圆数里的地点。
党参依旧一种十分警觉的古生物,他们在每座山体上都能够设立瞭望台,并轮
流担当瞭望工作,以担保在第一时间得知外敌的凌犯。 丹参们希望那N
段山脉每段都足以建造瞭望台或酒店的里边之一,只有知足那么些条件的整座山脉才或然有土精居住。 将来你希望知晓,长度为N
的只怕有太子参居住的群山有微微种。两座山脉A 和B区别当且仅当存在五个i,使得 Ai≠Bi。由于那个数据或许不小,你只对它 除以P的余数感兴趣。

Description

典故自古以来,大地上位居着一种神秘的浮游生物:沙参。
人参喜欢住在连绵不绝的山峰中。具体地说,一座长度为 N 的群山 H可分
为从左到右的 N 段,每段有二个独步天下的万丈 Hi,个中Hi是1到N 之间的正
整数。
假若一段山脉比全数与它周边的山脉都高,则这段山脉是二个深山。位于边
缘的山峰唯有一段左近的群山,别的都有两段(即左侧和左边手)。
类似地,假若一段山脉比有所它相近的山脊都低,则这段山脉是一个峡谷。
神草们有二个同步的爱怜——吃酒,客栈能够举行在峡谷之中。人衔的饭馆不论白天黑夜总是热热闹闹,野山参美酒的香气能够飘到方圆数里的地方。
西洋参依然一种异常的小心的古生物,他们在每座山体上都能够设置瞭望台,并轮
流负责瞭望工作,以担保在第临时间得知外敌的凌犯。 野山参们希望那N
段山脉每段都可以建造瞭望台或酒吧的在那之中之一,唯有满意那一个条件的整座山脉才恐怕有黄参居住。 今后你指望明白,长度为N
的或然有人参居住的山脉有稍许种。两座山脉A 和B区别当且仅当存在一个i,使得 Ai≠Bi。由于那一个数目大概相当大,你只对它 除以P的余数感兴趣。

Input

仅含一行,四个正整数 N, P。

Input

仅含一行,五个正整数 N, P。

Output

仅含一行,贰个非负整数,表示您所求的答案对P取余 之后的结果。

Output

仅含一行,四个非负整数,表示您所求的答案对P取余 之后的结果。

Sample Input

4 7

Sample Input

4 7

Sample Output

3

Sample Output

3

HINT

图片 1 
对于 20%的数据,满足 N≤10; 
对于 40%的数据,满足 N≤18; 
对于 70%的数据,满足 N≤550; 
对于 100%的数据,满足 3≤N≤4200,P≤109

HINT

图片 2 
对于 20%的数据,满足 N≤10; 
对于 40%的数据,满足 N≤18; 
对于 70%的数据,满足 N≤550; 
对于 100%的数据,满足 3≤N≤4200,P≤109

Source

第一轮Day2

 

题解 style=”font-size: 14pt;”> style=”font-size: 14pt;”> 

将标题简化为1-n的有着排列中级知识分子足高低交替出现的个数,可以用动态规划落到实处。

我们用f[n][k]代表n个数,最后多个为k且最终五个递增,g[n][k]代表n个数尾数数为k且倒数递减。

对于f[n][k],若我们将数列中各类数x换为n+1-x,则就成了g[n][n+1-k],所以可得f[n][k]=g[n][n+1-k]。

那么可得:

图片 3

进而动态调换方程为f[n][k]=f[n][k-1]+f[n-1][n-k+1]

图片 4

由于对称性,最后的答案为2ans。

唯独难点范围n<=4200,所以想到用滚动数组来减弱空间,于是那道题就AC了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cmath>
 6 
 7 #define N 4307
 8 using namespace std;
 9 
10 int n,p;
11 int f[2][N],ans=0,x=0,y=1;
12 
13 int main()
14 {
15     scanf("%d%d",&n,&p);
16     if (n==1){cout<<1<<endl;return 0;}
17 
18     f[0][1]=1;
19     for (int i=2;i<=n;i++)
20     {
21         for (int j=1;j<=i;j++) f[y][j]=(f[y][j-1]+f[x][i-j+1])%p;
22         swap(x,y);
23     }
24     for (int i=1;i<=n;i++) ans=(ans+f[x][i])%p;
25     ans=(ans*2)%p;
26     
27     printf("%d\n",ans);
28 }

 

Source

第一轮Day2

  方今做题都以这种想到了秒A,想不到刚一天也打不出去的题啊……

  那道题当时想的是四个点多少个点的转变,因为只要不去思虑山脉两端的话把它们位于大肆一个山脉两边都是官方的。然后就不知晓怎么搞了。

  事实注明小编也许太菜了……

  我们设f[i][j]为我们选i个数(大小Infiniti制),个中第j小的数位居发轫且她为山谷的方案数,那么它能够从g[i-1][k](j<=k<=i-1),g数组表示i个数中第k小的数在始发且她为山体的方案数。那们转移的实际意义就是把j放在十二分山峰前面。为何如此合法吗?因为一旦三个数是i个数里第j小的,那么他肯定是比不上i-1个数里第j个数大的。

  可是由于那是三个颠簸系列,大家让每一个岗位的可观成为i-x+1,那么大家就能够由f[i][j]的到g[i][i-j+1],将四个姿态合并一下就收获了上边只和f有关的转变方程

    f[i][j]=∑f[i-1][1~i-j]

  所以大家就足以在n^2的日子复杂度内求出全部的f,再把f加和乘以2就是答案。

图片 5图片 6

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<string>
 8 #include<queue>
 9 #define N 5000
10 using namespace std;
11 long long f[2][N];
12 int n,p;
13 int main(){
14     scanf("%d%d",&n,&p);
15     int now=1,la=0;
16     f[now][1]=1;
17     for(int i=2;i<=n;i++)
18     {
19         swap(now,la);
20         long long sum=0;
21         memset(f[now],0,sizeof(f[now]));
22         for(int j=i-1;j>0;j--)
23         {
24             sum+=f[la][i-j];
25             sum%=p;
26             f[now][j]=sum;
27         }
28     }
29     long long ans=0;
30     for(int i=1;i<n;i++)
31     {
32         ans+=f[now][i];
33         ans%=p;
34     }
35     ans*=2;
36     ans%=p;
37     printf("%lld\n",ans);
38     return 0;
39 }

View Code

相关文章