JOISC2020 Legendary Dango Maker

先随便想一个贪心策略。

博主的想法类似匈牙利：以任意顺序枚举一个非 W 团子 \(A\)，从 \(A\) 团子开始枚举八个方向，如果某个方向上的团子是 W 且没被用过，则考虑再往这个方向上走一步的团子 \(B\) 是否是非 W 的、和当前团子不同的团子。如果不同则尝试把 \(AB\) 串起来，如果 \(B\) 没有和别的团子串起来则直接串，否则再从跟 \(B\) 串在一起、跟 \(B\) 不同颜色的团子开始尝试，如果尝试成功再把当前三个团子串上。

直接跑这个贪心策略一般可以得到 \(20 \sim 50\) 的分数，场外赛拿了 39 分，而且跑起来非常快。

然后对这个贪心策略进行随机化爬山：对于旧方案的每一组已经匹配好的团子以一定的几率将这个匹配撤销，然后获得一大堆新的没有匹配的非 W 团子，再随机顺序枚举非 W 团子进行匹配，得到新方案。如果新方案匹配数比旧方案大则选择新方案，否则保留旧方案。

对于 T4 只要爬 2s 左右就能爬到满分，因为图中非 W 的团子数量比较稀疏，其次 T2T3T6 大概要爬 5 到 10 分钟的样子，T1T5 可能因为数据比较随机所以在本机上爬了半个小时，大概一个半小时能够出所有解，这已经足够了。而且一般的机子比博主的本快很多所以还是比较划算的。

当然用模拟退火可能可以更厉害，但是博主不太会用，每一次写模拟退火都只能搞出更劣解 TAT

这种 贪心->随机化爬山 的思路对于很多问题应该是通用的，可以参考 JOISC2018 的提答题，思路是类似的。这可比你国 OI 十合一提答清新多了 = =。

//刷一个比较厉害的初始解
#include
#include
#include
#include
#include
#include
#include
#include
//STL
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//C++11 needed
#include
#include
#include
using namespace std;

#define PII pair < int , int >
const int dir[8][2] = {1,0,-1,0,0,1,0,-1,1,1,-1,-1,1,-1,-1,1};
char str[503][503]; int N , M; PII match[503][503];

char getop(int id){
	switch(id >> 1){
	case 0: return '|';
	case 1: return '-';
	case 2: return '\\';
	case 3: return '/';
	}
	return -1;
}

int getid(char op){
	switch(op){
	case '|': return 0;
	case '-': return 1;
	case '\\': return 2;
	case '/': return 3;
	}
	return -1;
}

bool vis[503][503]; vector < PII > in;
bool dfs(int x , int y){
	if(vis[x][y]) return 0;
	vis[x][y] = 1; in.push_back(make_pair(x , y));
	for(int i = 0 ; i < 8 ; ++i){
		int wx = x + dir[i][0] , wy = y + dir[i][1] , px = wx + dir[i][0] , py = wy + dir[i][1];
		if(str[wx][wy] == 'W' && str[px][py] + str[x][y] == 'G' + 'P'){
			int tx = match[px][py].first , ty = match[px][py].second; str[wx][wy] = getop(i);
			if(tx == -1 || dfs(tx , ty)){
				if(~tx)
					for(int p = 0 ; p < 8 ; ++p)
						if(px + 2 * dir[p][0] == tx && py + 2 * dir[p][1] == ty)
							str[px + dir[p][0]][py + dir[p][1]] = 'W';
				match[px][py] = make_pair(x , y); match[x][y] = make_pair(px , py); return 1;
			}
			str[wx][wy] = 'W';
		}
	}
	return 0;
}

int sum = 0; mt19937 rnd(time(0));
void go(bool flg){
	vector < pair < int , int > > pot;
	for(int i = 1 ; i <= N ; ++i)
		for(int j = 1 ; j <= M ; ++j)
			if(match[i][j].first == -1 && (str[i][j] == 'G' || str[i][j] == 'P'))
				pot.push_back(make_pair(i , j));
	if(flg) shuffle(pot.begin() , pot.end() , rnd);
	for(auto t : pot)
		if(match[t.first][t.second].first == -1){
			sum += dfs(t.first , t.second);
			for(auto t : in) vis[t.first][t.second] = 0;
			in.clear();
		}
}

int main(){
	scanf("%d %d" , &N , &M);
	for(int i = 1 ; i <= N ; ++i) scanf("%s" , str[i] + 1);
	for(int i = 1 ; i <= N ; ++i) for(int j = 1 ; j <= M ; ++j) match[i][j] = make_pair(-1 , -1);
	go(0);

	fprintf(stderr , "%d\n" , sum);
	static PII tmatch[503][503]; static char tmap[503][503];
	for(int times = 1 ; times <= 50 ; ++times)
		for(int T = 1 ; T <= 80 ; ++T){
			memcpy(tmatch , match , sizeof(tmatch));
			memcpy(tmap , str , sizeof(tmap)); int preans = sum;
			vector < pair < int , int > > tw;
			for(int i = 1 ; i <= N ; ++i)
				for(int j = 1 ; j <= M ; ++j) if(!isupper(str[i][j])) tw.push_back(make_pair(i , j));
			shuffle(tw.begin() , tw.end() , rnd);
			for(auto p : tw)
				if(!(rnd() % (int)ceil(1.4 * T))){
					int x = p.first , y = p.second , p = getid(str[x][y]); str[x][y] = 'W'; --sum;
					match[x + dir[p << 1][0]][y + dir[p << 1][1]] = PII(-1 , -1);
					match[x + dir[p << 1 | 1][0]][y + dir[p << 1 | 1][1]] = PII(-1 , -1);
				}
			go(1);
			if(sum < preans){memcpy(match , tmatch , sizeof(tmatch)); memcpy(str , tmap , sizeof(tmap)); sum = preans;}
			if(T % 10 == 0) fprintf(stderr , "%d\n" , sum);
		}
	for(int i = 1 ; i <= N ; ++i) printf("%s\n" , str[i] + 1);
	return 0;
}

//稍微改了一下上面的代码，用一个已知解刷更厉害的解，爬山次数比上面多一些
#include
#include
#include
#include
#include
#include
#include
#include
//STL
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//C++11 needed
#include
#include
#include
using namespace std;

#define PII pair < int , int >
const int dir[8][2] = {1,0,-1,0,0,1,0,-1,1,1,-1,-1,1,-1,-1,1};
char str[503][503]; int N , M; PII match[503][503];

char getop(int id){
	switch(id >> 1){
	case 0: return '|';
	case 1: return '-';
	case 2: return '\\';
	case 3: return '/';
	}
	return -1;
}

int getid(char op){
	switch(op){
	case '|': return 0;
	case '-': return 1;
	case '\\': return 2;
	case '/': return 3;
	}
	return -1;
}

bool vis[503][503]; vector < PII > in;
bool dfs(int x , int y){
	if(vis[x][y]) return 0;
	vis[x][y] = 1; in.push_back(make_pair(x , y));
	for(int i = 0 ; i < 8 ; ++i){
		int wx = x + dir[i][0] , wy = y + dir[i][1] , px = wx + dir[i][0] , py = wy + dir[i][1];
		if(str[wx][wy] == 'W' && str[px][py] + str[x][y] == 'G' + 'P'){
			int tx = match[px][py].first , ty = match[px][py].second; str[wx][wy] = getop(i);
			if(tx == -1 || dfs(tx , ty)){
				if(~tx)
					for(int p = 0 ; p < 8 ; ++p)
						if(px + 2 * dir[p][0] == tx && py + 2 * dir[p][1] == ty)
							str[px + dir[p][0]][py + dir[p][1]] = 'W';
				match[px][py] = make_pair(x , y); match[x][y] = make_pair(px , py); return 1;
			}
			str[wx][wy] = 'W';
		}
	}
	return 0;
}

int sum = 0; mt19937 rnd(time(0));
void go(bool flg){
	vector < pair < int , int > > pot;
	for(int i = 1 ; i <= N ; ++i)
		for(int j = 1 ; j <= M ; ++j)
			if(match[i][j].first == -1 && (str[i][j] == 'G' || str[i][j] == 'P'))
				pot.push_back(make_pair(i , j));
	if(flg) shuffle(pot.begin() , pot.end() , rnd);
	for(auto t : pot)
		if(match[t.first][t.second].first == -1){
			sum += dfs(t.first , t.second);
			for(auto t : in) vis[t.first][t.second] = 0;
			in.clear();
		}
}

int main(){
	N = 500; M = 500;
	for(int i = 1 ; i <= N ; ++i) scanf("%s" , str[i] + 1);
	for(int i = 1 ; i <= N ; ++i) for(int j = 1 ; j <= M ; ++j) match[i][j] = make_pair(-1 , -1);
	for(int i = 1 ; i <= N ; ++i)
		for(int j = 1 ; j <= M ; ++j)
			if(!isupper(str[i][j])){
				int p = getid(str[i][j]); ++sum;
				match[i + dir[p << 1][0]][j + dir[p << 1][1]] = PII(i + dir[p << 1 | 1][0] , j + dir[p << 1 | 1][1]);
				match[i + dir[p << 1 | 1][0]][j + dir[p << 1 | 1][1]] = PII(i + dir[p << 1][0] , j + dir[p << 1][1]);
			}

	fprintf(stderr , "%d\n" , sum);
	static PII tmatch[503][503]; static char tmap[503][503];
	for(int times = 1 ; times <= 500 ; ++times)
		for(int T = 1 ; T <= 30 ; ++T){
			memcpy(tmatch , match , sizeof(tmatch));
			memcpy(tmap , str , sizeof(tmap)); int preans = sum;
			vector < pair < int , int > > tw;
			for(int i = 1 ; i <= N ; ++i)
				for(int j = 1 ; j <= M ; ++j) if(!isupper(str[i][j])) tw.push_back(make_pair(i , j));
			shuffle(tw.begin() , tw.end() , rnd);
			for(auto p : tw)
				if(!(rnd() % (int)ceil(3 * T))){
					int x = p.first , y = p.second , p = getid(str[x][y]); str[x][y] = 'W'; --sum;
					match[x + dir[p << 1][0]][y + dir[p << 1][1]] = PII(-1 , -1);
					match[x + dir[p << 1 | 1][0]][y + dir[p << 1 | 1][1]] = PII(-1 , -1);
				}
			go(1);
			if(sum < preans){memcpy(match , tmatch , sizeof(tmatch)); memcpy(str , tmap , sizeof(tmap)); sum = preans;}
			if(T % 10 == 0) fprintf(stderr , "%d\n" , sum);
		}
	for(int i = 1 ; i <= N ; ++i) printf("%s\n" , str[i] + 1);
	return 0;
}
基础算法——贪心基础算法——随机化

相关

标签