神草部落

1925: [Sdoi2010]西洋参部落

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 1385  Solved: 856
[Submit][Status][Discuss]

1925: [Sdoi2010]鬼盖部落

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 1300  Solved: 800
[Submit][Status][Discuss]

Description

相传以前到现在,大地上位居着一种神秘的生物体:海腴。
鬼盖喜欢住在连绵不绝的深山中。具体地说,一座长度为 N 的山体 H可分
为从左到右的 N 段,每段有一个无比的莫斯中国科学技术大学学 Hi,当中Hi是一到N 之间的正
整数。
如若1段山脉比全部与它相近的群山都高,则那段山脉是1个山体。位于边
缘的深山唯有1段相近的深山,其他都有两段(即左边和右边)。
类似地,若是1段山脉比全数它相近的山脉都低,则那段山脉是1个峡谷。
西洋参们有二个一块的喜爱——饮酒,宾馆能够设立在低谷之中。太子参的商旅不论白天黑夜总是人声鼎沸,野山参美酒的香味能够飘到方圆数里的地点。
高丽参依然壹种相当警惕的海洋生物,他们在每座山体上都得以设置瞭望台,并轮
流担当瞭望工作,以管教在第一时间得知外敌的侵袭。 黄参们希望那N
段山脉每段都能够建造瞭望台或旅舍的个中之1,唯有满足这些原则的整座山脉才也许有丹参居住。 以往你指望了然,长度为N
的恐怕有土精居住的山脉有多少种。两座山脉A 和B分歧当且仅当存在多少个i,使得 Ai≠Bi。由于这些数目大概十分的大,你只对它 除以P的余数感兴趣。

Description

相传很久从前,大地上位居着一种神秘的海洋生物:海腴。
太子参喜欢住在连绵不绝的山脉中。具体地说,1座长度为 N 的山峰 H可分
为从左到右的 N 段,每段有三个旷世的可观 Hi,当中Hi是1到N 之间的正
整数。
如若1段山脉比有所与它相近的山体都高,则这段山脉是一个山体。位于边
缘的山脊只有1段周围的山脉,其余都有两段(即左侧和左边)。
类似地,假诺壹段山脉比有所它相近的群山都低,则那段山脉是一个峡谷。
黄党们有3个联机的珍重——饮酒,商旅能够实行在谷底之中。海腴的酒店不论白天黑夜总是人声鼎沸,西洋参美酒的芬芳能够飘到方圆数里的地点。
党参如故1种非常小心的海洋生物,他们在每座山体上都能够设置瞭望台,并轮
流担当瞭望工作,以担保在第暂时间得知外敌的凌犯。 神草们希望那N
段山脉每段都可以建造瞭望台或酒馆的个中之一,唯有满足那个条件的整座山脉才只怕有土精居住。 以往你指望知晓,长度为N
的只怕有人葠居住的群山有稍许种。两座山脉A 和B区别当且仅当存在1个i,使得 Ai≠Bi。由于这么些数额大概非常大,你只对它 除以P的余数感兴趣。

Input

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

Input

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

Output

仅含一行,2个非负整数,表示您所求的答案对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

 

sdfzgzk的blog里讲得太领会了……

mod sdfzgzk

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

 

 

 

 

 

 

 

Source

第一轮Day2

图片 3图片 4

/*
Orz 魏铭。
想出来满分做法。。但是只能70分。
首先,设状态f[i][H][0/1]表示序列posi是H,且为山峰/山谷。然后转移很显然。
不过实现只能强打记忆化搜索。为什么呢?因为他是一个排列。转递推就要状压。就是用bitset也会爆。
抛开空间不讲。时间也过不了。
为什么?转移时O(n)的。如何优化?用前缀和优化变为O(1)。
在处理好空间且保证状态正确的前提下,转成递推,用前缀和转移就好了。当时也想到了,但,写不出来。
当场 魏铭 就用一种很神奇的方法,解决了我的问题,然,我还是看不懂。码力太弱了。。。
此题对我感触很大。
思维:从裸暴力->状压剪枝->换状态->换状态->换状态->优化->正解思路≠>正解代码(码力弱)。
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
typedef long long ll;
const int N=555;
int n,vis[N];
ll f[N][N][2];
ll ans,mod;
//d=1 high
//d=0 low
ll dfs(int cur,int h,bool d){
    ll &res=f[cur][h][d];
    if(~res) return res;
    res=0;
    if(cur>=n) return res=1; 
    if(d){
        for(int i=1;i<h;i++){
            if(!vis[i]){
                vis[i]=1;
                res+=dfs(cur+1,i,!d);
                vis[i]=0;
            }
        }
    }
    else{
        for(int i=h+1;i<=n;i++){
            if(!vis[i]){
                vis[i]=1;
                res+=dfs(cur+1,i,!d);
                vis[i]=0;
            }
        }
    }
    return res%=mod;
}
inline void DFS(){
    for(int i=1;i<=n;i++){
        vis[i]=1;
        dfs(1,i,0);
        dfs(1,i,1);
        vis[i]=0;
    }
    for(int i=1;i<=n;i++){
        ans=(ans+f[1][i][0]+f[1][i][1])%mod;
    }
}
int main(){
    set(goblin);
    memset(f,-1,sizeof f);
    scanf("%d%I64d",&n,&mod);
    if(n==1){printf("%I64d",1LL%mod);}
    if(mod==1){printf("0");}
    DFS();
    printf("%I64d",ans);
    return 0;
} 
/*
附魏铭100分代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define zbwmqlw
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define pow(x) (1<<(x))
const int inf=0x3f3f3f3f;
typedef __int64 LL;
template<class T> void checkmin(T &a,const T &b) 
{if (b<a) a=b;}
template<class T> void checkmax(T &a,const T &b)
{if (b>a) a=b;}

const int N=4300;
int a[20];
bool vis[20],now,last;
int n,ans;
LL f[2][N][2],mo;

void dfs(int depth)
{
    if (depth==n+1) {
        ++ans;
        return;
    }
    int i;
    for (i=1;i<=n;++i) if (!vis[i]) {
        a[depth]=i;
        if (depth>2 && (a[depth]>a[depth-1])==(a[depth-1]>a[depth-2])) continue;
        vis[i]=true;
        dfs(depth+1);
        vis[i]=false;
    }
}

void solvedfs()
{
    ans=0;
    dfs(1);
    printf("%d %d\n",n,ans);
    exit(0);
}

void solvedp()
{
    int i,j,k;
    now=true; last=false;
    memset(f[now],0,sizeof(f[now]));
    for (j=0;j<n;++j) f[now][j][0]=f[now][j][1]=1;
    for (i=2;i<=n;++i) {
        now^=1; last^=1;
        memset(f[now],0,sizeof(f[now]));
        LL s0=0,s1=0;
        for (k=0;k+i-1<=n;++k) s1+=f[last][k][1];
        for (j=0;j+i<=n;++j) {
            s0+=f[last][j][0];
            s1-=f[last][j][1];
            f[now][j][1]=s0%mo;
            f[now][j][0]=s1%mo;
        }
    }
    printf("%I64d\n",(f[now][0][0]+f[now][0][1])%mo);
}

int main()
{
    freopen("goblin.in","r",stdin);
    freopen("goblin.out","w",stdout);
    scanf("%d%I64d",&n,&mo);
    solvedp();
    fclose(stdout);
}

*/

61九分心痛代码

AC思路:http://blog.csdn.net/mrazer/article/details/53426415?locationNum=12&fps=1

#include<cstdio>
#define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=4201;
int f[2][N],n,now,mod,ans;
int main(){
    set(goblin);
    scanf("%d%d",&n,&mod);
    f[now][1]=1;
    for(int i=2;i<=n;i++){
        now^=1;
        for(int j=1;j<=i;j++){
            f[now][j]=(f[now][j-1]+f[now^1][i-j+1])%mod;
        }
    }
    for(int i=1;i<=n;i++) ans=(ans+f[now][i])%mod;
    printf("%d\n",ans*2%mod);
    return 0;
}

 

 

相关文章