第十九天 2021-3-27备战CCFCSP

刷题模块：CCF 202009

最终计划

1. AcWing 算法基础课程 每日一个视频
2. AcWing 算法基础课程 每日多个算法模板
3. CCF CSP 每日5道比赛真题

比赛技巧：如何改变输入输出流

#include <stdio.h>

int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	int x,y;
	scanf("%d%d",&x,&y);
	printf("%d %d",x,y);
} 

CCF CSP:202009-1

枚举法，时间复杂度O(n）

#include<iostream>

using namespace std;

const int N=200;
int n,X,Y,p1=0,p2=1,p3=2;
int x,y;
int d2[N];

int main(){
    scanf("%d%d%d",&n,&X,&Y);
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        d2[i]=(x-X)*(x-X)+(y-Y)*(y-Y);
    }

    for(int i=0;i<n;i++){
        if(d2[i]<d2[p1]) p1=i;;
    }
    for(int i=0;i<n;i++){
        if(i!=p1 && d2[i]<d2[p2]) p2=i;
    }
    for(int i=0;i<n;i++){
        if(i!=p1 && i!=p2 &&d2[i]<d2[p3]) p3=i;
    }
    printf("%d\n%d\n%d\n",p1+1,p2+1,p3+1);
}

大佬解法：只保存最小的前三位

#include<iostream>
#include<stdio.h>
using namespace std;

int main(){
	int n,X,Y;
	scanf("%d%d%d",&n,&X,&Y);
	
	int dx,dy;
	int no1=0,no2=0,no3=0,d1=1e8,d2=1e8,d3=1e8;
	
	for(int i=0;i<n;i++){
		scanf("%d%d",&dx,&dy);
		int d=(X-dx)*(X-dx)+(Y-dy)*(Y-dy);
		
		if(d<d3){
			d3=d;
			no3=i;
		}
		
		if(d3<d1){
			swap(d3,d1);
			swap(no3,no1);
			swap(d3,d2);
			swap(no3,no2); 
		}else if(d3<d2){
			swap(d3,d2);
			swap(no3,no2);
		}
	}
	
	printf("%d\n%d\n%d\n",no1+1,no2+1,no3+1);
	return 0;
} 

CCF CSP:202009-2

个人解法，坑真多

#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

int n,k,t,xl,yd,xr,yu;
int pass=0,stay=0;
int pcount,scount,maxscount,flag;
int x,y;

int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	
	scanf("%d%d%d%d%d%d%d",&n,&k,&t,&xl,&yd,&xr,&yu);
	
	for(int i=0;i<n;i++){
		pcount=0;
		scount=0;
		maxscount=0;
		flag=0;
		for(int j=0;j<t;j++){
			scanf("%d%d",&x,&y);
			if(x>=xl && x<=xr && y>=yd && y<=yu){
				pcount++;
				if(flag) scount++;
				else scount=1;	
				flag=1;
			}else{
				maxscount=max(scount,maxscount);
				flag=0;
			}
		}
		maxscount=max(scount,maxscount);
		if(pcount>0) pass++;
		if(maxscount>=k) stay++;
	}
	
	printf("%d\n%d",pass,stay);
	return 0;
}