首页 > 代码库 > 17-05-24模拟赛

17-05-24模拟赛

2024-09-25 11:16:02   258人阅读

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 }

 

17-05-24模拟赛


联系
我们