BuaacodingT141 microhhh的回城题解（模拟）

题目链接

解题思路

这题挺有意思的。本来寻思放在\(DS\)第一次练习赛应该不会很难吧，结果愣是卡在数据范围上写不出来。

然后暴力过掉了,但是用了\(1019ms\)。感觉可以继续优化。（放一下暴力代码，不解释了）

#include<stdio.h>

#include<string.h>

int n,m;

char map[10010][10010];//char防止卡空间

int main(){

	int i,T,j,x,c,b,l,k;

	scanf("%d",&T);

	for(k=1;k<=T;k++){

		printf("Case %d #:",k);

		memset(map,0,sizeof(map));

		scanf("%d%d%d",&n,&m,&l);

		for(i=0;i<m;i++){

			scanf("%d%d",&c,&b);

			map[c][b]=1;

			map[c+1][b]=2;

		}

		for(i=0;i<n;i++){

			x=i;

			for(j=1;j<=l;j++){

				if(map[x][j]==1)x++;

				else if(map[x][j])x--;

			}

			printf(" %d",x);

		}

		printf("\n");

	}

	return 0;

}

又在想如果在暴力模拟的时候记录一下每列的头结点，可以进行二分查找，复杂度会下来一个\(logn\)。

码量略大，不过优化了不少。代码这里就不放了。

然后突然想到其实这就是一个交换终点的问题。从下面向上每一条边都对应一次终点的交换，去掉重边即可。\(7msAC\)。

AC代码

#include<cstdio>

#include<algorithm>

int n,m,l;

struct Path{

	int c,k;

	bool operator<(const Path&b)const{return k>b.k||(k==b.k&&c<b.c);}

}e[100010];

int pre[10010],end[10010],T,i,j,p,q,t;

int main(){

	scanf("%d",&T);

	for(j=1;j<=T;j++){

		scanf("%d%d%d",&n,&m,&l);

		for(i=0;i<m;i++)scanf("%d%d",&e[i].c,&e[i].k);

		std::sort(e,m+e);

		for(i=0;i<n;i++)pre[i]=i;

		for(i=0;i<m;i++){

			p=e[i].c,q=p+1;

			if(i&&e[i].c==e[i-1].c&&e[i].k==e[i-1].k);//去重

			else t=pre[p],pre[p]=pre[q],pre[q]=t;

		}

		printf("Case %d #:",j);

		for(i=0;i<n;i++)printf(" %d",pre[i]);

		putchar('\n');

	}

	return 0;

}

巴特西

BuaacodingT141 microhhh的回城题解（模拟）

题目链接

解题思路

AC代码

最新文章

热门文章

巴特西

BuaacodingT141 microhhh的回城 题解（模拟）

题目链接

解题思路

AC代码

最新文章

热门文章

BuaacodingT141 microhhh的回城题解（模拟）