首页 > 其他分享 >9.23 csp

9.23 csp

时间：2024-09-23 21:02:43浏览次数：1  
标签：9.23 int flen len ans fbisum csp man

今天模拟赛出了四道zroi的题，挺GG的。

T1、奇观

因为删除的边比较少，所以从m入手，f[i][j]表示长度为i，终点为j的链的方案数。

C 是长度为3的链，F是 1条 长度为3 的链 和 2条 长度为2 的链。

输出 CCF 即可

G

T2、铁路

救命的签到题。

因为每次合并时每走一个点就会减少一个点，所以我们直接跳就行。

不需要建新的点，而是用dep值最小的点代替新点所包含的所有点。或者说，每次合并 x 到 y 上的点，就把他们都合并到 lca(x,y)上去。合并只需要用并查集合并即可。

G

T3、光纤

真正能学知识的题。

直接学了一个‘旋转卡壳’。

本题题意是找一条直线使得所有点到他的距离最小，可以把点都整成一个凸包（可以合并两个凸壳），然后旋转卡壳去找最小的最大值。

也就是枚举凸壳上的每条边和一个对应的点让这个点到这条边的距离最大。（双指针）

求一个点到一条直线的距离：

知道 点A 和 线段BC，用向量叉积求出三角形面积，然后用面积除以长就是高。

zher 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define ps emplace_back
#define mk make_pair
typedef unsigned long long ull;
const int N=1e6+10;
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:f=1),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
__int128 n,q[N],top,q1[N],top1;
struct jj{
	__int128 x,y;
}di[N],zan[N];
#define K(i,j) ((double)(di[j].y-di[i].y)/(di[j].x-di[i].x))
#define ne(x) (x==top?1:x+1)
#define X(i,j) (di[j].x-di[i].x)
#define Y(i,j) (di[j].y-di[i].y)
#define cha(x,y,z) (X(x,y)*Y(x,z)-Y(x,y)*X(x,z))
#define len(x,y) (X(x,y)*X(x,y)+Y(x,y)*Y(x,y))
#define abs(x) (x>=0?x:-x)
pair<__int128,__int128> ans;
char anss[N];
inline void print(__int128 x){
	if(!x)putchar('0');
	else{
		if(x<0)x=-x,putchar('-');
		int cnt=0;
		while(x)anss[++cnt]=x%10+'0',x/=10;
		for(int i=cnt;i;--i)
			putchar(anss[i]);
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	if(n<=2)return cout<<"0/1",0;
	for(int i=1;i<=n;++i)
		di[i].x=read(),di[i].y=read();
	sort(di+1,di+1+n,[](const jj&x,const jj&y){return x.x==y.x?x.y<y.y:x.x<y.x;});
	n=unique(di+1,di+1+n,[](const jj&x,const jj&y){return x.x==y.x&&x.y==y.y;})-di-1;
	for(int i=1;i<=n;++i){
		while(top>1&&(K(q[top],i)<=K(q[top-1],q[top]))){
			--top;
		}
		q[++top]=i;
	}
	for(int i=n;i;--i){
		while(top1>1&&K(i,q1[top1])<=K(q1[top1],q1[top1-1]))--top1;
		q1[++top1]=i;
	}
	for(int i=2;i<top1;++i){
		q[++top]=q1[i];
	}
	for(int i=1;i<=top;++i)
		zan[i]=di[q[i]];
	for(int i=1;i<=top;++i)
		di[i]=zan[i];
	for(int i=1,j=3;i<=top;++i){
		while((j==ne(i))||((abs(cha(j,i,ne(i))))<=(abs(cha(ne(j),i,ne(i)))))){
			j=ne(j);
		}
		if(!ans.se||(double)ans.fi/ans.se>(double)cha(j,i,ne(i))*cha(j,i,ne(i))/len(i,ne(i)))ans.fi=cha(j,i,ne(i))*cha(j,i,ne(i)),ans.se=len(i,ne(i));
	}
	__int128 gcd=__gcd(ans.fi,ans.se*4);
	print(ans.fi/gcd);putchar('/');print(ans.se*4/gcd);
}

T4、权值

完全不会写。。。

考场上把题看假了，抱着试一试的心态打了颗线段树，他可以处理不包含操作 4 的极长正数连续段的 乘积、长度，一共打和调了两个半小时，最后调出来了，然后发现读题读假了，那就先把他种在这吧。

tree 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define ps emplace_back
#define mk make_pair
const int N=1e6+10;
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))(c=='-'?f=-1:f=1),c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
uint sum[N],fsum[N],man[N],bisum[N][2],fbisum[N][2],tag[N];//man qujiansuoyoushudejueduizhide chengji
int len[N][2],flen[N][2],fuhao[N];
bool fan[N];
inline uint qp(uint x,int y){
	uint ans=1;
	while(y){
		if(y&1)ans*=x;
		x*=x;y>>=1;
	}
	return ans;
}
inline void qing(int k){

	sum[k]=fsum[k]=bisum[k][0]=bisum[k][1]=fbisum[k][0]=fbisum[k][1]=len[k][0]=len[k][1]=flen[k][0]=flen[k][1]=0;
}
inline void up(int k,int l,int r){
	int mid=l+r>>1;
	man[k]=man[k<<1]*man[k<<1|1];
	if(len[k<<1][1]&&len[k<<1|1][0])sum[k]=sum[k<<1]+sum[k<<1|1]-bisum[k<<1][1]*len[k<<1][1]-bisum[k<<1|1][0]*len[k<<1|1][0]+(bisum[k<<1][1]*bisum[k<<1|1][0])*(len[k<<1][1]+len[k<<1|1][0]);
	else sum[k]=sum[k<<1]+sum[k<<1|1];
	if(flen[k<<1][1]&&flen[k<<1|1][0])fsum[k]=fsum[k<<1]+fsum[k<<1|1]-fbisum[k<<1][1]*flen[k<<1][1]-fbisum[k<<1|1][0]*flen[k<<1|1][0]+(fbisum[k<<1][1]*fbisum[k<<1|1][0])*(flen[k<<1][1]+flen[k<<1|1][0]);
	else fsum[k]=fsum[k<<1]+fsum[k<<1|1];
	if(len[k<<1][0]==mid-l+1&&len[k<<1|1][0])len[k][0]=len[k<<1][1]+len[k<<1|1][0],bisum[k][0]=bisum[k<<1][0]*bisum[k<<1|1][0];
	else len[k][0]=len[k<<1][0],bisum[k][0]=bisum[k<<1][0];
	if(len[k<<1|1][1]==r-mid&&len[k<<1][1])len[k][1]=len[k<<1|1][1]+len[k<<1][1],bisum[k][1]=bisum[k<<1][1]*bisum[k<<1|1][1];
	else len[k][1]=len[k<<1|1][1],bisum[k][1]=bisum[k<<1|1][1];
	if(flen[k<<1][0]==mid-l+1&&flen[k<<1|1][0])flen[k][0]=flen[k<<1][1]+flen[k<<1|1][0],fbisum[k][0]=fbisum[k<<1][0]*fbisum[k<<1|1][0];
	else flen[k][0]=flen[k<<1][0],fbisum[k][0]=fbisum[k<<1][0];
	if(flen[k<<1|1][1]==r-mid&&flen[k<<1][1])flen[k][1]=flen[k<<1|1][1]+flen[k<<1][1],fbisum[k][1]=fbisum[k<<1][1]*fbisum[k<<1|1][1];
	else flen[k][1]=flen[k<<1|1][1],fbisum[k][1]=fbisum[k<<1|1][1];
}
inline void down(int k,int l,int r){
	int mid=l+r>>1;
	// if(k==12)cout<<tag[k]<<' '<<fan[k]<<' '<<fuhao[k]<<"NIU"<<endl;
	if(tag[k]){
		// len[k<<1][0]=len[k<<1][1]=mid-l+1,len[k<<1|1][0]=len[k<<1|1][1]=r-mid;
		tag[k<<1]=tag[k<<1|1]=tag[k];man[k<<1]=qp(tag[k],(mid-l+1)),man[k<<1|1]=qp(tag[k],(r-mid));
		tag[k]=0;
	}
	if(fan[k]){
		swap(sum[k<<1],fsum[k<<1]);swap(len[k<<1],flen[k<<1]),swap(bisum[k<<1],fbisum[k<<1]),fan[k<<1]^=1;fuhao[k<<1]*=-1;
		swap(sum[k<<1|1],fsum[k<<1|1]);swap(len[k<<1|1],flen[k<<1|1]),swap(bisum[k<<1|1],fbisum[k<<1|1]),fan[k<<1|1]^=1;fuhao[k<<1|1]*=-1;
		fan[k]=0;
	}
	if(fuhao[k]){
		qing(k<<1),qing(k<<1|1);
		fuhao[k<<1]=fuhao[k<<1|1]=fuhao[k];
		if(fuhao[k]==1){
			sum[k<<1]=man[k<<1]*(mid-l+1);len[k<<1][0]=len[k<<1][1]=mid-l+1;bisum[k<<1][0]=bisum[k<<1][1]=man[k<<1];
			sum[k<<1|1]=man[k<<1|1]*(r-mid),len[k<<1|1][0]=len[k<<1|1][1]=r-mid,bisum[k<<1|1][0]=bisum[k<<1|1][1]=man[k<<1|1];
		}
		else{
			fsum[k<<1]=man[k<<1]*(mid-l+1);flen[k<<1][0]=flen[k<<1][1]=mid-l+1;fbisum[k<<1][0]=fbisum[k<<1][1]=man[k<<1];
			fsum[k<<1|1]=man[k<<1|1]*(r-mid),flen[k<<1|1][0]=flen[k<<1|1][1]=r-mid,fbisum[k<<1|1][0]=fbisum[k<<1|1][1]=man[k<<1|1];	
		}
		fuhao[k]=0;
	}
	// if(k==12)cout<<man[25]<<' '<<sum[25]<<"MO"<<endl;
}
inline void add1(int k,int l,int r,int L,int R,int v){
	if(L<=l&&r<=R){
		qing(k);man[k]=qp(v,r-l+1);
		if(v>0){
			fuhao[k]=1;
			len[k][0]=len[k][1]=r-l+1;bisum[k][0]=bisum[k][1]=man[k],sum[k]=man[k]*(r-l+1),tag[k]=v,fan[k]=0;
		}
		else{
			fuhao[k]=-1;v=-v;
			flen[k][0]=flen[k][1]=r-l+1;fbisum[k][0]=fbisum[k][1]=man[k],fsum[k]=man[k]*(r-l+1),tag[k]=v,fan[k]=0;
		}
		return;
	}
	down(k,l,r);
	int mid=l+r>>1;
	if(L<=mid)add1(k<<1,l,mid,L,R,v);
	if(R>mid)add1(k<<1|1,mid+1,r,L,R,v);
	up(k,l,r);
}
inline void add2(int k,int l,int r,int L,int R,int v){
	if(L<=l&&r<=R){
		qing(k);
		if(v>0){
			fuhao[k]=1;
			len[k][0]=len[k][1]=r-l+1;bisum[k][0]=bisum[k][1]=man[k],sum[k]=man[k]*len[k][0],fan[k]=0;
		}
		else{
			fuhao[k]=-1;
			flen[k][0]=flen[k][1]=r-l+1;fbisum[k][0]=fbisum[k][1]=man[k],fsum[k]=man[k]*len[k][0],fan[k]=0;
		}
		return ;
	}
	down(k,l,r);
	int mid=l+r>>1;
	if(L<=mid)add2(k<<1,l,mid,L,R,v);
	if(R>mid)add2(k<<1|1,mid+1,r,L,R,v);
	up(k,l,r);
}
inline void add3(int k,int l,int r,int L,int R){
	 if(L<=l&&r<=R){
	 	fan[k]^=1;fuhao[k]*=-1;
	 	swap(sum[k],fsum[k]),swap(len[k],flen[k]),swap(bisum[k],fbisum[k]);
	 	return;
	 }
	 down(k,l,r);
	 int mid=l+r>>1;
	 if(L<=mid)add3(k<<1,l,mid,L,R);
	 if(R>mid)add3(k<<1|1,mid+1,r,L,R);
	 up(k,l,r);
}
struct jj{
	uint sum,bisum[2];
	int len[2];
};
inline jj ask(int k,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return jj{sum[k],bisum[k][0],bisum[k][1],len[k][0],len[k][1]};
	}
	down(k,l,r);
	int mid=l+r>>1;

	if(L<=mid&&R>mid){
		auto i=ask(k<<1,l,mid,L,R),j=ask(k<<1|1,mid+1,r,L,R);
		if(i.len[1]&&j.len[0])i.sum=i.sum+j.sum-i.bisum[1]*i.len[1]-j.bisum[0]*j.len[0]+(i.bisum[1]*j.bisum[0])*(i.len[1]+j.len[0]);
		else i.sum=i.sum+j.sum;
		if((i.len[0]==mid-max(l,L)+1)&&j.len[0])i.len[0]=i.len[0]+j.len[0],i.bisum[0]=i.bisum[0]*j.bisum[0];
		if((j.len[1]==min(r,R)-mid)&&i.len[1])i.len[1]=i.len[1]+j.len[1],i.bisum[1]=i.bisum[1]*j.bisum[1];
		else i.len[1]=j.len[1],i.bisum[1]=j.bisum[1];
		return i;
	}
	if(L<=mid)return ask(k<<1,l,mid,L,R);
	return ask(k<<1|1,mid+1,r,L,R);
}
int n,m,a[N];
inline void jian(int k,int l,int r){
	if(l==r){
		if(a[l]>0){
			bisum[k][0]=bisum[k][1]=sum[k]=man[k]=a[l],len[k][0]=len[k][1]=1;
		}
		else{
			fbisum[k][0]=fbisum[k][1]=fsum[k]=man[k]=-a[l],flen[k][0]=flen[k][1]=1;
		}
		// cout<<l<<' '<<k<<' '<<sum[k]<<' '<<fsum[k]<<endl;
		return ;
	}
	int mid=l+r>>1;
	jian(k<<1,l,mid),jian(k<<1|1,mid+1,r);
	up(k,l,r);
}
int main(){
	// #ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	// #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	if(m<=1000){
		for(int i=1,op,l,r,x;i<=m;++i){
			op=read(),l=read(),r=read();
			if(op==5){
				uint anss=0;
				for(int j=l;j<r;){
					while(j<=r&&a[j]<=0)++j;
					uint ans=1,cnt=0;
					while(j<=r&&a[j]>0)
						ans*=a[j],++cnt,++j;
					anss+=ans*cnt;
				}
				cout<<anss<<'\n';
			}
			else{
				x=read();
				if(op==1){
					for(int j=l;j<=r;++j)
						a[j]=x;
				}
				else if(op==2){
					for(int j=l;j<=r;++j)
						a[j]=abs(a[j])*x;
				}
				else if(op==3){
					for(int j=l;j<=r;++j)
						a[j]*=x;
				}
				else {
					for(int j=l;j<=r;++j){
						a[j]>0?a[j]=1:a[j]=-1;
						a[j]*=x;
					}
				}
			}
		}

		return 0;
	}
	// cout<<1<<endl;
	jian(1,1,n);
	for(int i=1,op,l,r,x;i<=m;++i){
		op=read(),l=read(),r=read();
		if(op==5)cout<<ask(1,1,n,l,r).sum<<'\n';
		else if(op==1)add1(1,1,n,l,r,read());
		else if(op==2)add2(1,1,n,l,r,read());
		else{
			x=read();
			if(x==-1)add3(1,1,n,l,r);
		}
		// cout<<endl;
	}

}

[========]

[========]

image

今天打的其实不尽人意，只要是T1没签上，一开始看到这题的时候就没想到他是签到题，以为不太可做，结果也就想都没想直接裸了个最简单的暴力，然后就去看T2了，但其实打个好一点的暴力就能拿80分，我只拿了30分，要不然能上第7。然后后面因为读假题导致我觉得T4可做，直接把赌注全压在了T4上，很大程度上也影响我没有再去改T1，但是能赛时打出7k的代码，这场考试也是有鼓励作用的。

那就继续走吧。

标签：9.23,int,flen,len,ans,fbisum,csp,man
From： https://www.cnblogs.com/GGrun-sum/p/18427806

相关文章

  • 9.23 D 暂存
    鉴于5k和int_R等大神都认为这道题80pts档是一个普通的线段树，作为一个线段树狂热爱好者果断尝试，但在打出30行的pushup后蚌埠住了，但还是想切掉，所以暂存一下，什么时候打出来什么时候删置顶。目前进度：pushup，建树你们要是能发现问题记得说啊，#include<bits/stdc++.h>#defi......
  • [赛记] csp-s模拟3
    奇观55pts赛时打的$\Theta(n^5)$和$m=0$的特殊性质拿了55pts；考虑正解，首先，$CCF$这三个字母是可以分开维护的；对于$C$，其可以看作一个连了四个点的线段，对于$F$，其可以看作一个连了三个点的线段在再最后分别多连两个点；设$f_{i,j}$表示维护一个连了$i$......
  • CSP 集训记录
    用来整理模拟赛等9.23csp-3【noip23ZR二十连测DAY10】保龄.A.奇观狗市题目描述。不是这题意太大歧义了吧，我讨厌的第二种出题人——题意描述相当不清。CTH：13座城市又不代表是13座不同的城市。直接看形式化题目的话（如果能看懂要干什么）那这题确实不难。解：容易发......
  • 信息学奥赛复赛复习01-CSP-J2019-01-字符、字符数组、字符串、string、字符串读取
    信息学奥赛复赛复习01-CSP-J2019-01-字符、字符数组、字符串、string、字符串读取PDF文档公众号回复关键字:2024092312019CSP-J题目1数字游戏[题目描述]小K同学向小P同学发送了一个长度为8的01字符串来玩数字游戏，小P同学想要知道字符串中究竟有多少个1。注......
  • 云原生周刊：Artifact Hub 成为 CNCF 孵化项目｜2024.9.23
    开源项目推荐CorootCoroot是一个开源监控工具，旨在为云原生应用提供可观察性。它通过整合指标、日志和追踪信息，专注于提供应用性能的洞察。DirectPVDirectPV是一个开源项目，旨在为Kubernetes工作负载提供高效的直接卷访问。它通过允许应用绕过容器运行时，直接访问持久卷，从而......
  • 『模拟赛』CSP-S模拟3
    因为正式集训所以不叫加赛了。RankUpd：非常好数据，掉分掉Rank。还行，其实是Rank6，其实其实是Rank4（丁真说正式比赛不会改数据。A.奇观简单题（？）。赛时琢磨了一会想到了\(Ans=C\cdotC\cdotF\)，打出了\(m=0\)性质和\(O(n^2)\)dp的暴力一共80pts。赛后发现在我做法的......
  • CSP 初赛游寄
    前言时间是什么，一个定义还是具体的量，是否存在，令人捉摸不透，但不变的终有一点，一切都在变化啊，毕竟运动是绝对的\(CSP-J/S\),去年九月对于这个名词的理解，我还是一知半解。刚踏上信息竞赛的道路，不知道这意味着什么，转眼间，又一个九月，再次踏入一中的校门，看见新七年级与我们之前同样的期......
  • 9.23 海报＋PDF水印运用
    任务2：海报以宣传校植物研学社为主题，吸引天华小学学生积极报名加入校植物研学社，与学校聘请特邀的植物学专家、生物老师、同学共度一场植物奇遇记，在植物的世界中展开探索与冒险。在每周一次的研学社活动中，教师会提供各种各样的植物标本与实物，学生可以在专家、教师的帮助、引导下了......
  • 9.23人工
    可画海报主题：植物研学社任务2:通过本节课的学习，我们使用可画制作了一个应用于教育课堂的海报。我们选择了植物研学社的招新作为主题，在该海报中，我们加入了各种植物类型的图片，并且通过文本框对植物研学社进行了一定的介绍，包括标语、名称、logo、水印等。另外，还通过“草料二维码”......
  • csp
    #include<iostream>usingnamespacestd;boolisPrime(intn){if(n<=1){returnfalse;}for(inti=2;i*i<=n;i++){if(n%i==0){returnfalse;}}returntrue;......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99