midpoint displacement
题目描述:
midpoint displacement算法是一种能够用于生成一维噪声的算法。
通俗地讲,你有一个长度为2^n+1的数组,初始时给你两端的权值,你要随机性地给每个下标赋一个权值,最终这个数组在统计学上会有一些优秀的性质。直观地讲,如果把权值视为高度的话,他会较为平滑而又有所起伏,仿佛层峦叠嶂在你眼前。
整个算法由若干次midpoint displacement不断进行来构成。
在一次midpoint displacement中,对于除了最后一个下标外的每一个已经被赋值的下标i,找到他后面第一个已经被赋值的下标j,将i和j的中点的权值设为i的权值与j的权值的平均数+一个随机数(可能为负,假设范围为[-lim,lim])
每进行一次midpoint displacement,随机数的范围lim就会缩小一倍。
当所有下标都被赋值,算法结束。
为了测评方便,避免随机化与浮点数,在本题中使用光老犇随机器,一定会随机到最大的数,同时不取平均数,而是直接作和。也就是说,在midpoint displacement的时候,我们令中点的权值等于两端的权值的和加上lim,模1e9+7。并且,每进行完一次midpoint displacement,我们将lim乘以2,并模1e9+7
在样例解释中你可以得到详细的解释。
现在给定n,初始时两端的权值,以及随机数的初始范围,请计算最终每个点的权值和模1e9+7
输入格式:
一行4个整数,分别代表n,左端权值,右端权值,随机数的初始范围
输出格式:
一行一个整数,代表最终所有元素的和模1e9+7
样例输入:
3 1 1 1
样例输出:
65
样例解释:
n=3,所以数组长度为2^n+1=9
最终数组如下:
1 11 6 13 3 13 6 11 1
初始时左右两端为1,lim=1
下标从1开始
a[5]=a[1]+a[9]+lim=3
lim=lim*2=2
a[3]=a[1]+a[5]+lim=6
a[7]=a[5]+a[9]+lim=6
lim=lim*2=4
a[2]=a[1]+a[3]+lim=11
a[4]=a[3]+a[5]+lim=13
a[6]=a[5]+a[7]+lim=13
a[8]=a[7]+a[9]+lim=11
所有点都被赋值,算法结束。
所有元素和为65
提示:请注意你的程序在进行连续加法时是否会超出int型整数的范围
数据范围与约定:
对于所有数据,0<=两端权值、lim<=32767
测试点编号 |
n |
其他约定 |
1 |
<=23 |
a[1]=a[2^n+1]=lim=0 |
2 |
<=3 |
|
3 |
<=3 |
|
4 |
<=3 |
|
5 |
<=16 |
|
6 |
<=16 |
|
7 |
<=16 |
|
8 |
<=23 |
|
9 |
<=23 |
|
10 |
<=23 |
|
我的程序--60
#include<stdio.h> #include<iostream> #include<math.h> #include<string.h> #include<algorithm> using namespace std; int MAXN=1000000007; int a[9000000]; int n,lim; long long sum=0; int main() { freopen("midpointdisplacement.in","r",stdin); freopen("midpointdisplacement.out","w",stdout); int i,j; int cnt=0,mid; cin>>n; n=(1<<n)+1;//r=n; cin>>a[1]>>a[n]>>lim; if(a[1]==0&&a[n]==0&&lim==0){cout<<0<<endl;return 0;} cnt=(n-1)/2; while(cnt!=0) { mid=1; while(mid!=n) { mid=mid+cnt; if(a[mid]==0) { a[mid]=a[mid-cnt]+a[mid+cnt]+lim; //cout<<mid<<" "<<a[mid]<<endl; } } lim=lim*2; cnt=cnt/2; //cout<<cnt<<endl; } for(i=1;i<=n;i++) { sum=sum+a[i]; sum=sum%MAXN; } cout<<sum%MAXN<<endl; return 0; }
超时了,4 re
满分--递归法 //inline 读入优化
c++中 cin 的读入效率是很低很低的,一般可以用scanf,
但有时一些变态题也会TLE,比如noip2011 道路修建,读入数据超大的,
所以用快速读入(只能读数字)
输入字符转换成数字,效率高,在输入数据量特别大的时候采用快速读入可以避免超时
当然正负可以保证。const int mod=1e9+7;注意是 1 不是l!!
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<map> #define mod 1000000007 #define ll long long using namespace std; ll n,l,r,lim,ans; /*inline ll read() { ll f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }*/ void plu(int step,ll x,ll y,ll li) { if(step<=n) { step++; ll h=(x+y+li)%mod; ans=(ans+h)%mod; li=(li*2)%mod; plu(step,x,h,li);plu(step,h,y,li); } } int main() { //freopen("midpointdisplacement.in","r",stdin); //freopen("midpointdisplacement.out","w",stdout); cin>>n>>l>>r>>lim; n=read();l=read();r=read();lim=read(); ans=(l+r)%mod; plu(1,l,r,lim); cout<<ans<<endl; return 0; }
给你一个字符串,请问其有多少个子序列为erewrwerwer
输入格式:
一行一个字符串,由小写字母’e’、’w’或者’r’组成
输出格式:
一行一个整数,表示为erewrwerwer的子序列数,模1e9+7
样例输入:
erewrwerwererewrwerwer
样例输出:
260
数据范围与约定:
设n为字符串长度
对于前%20的数据,n<=11
对于另外%30的数据,n<=20
对于%100的数据,n<=100000
首先可以骗20分,<11 =0,=11PD;
100分dp
法一 注意右移
#include<bits/stdc++.h> using namespace std; const long long wangziheng=1e9+7; char a[100005]; long long dp[100005][12],n; int main() { scanf("%s",a+1); n=strlen(a+1);//开始串长半天有问题 for(int i=1;i<=n;i++) { for(int j=1;j<=11;j++) dp[i][j]=dp[i-1][j];//右移 erewrwerwer if(a[i]=='e') { dp[i][1]=(dp[i-1][1]+1)%wangziheng;//第一个点特殊处理 dp[i][3]=(dp[i][3]+dp[i-1][2])%wangziheng;//dp[i][j]表示从第 dp[i][7]=(dp[i][7]+dp[i-1][6])%wangziheng; dp[i][10]=(dp[i][10]+dp[i-1][9])%wangziheng; } if(a[i]=='r') { dp[i][2]=(dp[i][2]+dp[i-1][1])%wangziheng; dp[i][5]=(dp[i][5]+dp[i-1][4])%wangziheng; dp[i][8]=(dp[i][8]+dp[i-1][7])%wangziheng; dp[i][11]=(dp[i][11]+dp[i-1][10])%wangziheng; } if(a[i]=='w') { dp[i][4]=(dp[i][4]+dp[i-1][3])%wangziheng; dp[i][6]=(dp[i][6]+dp[i-1][5])%wangziheng; dp[i][9]=(dp[i][9]+dp[i-1][8])%wangziheng; } } } cout<<dp[n][11]; return 0; }
法二
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<map> #define mod 1000000007 #define ll long long const int maxn=100000+10; using namespace std; char b[maxn],a[20]={'e','e','r','e','w','r','w','e','r','w','e','r'}; ll l,ans,f[maxn][12]; int main() { //freopen("erewrwerwer.in","r",stdin); //freopen("erewrwerwer.out","w",stdout); gets(b+1);l=strlen(b+1); for(int i=0;i<=l;i++) f[i][0]=1; for(int i=1;i<=l;i++) for(int j=1;j<=min(11,i);j++) { if(a[j]==b[i]) f[i][j]=(f[i][j]+f[i-1][j-1])%mod; f[i][j]=(f[i][j]+f[i-1][j])%mod; } cout<<f[l][11]<<endl; }