这套题总体来说比较简单，但是有一些分数我没有拿到，先说T1，我10分钟左右打完了60分的暴力，然后就开始打表找规律，好像只有我去找了循环节，找规律找了一个多小时，到八点四十的时候我还没有正解做法，就直接弃掉了，浪费了好多时间.....然后是T2，看到n==1的点果断输出1，拿了20分走人，然后是T3，我觉得跟之前考过的一道题比较像，但是那道题我没有改过，不过应该是可以用类似的思想，点分治，但是我觉得复杂度有问题，于是看到了\(k==1\)的特殊性质，就去想了一个\(o(n)\)的树上dp,然后打暴力验证，最后竟然把点分治给忘了！！！！，然后是T4，我研究了一下式子，发现满足条件的点可以写成\(deep_v-deep_u=kx+y\)的形式，但是我觉得复杂度应该没什么变化，还是个暴力，就直接打了个最省事的暴力走人了，考完发现数据太水了，第三，四题我的思路完全可以过，A掉的人还是不少的。

总结一下：1.有一些思路先写下来，避免一会忘了。2.考试代码能优化一点是一点，别偷懒。3.合理安排时间，如果一个多小时还没正解思路就赶紧换题

T1 异或

思路：这题真是。。基本上人手一个AC，但是只有我去找循环节把自己搞傻了，没发现二进制下数字的表示规律。正解：考虑每一位的贡献,从低到高的第\(i\)位会每隔\(2^i\)个数变化一次,于是第\(i\)位对答案的贡献就是\(\lfloor\frac{n}{2^i}\rfloor\),把每一位的贡献加起来即可.

代码如下：

AC_code




#include<bits/stdc++.h>

signed main(){long long n,ans=0;scanf("%lld",&n);for(long long i=0;(1ll<<i)<=n;i++) ans+=(n/(1ll<<i));printf("%lld\n",ans);return 0; }

T2 赌神

思路：先说一下什么叫最优策略，就是保证在任何时候都没有更劣的策略，对于这道题而言，在最优策略下,不同的掉球情况下你最终所能获得的筹码数应该相同。

代码如下：

AC_code


#include<bits/stdc++.h>

#define int long long

#define re register int

#define ii inline int

#define iv inline void

using namespace std;

const int N=1e6+10;

const int mo=998244353;

int n,inv,ans=1,up,down=1;

int a[N],jc[N];

ii read()

{

	int x=0;char ch=getchar();bool f=1;

	while(ch<'0' or ch>'9')

	{

		if(ch=='-') f=0;

		ch=getchar();

	}

	while(ch>='0' and ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

ii ksm(int d,int z)

{

	int out=1;

	while(z){ if(z&1) out=out*d%mo;z>>=1;d=d*d%mo;}

	return out%mo;

}

signed main()

{

	n=read();

	for(re i=1;i<=n;i++) a[i]=read(),up=up+a[i];

	jc[0]=1;

	for(re i=1;i<N;i++) jc[i]=jc[i-1]*i%mo;

	for(re i=1;i<=n;i++) down=down*jc[a[i]]%mo;

	for(re i=1;i<=up;i++) ans=ans*i%mo;

	ans=ans%mo*ksm(down,mo-2)%mo;

	up=ksm(n,up)%mo;

	ans=up*ksm(ans,mo-2)%mo;

	printf("%lld\n",ans);

    return 0;

}

T3 路径

思路：我现在只会复杂度在\(o(n^2\times log(n))\)左右的做法，因为数据较水的原因，这题可以过，思路是点分治，显然是运用点分治思想的裸题，但是要存储每个点到分治中心的距离，以及这个距离的个数，不能一个一个存，会超时，虽然这样优化以后复杂度也是假的。。。

其实正解就是在此基础上用了一个fft优化，但是我不会，可以看这里

代码如下：

AC_code


#include<bits/stdc++.h>

#define re register int

#define ii inline int

#define iv inline void

#define head heeadd

#define next net

#define ms md

#define f() cout<<"YES"<<endl

using namespace std;

const int N=1e6+10;

const int mo=998244353;

int n,k,root,jd,tot;

int to[N<<1],head[N],next[N<<1];

int fa[N],deep[N],size[N],md[N];

int cun[N],col[N],cun_col[N];

int c2[N],cun_c2[N];

bool vis[N],hav[N],h2[N];

long long ans;

ii read()

{

	int x=0;char ch=getchar();bool f=1;

	while(ch<'0' or ch>'9')

	{

		if(ch=='-') f=0;

		ch=getchar();

	}

	while(ch>='0' and ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

iv add(int x,int y)

{

	to[++tot]=y;

	next[tot]=head[x];

	head[x]=tot;

}

long long ksm(long long d,long long z)

{

	long long out=1;

	while(z)

	{

		if(z&1) out=out*d%mo;

		z>>=1;

		d=d*d%mo;

	}

	return out;

}

iv get_root(int st,int f)

{

	size[st]=1,md[st]=0;

	for(re i=head[st];i;i=next[i])

	{

		int p=to[i];

		if(p==f or vis[p]) continue;

		get_root(p,st);

		size[st]+=size[p];

		md[st]=max(md[st],size[p]);

	}

	md[st]=max(md[st],jd-size[st]);

	if(md[st]<md[root]) root=st;

}

iv get_dis(int st,int f)

{

	deep[st]=deep[f]+1;

	if(!h2[deep[st]]) h2[deep[st]]=1,cun_c2[++cun_c2[0]]=deep[st],c2[deep[st]]++;

	else c2[deep[st]]++;

	for(re i=head[st];i;i=next[i])

	{

		int p=to[i];

		if(p==f or vis[p]) continue;

		get_dis(p,st);

	}

}

iv calc(int st)

{

	for(re i=1;i<=cun_col[0];i++) hav[cun_col[i]]=0,col[cun_col[i]]=0;

	cun_col[0]=0;

	cun_col[++cun_col[0]]=0,hav[0]=1,col[0]=1;

	deep[st]=0;

	for(re i=head[st];i;i=next[i])

	{

		int p=to[i];

		if(vis[p]) continue;

		cun_c2[0]=0;

		get_dis(p,st);

		for(re j=1;j<=cun_col[0];j++)

		{

			for(re b=1;b<=cun_c2[0];b++)

				ans=(ans+1ll*ksm(cun_col[j]+cun_c2[b],k)%mo*1ll*col[cun_col[j]]%mo*1ll*c2[cun_c2[b]]%mo)%mo;

		}

		for(re b=1;b<=cun_c2[0];b++)

		{

			if(!hav[cun_c2[b]]) hav[cun_c2[b]]=1,cun_col[++cun_col[0]]=cun_c2[b],col[cun_c2[b]]+=c2[cun_c2[b]];

			else col[cun_c2[b]]+=c2[cun_c2[b]];

			h2[cun_c2[b]]=0,c2[cun_c2[b]]=0;

		}

	}

}

iv solve(int st)

{

	vis[st]=1;

	calc(st);

	for(re i=head[st];i;i=next[i])

	{

		int p=to[i];

		if(vis[p]) continue;

		root=0,ms[0]=jd=size[p]+1;

		get_root(p,st);

		solve(p);

	}

}

signed main()

{

	n=read(),k=read();

	int u,v;

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

	{

		u=read(),v=read();

		add(u,v),add(v,u);

	}

	ms[0]=jd=n+1;

	get_root(1,0);

	solve(root);

	printf("%lld\n",ans);

    return 0;

}

T4 树

思路：这道题真的很暴力呀，数据真的是太水了。首先我们把满足条件的点化成\(deep_v-deep_u=k\times x+y\)的形式，然后我们用一个vector存储每一层（到达跟节点距离为x）的点，最后直接暴力枚举下跳即可。

代码如下:

AC_code


#include<bits/stdc++.h>

#define re register int

#define ii inline int

#define iv inline void

#define head heeadd

#define next net

using namespace std;

const int N=3e5+10;

int n,q,tot,timi;

int to[N<<1],head[N<<1],next[N<<1],val[N];

int fa[N],deep[N],dfn[N],size[N],md[N];

vector<int> v[N];

ii read()

{

	int x=0;char ch=getchar();bool f=1;

	while(ch<'0' or ch>'9')

	{

		if(ch=='-') f=0;

		ch=getchar();

	}

	while(ch>='0' and ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

iv add(int x,int y)

{

	to[++tot]=y;

	next[tot]=head[x];

	head[x]=tot;

}

iv dfs(int st,int f)

{

	deep[st]=deep[f]+1,fa[st]=f,dfn[st]=++timi,size[st]=1,md[st]=deep[st];

	v[deep[st]].push_back(st);

	for(re i=head[st];i;i=next[i])

	{

		int p=to[i];

		if(p==f) continue;

		dfs(p,st);

		size[st]+=size[p];

		md[st]=max(md[st],md[p]);

	}

}

iv change(int p,int x,int y,int z)

{

	for(re i=deep[p]+y;i<=md[p];i+=x)

		for(re j=0;j<v[i].size();j++)

			if(dfn[v[i][j]]>=dfn[p] and dfn[v[i][j]]< dfn[p]+size[p]) val[v[i][j]]+=z;

}

signed main()

{

	n=read(),q=read();

	int u,v,opt,x,y,z;

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

	{

		u=read(),v=read();

		add(u,v),add(v,u);

	}

	dfs(1,0);

	while(q--)

	{

		opt=read();

		if(opt==1) u=read(),x=read(),y=read(),z=read(),change(u,x,y,z);

		else u=read(),printf("%d\n",val[u]);

	}

    return 0;

}

巴特西

noip模拟测试52

T1 异或

T2 赌神

T3 路径

T4 树

最新文章

热门文章