T1【GDKOI 2021普及組DAY1】地圖 （map）

比較顯然的數學規律題，直接上代碼

#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,a[2005][2005],b1,b2,num1,num2,js1,js2;
bool bj1[2005],bj2[2005];
int main(){
	fre(map);
	scanf("%d",&n);
	Fu(i,1,n) Fu(j,1,n) scanf("%d",&a[i][j]);
	if(a[1][1]){
		printf("1 1");
		return 0;
	}
	Fu(i,1,n) b1^=a[i][n],b2^=a[n][i];
	Fu(i,2,n-1){
		int c1=0,c2=0;
		Fu(j,2,n){
			c1^=a[j][i];
			c2^=a[i][j];
		}
		bj1[i]=a[1][i]^(b1^c1);
		bj2[i]=a[i][1]^(b2^c2);
	}
	Fu(i,2,n-1){
		if(bj1[i]) num1++,js1=i;
		if(bj2[i]) num2++,js2=i;
	}
	if(num1==0&&num2==1) printf("%d 1",js2);
	else if(num1==1&&num2==0) printf("1 %d",js1);
	else if(num1>1&&num2==0) printf("1 %d",n);
	else if(num1==0&&num2>0) printf("%d 1",n);
	else if(num1==1&&num2==1) printf("%d %d",js2,js1);
	else if(num1>1&&num2==1) printf("%d %d",js2,n);
	else if(num1==1&&num2>1) printf("%d %d",n,js1);
	else printf("%d %d",n,n);
	return 0;
}

T2【GDKOI 2021普及組DAY1】灌水 （water）

第一眼，暴力；
第二眼，要不優化一下；
第三眼，倍增；
第四眼，直接AC
首先，設 l [ i , j ] l[i,j] l[i,j]表示這個位置，左邊第 2 j 2^j 2j高的地方， r [ i , j ] r[i,j] r[i,j]表示這個位置，右邊第 2 j 2^j 2j高的地方
倍增亂搞

#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline int read(){ int f=1,x=0; char s=getchar(); while(s<'0'||s>'9') { if (s=='-') f=-1; s=getchar(); } while(s>='0'&&s<='9') { x=x*10+s-'0'; s=getchar(); } return x*f; }
using namespace std;
int l[200005][20],r[200005][20],n,q;
long long a[200005],sum[200005];
int find_l(int o,long long num){
	if(a[o-1]>num) return o-1;
	int w=o-1;
	Fd(j,19,0){
		if(a[l[w][j]]<num){
			w=l[w][j];
		}
	}
	return l[w][0];
}
int find_r(int o,long long num){
	if(a[o+1]>num) return o+1;
	int w=o+1;
	Fd(j,19,0){
		if(a[r[w][j]]<num){
			w=r[w][j];
		}
	}
	return r[w][0];
}
int main(){
	fre(water);
	scanf("%d%d",&n,&q);
	Fu(i,1,n){
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
		Fu(j,0,19) r[i][j]=n+1;
	}
	a[0]=a[n+1]=10000000005;
	Fu(i,1,n){
		l[i][0]=find_l(i,a[i]);
		Fu(j,1,19) l[i][j]=l[l[i][j-1]][j-1];
	}
	Fd(i,n,1){
		r[i][0]=find_r(i,a[i]);
		Fu(j,1,19) r[i][j]=r[r[i][j-1]][j-1];
	}
	Fu(i,1,q){
		int x;
		long long y;
		scanf("%d%lld",&x,&y);
		int ll=find_l(x,y-1),rr=find_r(x,y-1);
		long long u=y*(rr-ll-1)-sum[rr-1]+sum[ll];
		printf("%lld\n",u);
	}
	return 0;
}

T3【GDKOI 2021普及組DAY1】配對（match）

#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,ll,rr,a[1000005],ans;
int main(){
	fre(match);
	scanf("%d%d%d",&n,&ll,&rr);
	Fu(i,1,n) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int l=1,r=n;
	while(l<r){
		if(a[l]+a[r]>rr) r--,ans++;
		else if(a[l]+a[r]<ll) l++,ans++;
		else l++,r--;
		if(l==r) ans++;
	}
	printf("%d",ans);
	return 0;
}

T4【GDKOI 2021普及組DAY1】旅行（travel）

#include<bits/stdc++.h>
#define Fu(i,a,b) for(int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
inline int read(){ int f=1,x=0; char s=getchar(); while(s<'0'||s>'9') { if (s=='-') f=-1; s=getchar(); } while(s>='0'&&s<='9') { x=x*10+s-'0'; s=getchar(); } return x*f; }

int n,m,q,ans[200005],fa[200005],size[200005],js=1;

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

struct node{
	int x,z,num;
}b[200005];

struct egde{
	int u,v,w;
}a[400005];

bool cmp1(egde x,egde y){ return x.w<y.w; }

bool cmp2(node x,node y){ return x.z<y.z; }

int main(){
	fre(travel);
	n=read(),m=read();
	Fu(i,1,m) a[i].u=read(),a[i].v=read(),a[i].w=read();
	Fu(i,1,n) fa[i]=i,size[i]=1;
	sort(a+1,a+1+m,cmp1);
	q=read();
	Fu(i,1,q){
		b[i].x=read(),b[i].z=read();
		b[i].num=i;
	}
	sort(b+1,b+1+q,cmp2);
	a[m+1].w=0x7fffffff;
	Fu(i,1,m+1){
		while(b[js].z<a[i].w&&js<=q){
			ans[b[js].num]=size[find(b[js].x)];
			js++;
		}
		if(find(a[i].v)!=find(a[i].u)){
			size[find(a[i].v)]+=size[find(a[i].u)];
			fa[find(a[i].u)]=find(a[i].v);
		}
	}
	Fu(i,1,q) printf("%d\n",ans[i]);
	return 0;
}

分數100+100+100+35=335

改題100+100+100+100=400

總結

發揮一般，本來能AK，