葡京娱乐场土精部落

1925: [Sdoi2010]太子参部落

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

[Sdoi2010]高丽参部落

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

Description

相传很久从前,大地上位居着一种神秘的海洋生物:野山参。
防党参喜欢住在连绵不绝的群山中。具体地说,一座长度为 N 的深山 H可分
为从左到右的 N 段,每段有三个整个世界无双的万丈 Hi,个中Hi是1到N 之间的正
整数。
假设一段山脉比有所与它附近的山脉都高,则那段山脉是1个深山。位于边
缘的群山唯有一段附近的群山,其余都有两段(即右边和右手)。
类似地,如若一段山脉比有所它附近的山体都低,则那段山脉是2个峡谷。
土精们有八个同步的爱好——喝酒,饭馆能够举行在峡谷之中。高丽参的小吃摊
不论白天黑夜总是人声鼎沸,沙参美酒的香气扑鼻能够飘到方圆数里的地点。
黄党依旧一种越发小心的古生物,他们在每座山体上都能够设立瞭望台,并轮
流担当瞭望工作,以担保在第叁时半刻间得知外敌的侵犯。 人衔们希望那N
段山脉每段都足以建造瞭望台或客栈的里边之一,只有满足这么些规则的整座山脉才大概有地精居住。 现在你希望知晓,长度为N
的或是有人参居住的山体某些许种。两座山脉A 和B不一样当且仅当存在贰个i,使得 Ai≠Bi。由于这些数据也许十分的大,你只对它 除以P的余数感兴趣。

Description

相传很久在此以前,大地上位居着一种神秘的古生物:高丽参。
人衔喜欢住在连绵不绝的山体中。具体地说,一座长度为 N 的山脉 H可分
为从左到右的 N 段,每段有三个无比的惊人 Hi,个中Hi是1到N 之间的正
整数。
假设一段山脉比全体与它附近的深山都高,则那段山脉是一个深山。位于边
缘的山体只有一段附近的山脊,其余都有两段(即左侧和右手)。
类似地,假设一段山脉比全数它附近的山峰都低,则这段山脉是二个低谷。
土精们有二个联机的喜爱——饮酒,饭店能够设置在谷底之中。黄参的小吃摊
不论白天黑夜总是人声鼎沸,海腴美酒的白芷能够飘到方圆数里的地点。
上党参依然一种11分警觉的古生物,他们在每座山体上都足以设立瞭望台,并轮
流担当瞭望工作,以确定保证在第②时半刻间得知外敌的侵略。 丹参们希望那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

  近期做题都以那种想到了秒A,想不到刚一天也打不出来的题啊……

  那道题当时想的是四个点四个点的变换,因为假如不去考虑山脉两端的话把它们位于任意3个山脉两侧都以官方的。然后就不知晓怎么搞了。

  事实评释小编要么太菜了……

  我们设f[i][j]为大家选i个数(大小无限制),在那之中第j小的数位居起首且她为山谷的方案数,那么它能够从g[i-1][k](j<=k<=i-1),g数组表示i个数中第k小的数在开端且她为山体的方案数。那们转移的实际意义便是把j放在12分山峰前边。为何那样合法吗?因为如若一个数是i个数里第j小的,那么他迟早是不如i-二个数里第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正是答案。

葡京娱乐场 3葡京娱乐场 4

 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

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]。

那么可得:

葡京娱乐场 5

就此动态转换方程为f[n][k]=f[n][k-1]+f[n-1][n-k+1]

葡京娱乐场 6

是因为对称性,最后的答案为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 }

 

相关文章