\(noip模拟26\;solutions\)

这个题我做的确实是得心应手，为啥呢，因为前两次考试太难了

T1非常的简单，只不过我忘记了一个定理，

T2就是一个小小的线段树，虽然吧我曾经说过我再也不写树状数组了，但是我看见最长上升子序列就兴奋了

码了个树状数组就溜走了，用时仅为10min，60pts，组合拳

T3我就是nb

\(T1\;神炎皇\)

这个就是一个小小的推式子，让我给你推一推

\(a+b\,|\, a*b\),设\(d=gcd(a,b),x=a/d,y=b/d\),所以x和y互质

我们有\(k*(x+y)\,|\,x*y*d^2<====>(x+y)\,|\,x*y*d\)

因为x，y互质所以（x+y）| d,设(x+y)=k

\(k*d<=n并且k\,|\,d并且k<{d}\)，所以这样的d一共有\(\frac{n}{k^2}\)个

这种x与y互质，x+y为定值，你发现x与x+y也是互质的，所以每一个k对应的x+y都有\(\phi(k)\)

k的范围是\(\sqrt{n}\)

那么接下来的事就只剩下线性筛了;

AC_code


#include<bits/stdc++.h>

using namespace std;

#define re register int

#define ll long long

const int N=1e7+5;

ll n,ans,sn;

int p[N],cnt,f[N];

bool vis[N];

signed main(){

	scanf("%lld",&n);

	sn=sqrt(n);

	//memset(vis,1,sizeof(vis));

	//cout<<vis[1]<<endl;

	for(re i=2;i<=sn;i++){

		if(!vis[i])p[++cnt]=i,f[i]=i-1;

		for(re j=1;j<=cnt&&p[j]*i<=sn;j++){

			vis[p[j]*i]=true;

			if(i%p[j]==0){

				f[i*p[j]]=f[i]*p[j];

				break;

			}

			else f[i*p[j]]=f[i]*f[p[j]];

		}

	}

	for(re i=1;i<=sn;i++){

		ans+=f[i]*(n/i/i);

	}

	printf("%lld",ans);

}

\(T2\;降雷皇\)

这个题真的是简单极了，我也没想到会有这么简单的题，打了个60分的组合拳就走了

最后发现这个用线段树维护一下就好了

毕竟是动态开点，而且这个电阻值只有1e5，完全不需要离散化，

对于每一种长度也就是最长上升子序列的长度建立一个线段树，

线段树的下标是电阻值，因为你查询的时候是按照电阻值来查询的

线段树中维护的权值即为方案数，这样遍历一遍这个序列，\(O(nlogn)\)就可以解决方案数了

最后直接输出最长长度的线段树的所有权值加和,说白了就是根节点的sum

AC_code


#include<bits/stdc++.h>

using namespace std;

#define re register int

const int N=1e5+5;

const int mod=123456789;

int n,typ,ans1,ans2;

int omu[N],f[N],sum[N];

struct SZSZ{

	int tr[N];

	int lb(int x){return x&(-x);};

	void ins(int x,int v){

		for(re i=x;i<=1e5;i+=lb(i))

			tr[i]=max(tr[i],v);

	}

	int query(int x){

		int ret=0;

		for(re i=x;i;i-=lb(i))

			ret=max(ret,tr[i]);

		return ret;

	}

}sz;

int dp[N];

struct XDS{

	int ls[N*80],rs[N*80];

	int sum[N*80];

	int seg;

	void pushup(int x){

		sum[x]=(sum[ls[x]]+sum[rs[x]])%mod;

		return ;

	}

	void ins(int &x,int l,int r,int pos,int v){

		if(!x)x=++seg;

		if(l==r){

			sum[x]=(sum[x]+v)%mod;

			return ;

		}

		int mid=l+r>>1;

		if(pos<=mid)ins(ls[x],l,mid,pos,v);

		else ins(rs[x],mid+1,r,pos,v);

		pushup(x);return ;

	}

	int query(int x,int l,int r,int ql,int qr){

		if(!x)return 0;

		if(ql<=l&&r<=qr)return sum[x];

		int mid=l+r>>1,ret=0;

		if(ql<=mid)ret=(ret+query(ls[x],l,mid,ql,qr))%mod;

		if(qr>mid)ret=(ret+query(rs[x],mid+1,r,ql,qr))%mod;

		return ret;

	}

}xds;

int rt[N];

signed main(){

	scanf("%d%d",&n,&typ);

	for(re i=1;i<=n;i++){

		scanf("%d",&omu[i]);

		dp[i]=sz.query(omu[i]-1)+1;

		ans1=max(ans1,dp[i]);

		sz.ins(omu[i],dp[i]);

		//cout<<omu[i]<<" "<<dp[i]<<endl;

	}

	printf("%d\n",ans1);

	if(typ==1){

		int R=1e5+1,mn=0x3f3f3f3f;

		for(re i=1;i<=n;i++){

			int tmp=xds.query(rt[dp[i]-1],1,R,1,omu[i]-1);

			if(mn>=omu[i]&&tmp==0)tmp=1,mn=omu[i];

			xds.ins(rt[dp[i]],1,R,omu[i],tmp);

		}

		printf("%d",xds.query(rt[ans1],1,R,1,R));

	}

}

\(T3\;幻魔皇\)

这整一棵树都充斥这非波那契数列，真的就直接倒就好了

其实还有更简单的\(O(n^2)\)做法还比我的简单，比我的快

去看别人的博客吧，我这个非常难理解，

主要思路就是，首先枚举每一层，每一层的黑色节点和白色节点的类型都是一样的

黑色节点直接枚举左右儿子就行，白色节点就是直接用自己连接自己子树中的白色节点

注意黑色子树中有一个不符合规律的，就是这个黑色节点的白儿子，把这个拎出来单独算

AC_code


#include<bits/stdc++.h>

using namespace std;

#define re register int

const int N=5e3+5;

const int mod=123456789;

int fb[N],ffb[N][N*2],ans[N*2],n;

signed main(){

	scanf("%d",&n);

	fb[1]=1;fb[2]=1;

	for(re i=3;i<=5000;i++)

		fb[i]=(fb[i-1]+fb[i-2])%mod;

	for(re i=2;i<=n;i++){

		for(re j=1;j<=2*n;j++)

			ffb[i][j]=(ffb[i][j]+ffb[i-1][j])%mod;

		for(re j=3;j<=n;j++){

			//if(i==4&&j==3)cout<<ffb[j][i+j]<<" "<<i+j<<endl;

			ffb[max(j,i)][i+j]+=1ll*fb[i-1]*fb[j-2]%mod;

			ffb[max(j,i)][i+j]%=mod;

			//if(i==4&&j==3)cout<<ffb[j][i+j]<<endl;

		}

	}

	//cout<<ffb[4][7]<<endl;

	for(re i=2;i<=n;i++){

		for(re j=5;j<=2*(n-i);j++){

			ans[j]+=1ll*fb[i-1]*ffb[n-i][j]%mod;

			ans[j]%=mod;

		}

		for(re j=i+2;j<=n;j++){

			ans[j-i+1]+=1ll*fb[i-1]*fb[j-i-1]%mod;

			ans[j-i+1]%=mod;

		}

		for(re j=i+2;j<=n;j++){

			ans[j-i]+=1ll*fb[i-2]*fb[j-i-1]%mod;

			ans[j-i]%=mod;

		}

	}

	for(re j=3;j<=n;j++){

		ans[j-1]+=fb[j-2];

		ans[j-1]%=mod;

	}

	for(re i=1;i<=2*n;i++)printf("%d ",ans[i]);

}

巴特西

noip模拟26[肾炎黄·酱累黄·换莫黄]

\(noip模拟26\;solutions\)

\(T1\;神炎皇\)

\(T2\;降雷皇\)

\(T3\;幻魔皇\)

最新文章

热门文章