首页 > 代码库 > 【55测试】【字符串】【栈】【找规律】
【55测试】【字符串】【栈】【找规律】
集训第二天，额，考崩了。
第一题 hao 大意：（这个名字就不要在意了，其实是祖玛游戏）
模拟祖玛游戏的模式，给一个‘A‘~‘Z‘的字符串，然后有t个插入操作为 “ 添加后的在原字符串的位置 x 插入元素 c ”，字符串中有超过或等于 3 个相同的字符，则被消除，输出每次操作后剩余的字符串，如果为空，则输出“-”。
样例： ACCBA 输出： ABCCBA
5 AABCCBA
1 B AABBCCBA
0 A -
2 B A
4 C
0 A
解：
先开始我用的string，但是cin>>s并不能读取输入为空的情况，所以，就用char来做。插入和删除都用strcpy来做，这个还需熟练。然后每次插入一个后，用while来判断它及不断删除后能不能再继续删除，然后删除。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 3005 6 using namespace std; 7 int n,pos,en; 8 char s[maxn]; 9 bool pd(int p)10 {11 int l=strlen(s),sum1=0,sum2=0;12 for (int i=p+1;i<l;i++)13 if (s[i]==s[p]) {14 en=i;15 sum1++;16 }17 else break;18 for (int i=p-1;i>=0;i--)19 if (s[i]==s[p]) {20 pos=i;21 sum2++;22 }23 else break;24 if (sum1+sum2+1>=3) return true;25 else return false;26 }27 void work(int st)28 {29 pos=st;30 while (1)31 {32 en=pos;//初值 33 if (strlen(s)==0) return ;//判断empty 34 if (pd(pos)) {35 int len=0;char tmp[maxn];36 //len=en-pos+1;37 strcpy(tmp,s+en+1);//******38 strcpy(s+pos,tmp);39 pos--;40 }41 else return ;42 }43 }44 void print()45 {46 int l=strlen(s);47 if (l==0) {48 printf("-");49 printf("\n");50 }51 else cout<<s<<endl;52 return ;53 }54 int main()55 {56 freopen("hao.in","r",stdin);57 freopen("hao.out","w",stdout); 58 s[0]=getchar();59 if(s[0]>=‘A‘&&s[0]<=‘Z‘) scanf("%s",s+1);60 else s[0]=0;61 62 cin>>n;63 for (int i=1;i<=n;i++)64 {65 int x;char a[maxn];66 int l=strlen(s);67 scanf("%d%s",&x,a);68 strcpy(a+1,s+x);69 strcpy(s+x,a);70 work(x);71 print();72 }73 return 0;74 }75 /*76 insert77 char tmp[1005];78 strcpy(tmp+1,s+k);79 strcpy(s+k,tmp);80 81 delete82 st--end--83 strcpy(tmp,s+end);84 strcpy(s+st,tmp); 85 86 */
第二题 kun 大意：（好吧，又来解释题目名字，就是栈排序）
给一个数字序列，通过一个栈对这个序列进行排序，输出按最大字典序的排序后的序列。即：序列 2 1 3，可以通过 2,1入栈，输出3，再输出栈内的1,2得到最大字典序输出。而 3 1 2也可以通过一个栈，得到 3 2 1。数据保证为1~n的全排列。
解：
先开始不懂什么是最大字典序，然后就乱搞，一个点都没有过。最大字典序，就是第一个数为最大的，也就是n（由题中的数据保证可知），然后下一个数不一定是第二大的，而应是相对而言在栈外或者在栈首的最大的。所以可以设一个cur表示当前的相对最大，cur从n~1递减；在1~n的循环中：如果不在栈内，那就让cur之前的全部入栈，while在栈内但不在栈首，那cur--，while在栈首，就输出并且cur--，如果循环到n，就输出栈内的所有元素。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1000005 6 using namespace std; 7 int n,s[maxn],head,stak[maxn],cur; 8 bool in[maxn]; 9 int main()10 {11 freopen("kun.in","r",stdin);12 freopen("kun.out","w",stdout);13 cin>>n;14 for (int i=1;i<=n;i++)15 scanf("%d",&s[i]);16 cur=n;17 for (int i=1;i<=n;i++)18 {19 while (in[cur]&&stak[head]!=cur) cur--;//在栈内，不能取 20 while (head!=0&&stak[head]>=cur)//栈顶有更优的解 21 {22 printf("%d ",stak[head]);23 if (stak[head]==cur) cur--;24 head--;25 while (in[cur]&&stak[head]!=cur) cur--;26 }27 if (s[i]==cur){//在栈外找到一个大的 28 cur--;29 printf("%d ",s[i]);30 }31 else {//不是优解，入栈 32 in[s[i]]=true;33 stak[++head]=s[i];34 }35 if (i==n){36 while (head!=0)37 {38 printf("%d ",stak[head]);39 head--;40 }41 }42 }43 return 0;44 }
第三题 nan 大意：（纯粹的找规律）
有一个序列，前三项为1 2 2，然后从第三个数开始考虑：第三个数是2 ，所以在序列里添加 2个3， 得到1 2 2 3 3；
第四个数是3，所以在序列里添加 3个4，得到 1 2 2 3 3 4 4 4。
last[x]表示数字x在序列中最后出现的位置，有t个询问，输出last[last[x]];
解：
因为数据太大，存不下，所以打表过了30%。那么我们现在来找规律。
1、序列： 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10..........
2、last[x]:1 3 5 8 11 15 19 23 28 33 38 44 50 56 62 69 76 83 90.......
3、last[last[x]]:1 5 11 23 38 62 90 122.........
那么我们把第3 行 last[last[x]]做差，此项减上一项，得到：1 4 6 12 15 24 28 32 45 50........
改变一下就是：1*1， 2*2 ，2*3，3*4，3*5，4*6，4*7，4*8，5*9，5*10........
即一个从1 递增的i * 原序列 1 2 2 3 3 4 4 4 5 5.......
再合并一些得到：1*1，2*(2+3), 3*(4+5), 4*(6+7+8),......
每一项用等差和表示，（首项+尾项）*项数 / 2.
然后用一个前缀和的方式记录答案。但是有可能询问的不是那一段的末尾，就需要用上一段的前缀和加上这一段。如当询问7的时候，7在 4 4 4 4中的第二个，所以就ans加上 到3 的前缀和，再加上从4开始的等差和就可以了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1300005 6 #define P 1000000007 7 #define ll long long 8 using namespace std; 9 ll t,sum[maxn],cur,last[maxn];10 struct pp{11 ll l,r;12 };13 pp f[maxn];14 void pre()15 {16 f[1].l=f[1].r=1;17 f[2].l=2;f[2].r=3;18 last[1]=1;last[2]=3;cur=2;19 for (ll i=3;i<=maxn+1;i++)20 {21 last[i]=last[i-1]+cur;22 f[i].l=last[i-1]+1;23 f[i].r=last[i];24 if (i>=last[cur]) cur++;// >=25 }26 for (ll i=1;i<=maxn+1;i++)27 {28 sum[i]=sum[i-1]+(f[i].l+f[i].r)*i*(f[i].r-f[i].l+1)/2%P;29 sum[i]%=P;30 }31 }32 int main()33 {34 freopen("nan.in","r",stdin);35 freopen("nan.out","w",stdout);36 pre();37 cin>>t;38 for (int i=1;i<=t;i++){39 ll x,ans=0;40 scanf("%I64d",&x);41 ll li=1,ri=maxn+1;42 while (li<=ri){43 ll mid=(li+ri)>>1;44 if (f[mid].r<x) li=mid+1;45 else ri=mid-1;46 }47 //if (f[ri].r<x) ri+=1;48 ans=sum[ri];49 ans+=(ri+1)*(x+f[ri+1].l)*(x-f[ri].r)/2%P;50 ans%=P;51 printf("%I64d\n",ans);52 }53 return 0;54 }
明天加油！
【55测试】【字符串】【栈】【找规律】