17-05-24模拟赛

T1:

(1)将两种数分别放入两个队列中，对当前的两个数进行比较，将较小的数放入答案栈并进行扩展即可。

(2)从前往后维护答案栈的单调不增性，若删的数字达到m个则将剩余数字全部进栈，若答案栈搜完但删的数字仍不到m个则从后往前删去数字直到删的数字达到m个。

Code:

 1 #include<iostream> 
 2 #include<cmath> 
 3 #include<cstdio> 
 4 #include<cstdlib> 
 5 #include<cstring> 
 6 #include<algorithm> 
 7 using namespace std; 
 8 int q[2][50005],qu[30005],head[2],tail[2]; 
 9 char ch[200005]; 
10 int k,m,cnt=1,x,del=0; 
11 int main() 
12 { 
13     scanf("%d%d",&k,&m);qu[1]=1;q[0][1]=3;q[1][1]=9; 
14     head[0]=head[1]=1;tail[1]=tail[0]=1; 
15     while (cnt<k){ 
16         if (q[0][head[0]]<q[1][head[1]])qu[++cnt]=q[0][head[0]],head[0]++; 
17         else qu[++cnt]=q[1][head[1]],head[1]++; 
18         q[0][++tail[0]]=(qu[cnt]<<1)+1;q[1][++tail[1]]=(qu[cnt]<<2)+5; 
19     } 
20     for (int i=1;i<=cnt;++i) printf("%d",qu[i]);cout<<endl; 
21     int cur=0;ch[0]='1'; 
22     for (int i=2;i<=cnt;++i){ 
23         char x[7];sprintf(x,"%d",qu[i]); 
24         for (int j=0;j<strlen(x);++j){ 
25             if (del==m) ch[++cur]=x[j]; 
26             else { 
27                 while (x[j]>ch[cur]&&cur>=0&&del<m) --cur,++del;ch[++cur]=x[j]; 
28             } 
29         } 
30     } 
31     if (del<m) cur-=(m-del); 
32     for (int i=0;i<=cur;++i) printf("%c",ch[i]);return 0; 
33 }

T2:

(1)读入时将大于b的数的a值设为1,小于b的数的a值设为-1,b的a值设为0,并找到b的位置。

(2)从b开始分别向左向右求前缀和，并将该和存在的个数+1。

(3)搜索前缀和的个数，答案加上两个相加为0的前缀和的个数的乘积。

注意到C++语言不支持数组下标为负，所以前缀和初始化时以n开始，答案应加上两个相加为2n的前缀和的个数的乘积。

Code:

 1 #include<iostream> 
 2 #include<cmath> 
 3 #include<cstdio> 
 4 #include<cstdlib> 
 5 #include<cstring> 
 6 #include<algorithm> 
 7 using namespace std; 
 8 int a[100005],l[200005],r[200005],x,y,t,n,b,pos=0,ans; 
 9 int main() 
10 {
11     scanf("%d%d",&n,&b);
12     for (int i=1;i<=n;++i){ 
13         scanf("%d",&t);if(t==b) a[i]=0,pos=i; 
14         else a[i]=t>b?1:-1; 
15     }x=y=n;l[n]=r[n]=1; 
16     for (int i=pos-1;i;--i) x+=a[i],l[x]++; 
17     for (int i=pos+1;i<=n;++i) y+=a[i],r[y]++; 
18     for (int i=1;i<=(n<<1);++i) ans+=l[i]*r[(n<<1)-i]; 
19     printf("%d",ans);return 0; 
20 }

T3:

考虑该式的数据范围(m<10¹⁷)，我们考虑对其进行二分求解。

若m为偶数，注意到(n+n²+...+n^m) mod p可以看作((n+n²+...+n^m/2) mod p+n^m/2*((n+n²+...+n^m/2) mod p) mod p) mod p,

则只要递归算出(n+n²+...+n^m/2)的值并用快速幂算出n^m/2的值即可。

若m为奇数，注意到(n+n²+...+n^m) mod p可以看作((n+n²+...+n^m/2) mod p+n^m/2+1*((n+n²+...+n^m/2) mod p+1) mod p) mod p,(“/”向下取整)

则只要递归算出(n+n²+...+n^m/2)的值并用快速幂算出n^m/2+1的值即可。

Code:

 1 #include<iostream> 
 2 #include<cmath> 
 3 #include<cstdio> 
 4 #include<cstdlib> 
 5 #include<cstring> 
 6 #include<algorithm> 
 7 #define ll long long 
 8 using namespace std; 
 9 ll n,m,p; 
10 ll qpow(ll x){ 
11     ll mul=n,ans=1; 
12     while(x){ 
13         if (x&1ll) ans=(ans*mul)%p; 
14         mul=(mul*mul)%p;x>>=1; 
15     } 
16     return ans; 
17 } 
18 ll sum(ll x){ 
19     if (x==1) return n%p;ll t=sum(x>>1); 
20     if (x&1ll) return (t+qpow((x>>1)+1)*(t+1)%p)%p; 
21     else return (t+qpow(x>>1)*t%p)%p; 
22 } 
23 int main() 
24 { 
25     scanf("%lld%lld%lld",&n,&m,&p); 
26     printf("%lld",sum(m));return 0; 
27 }

T4:期望dp,注意细节处理。

Code:

 1 #include<iostream> 
 2 #include<cmath> 
 3 #include<cstdio> 
 4 #include<cstdlib> 
 5 #include<cstring> 
 6 #include<algorithm> 
 7 using namespace std; 
 8 int R,T; 
 9 double f[503][503],H; 
10 int main() 
11 { 
12     scanf("%d%lf%d",&R,&H,&T); 
13     for (int i=1;i<=T;++i) 
14     for (int j=1;j<=R;++j){ 
15         double sum=H*(R-j)*f[i-1][j];
16         for (int k=1;k<=j;++k){ 
17             double dh=floor(f[i-1][j]-f[i-1][k]); 
18             if (dh<0) dh=0;if (dh>H) dh=H; 
19             sum+=f[i-1][j]*dh; 
20             sum+=(H-dh)*f[i-1][k]+(H+1.0+dh)*(H-dh)/2.0; 
21         }f[i][j]=sum/H/double(R);    
22     }printf("%.3lf",f[T][R]);return 0; 
23 }