NOIP2017题目

作为NOIP2017考场爆零的选手,我来考完当一波马后炮(绝望..)

Day1

Day1除了T3都很SB(T1我不会证明)

T1

小凯的疑惑

#include<stdio.h>
#include<stdlib.h>
int main(){
    long long a,b;scanf("%lld%lld",&a,&b);
    printf("%lld
",a*b-a-b);
    return 0;
}

T2

时间复杂度
模拟大活题,你可以选择DeBug(1h+10min)就可以AC

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
#define ll long long
#define re register
using namespace std;
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
int t,L,have,val[100010],fuza,refuza;
char Time[10],For[10],For2[10];bool use[30],cant[1000010];
char Bian[1000010][2];
int main(){
	cin>>t;
	while(t--){
		cin>>L>>Time;fuza=0;refuza=0;int flag=0;have=0;
		int flagcan=0;
		memset(use,0,sizeof(use));memset(cant,0,sizeof(cant));
		for(re int i=1;i<=L;i++){
			char ch;
			cin>>ch;
			if(ch=='F'){
				fuza++;
				cin>>Bian[fuza];
				if(use[Bian[fuza][0]-'a']){flag=1;}
				use[Bian[fuza][0]-'a']=1;
				cin>>For;cin>>For2;
				if(flagcan){cant[fuza]=1;use[Bian[fuza][0]-'a']=0;continue;}
				if(flag)continue;
				int b1=0,b2=0;
				if(For[0]=='n')b1=1;
				if(For2[0]=='n')b2=1;
				if((!b1 && b2))val[++have]=1;
				else if(!b2 && b1 || (strlen(For)>strlen(For2) || (strcmp(For,For2))>0 && strlen(For)==strlen(For2))){
					cant[fuza]=1;flagcan=1;
					use[Bian[fuza][0]-'a']=0;
				}
			}
			else{
				if(cant[fuza]){cant[fuza--]=0;continue;}
				else flagcan=0;
				use[Bian[fuza][0]-'a']=0;
				refuza=max(refuza,have);
				if(val[have])val[have--]=0;
				fuza--;
				if(fuza<0)flag=1;
			}
		}
		if(flag || fuza!=0)puts("ERR");
		else{
			if(Time[2]=='1'){
				if(refuza==0)puts("Yes");else puts("No");
			}
			else{
				int i=4,ref=0;
				while(Time[i]>='0' && Time[i]<='9')ref=(ref*10)+Time[i++]-'0';
				if(ref!=refuza)puts("No");
				else puts("Yes");
			}
		}
	}
	return 0;
}

Day2

T1

奶酪

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
inline int gi() {
    int sum=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum*f;
}
struct node {
    long long x,y,z;
} a[1010];
int g[1010][1010],di[1010],ding[1010],dp[1010];
int cmp(node a,node b) {
    return a.z<b.z;
}
long long dis(int i,int j) {
    return (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z);
}
int main() {
    int i,j,k,n,m,h,r;
    int T=gi();
    while(T--) {
        n=gi();
        h=gi();
        r=gi();
        for(i=1; i<=n; i++) {
            scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
        }
        std::sort(a+1,a+n+1,cmp);
        memset(g,0,sizeof(g));
        memset(di,0,sizeof(di));
        memset(ding,0,sizeof(ding));
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(dis(i,j)<=1ll*4*r*r)
                    g[i][j]=1;
        for(i=1; i<=n; i++) {
            if(a[i].z-r<=0)di[i]=1;
            if(a[i].z+r>=h)ding[i]=1;
        }
        for(i=1; i<=n; i++)
            if(di[i])dp[i]=1;
            else dp[i]=0;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(g[i][j])
                    if(dp[j])dp[i]=1;
        int fla=0;
        for(i=1; i<=n; i++)
            if(dp[i] && ding[i]) {
                fla=1;
                break;
            }
        if(fla)printf("Yes
");
        else printf("No
");
    }
    return 0;
}