这套是黈力的题，题目应该比我出的难，每道题都想了好久，没有一眼秒，因为种种原因晚交了7min，如果多7min就能多30分啊。

T1 马三的数列

很明显只要对于每个数求出在左边最多能伸展几个，右边最多能伸展几个，乘起来就可以了

于是每次维护一个单调下降的数列，然后一个一个数加进来判断就行啦

一开始没考虑负数，幸亏黈力提醒，不然就爆0啦！

#include<cstdio>
#define N 1111111
long 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放到最后

然后求的时候可以用分子和分母先求好，求完后再逆元弄一次就可以了

#include<cstdio>
#define MOD 1000000007
#define N 222222
typedef 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个点，但写了好久、、

#include<cstdio>
#include<cstring>
#define MOD 1000000007
long 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");
        }
    }
	}
}

• 相关文章推荐
• 全局相关文章