noip仿真模拟44 solutions

这一场抱零的也忒多了,因为我仅有45pts

听说好像是把几身题里边较难的整理出去使我们考试能够顺利通过

好激烈啊,此次的考試我仅有第一题骗了40pts,别的都抱零了

T1 Emotional Flutter

这一我立即用线段树维护保养解集,

那样的,你不能碰到每一个黑块,因此 每一个黑块都相匹配着一个不踩他的范畴

大家用线段树维护保养这种范畴的相交,由于函数值域有点儿大因此 炸了

40pts



#include<bits/stdc  .h>
using namespace std;
#define re register int 
#define ll long long
const int N=5e5 5;
ll T,s,k,n,cnt,a[N],pre[N];
struct XDS{
	int mx[N*15],ls[N*15],rs[N*15],laz[N*15];
	int seg,rt;
	void clear(){seg=0;rt=0;mx[0]=mx[1]=0;}
	int newNode(){  seg;ls[seg]=rs[seg]=mx[seg]=laz[seg]=0;return seg;}
	void pushup(int x){
		mx[x]=max(mx[ls[x]],mx[rs[x]]);
		return ;
	}
	void pushdown(int x){
		if(!laz[x])return ;
		if(!ls[x])ls[x]=newnode();
		if(!rs[x])rs[x]=newnode();
		mx[ls[x]] =laz[x];
		mx[rs[x]] =laz[x];
		laz[ls[x]] =laz[x];
		laz[rs[x]] =laz[x];
		laz[x]=0;
		return ;
	}
	void ins(int &x,int l,int r,int ql,int qr){
		if(ql>r||qr<l||ql>qr)return ;
		if(!x)x=newnode();
		if(ql<=l&&r<=qr){
			laz[x]  ;mx[x]  ;
			return ;
		}
		pushdown(x);
		int mid=l r>>1;
		if(ql<=mid)ins(ls[x],l,mid,ql,qr);
		if(qr>mid)ins(rs[x],mid 1,r,ql,qr);
		pushup(x);return ;
	}
}xds;
signed main(){
	//cout<<(sizeof(xds.mx)*4 sizeof(a) sizeof(pre)>>20)<<endl;
	//xds.mx[1]=10000;cout<<xds.mx[1]<<endl;
	scanf("%lld",&T);
	while(T--){cnt=0;
		scanf("%lld%lld%lld",&s,&k,&n);
		for(re i=1;i<=n;i  ){
			scanf("%lld",&a[i]),pre[i]=pre[i-1] a[i];
		}
		for(re i=0;i<=n;i  ){
			if(i&1)continue;cnt  ;
			ll tmp=pre[i]%k,l0=-1,r0=-1,l1=-1,r1=-1;
			if(a[i 1] tmp s<=k){
				l0=0,r0=k-a[i 1]-tmp-s;
				xds.ins(xds.rt,0,k-1,l0,r0);
			}
			if(tmp){
				l1=k-tmp,r1=min(l1 k-a[i 1]-s,k-1);
				xds.ins(xds.rt,0,k-1,l1,r1);
			}
		}
		if(xds.mx[xds.rt]>=cnt)printf("TAK\n");
		else printf("NIE\n");
		xds.clear();
	}
}


实际上正确的答案也是有\(log\)的,只不过是他的放到了1e5上,可是我的放到了1e9*1e5上,而且室内空间仿佛都不太够

每一次只有超越k个格,那麼大家每一次碰到的点在%k实际意义下都是在一个点上

而且这一点不可以被一切一个黑块遮盖,因此 把全部黑块弄出来

排列,减掉不起作用的,随后去遮盖,假如能寻找缺口便是合理合法的

脚内长为s,立即对黑块的长的 s,

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=5e5 5;
ll T,s,k,n,a[N],fro;
struct node{
	ll l,r;
	node(){}
	bool operator < (node x)const{
		if(l==x.l)return r>x.r;
		return l<x.l;
	}
}sca[N];
int cnt,mnt;
signed main(){
	scanf("%lld",&T);
	while(T--){
		cnt=0;mnt=0;fro=0;
		scanf("%lld%lld%lld",&s,&k,&n);
		//if(k<s){printf("NIE\n");continue;}
		bool flag=false;
		for(re i=1;i<=n;i  ){
			scanf("%lld",&a[i]);
			if(a[i] s>k&&(i&1))flag=true;
		}
		if(flag||k<s){printf("NIE\n");continue;}
		//cout<<"Sb"<<endl;
		for(re i=1;i<=n;i  ){
			if((i^1)&1){fro =a[i];continue;}
			a[i] =s;a[i 1]-=s;
			ll pl=(fro 1)%k,pr=(fro a[i]-1)%k;
			//cout<<i<<" "<<pl<<" "<<pr<<endl;
			fro =a[i];
			sca[  cnt].l=pl;
			if(pr>=pl)sca[cnt].r=pr;
			else {
				sca[cnt].r=k-1;
				sca[  cnt].l=0;
				sca[cnt].r=pr;
			}
			//cout<<i<<" "<<sca[cnt].l<<" "<<sca[cnt].r<<endl;
		}
		sort(sca 1,sca cnt 1);mnt=1;
		for(re i=2;i<=cnt;i  ){
			if(sca[i].l>=sca[mnt].l&&sca[i].r<=sca[mnt].r)continue;
			sca[  mnt]=sca[i];
		}
		flag=false;
		if(sca[1].l!=0||sca[mnt].r!=k-1)flag=true;
		//cout<<flag<<endl;
		for(re i=1;i<mnt;i  ){
			if(sca[i].r 1<sca[i 1].l){
				//cout<<i<<endl;
				flag=true;
			}
			if(flag)break;
		}
		//cout<<sca[1].l<<" "<<sca[mnt].r<<endl;
		if(flag)printf("TAK\n");
		else printf("NIE\n");
	}
}


留意边界争端极为ex

T2 Medium Counting

正确的答案与我考试场上想的一样,便是运用后边的尺寸计划方案发布前边的计划方案数

可是我考试场上只有一个基本的构思,沒有实际的完成出去,因此 00000

假如当今字符串数组短得话,后边补0就可以了

随后大家针对当今这一位,大家枚举类型分界线,看什么时候 1

随后立即记忆化搜索就好了

dp二维数组含意:dp[i][j][l][r]表明i位,最少的是c,范畴是l-r,的计划方案数

假如当今这一位被评定为c,那麼前边的字符串数组就不可以依据当今这一位来分辨

只有用后边的标识符来差别她们的尺寸,这个时候就迁移到下一层

最终小小判一下界限就可以了

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const ll mod=990804011;
ll n,dp[25][28][55][55];
char ch[55][25];
int a[55][25];
ll dfs(int p,int c,int l,int r){
	if(dp[p][c][l][r]!=-1)return dp[p][c][l][r];
	if(l>r)return dp[p][c][l][r]=1;
	if(p>20)return dp[p][c][l][r]=(l==r);
	if(c>26)return 0;
	dp[p][c][l][r]=dfs(p,c 1,l,r);
	//cout<<dp[p][c][l][r]<<endl;
	for(re i=l;i<=r;i  ){
		if((a[i][p]!=c&&a[i][p]!=27)||(a[i][p]==27&&!c))break;
		dp[p][c][l][r]=(dp[p][c][l][r] dfs(p 1,0,l,i)*dfs(p,c 1,i 1,r)%mod)%mod;
	}
	return dp[p][c][l][r];
}
signed main(){
	memset(dp,-1,sizeof(dp));
	scanf("%lld",&n);
	for(re i=1;i<=n;i  ){
		scanf("%s",ch[i] 1);
		for(re j=1;j<=strlen(ch[i] 1);j  ){
			if(ch[i][j]=='?')a[i][j]=27;
			else a[i][j]=ch[i][j]-'a' 1;
		}
	}
	printf("%lld",dfs(1,0,1,n));
}


T3 Huge Counting

这一也是一个更为恶心想吐的记数题,我确实不想说啥了

或是数位dp,害,气人了

她们都说挺显而易见的是可重集排序,吼吼吼,我TM看过大半天才看出去

每一次挑选一个数-1,因此 减的次序便是一个排序,由于许多同一位的加减法是同样的,因此 可多次

那么就立即套公式计算就可以了\(\huge\frac{(\sum{x_i})!}{\prod{x_i!}}\)

因此你只必须分辨奇偶性就可以了(殊不知我考试场上并沒有看到mod2)

用那一个經典公式计算\(sum_2(x!)=\frac{x}{2} \frac{x}{4} \frac{x}{8} …..\)

暴力行为求得话能够 取得40pts的优异成绩

40pts

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=15;
const ll mod=990804011;
ll T,k,l[N],r[N],ans,ji[N];
void dfs(int x){
	if(x==k 1){
		ll tmp=0,sum=0,t=2;
		for(re i=1;i<x;i  )tmp =ji[i];
		tmp/=2;while(tmp)sum =tmp,tmp/=2;
		for(re i=1;i<x;i  ){
			ll now=ji[i]/2;
			while(now)sum-=now,now/=2;
		}
		if(!sum)ans  ;
		//if(ji[1]!=0)cout<<ji[1]<<endl;
		if(ans>mod)ans-=mod;
		return ;
	}
	for(ll i=l[x];i<=r[x];i  ){
		ji[x]=i-1;dfs(x 1);
	}
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&k);ans=0;
		for(re i=1;i<=k;i  )scanf("%lld%lld",&l[i],&r[i]);
		dfs(1);
		printf("%lld\n",ans);
	}
}


随后你发觉左右两一部分,假如加和沒有进位得话,她们2个有的2的因素数量是同样的

因此 假如想让这种x对答案有奉献,就需要让这种x的二进制表明每一位上最多有一个1

因此 立即多位do,设dp[i][s]表明第i位,卡界限的状况为s,便是每一个x的

留意不必臆想去卡左右界限,由于二维数组开不出来,因此 要容斥,多步的

我是用dfs完成的容斥指数,还可以用1的个数的奇偶性来明确

立即迁移就可以了,我是看了题解编码才会的。。。。。。。

迁移的情况下,我们要先把每一个卡界限的0拿出来,

此刻全是0,计划方案行得通,

再去枚举类型每一个很有可能的1,假如卡界限就需要把界限卡上,

假如流畅,那么就或是原先的界限

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
#define ll long long
const int N=15;
const ll mod=990804011;
ll T,k,l[N],r[N],ans,ji[N];
ll f[52][1<<10];
ll get_ans(){
	memset(f,0,sizeof(f));
	f[50][(1<<k)-1]=1;
	for(re i=50;i>=1;i--){
		for(re j=0;j<(1<<k);j  ){
			if(!f[i][j])continue;
			ll tmp=0;
			for(re l=1;l<=k;l  )
				if((j>>l-1)&1 && ((ji[l]>>i-1)^1)&1)
					tmp|=(1<<l-1);
			f[i-1][tmp]=(f[i-1][tmp] f[i][j])%mod;
			for(re l=1;l<=k;l  )
				if(((j>>l-1)^1)&1)f[i-1][tmp]=(f[i-1][tmp] f[i][j])%mod;
				else if((ji[l]>>i-1)&1)f[i-1][tmp|(1<<l-1)]=(f[i-1][tmp|(1<<l-1)] f[i][j])%mod;
		}
	}
	ll ret=0;
	for(re i=0;i<(1<<k);i  )ret=(ret f[0][i])%mod;
	return ret;
}
void dfs(int x,int fl){
	if(x==k 1){
		ans=(ans get_ans()*fl mod)%mod;
		return ;
	}
	ji[x]=r[x];
	dfs(x 1,fl);
	if(l[x]-1>=0){
		ji[x]=l[x]-1;
		dfs(x 1,-fl);
	}
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&k);ans=0;
		for(re i=1;i<=k;i  )scanf("%lld%lld",&l[i],&r[i]),l[i]--,r[i]--;
		dfs(1,1);
		printf("%lld\n",ans);
	}
}


T4 标识符清除2

说实话,一开始我连题面都没看懂,

之后发觉是寻找一个和原字符串数组t结合同样的01串

那样的话,大家先寻找全部行得通的t

立即用KMP从n往前跳,全部蹦出来的数,用n减掉它,便是一个行得通的t

随后考虑到结构这一01串,我们要把KMP配对到的全部的长短记下来

假如下一个的长短\(\le\)当今的2倍,那么就立即拷贝以往就可以了

否则的话,我也把正中间的全干成0,随后再跑一边KMP,看一下还是否原先的配对

我是立即将以前的p表针记下来,随后立即跳回去,

要不是原先的配对了,就把最终一位换为1

AC_code

#include<bits/stdc  .h>
using namespace std;
#define re register int
const int N=2e5 5;
char ch[N];
int T,n,fail[N],p,len[N],cnt;
int nxt[N],pri[N],tot;
void kmp(int l,int r){
	for(re i=l;i<=r;i  ){
		while(pri[i]!=pri[p 1]&&p)p=nxt[p];
		if(pri[i]==pri[p 1])p  ;
		nxt[i]=p;
	}
}
signed main(){
	scanf("%d",&T);
	while(T--){
		memset(fail,0,sizeof(fail));
		memset(len,0,sizeof(len));
		memset(nxt,0,sizeof(nxt));
		memset(pri,0,sizeof(pri));
		p=cnt=tot=0;
		scanf("%s",ch 1);n=strlen(ch 1);
		//cout<<"sb"<<endl;
		for(re i=2,j=0;i<=n;i  ){
			while(ch[i]!=ch[j 1]&&j)j=fail[j];
			if(ch[i]==ch[j 1])j  ;
			//cout<<i<<" "<<j<<endl;
			fail[i]=j;
		}
		int now=n;while(now)len[  cnt]=now,now=fail[now];//cout<<now<<endl;
		if(len[cnt]>1)pri[len[cnt]]=1;
		kmp(2,len[cnt]);
		//cout<<"sb"<<endl;
		//cout<<p<<endl;
		for(re i=cnt-1;i>=1;i--){
			if(len[i]>len[i 1]*2){
				kmp(len[i 1] 1,len[i]-len[i 1]-1);
				int pi=p;
				for(re j=1;j<=len[i 1];j  )pri[len[i]-len[i 1] j]=pri[j];
				kmp(len[i]-len[i 1],len[i]);
				//for(re j=1;j<=len[i];j  )cout<<pri[j];cout<<endl;
				//cout<<nxt[len[i]]<<endl;
				if(nxt[len[i]]!=len[i 1]){
					p=pi;pri[len[i]-len[i 1]]=1;
					kmp(len[i]-len[i 1],len[i]);
				}
			}
			else {
				for(re j=len[i 1] 1;j<=len[i];j  )
					pri[j]=pri[j-len[i] len[i 1]];
				kmp(len[i 1] 1,len[i]);
			}
		}
		for(re i=1;i<=n;i  )printf("%d",pri[i]);
		printf("\n");
	}
}