noip模拟42[很有感觉哦哦哦]

2024-01-16 18:21:16

noip模拟42 solutions

其实吧，这次考试还是非常成功的，找到感觉，

这才是noip的真正难度吧，前两题足够我切掉。。。

后面两个有一点小小的思路，看题解看一会就会了

不对不对，我真的看了好久题解都没想出来。。。

真的挺难的。。。。哭

T1 卷

这这这这这就是一个一眼就能切的树形dp，

这个转移真的一眼就能想出来，一个选一个不选嘛，这有啥难的

然后就是转移的时候有个比较大小的东西

我们用log实现，log几都行，我试过都不会炸

因为考场上不知道log函数的底数是e，直接用它做的，也A掉了

AC_code


#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define ld long double
const int N=2e5+5;
const ll mod=1e9+7;
int n;
ll w[N],dp[N][2],ans;
ld sum[N][2];
int to[N*2],nxt[N*2],head[N],rp;
void add_edg(int x,int y){
	to[++rp]=y;
	nxt[rp]=head[x];
	head[x]=rp;
}
void dfs(int x,int f){
	dp[x][1]=w[x];dp[x][0]=1;
	sum[x][1]=log(w[x]);
	//sum[x][0]=log(1);
	//cout<<x<<" "<<sum[x][0]<<endl;
	for(re i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==f)continue;
		dfs(y,x);
		if(sum[y][1]>sum[y][0]){
			dp[x][0]=dp[x][0]*dp[y][1]%mod;
			sum[x][0]=sum[x][0]+sum[y][1];
		}
		else {
			dp[x][0]=dp[x][0]*dp[y][0]%mod;
			sum[x][0]=sum[x][0]+sum[y][0];
		}
		dp[x][1]=dp[x][1]*dp[y][0]%mod;
		sum[x][1]=sum[x][1]+sum[y][0];
	}
}
signed main(){
	//cout<<(sizeof(sum)>>20)<<endl;
	scanf("%d",&n);
	for(re i=1;i<=n;i++)scanf("%lld",&w[i]);
	for(re i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		add_edg(x,y);add_edg(y,x);
	}
	dfs(1,0);
	if(sum[1][1]>sum[1][0])ans=dp[1][1];
	else ans=dp[1][0];
	printf("%lld",ans);
}

T2 简单题

说实话这个题真简单，我真不会，而且正解是真牛逼

考场上就想到了会有一堆链长不超过\(logn\)的链上必须隔一个选一个

然后我就去枚举每一个作为底数的奇数了。TTTTT

40pts


#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=1e7+5;
const ll mod=10000019;
ll ksm(ll x,ll y){
	ll ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
ll jc[N>>1];
ll C(ll x,ll y){
	if(x<y)return 0;
	if(!y)return 1;
	return jc[x]*ksm(jc[x-y]*jc[y]%mod,mod-2)%mod;
}
ll n,q,m;
ll sum,nuf,rst,bas=1;
signed main(){
	scanf("%lld%lld",&n,&q);
	for(re i=1;i<=n/2;i++){
		if((i^1)&1)continue;
		ll now=n/i;
		ll tmp=log2(now)+1;
		sum+=tmp/2;
		if(tmp&1)nuf++;
		else bas=bas*2ll%mod;
	}
	if(((n/2)^1)&1)rst=(n-n/2+1)/2;
	else rst=(n-n/2)/2;
	jc[0]=1;for(re i=1;i<=rst;i++)jc[i]=1ll*jc[i-1]*i%mod;
	//cout<<sum<<" "<<nuf<<" "<<rst<<endl;
	while(q--){
		scanf("%lld",&m);m-=sum;
		ll minn=max(m-rst,0ll);
		ll maxn=min(m,nuf),ans=0;
		//cout<<minn<<" "<<maxn<<endl;
		for(re i=minn;i<=maxn;i++)
			ans=(ans+C(nuf,i)*C(rst,m-i)%mod)%mod;
		ans=ans*bas%mod;
		printf("%lld\n",ans);
	}
}

毕竟链长不超过\(logn\)嘛，直接枚举链长他不香嘛，然后我就切掉了这个题

AC_code


#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=1e7+5;
const ll mod=10000019;
ll ksm(ll x,ll y){
	ll ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
ll jc[mod+10];
ll C(ll x,ll y){
	if(x<y)return 0;
	return jc[x]*ksm(jc[x-y]*jc[y]%mod,mod-2)%mod;
}
ll lus(ll x,ll y){
	if(!y)return 1;
	return lus(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
ll n,q,bas=1,m;
ll li,nuf,las,af=1;
signed main(){
	scanf("%lld%lld",&n,&q);
	las=n;
	for(re i=0;i>=0;i++){
		if(!las)break;
		ll tmp=las-n/bas;
		li+=((tmp+(las&1))/2*(i/2));
		if(i&1)(nuf+=(tmp+(las&1))/2)%mod;
		else af=af*ksm(2ll,(tmp+(las&1))/2)%mod;
		las=n/bas;
		//cout<<i<<" "<<nuf<<endl;
		//cout<<las<<" "<<tmp<<" "<<li<<endl;
		bas*=2;
	}jc[0]=1;
	//cout<<li<<" "<<nuf<<" "<<af<<endl;
	for(re i=1;i<=mod;i++)jc[i]=1ll*jc[i-1]*i%mod;
	while(q--){
		scanf("%lld",&m);
		m-=li;
		//cout<<m<<endl;
		if(m>nuf||m<0)printf("0\n");
		else printf("%lld\n",lus(nuf,m)*af%mod);
	}
}

T3 粉丝

这个直接看官方题解吧，挺好理解的啊;

建议先将这两种dp打一遍

首先这个\(f\)数组,就是一个完全背包问题

我这个写麻烦了，可看可不看

f[i][j]


#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=5005;
ll n,li,ri,mod;
ll dp[N][N],ans;
signed main(){
	scanf("%lld%lld%lld%lld",&li,&ri,&n,&mod);
	for(re i=li;i<=ri;i++)
		for(re j=1;j*i<=n;j++)
			dp[i][j*i]=1;
	for(re i=li;i<=n;i++){
		for(re j=1;j<=n;j++)(dp[i][j]+=dp[i-1][j])%=mod;
		for(re j=1;j*i<=n;j++){
			for(re k=1;k<=n-j*i;k++){
				if(dp[i-1][k])(dp[i][k+j*i]+=dp[i-1][k])%=mod;
			}
		}
	}
	//for(re i=li;i<=n;i++)if(dp[i][n]>0)(ans+=dp[i][n])%mod,cout<<i<<endl;
	printf("%lld",dp[n][n]);
}

g数组前一个转移是在当前序列后面添加一个0，后一个转移是对当前序列整体+1

前一个转移是可以改掉的,\(g[i][j]=g[i-1][j-x]+g[i][j-i]\)

这样就保证了序列的最小值是x，当然我这个也写麻烦了

g[i][j]


#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=5005;
ll n,li,ri,mod;
ll f[N][N],g1[N][N],g2[N][N],ans;
signed main(){
	scanf("%lld%lld%lld%lld",&li,&ri,&n,&mod);
	g1[0][0]=1;
	for(re i=1;i<=n;i++){
		for(re j=0;j<=n;j++){
			if(j>=li)(g1[i][j]+=g1[i-1][j-li])%=mod;
			if(j>=i)(g1[i][j]+=g1[i][j-i])%=mod;
		}
	}
	g2[0][0]=1;
	for(re i=1;i<=n;i++){
		for(re j=0;j<=n;j++){
			if(j>=ri+1)(g2[i][j]+=g2[i-1][j-ri-1])%=mod;
			if(j>=i)(g2[i][j]+=g2[i][j-i])%=mod;
		}
	}
	for(re i=1;i<=n;i++)(ans+=g1[i][n]-g2[i][n])%=mod;
	printf("%lld",ans);
}

就直接按照题解的思路，根号分治就行了

主要是利用了容斥原理，自己看吧

AC_code


#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
const int N=1e5+5;
ll l,r,n,mod;
ll f[N],g[N],sum[N];
ll get_ans(ll x){
	if(x>n)return 0ll;
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	memset(sum,0,sizeof(sum));
	ll b=max((ll)sqrt(n),x),ret=0;
	f[0]=g[0]=sum[0]=1;
	for(re i=x;i<b;i++)for(re j=i;j<=n;j++)f[j]=(f[j]+f[j-i])%mod;
	//cout<<b<<endl;
	for(re i=1;i<=n/b;i++){
		ll tmp=i*b;
		for(re j=i;j+tmp<=n;j++)g[j]=(g[j]+g[j-i])%mod;
		for(re j=0;j+tmp<=n;j++)sum[j+tmp]=(sum[j+tmp]+g[j])%mod;
	}
	for(re i=0;i<=n;i++)ret=(ret+f[i]*sum[n-i]%mod)%mod;
	return ret;
}
signed main(){
	scanf("%lld%lld%lld%lld",&l,&r,&n,&mod);
	printf("%lld",(get_ans(l)-get_ans(r+1)+mod)%mod);
}

T4 字符串

考场上仅仅想到了要把两侧相同的去掉，后面就没想到

中间只剩下\(A'+B+C+D\),或者，\(B+C+D+E'\)

这里就会出现一个性质，要么是\(A+C\)回文，要么是\(B+D\)

这两种情况是相同的，我们要求出最长回文长度，找到回文中心之后

向两侧扩展，一定有一段是真正连续的

还有一段是和这个串的前缀相同的，

那我们就可以直接用KMP，将这个串复制一遍，然后接在后面，

从后往前跑KMP，得到的就是最长的匹配长度

在利用\(manacher\)，直接找到中间的回文半径。。。。

AC_code


#include<bits/stdc++.h>
using namespace std;
#define re register int
const int N=5e6+5;
char ch[N],a[N<<1],b[N<<1];
int n,p[N<<1];
int nxt[N<<1],mxn[N<<1],ans;
void get_ans(){
	int len=2*n+1;
	a[0]='$';
	for(re i=1;i<=n;i++){
		a[i*2-1]='#';
		a[i*2]=ch[i];
	}
	a[n*2+1]='#';
	int mx=0,id=0;
	memset(p,0,sizeof(p));
	for(re i=1;i<=len;i++){
		if(i<mx)p[i]=min(p[id*2-i],mx-i);
		else p[i]=1;
		while(a[i+p[i]]==a[i-p[i]])p[i]++;
		if(mx<i+p[i])mx=i+p[i],id=i;
		//cout<<p[i]<<endl;
	}
	for(re i=1;i<=n;i++)b[i]=b[n*2-i+1]=ch[i];
	//for(re i=1;i<=2*n;i++)cout<<b[i];
	//cout<<endl;
	memset(nxt,0,sizeof(nxt));
	memset(mxn,0,sizeof(mxn));
	len=2*n;
	for(re i=len-1,j=0;i>=1;i--){
		while(j&&b[i]!=b[len-j])j=nxt[j];
		if(b[i]==b[len-j])j++;
		nxt[i]=j;
	}
	for(re i=n;i>=1;i--)mxn[i]=max(mxn[i+1],nxt[i]);
	for(re i=1;i<=len;i++){
		int l=(i-p[i])/2;
		int r=(i+p[i])/2;
		if(nxt[r]<=l)ans=max(ans,p[i]-1+2*nxt[r]);
		if(mxn[r]>=l)ans=max(ans,p[i]-1+2*l);
	}
}
signed main(){
	scanf("%s",ch+1);
	n=strlen(ch+1);int po;
	for(re i=1;i<=(n+1)/2;i++){
		if(ch[i]!=ch[n-i+1])break;
		po=i;
	}
	n-=2*po;
	for(re i=1;i<=n;i++){
		ch[i]=ch[i+po];
	}
	//cout<<n<<endl;
	get_ans();
	reverse(ch+1,ch+n+1);
	get_ans();
	//cout<<ans<<endl;
	printf("%d",ans+po*2);
}

码农公寓

noip模拟42 solutions

T1 卷

T2 简单题

T3 粉丝

T4 字符串

相关文章