团队模拟赛-Date

具体过程

• 开始看题，由于开的 \(linux\) 所以有点慢，不过还好。
• 开始写T1，首先用的是统计入度个数，但是不知道为啥炸了
• 调了很久的输入输出调不出来，感觉很生气，因为gyf已经A了，于是去做并查集做法。
• 然后一发入魂，开始做T2
• T2写了很久，期间翻了翻最段路模板，在建图上卡了很久，后来想到可以把无色点都pass掉。。
• 一发入魂，此时还有半小时结束
• 用10分钟快速写一个T3暴力，结果全T
• 剩下时间开始写T4正解，写不出，开始写暴力，暴力只那了20pts好伤心
• 最终rank 2，真的是太烂了。

经验教训

1. 无论如何要先调试好集成开发环境，比如T2写一半 \(Code:Blocks\) 炸裂，只能用 \(Sublime Text\) 和命令行编译。
2. 平时做题少看题解！不然真的自己想不出！
3. 一个做法调不出来就别死磕，重构代码yyds。
4. 要多刷难题，锻炼思维，例如平时做蓝或绿（主要因为黄也都做了百来道了）
5. 重刷模板题。
6. 最后啊啊我还是太弱了怎么这种比赛还能考这个分。

代码

T1：

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;
	int f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int f[100001];
int find(int x){
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
inline void uniond(int x,int y){
	f[x]=y;
}
int main(){
	for(int j=1;;j++){
		int x,y;
		int maxnode=-1;
		int flag=0;
		scanf("%d%d",&x,&y);
		for(int i=1;i<=100000;i++){
			f[i]=i;
		}
		if(x<0&&y<0){
			break;
		}
		if(x==0&&y==0){
			printf("Case %d is a tree.\n",j);
			continue;
		}
		while(x>0&&y>0){
			if(find(x)==find(y)){
				flag=1;
			}
			uniond(find(x),find(y));
			scanf("%d%d",&x,&y);
		}
		if(flag==0)
			printf("Case %d is a tree.\n",j);
		else{
			printf("Case %d is not a tree.\n",j);
		}
	}
	return 0;
}

T2:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int read(){
	int x=0;
	int f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int n,m;
inline int flat(int x,int y){
	return (x-1)*m+y;
}
struct lines{
	int to,val;
};
struct point{
	int id,distance;
	bool operator < (const point & a)const{
		return distance>a.distance;
	}
};
struct colorpoint{
	int x,y,color;
};
vector<colorpoint>aa;
priority_queue<point>q;
int dis[1010];
bool vis[1010];
vector<lines>g[1010];
int s,e;
void dij(){
	for(int i=1;i<=n;i++){
		if(i==s)continue;
		dis[i]=inf;
	}
	q.push({s,0});
	while(!q.empty()){
		point now=q.top();
		q.pop();
		if(vis[now.id])continue;
		vis[now.id]=1;
		int u=now.id;
		int a=g[u].size();
		for(int i=0;i<a;i++){
			if(dis[g[u][i].to]>dis[u]+g[u][i].val){
				dis[g[u][i].to]=dis[u]+g[u][i].val;
				q.push({g[u][i].to,dis[g[u][i].to]});
			}
		}
	}
}
int tag;
int main(){
	m=read();
	n=read();
	aa.push_back({1,1,1});
	for(int i=1,x,y,z;i<=n;i++){
		x=read();
		y=read();
		z=read();
		if(x==1&&y==1)s=i;
		if(x==m&&y==m){
			tag=1;
			e=i;
		}
		aa.push_back({x,y,z});
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			if(abs(aa[i].x-aa[j].x)+abs(aa[i].y-aa[j].y)==1)
			{
				g[i].push_back({j,abs(aa[i].color-aa[j].color)} );
				g[j].push_back({i,abs(aa[i].color-aa[j].color)} );
			}
			if(abs(aa[i].x-aa[j].x)+abs(aa[i].y-aa[j].y)==2){
				g[i].push_back({j,2+abs(aa[i].color-aa[j].color)} );
				g[j].push_back({i,2+abs(aa[i].color-aa[j].color)} );
			}
		}
	}
	if(tag==0){
		for(int i=1;i<=n;i++){
			if(abs(aa[i].x-m)+abs(aa[i].y-m)==1){
				g[i].push_back({n+1,2});
				g[n+1].push_back({i,2});
			}
		}
		n++;
		e=n;
	}
	dij();
	if(dis[e]>=inf){
		cout<<-1;
	}else{
		cout<<dis[e];
	}
	return 0;
}