首页 > 其他分享 >CSP2024 前集训：多校A层冲刺NOIP2024模拟赛18

CSP2024 前集训：多校A层冲刺NOIP2024模拟赛18

时间：2024-11-06 20:19:46浏览次数：1  
标签：unlocked int 18 void 多校 Tp CSP2024 read inline

前言

不知道咋回事儿？脑子里一直放歌。

然后 T3 空间给了 256，开了 256.23 死了。

T1 选彩笔

显然可以二分答案，所以现在有了 \(O(nv^3\log v)\) 的做法，去重后可以拿到 \(80pts\)，发现直接三维前缀和就可以做到 \(O(v^3\log v)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=260;
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,mx,ans,sum[N][N][N];
bool check(int mid)
{
	for(int la=0,ra=mid+1;ra<=mx;la++,ra++)
		for(int lb=0,rb=mid+1;rb<=mx;lb++,rb++)
			for(int lc=0,rc=mid+1;rc<=mx;lc++,rc++)
				if(sum[ra][rb][rc]-sum[la][rb][rc]-sum[ra][lb][rc]-sum[ra][rb][lc]+sum[la][lb][rc]+sum[la][rb][lc]+sum[ra][lb][lc]-sum[la][lb][lc]>=m)
					return 1;
	return 0;
}
signed main()
{
	freopen("rgb.in","r",stdin),freopen("rgb.out","w",stdout);
	read(n,m); for(int i=1,a,b,c;i<=n;i++)
		read(a,b,c),sum[++a][++b][++c]++,mx=max({mx,a,b,c});
	for(int i=1;i<=mx;i++) for(int j=1;j<=mx;j++) for(int k=1;k<=mx;k++) 
		sum[i][j][k]+=sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1];
	for(int l=0,r=mx,mid;l<=r;)
	{if(check(mid=l+r>>1)) r=mid-1,ans=mid; else l=mid+1;}
	write(ans);
}

T2 兵蚁排序

高级构造题，赛时没看，但是发现他都说了操作数不大于 \(n^2\) 就行，明摆着冒泡。

发现如果出现 \(b\) 中没有但是 \(a\) 中有的逆序对就无解，其余的直接冒泡即可。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1010;
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 T,n,a[N],b[N]; vector<pair<int,int> >ans;
signed main()
{
	freopen("sort.in","r",stdin),freopen("sort.out","w",stdout);
	for(read(T);T;T--,ans.clear())
	{
		read(n); bool flag=0;
		for(int i=1;i<=n;i++) read(a[i]);
		for(int i=1;i<=n;i++) read(b[i]);
		for(int i=1;i<=n;i++) 
		{
			for(int j=i;j<=n;j++)
			{
				if(a[j]<b[i]) {flag=1,i=n; break;}
				else if(a[j]==b[i])
				{
					for(int k=j;k>i;k--)
						swap(a[k-1],a[k]),ans.push_back(make_pair(k-1,k));
					break;
				}
			}
		}
		if(flag) {puts("-1"); continue;}
		puts("0"),write(ans.size()),puts("");
		for(auto pos:ans) write(pos.first,pos.second),puts("");
	}
}

T3 人口局 DBA

数位 DP 好题，直接上数位 DP，如果是递归的因为记忆化数组开不下分数不高，改成递推的能滚动一下就有 \(60\) 多分，加一些优化，只记录不是 \(limit\) 状态下的，这部分可以递推跑，跑出来的有用的就丢进去递归，这样能防止空间爆炸，有 \(91pts\)，再发现其本质，把递归那部分改成递推直接跑，就有了 \(97pts\)。

放一些代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2010,M=510,P=1e9+7,S=5e4+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,a[N],f[M][S],g[N][N<<1];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
inline int dfs(int len,int sum,bool limit,bool flag)
{
	if(sum>s||sum+(n-len+1)*(m-1)<s) return 0;
	if(len==n+1) return (sum==s);
	if(flag&&!limit&&f[len][sum]!=-1) return f[len][sum];
	int maxx=limit?a[len]:m-1,ans=0;
	if(flag) for(int i=0;i<=maxx;i++)
		ans=mod(ans,dfs(len+1,sum+i,limit&&(i==maxx),1));
	else
	{
		for(int i=1;i<=maxx;i++) 
			ans=mod(ans,dfs(len+1,sum+i,limit&&(i==maxx),1));
		ans=mod(ans,dfs(len+1,0,0,0));
	}
	if(!limit) f[len][sum]=ans;
	return ans;
}
inline int dfs2(int len,int sum,bool limit,bool flag)
{
	if(sum>s||sum+(n-len+1)*(m-1)<s) return 0;
	if(len==n+1) return (sum==s);
	if(flag&&!limit&&g[len][sum]!=-1) return g[len][sum];
	int maxx=limit?a[len]:m-1,ans=0;
	if(flag) for(int i=0;i<=maxx;i++)
		ans=mod(ans,dfs2(len+1,sum+i,limit&&(i==maxx),1));
	else
	{
		for(int i=1;i<=maxx;i++) 
			ans=mod(ans,dfs2(len+1,sum+i,limit&&(i==maxx),1));
		ans=mod(ans,dfs2(len+1,0,0,0));
	}
	if(!limit) g[len][sum]=ans;
	return ans;
}
signed main()
{
	freopen("dba.in","r",stdin),freopen("dba.out","w",stdout);
	read(m,n),memset(f,-1,sizeof(f)),memset(g,-1,sizeof(g));
	for(int i=1;i<=n;i++) read(a[i]),s+=a[i];
	if(s<=2*m) write(dfs2(1,0,1,0)-1);
	else write(dfs(1,0,1,0)-1);
}

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2010,M=4e6+10,P=1e9+7;
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,a[N],f[2][M][2]; 
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
signed main()
{
	freopen("dba.in","r",stdin),freopen("dba.out","w",stdout);
	read(m,n);
	for(int i=1;i<=n;i++) read(a[i]),s+=a[i]; reverse(a+1,a+1+n);
	f[0][s][0]=f[0][s][1]=1;
	for(int i=1,x=1,y=0;i<=n;i++,x^=1,y^=1)
	{
		for(int j=0;j<=min(s,(n-i+2)*(m-1));j++)
			f[x][j][0]=f[x][j][1]=0;
		for(int j=0;j<=min(s,(n-i+1)*(m-1));j++)
		{
			for(int k=0;k<=min(a[i]-1,s-j);k++)
			{
				f[x][j][0]=mod(f[x][j][0],f[y][j+k][0]);
				f[x][j][1]=mod(f[x][j][1],f[y][j+k][0]);
			}
			f[x][j][1]=mod(f[x][j][1],f[y][j+a[i]][1]);
			for(int k=a[i];k<=min(m-1,s-j);k++)
				f[x][j][0]=mod(f[x][j][0],f[y][j+k][0]);
		}
	}
	write(f[n&1][0][1]-1);
}

#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(3)
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
using namespace __gnu_pbds;
const int N=2000+1,P=1e9+7;
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,a[N],f[2][N*N]; unordered_map<int,int>mp[N];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
inline void dfs(int len,int sum,bool lim)
{
	if(sum+len*(m-1)<s) return ;
	if(!lim) return mp[len][s-sum]=0,void();
	int maxx=lim?a[len]:m-1;
	for(int i=0;i<=maxx&&sum+i<=s;i++) dfs(len-1,sum+i,lim&&(i==maxx));
}
inline int dp(int len,int sum,bool lim)
{
	if(!len) return sum==s;
	if(!lim) return mp[len][s-sum];
	int res=0,maxx=lim?a[len]:m-1;
	for(int i=0;i<=maxx&&sum+i<=s;i++)
		res=mod(res,dp(len-1,sum+i,lim&&(i==maxx)));
	return res;
}
signed main()
{
	freopen("dba.in","r",stdin),freopen("dba.out","w",stdout);
	read(m,n); for(int i=n;i;i--) read(a[i]),s+=a[i];
	dfs(n,0,1),f[0][0]=1;
	for(int i=1,x=1,y=0;i<=n;i++,x^=1,y^=1) for(int j=0;j<=s;j++)
	{
		f[x][j]=f[y][j],(j)&&(f[x][j]=mod(f[x][j],f[x][j-1]));
		(j>=m)&&(f[x][j]=mod(f[x][j],P-f[y][j-m]));
		if(mp[i].find(j)!=mp[i].end()) mp[i][j]=f[x][j];
	}
	write(dp(n,0,1)-1);
}

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2000+1,P=1e9+7;
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,sum,ans,a[N],f[2][N*N];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
signed main()
{
	freopen("dba.in","r",stdin),freopen("dba.out","w",stdout);
	read(m,n); for(int i=1;i<=n;i++) read(a[i]),sum+=a[i];
	f[0][0]=1; for(int i=1,x=1,y=0,s=a[n];i<=n;s+=a[n-i],i++,x^=1,y^=1)
	{
		for(int j=0;j<=sum;j++)
		{
			f[x][j]=f[y][j],(j)&&(f[x][j]=mod(f[x][j],f[x][j-1]));
			(j>=m)&&(f[x][j]=mod(f[x][j],P-f[y][j-m]));
		}
		for(int j=0;j<a[n-i+1];j++) ans=mod(ans,f[y][s-j]);
	}
	write(ans);
}

正解加个容斥就可以了，推推式子，但我懒得再写一遍了，沾官方题解了：

image

点击查看代码 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2010,P=1e9+7;
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,ans,a[N],jc[N*N],inv[N*N];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
inline int 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 m>n?0:1ll*jc[n]*inv[n-m]%P*inv[m]%P;}
inline int solve(int n,int s,int a,int res=0)
{
	for(int i=0;i<=n;i++)
		res=mod(res,1ll*mod((i&1?-1ll:1ll)*C(n,i)*(C(s-i*m+n,n)-C(s-a-m*i+n,n))%P,P));
	return res;
}
signed main()
{
	freopen("dba.in","r",stdin),freopen("dba.out","w",stdout);
	read(m,n); for(int i=1;i<=n;i++) read(a[i]),s+=a[i];
	jc[0]=1; for(int i=1;i<=n*m;i++) jc[i]=1ll*jc[i-1]*i%P;
	inv[n*m]=qpow(jc[n*m],P-2);
	for(int i=n*m-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%P;
	for(int i=1,j=0;i<=n;j+=a[i++]) ans=mod(ans,solve(n-i,s-j,a[i]));
	write(ans);
}

T4 银行的源起

不会。

标签：unlocked,int,18,void,多校,Tp,CSP2024,read,inline
From： https://www.cnblogs.com/Charlieljk/p/18528923

相关文章

  • P1802 5 倍经验日: 动态规划
    5倍经验日题目背景现在乐斗有活动了！每打一个人可以获得5倍经验！absi2011却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。题目描述现在absi2011拿出了$x$个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。由于迷你装药物每个只能用一次，......
  • 国标GB28181软件LiteGBS国标GB28181视频平台视频监控/视频监控汇聚系统方案
    随着信息技术的快速发展，视频监控系统已成为公共安全、城市管理和企业安防等领域的重要组成部分。然而，不同厂商生产的视频监控设备遵循不同的标准，导致设备之间无法互通，管理上面临困难，这为安防系统的建设带来了显著挑战。为了解决这一问题，公安部提出了GB28181标准，即GB/T28181—2016......
  • LOJ6118 「2017 山东二轮集训 Day7」鬼牌
    题意有\(n\)个球，\(m\)种颜色，\(i\)种颜色有\(a_i\)个球。每次随机选择两个球\(x\)，\(y\)。使两个球的颜色都变为\(y\)的颜色。问最终只有一个颜色的球的期望步数。\(n\le10^9,m\le10^5\)。Sol显然的，考虑先枚举最终颜色，我们只关心当前有多少个最终颜色的球。......
  • 国标GB28181公网平台LiteGBS国标GB28181网页直播平台Web界面：GB28181协议监控视频管理
    在数字化时代，视频监控系统已成为公共安全和企业管理中不可或缺的一部分。随着技术的进步，GB28181协议作为国家标准，为视频监控系统的互联互通提供了一个统一的平台。LiteGBS作为遵循GB28181协议的网页直播平台，以其高效、稳定的特性，为用户提供了一个强大的视频管理工具。LiteGBS是......
  • 国标GB28181摄像机接入EasyGBS国标GB28181视频平台：GB28181拉流、推流应用场景和特点
    国标GB/T28181作为安防视频领域的重要标准，为国标GB28181视频平台EasyGBS提供了无缝接入平台的统一框架。在这一框架下，国标GB28181摄像机接入EasyGBS国标GB28181视频平台，实现了实时监控、录像管理等多种功能，极大地提升了安防监控的效率和灵活性。以下是具体的应用场景和特点：......
  • 国标GB28181视频平台EasyGBS国标GB28181公网平台实时视频播放方案
    随着科技的飞速发展，视频监控技术已经成为维护公共安全、提升管理效率的重要手段。在这个背景下，国标GB28181视频平台EasyGBS凭借其强大的功能和灵活性，为视频监控行业带来了前所未有的便捷与安全。本文将详细介绍国标GB28181视频平台EasyGBS国标GB28181公网平台的实时视频播放方......
  • 代码随想录打卡Day18
    1.二叉搜索树的最小绝对差:题目描述给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。差值是一个正数，其数值等于两值之差的绝对值。示例1：输入：root=[4,2,6,1,3]输出：1代码:/***Definitionforabinarytreenode.*structTree......
  • 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\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99