【马三模拟赛】Day2题解
这套是黈力的题，题目应该比我出的难，每道题都想了好久，没有一眼秒，因为种种原因晚交了7min，如果多7min就能多30分啊。
T1 马三的数列
很明显只要对于每个数求出在左边最多能伸展几个，右边最多能伸展几个，乘起来就可以了
于是每次维护一个单调下降的数列，然后一个一个数加进来判断就行啦
一开始没考虑负数，幸亏黈力提醒，不然就爆0啦！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include<cstdio>#define N 1111111long long n,i,j,u,now,head,a[N],ans1[N],ans2[N],q[N];char ch;int main(){ scanf("%lld",&n); for(i=1;i<=n;i++)scanf("%lld",&a[i]); a[0]=-2e9;q[1]=1;head=1;ans1[1]=1; for(i=2;i<=n;i++){ while(a[i]>a[q[head]]&&head)head--; ans1[i]=i-q[head]; q[++head]=i; } a[n+1]=-2e9;q[0]=n+1;q[1]=n;head=1;ans2[n]=1; for(i=n-1;i;i--){ while(a[i]>=a[q[head]]&&head)head--; ans2[i]=q[head]-i; q[++head]=i; } for(i=1;i<=n;i++)printf("%lld ",ans1[i]*ans2[i]);} |
T2 马三的宝箱
一开始就想到把一个A，一个B，一个C取出来，剩下的再排，但似乎没法做
然后考虑AB、AC、BC之间两两的关系，想把他们都符合条件的概率容斥一下算出来，但答案不对，因为两两之间的关系会互相影响，所以概率不能这么算
然后我把初始的全排列全写了出来，一开始写错了。。然后发现似乎一开始A和B的关系固定，然后把AB打包起来和C比就行了
于是先求出全排列方案数ans，然后维护一个前缀和sum[i],每次ans=ans*a[i]/sum[i]，因为要让前面的打包起来合法，必须要让至少有一个i放到最后
然后求的时候可以用分子和分母先求好，求完后再逆元弄一次就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include<cstdio>#define MOD 1000000007#define N 222222typedef long long LL;LL n,i,j,fz,fm,x,y,a[N],sum[N];void exgcd(LL a,LL b,LL &x,LL &y){ if(!b){x=1;y=0;return;} exgcd(b,a%b,x,y); LL t=x;x=y;y=t-a/b*y;}int main(){ scanf("%lld",&n); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } fz=1;for(i=2;i<=sum[n];i++)fz=(fz*i)%MOD; fm=1;for(i=1;i<=n;i++)for(j=2;j<=a[i];j++)fm=(fm*j)%MOD; for(i=2;i<=n;i++){ fz=(fz*a[i])%MOD; fm=(fm*sum[i])%MOD; } exgcd(fm,MOD,x,y); if(x<0)x+=MOD; printf("%lld",(fz*x)%MOD);} |
T3 马三的密码
用了个傻逼的算法：HASH+矩乘 过了6个点，但写了好久、、
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include<cstdio>#include<cstring>#define MOD 1000000007long long n,p,q,x,i,j,now,wil,T,w,hash[1111111];bool ff;char s[1111111],ss[1111111],ch;struct JZ{long long x,y,m[3][3];}ans,def;JZ cheng(JZ a,JZ b){ JZ c;memset(c.m,0,sizeof c.m); c.x=a.x;c.y=b.y; for(int i=1;i<=a.x;i++) for(int j=1;j<=b.y;j++) for(int k=1;k<=a.y;k++) c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j])%MOD)%MOD; return c;}int main(){ scanf("%s",s);n=strlen(s); if(n>1111){ scanf("%lld",&T); hash[0]=s[0]-'a'+1; for(i=1;i<n;i++)hash[i]=(hash[i-1]*27+s[i]-'a'+1)%MOD; while(T--){ scanf("%lld",&p); if(p==1){ scanf("%lld",&x); scanf("%s",ss); s[x-1]=ss[0]; }else if(p==2){ scanf("%s",ss); hash[n]=(hash[n-1]*27+ss[0]-'a'+1)%MOD; s[n]=ss[0]; n++; }else if(p==3){ scanf("%s",ss);p=strlen(ss); now=ss[0]-'a'+1;w=27;for(j=1;j<p;j++)now=(now*27+ss[j]-'a'+1)%MOD,w=(w*27)%MOD; q=n/p;wil=hash[p*q-1]; ans.x=1;ans.y=2; ans.m[1][1]=now; ans.m[1][2]=1; def.x=def.y=2; def.m[1][1]=w;def.m[1][2]=0; def.m[2][1]=now;def.m[2][2]=1; w=q-1; for(;w;w>>=1){ if(w&1)ans=cheng(ans,def); def=cheng(def,def); } if(ans.m[1][1]==wil){ ff=1; for(i=p*q;i<n;i++)if(ss[i-p*q]!=s[i]){ff=0;break;} if(ff)puts("YES");else puts("NO"); }else puts("NO"); } } }else{ scanf("%d",&n); while(n--){ scanf("%d",&p); if(p==1){ scanf("%d",&x); scanf("%s",ss); s[x-1]=ss[0]; }else if(p==2){ scanf("%s",ss); for(j=0;j<strlen(ss);j++)s[strlen(s)]=ss[j]; }else if(p==3){ scanf("%s",ss);now=strlen(ss);ff=1; for(j=0;j<strlen(s);j++) if(ss[j%now]!=s[j]){ff=0;break;} if(ff)puts("YES");else puts("NO"); } } }} |
2015年7月14日 14:55
黈力的题多良心比你出的简单不知多少倍
2015年7月14日 14:56
只过了6个点就好意思说自己ak了
2015年7月15日 15:14
被主力爷骂了~~~~(>_<)~~~~