文档章节

JOISC2020 Legendary Dango Maker

o
 osc_t5nbj8ds
发布于 07/01 14:39
字数 1729
阅读 24
收藏 0
t2t

精选30+云产品,助力企业轻松上云!>>>

先随便想一个贪心策略。

博主的想法类似匈牙利:以任意顺序枚举一个非 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<cstdio>
#include<ctime>
#include<cctype>
#include<cassert>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<sstream>
//STL
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
//C++11 needed
#include<unordered_map>
#include<unordered_set>
#include<random>
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<cstdio>
#include<ctime>
#include<cctype>
#include<cassert>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<sstream>
//STL
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
//C++11 needed
#include<unordered_map>
#include<unordered_set>
#include<random>
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;
}
o
粉丝 0
博文 54
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

SequoiaDB监控与开发实践分析

使用背景 公司近期上线了一个新应用,底层数据库采用了国产的分布式数据库 – SequoiaDB。 因为需要将 SequoiaDB 集群纳入到公司的整个监控体系中,所以需要对 SequoiaDB 的状态、性能指标等...

巨杉数据库
46分钟前
18
0
如何导入其他Python文件? - How to import other Python files?

问题: How do I import other files in Python? 如何在Python中导入其他文件? How exactly can I import a specific python file like import file.py ? 我究竟该如何导入特定的python文件......

fyin1314
54分钟前
22
0
小程序上传图片 返回的地址出现回车空格问题

不知怎么回事 ,今天写小程序上传图片 之前是没问题的,今天突然出现很多回车空格问题 那怎么办呢,处理呗 //去掉空格str = str.replace(/\ +/g,""); console.log(str);//"{'retmsg':'suc......

子枫Eric
今天
6
0
Spring Boot + Spring Security自定义用户认证

自定义认证过程 自定义认证的过程需要实现Spring Security提供的UserDetailService接口 ,源码如下: public interface UserDetailsService { UserDetails loadUserByUsername(String use...

心田已荒
今天
12
0
DateTime2与SQL Server中的DateTime - DateTime2 vs DateTime in SQL Server

问题: Which one: 哪一个: datetime datetime2 is the recommended way to store date and time in SQL Server 2008+? 是在SQL Server 2008+中存储日期和时间的推荐方法吗? I'm aware of......

富含淀粉
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部