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

多校A层冲刺NOIP2024模拟赛05

时间：2024-10-12 20:10:41浏览次数：1  
标签：const 05 int 多校 read while DP NOIP2024 getchar

好数（number

没啥好说的直接 \(O(n^2)\) 枚举即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

const int N=2e6+107;
const int d=2e5;
int n,a[N],sum[N];

int read()
{
	int f=1,s=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
	return f*s;
}



signed main()
{
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	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-1;j++)
		{
			int x=a[i]-a[j]+d;
			if(sum[x]==1)
			{
				ans++;
				break;
			}	
		}
		for(int j=1;j<=i;j++) sum[a[i]+a[j]+d]=1;
	}
	printf("%d",ans);
}

SOS字符串（sos）

可DP，可分讨，我写的分讨，其实DP也是那个流程。如果DP，要正难则反，直接统计小于3个的情况，最后用 \(26^n\) 减去即可。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e6+107;
const int mod=1e9+7;
int n,ans;

int f[N][10];

int read()
{
	int f=1,s=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
	return f*s;
}

int dfs(int len,int k)
{
	if(f[len][k]!=-1) return f[len][k];
	if(len==0) 
	{
		if(k==0) return f[len][k]=1;
		else return f[len][k]=0;
	}
	
	int res=0;
	if(k==9) // 9: ' *SOS*SOS*SOS* '
	{
		(res+=dfs(len-1,8))%=mod;//*SOS*SOS*SO + S
		(res+=dfs(len-1,9)*26)%=mod;//*SOS*SOS*SOS* + A-Z
	}
	if(k==8)// 8: ' *SOS*SOS*SO '
	{
		(res+=dfs(len-1,7))%=mod;//*SOS*SOS*S + O
	}
	if(k==7)// 7: ' *SOS*SOS*S '
	{
		(res+=dfs(len-1,6))%=mod;//*SOS*SOS* + S
		(res+=dfs(len-1,7))%=mod;//*SOS*SOS(*S) + S
	}
	if(k==6)// 6: ' *SOS*SOS* '
	{
		(res+=dfs(len-1,5))%=mod;//*SOS*SO + S
		(res+=dfs(len-1,6)*25)%=mod;//*SOS*SOS* + A-Z - S
		(res+=dfs(len-1,7)*24)%=mod;//*SOS*SOS(*S) + A-Z -S(k==7) -O(k==8)
		(res+=dfs(len-1,8)*25)%=mod;//*SOS*SOS(*SO) + A-Z - S(k==9)
	}
	if(k==5)// 5: ' *SOS*SO '
	{
		(res+=dfs(len-1,4))%=mod;//*SOS*S + O
	}
	if(k==4)// 4: ' *SOS*S '
	{
		(res+=dfs(len-1,3))%=mod;//*SOS* + S
		(res+=dfs(len-1,4))%=mod;//*SOS(*S) + S
	}
	if(k==3)// 3: ' *SOS* '
	{
		(res+=dfs(len-1,2))%=mod;//*SO + S
		(res+=dfs(len-1,3)*25)%=mod;//*SOS* + A-Z -S(k==4) 
		(res+=dfs(len-1,4)*24)%=mod;//*SOS*S + A-Z -S(k==4) -O(k==5)
		(res+=dfs(len-1,5)*25)%=mod;//*SOS*SO + A-Z -S(k==6)
	}
	if(k==2)// 2: ' *SO '
	{
		(res+=dfs(len-1,1))%=mod;//*S + O
	}
	if(k==1)// 1: ' *S '
	{
		(res+=dfs(len-1,0))%=mod;//* + S
		(res+=dfs(len-1,1))%=mod;//(*S) + S
	}
	if(k==0)// 0: ' * '
	{
		(res+=dfs(len-1,0)*25)%=mod;//* + A-Z - S(k==1)
		(res+=dfs(len-1,1)*24)%=mod;//* + A-Z - S(k==1) - O(k==2)
		(res+=dfs(len-1,2)*25)%=mod;//* + A-Z -S(k==3)
	}
	return f[len][k]=res%mod;
}
// 0: ' * '
// 1: ' *S '
// 2: ' *SO '
// 3: ' *SOS* '
// 4: ' *SOS*S '
// 5: ' *SOS*SO '
// 6: ' *SOS*SOS* '
// 7: ' *SOS*SOS*S '
// 8: ' *SOS*SOS*SO '
// 9: ' *SOS*SOS*SOS* '
int res[N];
signed main()
{
	freopen("sos.in","r",stdin);
	freopen("sos.out","w",stdout);
	n=read();
	memset(f,-1,sizeof f);
	dfs(n,9);
	printf("%lld\n",f[n][9]%mod);
	return 0;
}

集训营的气球（balloon）

正难则反，首先我们可以想到直接跑01背包，然后统计小于 \(c\) 的情况，复杂度是 \(nc\) ，关键是修改操作，如何动态修改，这里有一个新的技巧：退背包（可能是我太菜了，第一次听到），每次修改的时候先退背包，再正常跑一遍的DP,然后就没啥了。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e6+107;
const int p=1e9+7;
int n,c,q;
int a[N],b[N];
int f[N],sum;

int read()
{
	int f=1,s=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
	return f*s;
}

int qpow(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b=b>>1;
	}
	return ans;
}


signed main()
{
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	n=read(),c=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	f[0]=1,sum=1;
	for(int i=1;i<=n;i++) 
	{
		sum=sum*(a[i]+b[i])%p;
		for(int j=c-1;j>=1;j--)
		{
			f[j]=(f[j-1]*a[i]%p+f[j]*b[i]%p)%p;
		}
		f[0]=f[0]*b[i]%p;
	}
	int q=read();
	for(int i=1;i<=q;i++)
	{
		int pos=read(),x=read(),y=read();
		sum=sum*qpow(a[pos]+b[pos],p-2)%p*(x+y)%p;
		int inv=qpow(b[pos],p-2);
		f[0]=f[0]*inv%p;
		for(int j=1;j<=c-1;j++) f[j]=(f[j]-f[j-1]*a[pos]%p+p)*inv%p;
		for(int j=c-1;j>=1;j--) f[j]=(f[j-1]*x%p+f[j]*y%p)%p;
		f[0]=f[0]*y%p;
		int res=sum;
		for(int j=0;j<c;j++) res=(res-f[j]+p)%p;
		a[pos]=x,b[pos]=y;
		printf("%lld\n",res);
	}
}

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

先求出树的重心，这里是会有两种情况：一个重心和两个重心。

我们先来设计一下DP，设 \(f[i][j]\) 表示以 \(i\) 为根的子树选了 \(j\) 个节点相互连通的方案数。其中这个 \(f\) ，我们可以通过树形背包DP来得到。\(f[u][i]+=f[v][j]*f[u][i-j]\)

那先来看有两个重心的情况，分析一下，首先连接两个重心的边肯定不能断，且两个重心除了相互连通外要有同样个数的节点与它相连。

那比较好解决，我们直接断边每个重心跑一遍DP，最后答案为 \(\sum_{i=1}^{n}f[c1][i]*f[c2][i]\)

接着来分析只有一个重心的时候，比较好像到的是，再跑一遍DP，我们设 \(g[i][j]\) 表示以 \(c\) 为根，大小为 \(i\) 的一个连通块中子树大小为 \(j\) 的方案数。由重心的性质：重心所有的子树大小不超过 \(n/2\) 可知，最后答案应为 \(\sum_{i,j*2<=i}\) 。

但这样的复杂度为 \(n^3\) 无法接受，我们考虑换个方法，考虑正难则反（真服了，一场模拟赛放三这玩意）,我们只需要用总方案减去那些子树节点大于 \(i/2\) 的情况。如果我们直接用 \(f\) 数组很明显不对，因为如果我们制定任意一个子树 \(v\) 的节点个数大于 \(i/2\) 为 \(j\) ，那此时 \(f[u][i-j]\) 因为考虑了 \(v\) 这个子树而会算重。这里我们就需要容斥一下，还是考虑退背包操作（这场模拟赛没话说），这个直接根据动态转移方程推一下，还是比较好说的，剩下的就没了。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

const int N=5000+107;
const int mod=10007;
int n;
int f[N][N],g[N][N];

int read()
{
	int f=1,s=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
	return f*s;
}

int h[N<<3],to[N<<3],nxt[N<<3],tot;
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
}

int sz[N],w[N],c[3],cnt;
void dfs(int u,int fa)
{
	sz[u]=1,w[u]=0;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v!=fa)
		{
			dfs(v,u);
			sz[u]+=sz[v];
			w[u]=max(w[u],sz[v]);
		}
	}
	w[u]=max(w[u],n-sz[u]);
	if(w[u]<=n/2) c[cnt++]=u;
}

void dp(int u,int fa)
{
	sz[u]=1;
	f[u][0]=f[u][1]=1;
	for(int x=h[u];x;x=nxt[x])
	{
		int v=to[x];
		if(v==fa) continue;
		dp(v,u);
		sz[u]+=sz[v];
		for(int i=sz[u];i>=0;i--)
		{
			for(int j=1;j<=sz[v]&&j<=i-1;j++)
			{
				(f[u][i]+=f[v][j]*f[u][i-j])%=mod;
			}
		}
	}
}

void solve2()
{
	
	dp(c[0],c[1]);
	dp(c[1],c[0]);
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		(ans+=f[c[0]][i]*f[c[1]][i]%mod)%=mod;
	}
	printf("%lld",ans);
}

void solve1()
{
	
	int u=c[0],ans=0;
	dp(u,0);
	for(int i=1;i<=n;i++) (ans+=f[u][i])%=mod;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		for(int j=1;j<=n;j++)
		{
			g[v][j]=f[u][j];
			for(int k=1;k<=min(j,sz[v]);k++)
			{
				g[v][j]=(g[v][j]-g[v][j-k]*f[v][k]%mod+mod)%mod;
			}
		}
	}
		
	for(int i=1;i<=n;i++)
	{
		for(int j=h[u];j;j=nxt[j])
		{
			int v=to[j];
			for(int k=(i+1)/2;k<=i&&k<=sz[v];k++)
			{
				ans=(ans-f[v][k]*g[v][i-k]%mod+mod)%mod;
			}
		}
	}
	printf("%lld\n",ans);
}

signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();
	for(int i=1;i<=n-1;i++)
	{
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	dfs(1,0);
	if(c[1]) solve2();
	else solve1();
	return 0;
}

标签：const,05,int,多校,read,while,DP,NOIP2024,getchar
From： https://www.cnblogs.com/zhengchenxi/p/18459699

相关文章

  • [46] (多校联训) A层冲刺NOIP2024模拟赛06
    HDK在与mt19937_64先生的石头剪刀布比赛中拿下十一连败的好成绩你也来试试吧#include<bits/stdc++.h>usingnamespacestd;#include"include/hdk/rand.h"usingnamespacehdk::Rand;chargetchar_(){charch=getchar();if(ch>='a'andch<='z......
  • 多校A层冲刺NOIP2024模拟赛06
    rank19，T1100pts，T230pts，T345pts，T420ptsT1小Z的手套（gloves）二分答案，贪心匹配\(O(n\logn)\)的check即可。时间复杂度\(O(n\log^2n)\)点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//usingnamespace__gnu_pbds;//usingnamespace__gnu_cxx;usi......
  • P10589 楼兰图腾
    Problem有n个记号在一面墙上从左往右排列，其离地面高度\(h_i\)不同，保证是1~n的一个排列，试求出有多少种如下两种情况\[①i<j<k\]\[②h_i>h_j<h_k或h_i<h_j>h_k\]其中在满足①②的情况下②分左右两种，\(n\le2\times10^5\)且\(Ans\le2^{64}-1\)Solve可以枚举每个\(i,j,k\)计算......
  • MT6705B
    MT6705B是用于反激式变换器的高性能45V同步整流器。MT6705B兼容各种反激转换器类型。支持DCM、CCM和准谐振模式。MT6705B集成了一个40V功率MOSFET，可以取代肖特基二极管，提高效率。VSW<VTH-ON时，MT6705B内部MOSFET导通。VSW>VTH-OFF时，MT6705B内部MOSFET关闭。MT670......
  • 105th 2024/10/11 模拟赛总结61
    傲慢，凭什么傲慢T1开幕雷击，认为水飞了”一眼CDQ板子啊“然后十五分钟时直接开打主要原因绝对是因为昨天场切了T1，所以飘起来了还是应该稳重一点，起码模几个不同数据再下定论实际上也真是水题，相当于板子了自己对排列不够熟悉，真的没想到是直接全局-部分正难则反？从没用上过自以......
  • 10.11日noip多校联考总结
    10.11日noip多校联考总结T1看到感觉像是一个很玄学的题目，在考场上推了大概一个多小时，又写了大概半个小时，终于调出来了。谨记：三分取mid需要进行浮点数运算。对于每一行和每一列定义两个数组来记录要加多少，因为我们只需要知道其中任意一个数就可以推出所有的数，那么考虑枚举x0，来......
  • 多校A层冲刺NOIP2024模拟赛05
    A.好数（number）很容易想到\(n^3\)枚举两个，看第三个是否出现，扩展一下，枚举一个，看剩下需要的和是否出现过，提前处理出两两的和和最早能合出这个数的位置，复杂的\(O(n^2)\)点击查看代码#include<bits/stdc++.h>constintmaxn=5000+10;usingnamespacestd;intn,a[maxn],cnt,......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛05
    Rank烂。A.好数（number）签，唐，没签上。考虑之前几次类似的题方法都是选\(k-1\)的方案存起来以使总复杂度除以一个\(n\)，故考虑记共\(n^2\)个两两组合之和，枚举当前点\(i\)前面的点，找是否有值为它们的差的组合，复杂度\(\mathcal{O(n^2)}\)，用map记再挂个\(\logn\)。赛......
  • 多校A层冲刺NOIP2024模拟赛05
    T1、好数（number）签到题把选三个数相加拆为选择一个数，然后看前面有没有能用两个数组合出答案。$O(n^2)$。码(#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<int,int>pii;#definemkmake_pair#de......
  • [45] (多校联训) A层冲刺NOIP2024模拟赛05
    这是什么午休，大黄突然走进来大黄：闪电特效！其他人：？大黄：5k!其他人：？？？大黄：【闪电特效】【闪电特效】男人中的男人【闪电特效】【闪电特效】雄性中的雄性【闪电特效】【闪电特效】巅峰！【闪电特效】【闪电特效】A.好数简单变形一下\[f_i+f_j+f_k=c\]\[f_j+f_k=c-f_i\]然......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99