首页 > 其他分享 >CSP模拟3

CSP模拟3

时间：2024-09-26 18:12:37浏览次数：8  
标签：ch return int st while ans CSP 模拟

T1 奇观

挺有趣的思路，每个字母相互独立， \(C\) 和 \(F\) ，我们可以把 \(C\) 分成一个两个端点和一个三个端点的路径（以同一个起点开始）,而 \(F\) 为了方便统计，我们也可以把它分成两个两个端点和一个三个端点的路径（同样是以同一个端点为起点）。那我们定义 $s_{i} = \sum_{j} [(i,j)双向联通] $ ，\(d_{i}= \sum_{j,k}[(i,j,k)双向联通]=\sum_{j}s_{j}[i,j双向联通]\)

那 \(C=\sum_{i}s_{i}*d_{i}\) , \(F=\sum_{i}s_{i}^{2}*d_{i}\) 。

正着遍历肯定会 \(T\) ，比较好知道如果不删点的话，答案为 \(n^{3}*(n-1)^{10}\) ,那我们可以试着看看删掉一个点会对答案造成什么影响，我们先把每个点 \(s_{i}\) 赋成 \((n-1)\) , \(d_{i}\) 赋成 \((n-1)^{2}\),那考虑删点就两种情况，一种是删的点的影响，一种是删掉这个点对其他点的影响，先看后一种，很明显被删的点的 \(s_{i}\) 应减去 \(1\) ,那每个点的 \(d_{i}\) 应该减去 \(2\) （删两个点）,那总共每个节点应减去 \((n*2)\) 个点，那只考虑这种肯定有所欠缺，我们既没有考虑这样对删掉点本身不再给另一个点施加影响，而且没考虑删掉点本身的 \(d_{i}\) 不应计算。

现在再考虑第一种情况，对于删掉的点的\(s_{i}\)减去 \(1\) ，\(d_{i}\) 则要减去 \((n-1)\) ，我们设被删的两个点为\(x,y\)，目前就两个问题，一个是已经被删的点再发生变化时，不会再对另一个点造成贡献（ \(x,y\) 已经被删, \(y\) 和另一个点再被删）。一个是减去点本身 \(d_{i}\) 也不应该被自身影响而减去值。知道了删点所造成的影响之后就比较好处理了，直接看代码吧。

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

#define int long long
const int N=3e5+107;
const int mod=998244353;
int n,m;

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

int s[N],d[N];
int a[N],b[N];
int vis[N];

signed main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) s[i]=n-1,d[i]=s[i]*s[i]%mod;
	for(int i=1;i<=m;i++)
	{
		a[i]=read(),b[i]=read();
		vis[a[i]]++,vis[b[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		d[a[i]]=(d[a[i]]-(n-1)+vis[b[i]]+mod)%mod;
		d[b[i]]=(d[b[i]]-(n-1)+vis[a[i]]+mod)%mod;
		s[a[i]]--,s[b[i]]--;
	}
	for(int i=1;i<=n;i++)
	{
		d[i]=(d[i]-m*2+(n-1)-s[i]+mod)%mod;
	}
	int ans1=0,ans2=0,ans=1;
	for(int i=1;i<=n;i++)
	{
		(ans1+=d[i]*s[i]%mod)%=mod;
		(ans2+=d[i]*s[i]%mod*s[i])%=mod;
	}
	ans=ans1*ans1%mod*ans2%mod;
	printf("%lld",ans);
}

T2铁路

比较明显可以用并查集来维护点的合并，一个问题就是搜一个点到新开的点时不太好处理，我们可以做一个新开点到原图的映射（好吧，其实也挺好处理的），那这题就没啥了。

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

const int N=5e5+107;
int n,m,ans;
int d[N<<1];

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

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

int f[N][23],dep[N];
bool vis[N];
void dfs(int u,int fat)
{
	dep[u]=dep[fat]+1;
	f[u][0]=fat;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fat) continue;
		if(!vis[v])
		{
			vis[v]=1;
			dfs(v,u);
		}
	}
}

int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y])
		{
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

int fa[N<<1];
int find(int x)
{
	return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}

void merge(int x,int y,int i)
{
	
	if(x>n) x=d[x];
	if(y>n) y=d[y];
	int z=find(lca(x,y));
	d[n+i]=z;
	while(x!=z) 
	{
		fa[x]=z;
		x=find(f[x][0]);
		ans--;
	}
	while(y!=z) 
	{
		fa[y]=z;
		y=find(f[y][0]);
		ans--;
	}
}

int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) fa[i]=i, d[i]=i;
	for(int i=1;i<=n-1;i++)
	{
		int x=read(),y=read();
		add(x,y); add(y,x);
	}
	dfs(1,1);
	for(int j=1;j<=20;j++)
	{
		for(int i=1;i<=n;i++)
		{
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	ans=n;
	for(int i=1;i<=m;i++)
	{
		int a=read(),b=read();
		merge(a,b,i);
		printf("%d\n",ans);
	}
}

T3光纤

计算几何

我们维护一个凸包，然后直接做旋转卡壳，额，剩下没啥了，都是板子。好吧，还是稍微说点，主要是了解一下向量的叉乘（向量积 \(cross\) ）和极角排序，向量积它的数值的几何意义比较重要，在二维空间里，它表示是两条边所构成平行四边形的面积，在三维空间里，它表示垂直于两条直线所在平面的法向量。而极角排序可以使用叉积来排序，也可以使用 \(C++\) 自带的 \(atan2\) 排序，它返回的是点 \((x,y)\) 与原点 \((0,0)\) 连线和 \(x\) 轴正方向的夹角弧度（ \(atan2()\) 相对于叉积排序精度低，但也够用了，而且它比较快，还方便）。

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

#define int long long

const int N=2e6+107;
int n,m;

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

void write(__int128 x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

struct Ans
{
	__int128 z,m;
	double val;
	bool operator >=(const Ans &a)const{return val>=a.val;}
	Ans min(Ans a,Ans b){return a.val<b.val?a:b;}
}ans;

struct lmy
{
	int x,y;
	double k;
	bool operator ==(const lmy &a)const{return (a.x==x)&&(a.y==y);}
}st[N],vec[N];
int tp;
bool comp1(lmy a,lmy b)
{
	if(a.y==b.y) return a.x<b.x;
	else return a.y<b.y;
}

int cross(lmy a,lmy b,lmy c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

//double dis(lmy a,lmy b)
//{
//	return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
//}

Ans dis(lmy a,lmy b,lmy c)
{
	__int128 yz=b.y-c.y,xz=b.x-c.x,n=a.x-b.x,m=b.y-a.y;
	Ans w={yz*yz*n*n+xz*xz*m*m+2*xz*yz*n*m,xz*xz+yz*yz,1.0*(yz*yz*n*n+xz*xz*m*m+2*xz*yz*n*m)/(xz*xz+yz*yz)};
	return w;
}

bool comp(lmy a,lmy b)
{
	if(a.k!=b.k) return a.k<b.k;
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int xx,yy;
signed main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n=read();
	if(n<=2)
	{
		printf("0/1");
		return 0;
	}
	for(int i=1;i<=n;i++) vec[i]={read(),read()};
	sort(vec+1,vec+n+1,comp1);
	
	n=unique(vec+1,vec+1+n)-(vec+1);
	st[++tp]=vec[1];
	xx=st[tp].x,yy=st[tp].y;
	for(int i=2;i<=n;i++) vec[i].k=atan2(vec[i].y-yy,vec[i].x-xx);
	sort(vec+2,vec+1+n,comp);
	st[++tp]=vec[2];
	for(int i=2;i<=n;i++)
	{
		while(tp>1&&cross(st[tp-1],st[tp],vec[i])<0) tp--;
		st[++tp]=vec[i];
	}
	st[++tp]=st[1];
	
	int l=1,r=1;
	for(l=1;l<tp;l++)
	{
		int last=r;
		while(dis(st[r%tp+1],st[l+1],st[l])>=dis(st[r],st[l+1],st[l]))
		{
			r=r%tp+1;
			if(r==last) return printf("0/1"),0;
		}
		ans=ans.min(ans,dis(st[r],st[l],st[l+1]));
	}
	ans.m*=4;
	__int128 gcd=__gcd(ans.m,ans.z);
	
	write(ans.z/gcd);
	printf("/");
	write(ans.m/gcd);
	return 0;

}

T4权值

超级线段树，不会，咕咕咕……

标签：ch,return,int,st,while,ans,CSP,模拟
From： https://www.cnblogs.com/zhengchenxi/p/18429075

相关文章

  • 信息学奥赛复赛复习04-CSP-J2019-04-加工零件-位运算、整数映射0或1、结构体、初始化
    PDF文档公众号回复关键字:2024092612019CSP-J题目4加工零件[题目描述]凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有n位工人，工人们从1∼n编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带......
  • 冲刺CSP联训模拟1
    A.几何设\(f_{i,j,k}\)表示前\(i\)个字符，分为两部分，分别为\(x\)的几倍加\(x\)的前\(j\)位，\(y\)的几倍加\(y\)的前\(k\)位,是否合法分别判断下一位\(i+1\)能否与\(x\)的下一位\(j+1\)和\(y\)的下一位\(k+1\)匹配，匹配上了就转移.最终答案就是\(f_{|s|......
  • 某模拟赛题
    题意有\(n\)个实数，第\(i\)个实数在\([0,2^{a_i}]\)中均匀分布。求任意一个数均小于\(n\)个数和的一半的概率。\(n\le5\cdot10^4,a_i\le50\)。解法题目即求\(\sum\limits_{i=1}^{n}P(x_i>\sum\limits_{j\neqi}x_j)\)，由于\(x_i\)和\(2^{a_i}-......
  • kafka生产者、消费者-命令行模式模拟
    win环境下，如果是linux，切换目录，用sh脚本就行kafka安装在上一篇https://www.cnblogs.com/qcy-blog/p/18428599Kraft启动kafkakafka-server-start.bat..\..\config\kraft\server.properties生产者，启动之后，命令行输入要生产的消息kafka-console-producer.bat--topictest-top......
  • CCF CSP-S 2024 提高组初赛解析
    CertifiedSoftwareProfessional-Senior非专业级软件能力认证测试本解析不提供阅读程序与完善程序题目的代码，如有需要请通过luogu.com.cn相关链接下载如有谬误烦请指正答案AACBBBDABDACBCD✓××BC✓✓✓BCC✓×✓CACAAAAAAABAA单项选择1在Linux系统中，如......
  • TS5A3166DBVR模拟开关IC芯片原装现货PDF数据手册引脚图功能框图
    TS5A3166的说明TS5A3166器件是一款单刀单掷(SPST)模拟开关，工作电压范围为1.65V至5.5V。此器件具有较低的导通状态电阻。该器件具有出色的总谐波失真(THD)性能和极低的功耗。这些特性使得这款器件适合于便携式音频应用中对于高效率、高电源密度和稳健性的需求。TS......
  • [34]（CSP 集训）CSP-S 联训模拟 1
    A几何重复若干次->不能重叠，因此考虑直接暴力DP设\(f_{i,j,k}\)表示主串匹配到第\(i\)位（将前\(i\)位分别归为两类），其中\(x\)在重复了若干次后，又匹配到了第\(j\)位，\(y\)在重复了若干次后，又匹配到了第\(k\)位转移非常好写，枚举\(i\)，尝试把\(s_{i}\)分别与\(x_......
  • 『模拟赛』冲刺CSP联训模拟1
    Rank我的我要爆了A.几何上来思路就假了，不知道，样例全过，本来就算假也能拿点，结果绑包了，妈的。正解dp，设\(f_{i,j,k}\)表示串\(s\)匹配到\(i\)位，模式串\(x\)拼接至\(j\)位，\(y\)拼接至\(k\)位是否可行，滚动数组优化，复杂度\(\mathcal{O(|s||x||y|)}\)，不太能过，位运......
  • [33]（CSP 集训）CSP-S 模拟 4
    A商品对于任意一组相邻的数\((l,r)\(l\ler)\)，可以发现，不管怎么压缩，都会有\(l\ler\)，也就是说，相邻两个数的大小关系是不变的那么我们就可以把\(\sum(|\max-\min|)\)拆出来，变成\[\sum(\max-\min)=\sum(\max)-\sum(\min)\]所以我们可以每对数里的\(\max\)和\(\min\)都......
  • CSP-J/S 2024游记
    24.9.21距离CSP-J/S2024第一轮还有0天。距离停课集训还有1天。集训日子加载中……24.9.22距离CSP-J/S2024第二轮还有33天。初赛成绩已出J:86S:68.5。今日份模拟赛初中联考期望：90+30+0+0=120，实际：90+30+0+0=120，大众分:100+40+40+......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99