首页 > 其他分享 >【考试题解】NOIP2024加赛2

【考试题解】NOIP2024加赛2

时间:2024-11-06 19:31:20浏览次数:3  
标签:int long 考试题 il 加赛 直径 ri NOIP2024 define

目录

A. 新的阶乘(factorial)

题目内容

定义运算 \(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1}\times1^{x}\),求 \(f(n)\) 的质因子分解形式。如:f(5)=2^8*3^3*5。\(n\le10^7\)。

部分分

?pts

枚举一个数的因子,暴力判质数,暴力统计。由于即没有打也不会分析复杂度,所以不知道有多少分。

正解

思路

首先需要筛素数。在 \(n\le10^7\) 的数据范围下埃氏筛和线性筛都可以。但是由于要记录所有素数,所以还是线性筛更方便。然后枚举范围内每个素数 \(a^k\) ,再枚举它们的 \(k\) 次方,注意到对于 \(a^k\) 能产生贡献的数呈等差数列分布。为了方便可以预处理出每个数的系数。然后直接做。由于对于 \(a^k\) 能产生贡献的数一定可以对 \(a^{k-1}\) 产生贡献,所以在算 \(a^k\) 时只相当于累加一个 \(a\) 的贡献。输出巨大,建议写快写。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
namespace inout
{
	#define super faster
	#ifdef super
		#define getchar getchar_unlocked
		#define putchar putchar_unlocked
	#endif
	template<typename tn> il void read(tn &x)
	{
		register bool op=false;
		register char ch=getchar();
		while(ch<'0'||ch>'9')
		{
			op|=(ch=='-');
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')
		{
			x=(x<<3)+(x<<1)+(ch^'0');
			ch=getchar();
		}
		if(op)
		{
			x=~x+1;
		}
	}
	template<typename tn> void writen (tn x)
	{
		if(x)
		{
			writen(x/10);
			putchar((x%10)|'0');
		}
	}
	template<typename tn> il void write(tn x)
	{
		if(x<0)
		{
			x=~x+1;
			putchar('-');
		}
		if(!x)
		{
			putchar('0');
		}
		writen(x);
	}
}using namespace inout;
int a,shu[10000001],cnt,xs[10000001];
bool su[10000001];
long long col[10000001];
il void aishi(int x)
{
	su[1]=true;
	for(ri i=2;i<=x;i++)
	{
		if(!su[i])
		{
			cnt++;
			shu[cnt]=i;
			for(ri j=2;i*j<=x;j++)
			{
				su[i*j]=true;
			}
		}
	}
}
int main()
{
	freopen("factorial.in","r",stdin);
	freopen("factorial.out","w",stdout);
	read(a);
	aishi(a);
	for(ri i=1;i<=a;i++)
	{
		xs[i]=a-i+1;
	}
	for(ri i=1;i<=cnt;i++)
	{
		register long long j=shu[i];
		for(ri k=1;j<=a;k++)
		{
			ri bg=j,ed=j*(a/j);
			ri num=ed/j;
			col[shu[i]]+=((xs[bg]+xs[ed])*1LL*num)>>1;
			j*=shu[i];
		}
	}
	putchar('f');
	putchar('(');
	write(a);
	putchar(')');
	putchar('=');
	for(ri i=1;i<=cnt;i++)
	{
		write(shu[i]);
		if(col[shu[i]]!=1)
		{
			putchar('^');
			write(col[shu[i]]);
		}
		if(i!=cnt)
		{
			putchar('*');
		}
	}
	return 0;
}

B. 博弈树(tree)

题目内容

给你一棵 \(n\) 个节点的树,\(q\) 次询问,每次给出起点 \(s\) 进行游戏,Alice 和 Bob 轮流在树上进行移动,但每次必须比上一次移动的距离要长,第一次可以移动任意距离。,Alice 先手,回答是 Alice 必胜还是 Bob 必胜。\(n,q\le10^5\)。

部分分

80pts

设 \(dp_{i,j}\) 表示当前在点 \(i\),下一步距离长度至少为 \(j\) 的状态。然后使用博弈论基本结论:如果当前状态的后继状态存在先手必败,则该状态先手必胜;否则先手必败。然后对于每个状态枚举合法点转移,状态数为 \(O(n^2)\),转移数为 \(O(n)\),单次转移由于判合法、找距离时求 lca 复杂度不同而不同,倍增、树剖 \(O(\log n)\),ST 表 \(O(1)\)。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,u,v,f[100001],g,dep[100001],fa[100001],dfs[100001],rks[100001],cnt,dp[2002][2002];
struct node
{
	int h,to;
}pic[200002];
struct STB
{
	int num[200002][22];
	il int dmin(int x,int y)
	{
		return dep[x]<dep[y]?x:y;
	}
	il void build(int x)
	{
		for(ri i=1;i<=x;i++)
		{
			num[i][0]=rks[i];
		}
		for(ri i=1;i<=__lg(x);i++)
		{
			ri k=1<<(i-1);
			for(ri j=1;(j+k+k-1)<=x;j++)
			{
				num[j][i]=dmin(num[j][i-1],num[j+k][i-1]);
			}
		}
	}
	il int lca(int x,int y)
	{
		if(x==y)
		{
			return x;
		}
		x=dfs[x],y=dfs[y];
		if(x>y)
		{
			swap(x,y);
		}
		ri z=__lg(y-x);
		return fa[dmin(num[x+1][z],num[y-(1<<z)+1][z])];
	}
}st;
il void ndin(int x,int y)
{
	g++;
	pic[g].to=y;
	pic[g].h=f[x];
	f[x]=g;
}
void dfs0(int x)
{
	cnt++;
	dfs[x]=cnt;
	rks[cnt]=x;
	for(ri i=f[x];i;i=pic[i].h)
	{
		ri y=pic[i].to;
		if(y!=fa[x])
		{
			fa[y]=x;
			dep[y]=dep[x]+1;
			dfs0(y);
		}
	}
}
il int dist(int x,int y)
{
	return dep[x]+dep[y]-(dep[st.lca(x,y)]<<1);
}
int dfs_pro(int x,int y)
{
	if(dp[x][y])
	{
		return dp[x][y];
	}
	for(ri i=1;i<=a;i++)
	{
		ri j=dist(x,i);
		if(j>=y&&dfs_pro(i,j+1)==-1)
		{
			dp[x][y]=1;
			return 1;
		}
	}
	dp[x][y]=-1;
	return -1;
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d%d",&a,&b);
	for(ri i=1;i<a;i++)
	{
		scanf("%d%d",&u,&v);
		ndin(u,v);
		ndin(v,u);
	}
	for(ri i=1;i<=a;i++)
	{
		dp[i][a]=-1;
	}
	dep[1]=1;
	dfs0(1);
	st.build(a);
	while(b--)
	{
		scanf("%d",&u);
		ri ans=dfs_pro(u,1);
		if(ans==1)
		{
			puts("Alice");
		}
		else
		{
			puts("Bob");
		}
	}
	return 0;
}

正解

思路

博弈论的题,于是猜猜结论。首先有一个显然的结论:直径端点的状态先手必胜。因为先手走一个直径,后手必没办法继续走。那么先手目的就是构造一个方案使得后手的下一次移动必须来到直径端点。问题来到直径上,先简化一下,考虑如果是一条链。

image

与直径端点相邻的点是先手必胜,比如 \(2\),可以走到 \(6\),因为距离限制,所以后手只能走到 \(7\),而 \(7\) 是先手必胜态,所以此时的 \(6\) 先手必败,此时的 \(2\) 先手必胜。

然后看 \(3\)。先手走向 \(5\),后手在 \(5\) 肯定不会走向直径端点 \(1\)。只能走向 \(2\),然而此时先手来到了 \(2\),后面还是先手必胜。所以 \(3\) 先手必胜。

对于 \(4\),注意到先手无论走到哪里,后手都可以继承到一个必胜局面,所以 \(4\) 后手必胜。那么 \(4\) 有没有更知名的身份呢?就是奇数长度直径的中点。注意偶数长度直径相当于没有中点,所以永远先手必败。

然后再来想一棵普通树的情况。奇数长度直径先手移动到直径中点就结束了。偶数长度直径先手只需要想办法让后手到达直径上即可。于是,先手移动到不在直径上的距离最远的点,后手以同样的策略移动,此时先手必须移动到直径上。这和我们刚才处理直径的方法很相似。实际上,后手走的路径长度就是树中第 \(2\) 小的,可以叫它“次直径”。那么,我们可以一直重复忽略当前直径的操作,直到存在奇数长度直径或自己在直径上。所以,这些点最后都有必胜策略。

然后代码实现就很好写了。两级dfs找直径是简单问题,后面直接判断,因为最多只有一个 Bob 能获胜的点。注意特判只有 \(1\) 个点的情况,由于没有路径,先手走不了,Bob 必胜。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,u,v,f[100001],g,dep[100001],fa[100001],cnt,root,ans,lim;
struct node
{
	int h,to;
}pic[200002];
il void ndin(int x,int y)
{
	g++;
	pic[g].to=y;
	pic[g].h=f[x];
	f[x]=g;
}
void dfs(int x)
{
	for(ri i=f[x];i;i=pic[i].h)
	{
		ri y=pic[i].to;
		if(fa[x]!=y)
		{
			fa[y]=x;
			dep[y]=dep[x]+1;
			dfs(y);
		}
	}
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d%d",&a,&b);
	if(a==1)
	{
		while(b--)
		{
			puts("Bob");
		}
		return 0;
	}
	for(ri i=1;i<a;i++)
	{
		scanf("%d%d",&u,&v);
		ndin(u,v);
		ndin(v,u);
	}
	root=1;
	dfs(1);
	for(ri i=1;i<=a;i++)
	{
		if(dep[i]>dep[root])
		{
			root=i;
		}
	}
	memset(dep,0,sizeof(dep));
	memset(fa,0,sizeof(fa));
	dfs(root);
	for(ri i=1;i<=a;i++)
	{
		if(dep[i]>dep[ans])
		{
			ans=i;
		}
	}
	if(!(dep[ans]&1))
	{
		lim=dep[ans]>>1;
		for(ri i=1;i<=lim;i++)
		{
			ans=fa[ans];
		}
	}
	else
	{
		ans=0;
	}
	while(b--)
	{
		scanf("%d",&u);
		if(u==ans)
		{
			puts("Bob");
		}
		else
		{
			puts("Alice");
		}
	}
	return 0;
}

C. 划分(divide)

题目内容

给你一个长度为 \(n\) 的 \(01\) 串 \(S\),将其划分为至少 \(k\) 段,把每一段看成二进制数求和,求最大值及方案数。答案都对 \(998244353\) 取模。\(n\le2\times10^6,1\le k\le n\)。

部分分

10pts

暴搜。枚举划分段结尾序列,然后找最大值和方案。

14pts

全是 \(0\) 时无论怎么划分都是 \(0\),所以直接找方案数。配合暴搜使用。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b;
const int mod=998244353,base=11491;
bool jw[2000002],te;
char c[2000002];
long long ans,cnt;
unordered_map<unsigned long long,bool>um;
namespace task1
{
	long long jc[2000002],ny[2000002];
	il long long qpow(long long x,long long y)
	{
		register long long rn=1;
		while(y)
		{
			if(y&1)
			{
				rn=(rn*x)%mod;
			}
			x=(x*x)%mod;
			y>>=1;
		}
		return rn;
	}
	il long long C(int x,int y)
	{
		if(x<y)
		{
			return 0;
		}
		return (((jc[x]*ny[x-y])%mod)*ny[y])%mod;
	}
	short main()
	{
		jc[0]=ny[0]=1;
		for(ri i=1;i<=a;i++)
		{
			jc[i]=(jc[i-1]*i)%mod;
			ny[i]=qpow(jc[i],mod-2);
		}
		for(ri i=b;i<=a;i++)
		{
			ans=(ans+C(a-1,i-1))%mod;
		}
		printf("0 %lld",ans);
		return 0;
	}
}
il void check()
{
	register long long num=0,now=0;
	register unsigned long long hs=0;
	for(ri i=1;i<=a;i++)
	{
		now<<=1;
		now|=(c[i]^'0');
		if(jw[i])
		{
			num+=now;
			now=0;
			hs*=base;
			hs+=i;
		}
	}
	if(um[hs])
	{
		return;
	}
	um[hs]=true;
	if(num>ans)
	{
		ans=num;
		cnt=0;
	}
	if(num==ans)
	{
		cnt++;
	}
}
void dfs(int x,int y)
{
	if(y>=b)
	{
		check();
	}
	if(x==a)
	{
		return;
	}
	jw[x]=true;
	dfs(x+1,y+1);
	jw[x]=false;
	dfs(x+1,y);
}
int main()
{
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	scanf("%d%d%s",&a,&b,c+1);
	te=true;
	for(ri i=1;i<=a;i++)
	{
		if(c[i]!='0')
		{
			te=false;
			break;
		}
	}
	if(te)
	{
		return task1::main();
	}
	jw[a]=true;
	dfs(1,1);
	printf("%lld %lld",ans,cnt);
	return 0;
}

正解

思路

分情况讨论。第一种就是上面部分分所说的全是 \(0\) 的情况。注意无论我们怎么划分前导 \(0\)(\(01\) 串开头的 \(0\))都不会对最大值产生影响,所以当 \(k\le\) 前导 \(0\) 数量 \(+1\) 时,答案即为整串的答案,方案数就是把所有前导 \(0\) 划分为 \(k\) 段且最后一段可为空的方案数。然后再考虑其他的情况,这些情况的最大值肯定能由一个最长段和其余的长度为 \(1\) 的段求得。这个最长段显然开头为 \(1\),然后分讨证明:

  1. 最长段长度为 \(1\),此时长度都相同,这个可以特判掉,直接出答案。

  2. 最长段长度为 \(2\),此时只有 \(1\) 个 \(2\) 和许多 \(1\) 的情况。

  3. 最长段长度 \(\ge3\)。如果不要最长段,那么最长段仅仅首位的贡献就需要两个开头为 \(1\) 的次长段来补充,而两个次长段的方案是无法构造出来的。

然后直接做。预处理原串哈希值,然后可以 \(O(\log n)\) 二分哈希找到以两个不同位置开头的最长段的第一个不同的位置,然后比较大小。统计时直接找最长串相同的就行。注意由于最长串的末位 \(1\) 在散串里贡献不变,所以这里的相同不考虑末位。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,bg,len,now;
const int mod=998244353,base=197;
char c[2000002];
long long ans,cnt,jc[2000002],ny[2000002],hs[2000002],bs[2000002];
il long long qpow(long long x,long long y)
{
	register long long rn=1;
	while(y)
	{
		if(y&1)
		{
			rn=(rn*x)%mod;
		}
		x=(x*x)%mod;
		y>>=1;
	}
	return rn;
}
il long long C(int x,int y)
{
	if(x<y)
	{
		return 0;
	}
	return (((jc[x]*ny[x-y])%mod)*ny[y])%mod;
}
il long long _hash(int x,int y)
{
	return (((hs[y]-hs[x-1]*bs[y-x+1])%mod)+mod)%mod;
}
il bool cmp(int x,int y)
{
	if(_hash(x,x+len-1)==_hash(y,y+len-1))
	{
		return false;
	}
	ri m=1,n=len;
	while(m!=n)
	{
		ri l=(m+n)>>1;
		if(_hash(x,x+l-1)!=_hash(y,y+l-1))
		{
			n=l;
		}
		else
		{
			m=l+1;
		}
	}
	return c[x+m-1]>c[y+m-1];
}
int main()
{
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	scanf("%d%d%s",&a,&b,c+1);
	jc[0]=ny[0]=bs[0]=1;
	for(ri i=1;i<=a;i++)
	{
		jc[i]=(jc[i-1]*i)%mod;
		ny[i]=qpow(jc[i],mod-2);
		hs[i]=(hs[i-1]*base+c[i])%mod;
		bs[i]=(bs[i-1]*base)%mod;
	}
	for(ri i=1;i<=a;i++)
	{
		if(c[i]!='0')
		{
			bg=i;
			break;
		}
	}
	if(!bg)
	{
		for(ri i=b;i<=a;i++)
		{
			cnt=(cnt+C(a-1,i-1))%mod;
		}
		printf("0 %lld",cnt);
		return 0;
	}
	if(bg>=b)
	{
		for(ri i=bg;i<=a;i++)
		{
			ans=((ans<<1)|(c[i]^'0'))%mod;
		}
		bg--;
		b--;
		for(ri i=b;i<=bg;i++)
		{
			cnt=(cnt+C(bg,i))%mod;
		}
		printf("%lld %lld",ans,cnt);
		return 0;
	}
	len=a-b+1,now=bg;
	if(len==1)
	{
		for(ri i=1;i<=a;i++)
		{
			if(c[i]=='1')
			{
				ans++;
				if(ans==mod)
				{
					ans=0;
				}
			}
		}
		printf("%lld 1",ans);
		return 0;
	}
	for(ri i=bg+1;i<=a-len+1;i++)
	{
		if(c[i]=='1'&&cmp(i,now))
		{
			now=i;
		}
	}
	for(ri i=bg;i<=a-len+1;i++)
	{
		if(_hash(now,now+len-2)==_hash(i,i+len-2))
		{
			cnt++;
		}
	}
	for(ri i=now;i<=now+len-1;i++)
	{
		ans=((ans<<1)|(c[i]^'0'))%mod;
	}
	for(ri i=bg;i<now;i++)
	{
		if(c[i]=='1')
		{
			ans++;
			if(ans==mod)
			{
				ans=0;
			}
		}
	}
	for(ri i=now+len;i<=a;i++)
	{
		if(c[i]=='1')
		{
			ans++;
			if(ans==mod)
			{
				ans=0;
			}
		}
	}
	printf("%lld %lld",ans,cnt);
	return 0;
}

D. 灯笼(lantern)

不会。

标签:int,long,考试题,il,加赛,直径,ri,NOIP2024,define
From: https://www.cnblogs.com/ywhhdjser-97/p/18530903

相关文章

  • NOIP加赛2
    rank15T1100,T280,T39,T40本来不想交的,但快结束的时候回头看见huge在看着我就慌了。T1新的阶乘签到题,将跑个类似于埃氏筛的东西就行了,时间复杂度\(O(n\log\logn)\)。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i......
  • NOIP2024加赛2
    NOIP2024加赛2题目来源:2023NOIPA层联测18\(T1\)HZTG5733.新的阶乘\(100pts\)预处理素数后直接对\(1\simn\)进行质因数分解因为有太多冗余枚举导致无法通过。考虑枚举最终形式。具体地,从质因数的角度入手,设当前枚举的质数为\(p\),暴力求出\(ip\)中\(p\)的指......
  • CSP2024 前集训:NOIP2024加赛 1
    前言赛时本来rk3,赛后自己加hack卡自己于是成rk4了。因为这场是假做法大战,T1假贪心有\(92pts\);T2\(O(n^2m)\)能过(是因为数据里\(m\le10\));T3相当抽象,赛时我打的爆搜只加了一个剪枝能得\(70pts\),赛后发现无解的时候会跑满,于是提前判掉无解就过了甚至最优解\(30ms\)......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18\(T1\)A.选彩笔(rgb)\(100pts/100pts\)观察到\(0\ler,g,b\le255\)且答案具有单调性,故考虑二分答案。将\(r,g,b\)分别抽象成三维坐标下的\(x,y,z\)。设当前二分出的答案为\(mid\),由调整法分析可知若存在一个边长为\(mid\)的......
  • [61] (多校联训) A层冲刺NOIP2024模拟赛18
    无论从什么意义上都能称得上挂75分的一场A.选彩笔好题答案显然可以二分突然发现我好像专长二分答案钦定最大差值\(dx\),将所有物品以\((r,g,b)\)看成三维空间坐标内的点,原问题可以转化成问空间里一个边长为\(dx\)的立方体内是否有至少\(k\)个点考虑到值域不大,可......
  • [赛记] 多校A层冲刺NOIP2024模拟赛16 && 17
    四舍五入100pts对于一个数$x$,可以发现它的答案可以分成两部分,一部分在$[2x+1,n]$范围内,一部分在小于它的数的范围内,前者$\Theta(1)$算,对于后者,我们发现满足这个要求的数$y$一定有$x\mody<w(x,y)$($w(x,y)$定义为如果$x\mody=0$,则$w(a,......
  • NOIP2024模拟赛21
    省流:没过T1,玩了1h俄罗斯,不好评价。还好T3一个小时写完了平方暴力,还没菜到离谱,感觉这才是一个正常的分数。但是好像正解要不到1h?T2的dp优化是我弱项,做不出正常,spdarkle是真逆天。怎么一眼的怎么一眼的怎么一眼的怎么一眼的怎么一眼的怎么一眼的怎么一眼的。发现后面又......
  • 多校A层冲刺NOIP2024模拟赛17
    多校A层冲刺NOIP2024模拟赛17T1、网格首先看上去很麻烦,但是最终所有的式子都可以写成几个数的积相加的形式,那么我们只要处理数(拼接起来)、数的积以及积的和。那么我们维护三个变量,第一个是$x$,表示最后一个积前面所有的数和,第二个是$y$,表示目前的积,第三个是z,表......
  • 多校 A 层冲刺 NOIP2024 模拟赛 17
    多校A层冲刺NOIP2024模拟赛17T1网格签到题注意到\(+\)与\(\times\)由于优先级其实是分开的,所以可以考虑每到达一个\(+\)计算一次贡献(乘上一个组合数),然后将前置贡献重新赋值为方案数,DP只需考虑连续\(\times\)段即可。时间复杂度\(O(nm)\)。T2矩形根号分治发现不......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\),\(s_{i,j}\in[1,9]\cup\{+,*\}\),从\((1,1)\)开始,仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径,求所有合法路径对应的表达式的运算结果之和,答案对\(998244353\)取模。部分分44pts爆搜,枚举路径,......