首页 > 其他分享 >CSP2024 前集训:NOIP2024加赛 2

CSP2024 前集训:NOIP2024加赛 2

时间:2024-11-06 21:21:51浏览次数:2  
标签:unlocked int void CSP2024 Tp read inline 加赛 NOIP2024

前言

T2 开太晚了,没打完,别的没怎么挂。

哦对,T1 以为埃筛复杂度是 \(n log^2\),实际上是 \(n \ln(\ln (n))\),结果以为复杂度是错的,然后本地不开 O2 都飞快,我甚至还在惊叹本地竟然能跑 \(5e9\)……

还有我之前不知道树的直径的中点时唯一的……

T1 新的阶乘

直接埃筛做完了。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e7+10,M=7e6+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,tot,prime[M]; ll cnt[M]; bool vis[N];
inline int calc(int x,int y,int res=0) {while(!(x%y)) x/=y,res++; return res;}
signed main()
{
	freopen("factorial.in","r",stdin),freopen("factorial.out","w",stdout);
	read(n),prime[++tot]=2;
	for(int i=2;i<=n;i+=2) vis[i]=1,cnt[1]+=calc(i,2)*(n-i+1);
	for(int i=3;i<=n;i+=2) if(!vis[i])
	{
		prime[++tot]=i;
		for(int j=i;j<=n;j+=i) vis[j]=1,cnt[tot]+=calc(j,i)*(n-j+1);
	}
	printf("f(%d)=",n);
	for(int i=1;i<tot;i++)
	{
		write(prime[i]);
		if(cnt[i]^1) putchar_unlocked('^'),write(cnt[i]);
		putchar_unlocked('*');
	}
	write(prime[tot]); if(cnt[tot]^1) putchar_unlocked('^'),write(cnt[tot]);
}

T2 博弈树

发现 Bob 只有在起点为直径的中点时必胜,其他 Alice 必胜。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define pb push_back
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,s,t,mx,lca,mid,f[N],g[N],fa[N],pos1[N],pos2[N]; vector<int>e[N];
inline void dfs(int x,int dad)
{
	fa[pos1[x]=pos2[x]=x]=dad; for(int y:e[x]) if(y!=dad)
	{
		dfs(y,x); if(f[x]<f[y]+1)
			pos2[x]=pos1[x],pos1[x]=pos1[y],g[x]=f[x],f[x]=f[y]+1;
		else if(g[x]<f[y]+1) pos2[x]=pos1[y],g[x]=f[y]+1;
	}
	if(f[x]+g[x]>=mx) s=pos1[x],t=pos2[x],lca=x,mx=f[x]+g[x];
}
signed main()
{
	freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
	read(n,m); for(int i=1,x,y;i<n;i++) read(x,y),e[x].pb(y),e[y].pb(x);
	dfs(1,0); if(mx&1) {while(m--) puts("Alice"); return 0;}
	for(int i=s,sum=0;i!=lca&&!mid;i=fa[i],sum++) if(sum==(mx>>1)) mid=i;
	for(int i=t,sum=0;i!=lca&&!mid;i=fa[i],sum++) if(sum==(mx>>1)) mid=i;
	if(!mid) mid=lca; for(int x;m;m--) read(x),puts(x!=mid?"Alice":"Bob");
}

T3 划分

数据点分治,当前缀 \(0\) 个数 \(\ge m-1\) 时第一问就是后面的全取就行了,第二问就是在前缀 \(0\) 里插板。

否则发现答案一定选择一个长度为 \(n-m+1\) 的区间,其他的区间都长度为 \(1\),因为这是 C++,所以需要用二分哈希找到 \(lcp\) 然后比较第 \(lcp+1\) 位判大小,然后就能找到最优区间了,但是第二问发现只要满足前 \(n-m\) 位相同即可,因为后面的 \(1\) 会补上。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e6+10,B=233,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,vl,vr,nl,nr,ans,lcp,sum,b[N],h[N],jc[N],inv[N]; char s[N];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
inline int ask(int l,int r) {return mod(h[r],P-1ll*h[l-1]*b[r-l+1]%P);}
inline bool check(int x,int y,int mid) {return ask(x,x+mid-1)==ask(y,y+mid-1);}
inline int calc(int l,int r,ll v=1,int res=0,int sum=0)
{
	for(int i=r;i>=l;i--,(v<<=1)%=P) res=mod(res,(s[i])*v),sum+=s[i];
	return res+(::sum-sum);
}
inline ll qpow(ll a,int b,ll res=1)
{for(;b;(a*=a)%=P,b>>=1) (b&1)&&((res*=a)%=P); return res;}
inline int C(int n,int m) {return 1ll*jc[n]*inv[n-m]%P*inv[m]%P;}
inline int num(int sum=m-1,int res=0,ll c=1)
{
	for(int i=m;i<=n;i++) if(!s[i]) sum++; else break; sum-=(sum==n);
	jc[0]=1; for(int i=1;i<=n;i++) jc[i]=1ll*jc[i-1]*i%P;
	inv[n]=qpow(jc[n],P-2); for(int i=n-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%P;
	for(int i=m-1;i<=sum;i++) res=mod(res,C(sum,i));
	return res;
}
signed main()
{
	freopen("divide.in","r",stdin),freopen("divide.out","w",stdout);
	read(n,m),scanf("%s",s+1); for(int i=1;i<=n;i++) s[i]-='0';
	for(int i=1;i<=n;i++) sum+=s[i]; if(n==m) return write(sum,1),0;
	for(int i=1;i<m;i++) if(s[i]) {ans=1,m=n-m+1; break;}
	if(!ans) return write(calc(m,n),num()),0;
	b[0]=1; for(int i=1;i<=n;i++) b[i]=1ll*b[i-1]*B%P;
	for(int i=1;i<=n;i++) h[i]=1ll*h[i-1]*B%P+s[i];
	for(vl=1,vr=m,nl=2,nr=m+1;nr<=n;nl++,nr++)
	{
		for(int l=0,r=m-1,mid;l<=r;)
			check(nl,vl,mid=l+r>>1)?(l=mid+1)&&(lcp=mid):(r=mid-1);
		lcp==m-1?(ans++):(s[nl+lcp])&&(vl=nl)&&(vr=nr)&&(ans=1);
	}
	write(calc(vl,vr),ans);
}

T4 灯笼

有这题吗?

标签:unlocked,int,void,CSP2024,Tp,read,inline,加赛,NOIP2024
From: https://www.cnblogs.com/Charlieljk/p/18531048

相关文章

  • NOIP2024 模拟赛 #15 总结
    Larunatrecy:信心赛。赛时T1求中位数,想起前两天做过的[ABC203D]Pond,考虑了二分答案。看出二分答案后不会做了,罚坐\(20\)min。然后发现我傻逼了,选出一个区间翻转,可以通过钦定右端点,找到最优的左端点得到,神仙Heldivis就出过一道这样的题。写完后调了下二分边界过了大样......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛18
    前言不知道咋回事儿?脑子里一直放歌。然后T3空间给了256,开了256.23死了。T1选彩笔显然可以二分答案,所以现在有了\(O(nv^3\logv)\)的做法,去重后可以拿到\(80pts\),发现直接三维前缀和就可以做到\(O(v^3\logv)\)。点击查看代码#include<bits/stdc++.h>#definell......
  • 『模拟赛』NOIP2024加赛2
    Rank一直烂,什么时候触底反弹(A.新的阶乘赛时觉得线筛一遍同时统计每个质数的指数就做完了,然后本机怎么跑不进1s,卡常卡了半个小时,最后没T,但是vector炸了,70pts。可以换思路考虑,赛时一直没转换过来。对于每个质数枚举其倍数统计贡献。复杂度不知道多少,跑得中等速度。点......
  • 「模拟赛」NOIP2024 模拟 2
    Rank14,190pts比赛链接新的阶乘容易发现只需要处理1~n的质因子分解即可,每个数\(i\)本来有\(n-i+1\)个我们在欧拉筛的过程中同时维护每个数的一个质因子\(pri\)每次从\(n\)到1把遇到的非质数\(i\)现有的个数加到他的质因子\(pri_i\)和\(\frac{i}{pri_i......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • 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 游记
    Day-1初赛就用Day-1好了。虽然已经拿过J组1=了但还是去参加J组了捏。。。初赛感觉打得挺好的qwq。强烈谴责泄题行为。。。不知道复赛会考什么呢。。。出成绩了。。。J91.5,S79.5,都稳了,准备开始搞复赛。Day0提前一天来到考点附近!住酒店爽爽爽!和同学聊了聊,一......
  • CSP2024 - J/S 年度总结大会报告
    CSP2024-J/S年度总结大会报告J组预估和总分都为:\(100+100+100+15=315.\)\(T_1,T_2\)还挺弱智的,就是没有\(15\min\)内\(A\)掉。\(T_3\)想了\(1h\)的完全背包做法加上\(1h\)的调试,真的慢(本质是对于\(dp\)没有深刻理解)。\(T_4\)是一个\(dp\),考场上没有想出来......
  • CSP2024 前集训:NOIP2024加赛 1
    前言赛时本来rk3,赛后自己加hack卡自己于是成rk4了。因为这场是假做法大战,T1假贪心有\(92pts\);T2\(O(n^2m)\)能过(是因为数据里\(m\le10\));T3相当抽象,赛时我打的爆搜只加了一个剪枝能得\(70pts\),赛后发现无解的时候会跑满,于是提前判掉无解就过了甚至最优解\(30ms\)......