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

多校A层冲刺NOIP2024模拟赛03

时间:2024-10-09 19:49:53浏览次数:9  
标签:03 const vis int 多校 long read while NOIP2024

T1.colorfu

正难则反,直接枚举横行,枚举右边界,如果相同,则会对后面以及它本身统计产生 \(1\) 的贡献,我们直接开个桶统计一下。

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

#define int long long
const int N=1000+107;
int n,m;
int a[N][N],cnt[N*N];
int 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;
}

signed main()
{
	freopen("colorful.in","r",stdin);
	freopen("colorful.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
		}
	}
	sum=n*(n+1)*m*(m+1)/4;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			for(int k=1;k<=m;k++)
			{
				if(a[i][k]==a[j][k])
				{
					++cnt[a[i][k]];
					ans+=cnt[a[i][k]];
				}
			}
			for(int k=1;k<=m;k++) cnt[a[i][k]]=0;
		}
	}
	printf("%lld",sum-ans);
}

T2.travel

双指针统计,不难发现值域很大,操作很少,我们发现一段区间更新后这一段时间的值不会立刻再发生改变,类似于莫队的移动边界到查询点的操作,我们差分处理一下,然后排序,直接模拟移动即可。

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

#define int long long
const int N=4e6+107;
const int mod=1e9+7;
int n,m,s,t;


struct lmy
{
	int x,pos,val;
}a[N];
bool comp(lmy a,lmy b){return a.pos==b.pos?a.val<b.val:a.pos<b.pos;}

int p[N],g[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 qpow(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b=b>>1;
	}
	return ans;
}


signed main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	n=read(),m=read(),s=read(),t=read();
	p[m*2+1]=s,p[m*2+2]=t+1;
	for(int i=1;i<=m;i++)
	{
		int x=read(),l=read(),r=read();
		p[i]=l,p[i+m]=r+1;
		a[i]={x,l,1},a[i+m]={x,r+1,-1};
	}
	sort(p+1,p+1+2*m+2),sort(a+1,a+1+2*m,comp);
//	int len=unique(p+1,p+1+2*m+2)-(p+1);
	int j=0; int ans=1; int snum=n;
	for(int i=1;i<m*2+2;i++)
	{
		while(j<m*2&&a[j+1].pos<=p[i])
		{
			j++;
			int x=a[j].x;
			int d=a[j].val;
			if(g[x]>0&&g[x]+d<=0) snum++;
			if(g[x]<=0&&g[x]+d>0) snum--;
			g[x]+=d;
		}
		ans=ans*qpow(snum,p[i+1]-p[i])%mod;
	}
	printf("%lld",ans);
	
}

T3.segment

题解挺清楚的

T4.experiment

计数DP转概率DP,首先将 \(i\) 向 \(b_i\) 建一条边,很显然 \(n\) 一定处于一颗基环树中,我们直接 \(dfs\) 找出环上最小的节点,接着枚举断边还是不断边,跑DP转移即可。我们设 \(f_i\) 表示 \(i\) 节点为猫的概率。 \(u\) 为当前节点, \(v\) 为子节点。

转移:

\(f_v=f_u*f_v\)

\(f_v=f_u*(1-f_v)\)

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

#define int long long
const int N=3e4+107;
const int mod=1e9+7;
const int inv2=500000004;
int n,root;
int b[N],vis[N];
char s[N];
int f[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 qpow(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b=b>>1;
	}
	return ans;
}

int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}

int dfs1(int x)
{
	vis[x]=1;
	int y=b[x];
	return (vis[y]==1)?x:dfs1(y);
}

void dfs(int x,int &root)
{
	root=min(root,x);
	vis[x]=1;
	int y=b[x];
	if(vis[y]==0) dfs(y,root);
}

signed main()
{
	freopen("experiment.in","r",stdin);
	freopen("experiment.out","w",stdout);
	int t=read();
	while(t--)
	{
		memset(vis,0,sizeof vis);
		int ans=0,sum=0;
		n=read();
		for(int i=1;i<=n;i++) fa[i]=i;
		
		for(int i=1;i<=n;i++) scanf(" %c",&s[i]);
		for(int i=1;i<=n;i++) 
		{
			b[i]=read();
			merge(i,b[i]);
			sum+=(s[i]=='?');
		}
		for(int i=1;i<=n;i++) 
		{
			if(find(i)==fa[n])
			{
				root=dfs1(i);
				break;
			}
		}
		memset(vis,0,sizeof vis);
		dfs(root,root);
		int num=0;
		for(int j=0;j<=1;j++)
		{
			for(int k=0;k<=1;k++)
			{
				for(int i=1;i<=n;i++) 
				{
					if(s[i]=='C') f[i]=1;
					if(s[i]=='.') f[i]=0;
					if(s[i]=='?') f[i]=inv2;
				}
				for(int i=1;i<=n;i++)
				{
					int y=b[i];
					if(i==root)
					{
						if(j==1) 
						{
							if(k==1) num=f[i]*f[y]%mod;
							if(k==0) num=f[i]*(1-f[y]+mod)%mod;
						}
						if(j==0)
						{
							if(k==1) num=(1-f[i]+mod)%mod*f[y]%mod;
							if(k==0) num=(1-f[i]+mod)%mod*(1-f[y]+mod)%mod;
						}
						f[i]=j;
						f[y]=k;
					}
					int tmp=f[i];
					f[i]=tmp*f[y]%mod;
					f[y]=(f[y]+((1-f[y]+mod)%mod)*tmp%mod)%mod;
				}
				ans=(ans+num*f[n]%mod)%mod;
			}
		}
		printf("%lld\n",ans*qpow(2,sum)%mod);
	}
}

标签:03,const,vis,int,多校,long,read,while,NOIP2024
From: https://www.cnblogs.com/zhengchenxi/p/18455012

相关文章

  • [44] (多校联训) A层冲刺NOIP2024模拟赛04
    A.02表示法这题放在ABCD题我可能不会奇怪,但是它放模拟赛T1了赛时代码#include<bits/stdc++.h>usingnamespacestd;classnum_string{ private: stringx; inlinevoiddevided_2(){ stringans="";intnow=0; for(inti=0;i<=(int)x.length()-1;++i){ ......
  • 多校A层冲刺NOIP2024模拟赛04
    多校A层冲刺NOIP2024模拟赛04学校OJ赛时rank28,T10pts,T2100pts,T320pts,T425ptsaccodersrank15,T1100pts,T2100pts,T320pts,T425pts不是,也没人告诉我两个OJ文件名不一样啊02表示法递归+高精除低精。点此查看代码#include<bits/stdc++.h>#include<bits/extc++.h>//......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛04
    Rank赤石场。A.02表示法签。若干天前在洛谷随到过,不过当时只看了眼讨论区就走了www还好本来不是很难。发现大体上是一个拆分二的幂的问题,从大到小枚举2的幂,判断有没有这个幂只用比较大小关系,然后再对指数做一个同样的操作,递归至不大于2为止,注意\(2^1\)不用输出(1......
  • 多校A层冲刺NOIP2024模拟赛04
    多校A层冲刺NOIP2024模拟赛04\(T1\)A.02表示法\(0pts/100pts\)弱化版:luoguP1010[NOIP1998普及组]幂次方递归模拟即可,二进制分解时需要写高精除低精。点击查看代码intr[810],t[810];chars[810],id[810][10];stringa;intchu(chars[]){ intn=strlen(s......
  • (概述)TMS320C203PZ、TMS320C203PZA、TMS320C203PZ80、TMS320C203PZ57、TMS320C203PZA57
    TMS320C2x是TMS230C2系列数字信号处理器(DSP)的新一代产品,它采用静态CMOS集成电路制造技术,其结构设计以TMS320C2x系列为基础,并按低功耗进行优化。先进的哈佛结构、片内外围模块、片内存储器和高度专业化指令系统的结合是&#39;C2xx器件工作灵活性和高速度的基础。TMS320C203为100脚PZ......
  • 03. defer和switch
    1.switchswitch语句是编写一连串if-else语句的简便方法。它运行第一个case值,值等于条件表达式的子句。Go的switch语句类似于C、C++、Java、JavaScript和PHP中的,不过Go只会运行选定的case,而非之后所有的case。在效果上,Go的做法相当于这些语言中为每个case......
  • why do we need 'select…for share' instead of a simple 'select'
    (Fromchatgpt)AsimpleSELECTqueryinPostgreSQLoperatesundertheMVCC(Multi-VersionConcurrencyControl)model,whichallowsittoreaddatawithoutlockingtherows.Thismeansitcanseeasnapshotofthedataatthestartofthetransaction,rega......
  • 学习011-08-03 Numeric Properties(数字属性)
    NumericProperties(数字属性)XAFsupportsPropertyEditorsfornumericdatatypes(byte,int,decimal,long,correspondingnullabletypes,etc.)onallplatforms.However,WinForms,ASP.NETWebForms,andBlazorUIapplicationsusedifferentformattingru......
  • 学习011-08-03-01 Numeric Properties in XPO(XPO中的数字属性)
    NumericPropertiesinXPO(XPO中的数字属性)TheexamplebelowillustrateshowtoimplementNumericPropertiesinanXPOpersistentclass.下面的示例说明了如何在XPO持久类中实现数字属性。C#privatedoubledoubleProperty;publicdoubleDoubleProperty{g......
  • 学习011-08-03-02 Numeric Properties in EF Core(EF Core中的数字属性)
    NumericPropertiesinEFCore(EFCore中的数字属性)TheexamplebelowillustrateshowtoimplementNumericPropertiesinanEFCoreclass.下面的示例说明了如何在EFCore类中实现数字属性。C#publicvirtualdoubleDoubleProperty{get;set;}publicvirtual......