PKUCPC2021 简略题解

A

题意简述:有一个\(n*m\)的点阵，每两个点之间能连边当且仅当他们距离为\(3\)或\(sqrt 5\)，定义一种边的选取方案是合法的要求边集内任意两条边不能共用一个端点。求边集的最大大小并输出一种方案。
并不会什么很靠谱的解法。
把每条边建出来然后二分图最大独立集即可，注意到边数不会超过\(12nm\)，所以直接跑即可。

B

大模拟没什么好写的。
并没有写代码，把同队的人的代码扒来了

#include<cstdio>
#include<algorithm>
using namespace std;
int T,n;
struct zj{
	int id,win,lost,same,gd,val,goal;
	int xgoal,xval,xgd;
	bool operator < (const zj &x)const{
		return val>x.val;
	}
}k[111];
struct zyy{
	int c,d;
}s[111][111];
	//if(s[x.id][y.id].c!=s[x.id][y.id].d)return s[x.id][y.id].c>s[x.id][y.id].d;
bool cmp(const zj &x,const zj &y){
	//if(x.val!=y.val)return x.val>y.val;
	if(x.xval!=y.xval)return x.xval>y.xval;
	if(x.xgd!=y.xgd)return x.xgd>y.xgd;
	if(x.xgoal!=y.xgoal)return x.xgoal>y.xgoal;
	if(x.gd!=y.gd)return x.gd>y.gd;
	if(x.goal!=y.goal)return x.goal>y.goal;
	return x.id<y.id;
}
int get(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)k[i].id=i,k[i].win=k[i].lost=k[i].same=k[i].gd=k[i].val=k[i].goal=k[i].xgoal=k[i].xval=k[i].xgd=0;
	for(int i=1;i<=(n-1)*n/2;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		s[a][b]=(zyy){c,d};
		s[b][a]=(zyy){d,c};
		k[a].goal+=c;
		k[b].goal+=d;
		if(c!=d){
			k[a].win+=(c>d?1:0);
			k[a].lost+=(c>d?0:1);
			k[a].gd+=c-d;
			k[a].val+=(c>d?3:0);
			k[b].gd+=d-c;
			k[b].win+=(d>c?1:0);
			k[b].lost+=(d>c?0:1);
			k[b].val+=(d>c?3:0);
		}
		else{
			k[a].same++;k[b].same++;
			k[a].val++;k[b].val++;
		}
	}
	sort(k+1,k+1+n);
	int l=1,r=1;
	while(l<=n){
		while(k[l].val==k[r+1].val&&r<n)r++;
		for(int p=l;p<r;p++){
			for(int i=p;i<=r;i++)k[i].xgoal=k[i].xval=k[i].xgd=0;
			for(int i=p;i<=r;i++){
				for(int j=i+1;j<=r;j++){
					k[i].xgoal+=s[k[i].id][k[j].id].c;
					k[j].xgoal+=s[k[i].id][k[j].id].d;
					k[i].xgd+=s[k[i].id][k[j].id].c-s[k[i].id][k[j].id].d;
					k[j].xgd-=s[k[i].id][k[j].id].c-s[k[i].id][k[j].id].d;
					if(s[k[i].id][k[j].id].c!=s[k[i].id][k[j].id].d){
						k[i].xval+=(s[k[i].id][k[j].id].c>s[k[i].id][k[j].id].d?3:0);
						k[j].xval+=(s[k[i].id][k[j].id].d>s[k[i].id][k[j].id].c?3:0);
					}
					else{
						k[i].xval++;k[j].xval++;
					}
				}
			}
			for(int i=p+1;i<=r;i++){
				if(cmp(k[i],k[p])){
					swap(k[i],k[p]);
				}
			}
		}
		l=r=r+1;
	}
	for(int i=1;i<=n;i++){
		printf("%d %d %d %d %d %d %d %d\n",i,k[i].id,k[i].val,k[i].win,k[i].same,k[i].lost,k[i].gd,k[i].goal);
	}
	return 0;
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d",&T);
	while(T--)get();
	return 0;
}

PKUCPC2021 简略题解

原文：https://www.cnblogs.com/275307894a/p/14782528.html