首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛05

多校A层冲刺NOIP2024模拟赛05

时间：2024-10-11 20:12:49浏览次数：9  
标签：05 int ll 多校 long pos mod NOIP2024 define

T1、好数（number）

签到题

把选三个数相加拆为选择一个数，然后看前面有没有能用两个数组合出答案。 $ O(n^2) $ 。

码( 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define mk make_pair
#define ps push_back
#define fi first
#define se second
const int N=1e6+10,inf=0x3f3f3f3f,B=2e5+10;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar_unlocked();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?-1:1,c=getchar_unlocked();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar_unlocked();
	return x*f;
}
int n,a[N];
bool f[N];
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<i;++j){
			if(f[a[i]-a[j]+B]){++ans;break;}
		}
		for(int j=1;j<=i;++j)
			f[a[i]+a[j]+B]=1;
	}
	cout<<ans;
}

T2、SOS字符串（sos）

也算签到题吧，但我被评测机创飞了。

直接暴力枚举写了个狗屎DP，算了下时间来到了 4e8。。。但加了一点剪枝后在本地跑了0.64s，然后自信交卷了。然后就T了！
所以评测机一秒到底能跑多少啊。

说下改进后的DP

一维状态记已经有了多少个 $ SOS $ ，另一维表示目前最后三个字符的状态，分别有 第一个有用的 $ S $ ,第一个有用的 $ O $ 、第二个有用的 $ S $ 和其他状态。直接转移即可。

这个确实快，1e8本地只跑了0.94s。

码( 
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define mk make_pair
#define ps push_back
#define fi first
#define se second
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar_unlocked();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?-1:1,c=getchar_unlocked();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar_unlocked();
	return x*f;
}
#define mo(x) (x>=mod?x-=mod:0)
int n;
ll f[2][4][4];
signed main(){

	freopen("sos.in","r",stdin);
	freopen("sos.out","w",stdout);
	// int ti=clock();
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	f[0][3][0]=1;
	int now=0,to=1;
	for(int i=0;i<n;++i){
		for(int k=0;k<=2;++k){
			(f[to][3][k]+=((f[now][0][k]+f[now][1][k]+f[now][2][k]+f[now][3][k])*25ll-f[now][0][k]))%=mod;
			(f[to][1][k]+=f[now][0][k]);f[to][1][k]>=mod?f[to][1][k]-=mod:0;
			(f[to][0][k]+=(f[now][3][k]+f[now][2][k]+f[now][0][k]))%=mod;
			(f[to][2][k+1]+=f[now][1][k]);f[to][2][k+1]>=mod?f[to][2][k+1]-=mod:0;
			f[now][0][k]=f[now][1][k]=f[now][2][k]=f[now][3][k]=0;
		}
		(f[to][2][3]+=f[now][2][3]*26ll)%=mod;f[now][2][3]=0;
		swap(now,to);
	}
	cout<<f[now][2][3]<<'\n';
	// cout<<(clock()-ti)/1e6<<endl;
}

T3、集训营的气球（balloon）

退背包的板子吧。

第一次接触退背包的题，但是考场上竟然YY出来了。

首先背包肯定会跑，但是每次修改都要重新跑一边背包的话复杂度就太高了。
但是你可以观察到每次只会修改一个地方，然后全局询问，那么你就可以用线段树去维护这个背包，直接单点修改即可，非常的好写。时间复杂度是 O $ (q c^2 log(n)) $，但是有点小卡常，反正我不用光速膜是过不去80分的点的。

线段树 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define mk make_pair
#define ps push_back
#define fi first
#define se second
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar_unlocked();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?-1:1,c=getchar_unlocked();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar_unlocked();
	return x*f;
}
int f[N<<1][21],a[N],b[N],n,C;
#define mo(x) (x>=mod?x-=mod:0)
inline void up(int a[],int b[],int c[]){
	for(int i=0;i<=C;++i)
		a[i]=0;
	for(int i=0;i<=C;++i){
		for(int j=0;j<=C;++j)
			(a[i+j>C?C:i+j]+=(ll)b[i]*c[j]%mod)%=mod;
	}
}
inline void add(int k,int l,int r,int pos){
	if(l==r)return (void)(f[k][0]=b[l],f[k][1]=a[l]);
	int mid=l+r>>1;
	pos<=mid?add(k<<1,l,mid,pos):add(k<<1|1,mid+1,r,pos);
	for(int i=0;i<=C;++i)
		f[k][i]=0;
	for(int i=0;i<=C;++i){
		for(int j=0;j<=C;++j)
			f[k][i+j>C?C:i+j]+=(ll)f[k<<1][i]*f[k<<1|1][j]%mod,mo(f[k][i+j>C?C:i+j]);
	}
}
inline void jian(int k,int l,int r){
	if(l==r)return (void)(f[k][0]=b[l],f[k][1]=a[l]);
	int mid=l+r>>1;
	jian(k<<1,l,mid),jian(k<<1|1,mid+1,r);
	for(int i=0;i<=C;++i){
		for(int j=0;j<=C;++j)
			f[k][i+j>C?C:i+j]+=(ll)f[k<<1][i]*f[k<<1|1][j]%mod,mo(f[k][i+j>C?C:i+j]);
	}
}
signed main(){
	// #ifndef ONLINE_JUDGE
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	// #endif
	// double ti=clock();
	// cout<<sizeof(f)/1024/1024<<endl;
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();C=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		b[i]=read();
	jian(1,1,n);
	int m=read();
	for(int j=1,pos;j<=m;++j){
		pos=read();a[pos]=read(),b[pos]=read();
		add(1,1,n,pos);
		cout<<f[1][C]<<'\n';
	}
	// cout<<(double)(clock()-ti)/1e6<<'\n';
}

其实但是打完这个就去看T4了，没想着能A了，但后面那个T4属实不太会，于是又回来看T3。

看看我们能不能把修改的复杂度降下来。先想想为什么线段树比暴力快呢？或者说为什么暴力很慢呢？因为每次重新跑一遍DP会丢失很多之前已经统计好的信息，然后又白白的去统计一堆已经统计过的信息，但其实有用的信息只有修改的地方改变了，那么线段树之所以快，就是因为他重新统计的信息少，浪费的信息少。那么我们能不能不浪费任何信息呢？

其实是可以的，背包与物品的顺序是无关的，那么我们可以假设每次修改的位置都是最后一个物品，那么第 n-1 个及以前的物品是不变的，再跑一次DP时跑到这的DP数组也是一点不变的，但我们又不能每次记倒数第二个DP数组，因为他并不是真的只改最后一个，只是假设而已，那么我们就得设法通过最终状态的DP数组求出 去除修改物品后的DP数组。

这个就叫退背包，我们通过正向的转移柿子去逆向解出原来的DP数组。

那这个题举例子吧：

设 $ f_i ，i∈[0,C] $ 表示有 $ i $ 个人选择的是 一血气球， $ f_i , [i=C+1] $ 表示至少有 $ C+1 $ 个人选择一血气球。pos 表示当前修改的位置。

我们可以写出转移柿子

\[f_i = f_{i-1} a_{pos} [i \gt 0] + f_i b[pos] \ \ \ \ \ (i∈[0,C]) \]

\[f_{C+1} = f_{C+1} (a_{pos}+b_{pos}) + f_{C} a_{pos} \]

那么我们把pos当做最后一个位置，于是就可以把柿子倒回去。设 $ g_i $ 表示不考虑 pos 这个位置时的 $ f_i $ 。

那么直接把上面的等式右边的 $ f_i $ 修改为 $ g_i $ 即可

\[f_i = g_{i-1} a_{pos} [i \gt 0] + g_i b[pos] \ \ \ \ \ (i∈[0,C]) \]

\[f_{C+1} = g_{C+1} (a_{pos}+b_{pos}) + g_{C} a_{pos} \]

怎么解呢，高斯消元？

其实不用，我们要知道 $ g_{C+1} $ 就得知道 $ g_C $ ，要知道 $ g_C $ ，就得知道 $ g_{C-1} $，以此类推，最后压力给到了 $ g_0 $ ，那 $ g_0 $ 是什么呢，就是除去 $ pos $ 这个位置上的人，所有人都选 b 的方案数。这个直接那所有的除个 $ b_{pos} $ 就行了。

\[然后你就什么都知道了 \]

求出 $ g_i $ 后，就可以求出新的 $ f_i $ 了，那么我们对于每次修改，只需要 $ O(C) $，的时间复杂度就可以处理了！

至此，就是场上想的退背包的过程，要学习退背包可以去专门学学，有板子题：P4141 消失之物。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define mk make_pair
#define ps push_back
#define fi first
#define se second
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
#define int ll
inline ll read(){
	char c=getchar_unlocked();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?-1:1,c=getchar_unlocked();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar_unlocked();
	return x*f;
}
ll f[2][22],a[N],b[N],ff[22],C,n;
inline ll qpow(ll x,ll y){
	ll ans=1;x%=mod;
	while(y){
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ans;
}
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read(),C=read();
	ll sumb=1;
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		b[i]=read(),sumb=sumb*b[i]%mod;
	int now=1,fr=0;
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=C+1;++j){
			// f[now][j]=0;
			f[now][j]=f[fr][j]*b[i]%mod;
			if(j)f[now][j]+=f[fr][j-1]*a[i]%mod;
			if(j==C+1)f[now][j]+=f[fr][j]*a[i]%mod;
			f[now][j]%=mod;
		}
		swap(now,fr);
	}
	for(int i=0;i<=C+1;++i)
		f[0][i]=f[fr][i];
	int m=read();
	for(int i=1,pos;i<=m;++i){
		pos=read();
		ll nyb=qpow(b[pos],mod-2);
		ff[0]=sumb*nyb%mod;
		for(int j=1;j<=C;++j){
			ff[j]=((f[0][j]-ff[j-1]*a[pos]%mod)*nyb%mod+mod)%mod;
		}
		ff[C+1]=((f[0][C+1]-ff[C]*a[pos]%mod)*qpow(a[pos]+b[pos],mod-2)%mod+mod)%mod;
		a[pos]=read(),b[pos]=read();sumb=sumb*nyb%mod*b[pos]%mod;
		for(int j=0;j<=C+1;++j){
			f[0][j]=ff[j]*b[pos]%mod;
			if(j)f[0][j]+=ff[j-1]*a[pos]%mod;
			if(j==C+1)f[0][j]+=ff[j]*a[pos]%mod;
			f[0][j]%=mod;
		}
		cout<<(f[0][C]+f[0][C+1])%mod<<'\n';
	}
}

T4、连通子树与树的重心（tree）

先膜拜一下Qyun，全场唯一一个拿分而且拿了50分的。

其实当时看到这个题的时候，有点抵触，因为这种题其实我没什么头绪，整了半个小时也没整出来啥，就放弃了。

这道题主要就是用重心的性质。

不太想写了，挂个题解吧。

image
image

咕了 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define mk make_pair
#define ps push_back
#define fi first
#define se second
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=10007;
inline ll read(){
	char c=getchar_unlocked();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?-1:1,c=getchar_unlocked();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar_unlocked();
	return x*f;
}
int n,cnt,hd[N],rt,sz[N],man[N],rt2;
int f[5001][5001],g[5001];
struct jj{
	int to,next;
}bi[N<<1];
inline void add(int x,int y){bi[++cnt]={y,hd[x]},hd[x]=cnt,bi[++cnt]={x,hd[y]},hd[y]=cnt;}
inline void findrt(int x,int f){
	sz[x]=1,man[x]=0;
	for(int i=hd[x];i;i=bi[i].next){int j=bi[i].to;if(j!=f)findrt(j,x),sz[x]+=sz[j],man[x]=max(man[x],sz[j]);}
	man[x]=max(man[x],n-sz[x]);
	if(man[x]<=(n>>1))rt=x;
}
inline void dfs(int x,int ff){
	f[x][1]=1;sz[x]=1;
	for(int i=hd[x];i;i=bi[i].next){
		int j=bi[i].to;
		if(j!=ff){
			dfs(j,x);
			for(int p=sz[x];p;--p){
				for(int k=1;k<=sz[j];++k)
					(f[x][p+k]+=f[x][p]*f[j][k]%mod)%=mod;
			}
			sz[x]+=sz[j];
		}
	}
}
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	for(int i=1;i<n;++i)
		add(read(),read());
	rt=1;
	findrt(1,0);
	for(int i=hd[rt];i;i=bi[i].next){
		int j=bi[i].to;
		if(man[j]==man[rt])rt2=j;
	}
	if(rt2){
		dfs(rt,rt2),dfs(rt2,rt);
		int ans=0;
		for(int i=1;i<=n;++i)
			(ans+=f[rt][i]*f[rt2][i]%mod)%=mod;
		cout<<ans<<'\n';
		return 0;
	}
	else{
		dfs(rt,0);
		//tuibao
		int ans=0;
		for(int i=1;i<=n;++i)
			ans=(ans+f[rt][i])%mod;
		for(int i=hd[rt];i;i=bi[i].next){
			int j=bi[i].to;
			for(int k=1;k<=n;++k){
				g[k]=f[rt][k];
				for(int p=1;p<=min(k,sz[j]);++p){
					g[k]=(g[k]-g[k-p]*f[j][p]%mod+mod)%mod;
				}
				for(int p=(k+1)>>1;p<=sz[j]&&p<=k;++p)
					ans=(ans-g[k-p]*f[j][p]%mod+mod)%mod;
			}
		}
		cout<<ans<<'\n';
	}
}

\[\]

\[\]

\[\]

\[\]

\[\]

\[\]

hard to say 

今天晚上开了动员大会，怎么说呢。算是点醒我吗？

今天看见暑假集训模拟赛的结果，退了不少，一开始还是在前面的，但是后面几场几乎是垫底了。

因为点什么呢，大概是当时有点拒绝思考吧，可能就确实是怕输吧。

但怕有什么用呢，就好好打模拟赛吧，也不要沾沾自喜，也不要患得患失，就学吧。

那我后悔学信奥吗，其实总来没后悔过，并不是因为今天huge说的话，而只是因为，就确实不后悔，其实平常总开玩笑，“还好我是信奥的”，但一点不后悔。放下架子，往前走吧。

标签：05,int,ll,多校,long,pos,mod,NOIP2024,define
From： https://www.cnblogs.com/GGrun-sum/p/18458839

相关文章

  • [45] (多校联训) A层冲刺NOIP2024模拟赛05
    这是什么午休，大黄突然走进来大黄：闪电特效！其他人：？大黄：5k!其他人：？？？大黄：【闪电特效】【闪电特效】男人中的男人【闪电特效】【闪电特效】雄性中的雄性【闪电特效】【闪电特效】巅峰！【闪电特效】【闪电特效】A.好数简单变形一下\[f_i+f_j+f_k=c\]\[f_j+f_k=c-f_i\]然......
  • 多校A层冲刺NOIP2024模拟赛05
    咋是计数专场啊，讨厌计数！就会一个签到题，恼了。rank21,T1100pts,T20pts,T320pts,T40ptsdp设计状态不行。T3典型的背包没看出来，T2简单dp不会设计状态。有一些套路还是要学好数（number）签到题。假设一个数\(a_i\)是好数，那么一定有\(a_i=a_x+a_y+a_z(x\ley\lez)\)用一个b......
  • 多校A层冲刺NOIP2024模拟赛05
    多校A层冲刺NOIP2024模拟赛05\(T1\)A.好数（number）\(100pts/100pts\)枚举两数之和，开个桶维护即可。点击查看代码inta[5010];unordered_map<int,bool>s;intmain(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout)......
  • 多校 A 层冲刺 NOIP2024 模拟赛 05
    多校A层冲刺NOIP2024模拟赛05T1好数（number）签到题首先\(O(nV)\)的背包暴力是显然的，注意到本题只需要合法性，状态只有\(0/1\)，上\(bitset\)优化转移即可。时间复杂度\(O(\frac{nV}{w})\)。T2SOS字符串（sos）签到题计数题难点在不重不漏，而本题则主要是不重。考虑一种好的......
  • ETA6005Q3Q 2.5A带动态路径管理的单节锂电开关型充电器
    2.5A带动态路径管理的单节锂电开关型充电器  ETA6005是一款充电电流达2.5A的单节锂电开关型充电。其集成了动态路径管理功能，内部路径的开关内阻仅50mohm，允许系统在没有电池的情况下，仍然可以在适配器存在是维持系统正常工作。ETA6005有特有的2级充电设定可通过引脚的0,1来设......
  • 学习011-08-05 Boolean Properties（布尔属性）
    BooleanProperties（布尔属性）InXAF,thefollowingcontrolscandisplayBooleanandNullableBooleanproperties:在XAF中，以下控件可以显示布尔和Nullable布尔属性：Acheckboxcontrol(default).复选框控件（默认）。Adrop-downcontrolthatdisplaysBooleanvaluesa......
  • PAT甲级1005 Spell It Right
    介绍Givenanon-negativeintegerN,yourtaskistocomputethesumofallthedigitsofN,andoutputeverydigitofthesuminEnglish.InputSpecification:Eachinputfilecontainsonetestcase.EachcaseoccupiesonelinewhichcontainsanN(≤10的1......
  • 2023杭电多校4
    2023杭电多校4a-bProblem题目大意：每个物品都有a,ba,ba,b两个值，......
  • 10.10日noip多校联考总结
    10.10日noip多校联考总结T1感觉就是个dij再多记录一个换乘次数然后就像普通dij一样跑就行了。但是必须得将换乘次数放进dis数组中当成一个状态记录下来，不能只记录在堆中，不然做法会假。T2发现m=0的部分分就是用一个数据结构维护区间最大子段和。m=1/2就是同时维护一个最大值......
  • [AGC054D] (ox) 题解
    感觉看到交换就应该要想到逆序对。思路一个前置小知识，我们把一个排列用相邻交换复原的最小次数是逆序对数量。考虑没有ox的情况。我们顺着扫一遍字符串。把左括号正一，右括号看作负一，当前缀和小于零以后，我们把后面最近的左括号提过来，这样可以构造出交换次数最少的合法括号串......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99