做过这题之后我才知道
  • 板块P3936 Coloring
  • 楼主Shiroko
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/9/14 22:50
  • 上次更新2023/11/5 13:10:51
查看原帖
做过这题之后我才知道
252015
Shiroko楼主2020/9/14 22:50

洛谷的长时限题目原来是有提交次数限制的

顺带问一句

#include<bits/stdc++.h>
using namespace std;

double t, t_delta = 0.99;

int n, m, c, ans, p[55], a[25][25];
int dx[5] = { 0,0,1,-1,1 };
int dy[5] = { 0,1,0,0,-1 };

void color()
{
	int k = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			a[i][j] = k;
			p[k]--;
			if (a[i][j - 1] && a[i][j - 1] != a[i][j])
				ans++;
			if (a[i - 1][j] && a[i - 1][j] != a[i][j])
				ans++;
			if (!p[k])
				k++;
		}
}

int calc(int x1, int y1, int x2, int y2)
{
	int res = ans;
	for (int i = 1; i <= 4; i++)
	{
		int X = x1 + dx[i];
		int Y = y1 + dy[i];
		if (a[X][Y] != a[x1][y1])
			res--;
		X = x2 + dx[i];
		Y = y2 + dy[i];
		if (a[X][Y] != a[x2][y2])
			res--;
	}
	swap(a[x1][y1], a[x2][y2]);
	for (int i = 1; i <= 4; i++)
	{
		int X = x1 + dx[i];
		int Y = y1 + dy[i];
		if (a[X][Y] != a[x1][y1])
			res++;
		X = x2 + dx[i];
		Y = y2 + dy[i];
		if (a[X][Y] != a[x2][y2])
			res++;
	}
	return res;
}

void SA()
{
	t = 5000;
	while (t >= 1e-10)
	{
		int x1 = rand() % n + 1;
		int x2 = rand() % n + 1;
		int y1 = rand() % m + 1;
		int y2 = rand() % m + 1;
		int energy = calc(x1, y1, x2, y2);
		int delta = energy - ans;
		if (delta < 0)
			ans = energy;
		else if (exp(-delta / t) * RAND_MAX > rand())
			swap(a[x1][y1], a[x2][y2]);
		t *= t_delta;
	}
}

void solve()
{
	color();
	while ((double)clock() / CLOCKS_PER_SEC < 4.5)
		SA();
}

int main()
{
	srand("两个恶臭数字的结合体");
	cin >> n >> m >> c;
	for (int i = 1; i <= c; i++)
		cin >> p[i];
	solve();
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
}

有哪位dalao能帮我看看哪里炸了吗

有些时候样例输出对的 有些时候错的

而且每一次交这份代码得分都会比前一次低(

2020/9/14 22:50
加载中...