首页 > 其他分享 >CSP2024总结(学术版)

CSP2024总结(学术版)

时间:2024-11-11 21:57:08浏览次数:1  
标签:总结 kkk int mid CSP2024 else ss vv 学术

J组T4

一道/赛上觉得很难/下来也听说很难/但听老师一讲也觉得只有中位绿/的题。

题目传送门


首先想到 \(r=1\) 时的做法,不难看出可以使用一个标记数组来存储,然后依次寻找离他最近的 \(1\) 看是否满足要求,标记即可。\(5\) pts拿到手。

然后发现可以扩展出一种类似递推的思想,设\(f_{i,j}\) 表示在第i轮时能否以j结尾,0为可以,1就不行。那么显而易见的类比上面的过程,只用找到距离当前数最近的有值的f就可以了。

如果仅仅到这里可能只有中位黄,但是题目告诉我们:一个人不能自己接自己的龙。 这里就有一个不太容易想到的思维转换,也就是你可以先去掉上一轮的值,后面在加回来这样就不会产生错误了。期望得分60~85pts看你怎么写。

进行细节上的优化+快读即可过掉本题。

#include<bits/stdc++.h>
using namespace std;
const int N=200005,R=105;
int t,n,k,q,r[N],c[N],now,arr,maxx,maxr,tt,i,j,qq,rr,len[N],mark[R][N];
vector<int> v[N],del[N],the[N];
int in(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
signed main(){
	t=in();
	for(tt=1;tt<=t;tt++){
		maxx=0;
		n=in(),k=in(),q=in();
		for(i=1;i<=n;i++){
			len[i]=in();
			v[i].clear();
			del[i].clear();
			the[i].clear();
			for(j=0;j<len[i];j++){
				del[i].push_back(0);
				the[i].push_back(0);
				arr=in();
				maxx=max(maxx,arr);
				v[i].push_back(arr);
			}
		}
		maxr=0;
		for(qq=1;qq<=q;qq++) r[qq]=in(),c[qq]=in(),maxr=max(maxr,r[qq]);
		for(i=0;i<=maxr;i++) for(j=0;j<=maxx;j++) mark[i][j]=0;
		
		mark[0][1]=1;
		for(rr=1;rr<=maxr;rr++){
			for(i=1;i<=n;i++){
				now=-1;
				for(j=0;j<len[i];j++) mark[rr-1][v[i][j]]-=del[i][j];
				for(j=0;j<len[i];j++){
					if(now!=-1&&j-now<k){
						mark[rr][v[i][j]]++;
						the[i][j]++;
					}
					if(mark[rr-1][v[i][j]]>0) now=j;
				}
				for(j=0;j<len[i];j++){
					mark[rr-1][v[i][j]]+=del[i][j];
					del[i][j]=the[i][j];
					the[i][j]=0;
				}
			}
		}
		for(qq=1;qq<=q;qq++){
			if(mark[r[qq]][c[qq]]){
				putchar('1');
				putchar('\n');
			}
			else{
				putchar('0');
				putchar('\n');
			}
		}
	}
	return 0;
}

S组T2

题目传送门

没有什么好说的,先想到二分,然后模拟。

注意写代码的时候添加一些注释,变量名规范,尽量多写函数,这样容易调试。后面就是经典dry摄像头模型了。

#include<bits/stdc++.h>

using namespace std;
int t,n,m,l,v,cnt,it,ss,len,be,en,mid,kkk,ans,now,jilu,p[200010];
double vv;
bool flag;
struct node{
	int d;
	int v;
	int a;	
}c[200010];
struct line{
	int ll;
	int rr;
}arr[200010];
int work1(){
	cnt=0;
	for(int i=1;i<=n;i++){
		if(c[i].a==0){
			if(c[i].v>v&&c[i].d<=p[m]) cnt++;
		} 
		else if(c[i].a>0){
			ss=p[m]-c[i].d;
			if(ss<0) continue;
			if(c[i].v*c[i].v+2*c[i].a*ss>=0)vv=sqrt(c[i].v*c[i].v+2*c[i].a*ss);
			else vv=0.000;
			if(vv>v) cnt++;
		}
		else{
			if(c[i].d<=p[m]){
				it=lower_bound(p+1,p+1+m,c[i].d)-p;
				ss=p[it]-c[i].d;
				if(c[i].v*c[i].v+2*c[i].a*ss>=0)vv=sqrt(c[i].v*c[i].v+2*c[i].a*ss);
				else vv=0.000;
				if(vv>v) cnt++;
			}
		}
	}
	return cnt;
}
bool cmp(line t1,line t2){
	return t1.rr<t2.rr;
}
int work2(){
	//zero
	len=0;
	for(int i=1;i<=n;i++){
		if(c[i].a==0){
			if(c[i].v>v&&c[i].d<=p[m]){
				arr[++len].ll=lower_bound(p+1,p+1+m,c[i].d)-p;
				arr[len].rr=m;
			}
		} 
		else if(c[i].a>0){
			ss=p[m]-c[i].d;
			if(c[i].v*c[i].v+2*c[i].a*ss>=0)vv=sqrt(c[i].v*c[i].v+2*c[i].a*ss);
			else vv=0.000;
			if(vv>v){
				kkk=lower_bound(p+1,p+1+m,c[i].d)-p;
				be=kkk;
				en=m;
				while(be<=en){
					mid=(be+en)/2;
					ss=p[mid]-c[i].d;
					if(c[i].v*c[i].v+2*c[i].a*ss>=0)vv=sqrt(c[i].v*c[i].v+2*c[i].a*ss);
					else vv=0.000;
					if(vv>v){
						ans=mid;
						en=mid-1;
					}
					else be=mid+1;
				}
				arr[++len].ll=ans;
				arr[len].rr=m;
			}
		}
		else{
			if(c[i].d<=p[m]){
				it=lower_bound(p+1,p+1+m,c[i].d)-p;
				ss=p[it]-c[i].d;
				if(c[i].v*c[i].v+2*c[i].a*ss>=0)vv=sqrt(c[i].v*c[i].v+2*c[i].a*ss);
				else vv=0.000;
				if(vv>v){
					kkk=lower_bound(p+1,p+1+m,c[i].d)-p;
					be=kkk;
					en=m;
					while(be<=en){
						mid=(be+en)/2;
						ss=p[mid]-c[i].d;
						if(c[i].v*c[i].v+2*c[i].a*ss>=0)vv=sqrt(c[i].v*c[i].v+2*c[i].a*ss);
						else vv=0.000;
//						cout<<be<<" "<<en<<"\n";
						if(vv>v){
							ans=mid;
							be=mid+1;
						}
						else en=mid-1;
					}
					arr[++len].ll=kkk;
					arr[len].rr=ans;
				}
			}
		}
	}
	//camera
//	for(int i=1;i<=len;i++){
//		printf("%d %d\n",arr[i].ll,arr[i].rr); 
//	} 
	sort(arr+1,arr+1+len,cmp);
	ans=1,now=arr[1].rr;
	for(int i=2;i<=len;i++){
		if(now<arr[i].ll){
			now=arr[i].rr;
			ans++;
		}	
	}
	return ans;
} 
signed main(){
//	freopen("detect.in","r",stdin);
//	freopen("detect.out","w",stdout);
	scanf("%d",&t);
	for(int tt=1;tt<=t;tt++){
		scanf("%d%d%d%d",&n,&m,&l,&v);
		flag=false;
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&c[i].d,&c[i].v,&c[i].a);
			if(c[i].a!=0) flag=true;
		}
		for(int i=1;i<=m;i++) scanf("%d",&p[i]);
//		work2();
		jilu=work1();
		if(jilu==0) printf("%d %d\n",jilu,m);
		else printf("%d %d\n",jilu,m-work2());
	}
	return 0;
}

S组T3

谔谔发现我赛场上思路正确但是数组开小。从此养成const好习惯。

标签:总结,kkk,int,mid,CSP2024,else,ss,vv,学术
From: https://www.cnblogs.com/joker-killer/p/18540673

相关文章

  • 2024.11.11总结
    John的农场是一张N*N的方格图,贝茜住在左上角(1,1),John住在右下角(N,N)。现在贝茜要去拜访John,每次都只能往四周与之相邻的方格走,并且每走一步消耗时间T。同时贝茜每走三步就要停下来在当前方格吃草,在每个方格吃草的用时是固定的,为H[i][j]。John想知道贝茜最少要多久才能到达Joh......
  • NOIP2024模拟赛#18 总结
    头要炸了。T1题面很好懂,手玩了一下发现答案最小是\((m-1)\timesn\)。可能会多出来一个长度为\(k\)的部分,会发现如果多出来一个长度为\(k\)的部分且合法,那么单个串\(1\simk\)位与\(n-k+1\simn\)位一定相同,\(k+1\simn\)位与\(1\simn-k\)一定相同。Hash判一下即......
  • 2024/11/11日工作总结
    完成数据结构pta实验题:6-3链表逆置:本题要求实现一个函数,将给定单向链表逆置,即表头置为表尾,表尾置为表头。链表结点定义如下:structListNode{intdata;structListNode*next;};函数接口定义:structListNode*reverse(structListNode*head);其中head是用户传入的链......
  • 快速排序,思路总结与实现
    思路找基准值(pivot)pivot=startorend比基准值小的放左边,大的放右边实现双指针,left从左到右找比基准值大的元素,right从右到左找比基准值小的元素找到后交换left和right指针的内容直到left=right这是递增排序,递减排序情况相反如果pivot=start,则右指针先动,否......
  • DP 技巧总结
    DP技巧总结进行了为期接近一周的DP特训,做了很多同学找的高质量题目,也学到了很多技巧。现在来把一些感觉比较有价值的技巧进行一些统一的总结。插入型DP这个东西之前应该在选拔期间的一场周测中见过,但是隔了很久,已经有所遗忘。这次题单里出现了两道类似的题目,我都不会做。其......
  • csp2024游记
    趁着还有记忆,就来写篇游记吧!\(upd:\)之前游记没发想等分出来,现在终于来喽!--\(2024.11.4\)初赛篇普及组今年的普及好好好好简单啊!基本上都是一眼题,一个小时就写完了。然后出考场一交流,发现我第一题记错\(int\)的范围了,喜提98。提高组今年的提高好好好好困难啊!基本上是......
  • 迟来的2023秋招总结,互联网&银行&国企&腾讯
    复制自本人知乎首先现在是2023年四月中旬,毕业的事情暂时告一段落,于是想吐槽顺便记录一下。23秋招其实是在2022年,而2022实在是这几年来行情最差的一年。犹记得20、21年秋天各个大厂号称“史上最大规模的秋招“,hc多开的薪资也高,一年比一年倒挂。当时我还觉得23年会更美好,没想到现......
  • 渗透测试中登录框骚操作总结(非常详细)零基础入门到精通,收藏这一篇就够了
    由于测试过程中很多系统我们能接触到的只有一个登陆界面,所以要充分挖掘漏洞,进行深入操作登录注册万能密码绕过登录存在SQL注入的情况下,有可能使用万能密码直接登录admin'or'1'='1'--``admin'OR4=4/*``"or"a"="a``'or''='``'or1=1--有超级多登录口SQL......
  • 20万字208道Java经典面试题总结(附答案)
    1、JDK和JRE有什么区别?JDK(JavaDevelopmentKit),Java开发工具包JRE(JavaRuntime Environment),Java运行环境JDK中包含JRE,JDK中有一个名为jre的目录,里面包含两个文件夹bin和lib,bin就是JVM,lib就是JVM工作所需要的类库。2、==和 equals 的区别是什么?对于基本类型,==比较的......
  • # 学期(如2024-2025-1) 学号(如:20241402) 《计算机基础与程序设计》第8周学习总结
    学期(如2024-2025-1)学号(如:20241402)《计算机基础与程序设计》第8周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标<写上......