10KB代码求调!!!!!
查看原帖
10KB代码求调!!!!!
1024904
LFRED2023楼主2024/9/7 15:09
#include<bits/stdc++.h>
using namespace std;
#define g register
int heng[5];
int lst_heng[5];
int ans_heng[5];
int shu[5];
int lst_shu[5];
int ans_shu[5];
int xie_1;
int ans_xie_1;
int lst_xie_1;
int xie_2;
int ans_xie_2;
int lst_xie_2;
int t[5][5];
int book[5][5];
int if_n = 0;

struct node{
	int x;
	int y;
	int maxn;
}que[20];
inline void dfs(int step)
{
	if(if_n) return;
	if(step == 17)
	{
//		if(xie_1 != ans_xie_1) return;
//		if(xie_2 != ans_xie_2) return;
//		for(int i = 1;i <= 4;++i)
//		{
//			if(heng[i] != ans_heng[i] || shu[i] != ans_shu[i]) return;
//		}
		for(int i = 1;i <= 4;++i)
		{
			for(int i1 = 1;i1 <= 4;++i1)
			{
				cout << t[i][i1] << " ";
			}
			cout << "\n";
		}
		
		if_n = 1;
		return;
	}
	int x = que[step].x;
	int y = que[step].y;
	if(book[x][y])
	{
		dfs(step + 1);
		return;
	}
	
	if(lst_xie_2 == 1 && x + y == 5)
	{
		int h = ans_xie_2 - xie_2;
		if(h == 0) return;
		
		
		if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
		if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
		if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
		if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
		if(x == y && xie_1 + h > ans_xie_1) return;
		if(x + y == 5 && xie_2 + h > ans_xie_2) return;
		if(h + shu[y] > ans_shu[y]) return;
		if(h + heng[x] > ans_heng[x]) return;
		
		t[x][y] = h;
		heng[x] += h;
		shu[y] += h;
		if(x == y) xie_1 += h;
		if(x + y == 5) xie_2 += h;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		heng[x] -= h;
		shu[y] -= h;
		if(x == y) xie_1 -= h;
		if(x + y == 5) xie_2 -= h;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
		return;
	}
	
	if(lst_xie_1 == 1 && x == y)
	{
		int h = ans_xie_1 - xie_1;
		if(h == 0) return;
		
		
		if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
		if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
		if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
		if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
		if(x == y && xie_1 + h > ans_xie_1) return;
		if(x + y == 5 && xie_2 + h > ans_xie_2) return;
		if(h + shu[y] > ans_shu[y]) return;
		if(h + heng[x] > ans_heng[x]) return;
		t[x][y] = h;
		heng[x] += h;
		shu[y] += h;
		if(x == y) xie_1 += h;
		if(x + y == 5) xie_2 += h;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		heng[x] -= h;
		shu[y] -= h;
		if(x == y) xie_1 -= h;
		if(x + y == 5) xie_2 -= h;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
		return;
	}
	if(lst_heng[x] == 1)
	{
		int h = ans_heng[x] - heng[x];
		if(h == 0) return;
		
		
		if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
		if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
		if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
		if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
		if(x == y && xie_1 + h > ans_xie_1) return;
		if(x + y == 5 && xie_2 + h > ans_xie_2) return;
		if(h + shu[y] > ans_shu[y]) return;
		if(h + heng[x] > ans_heng[x]) return;
		t[x][y] = h;
		heng[x] += h;
		shu[y] += h;
		if(x == y) xie_1 += h;
		if(x + y == 5) xie_2 += h;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		heng[x] -= h;
		shu[y] -= h;
		if(x == y) xie_1 -= h;
		if(x + y == 5) xie_2 -= h;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
		return;
	}
	
	if(lst_shu[y] == 1)
	{
		int h = ans_shu[y] - shu[y];
		
		
		if(lst_heng[x] == 1 && h != ans_heng[x] - heng[x]) return;
		if(lst_shu[y] == 1 && h != ans_shu[y] - shu[y]) return;
		if(lst_xie_1 == 1 && x == y && h != ans_xie_1 - xie_1) return;
		if(lst_xie_2 == 1 && x + y == 5 && h != ans_xie_2 - xie_2) return;
		if(h == 0) return;
		if(x == y && xie_1 + h > ans_xie_1) return;
		if(x + y == 5 && xie_2 + h > ans_xie_2) return;
		if(h + heng[x] > ans_heng[x]) return;
		t[x][y] = h;
		heng[x] += h;
		shu[y] += h;
		if(x == y) xie_1 += h;
		if(x + y == 5) xie_2 += h;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		heng[x] -= h;
		shu[y] -= h;
		if(x == y) xie_1 -= h;
		if(x + y == 5) xie_2 -= h;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
		return;
	}
//	if(x > 1 && y == 1)
//	{
//		if(heng[x - 1] != ans_heng[x - 1]) return;
//	}
//	if(x == 4)
//	{
//		if(y > 1)
//		{
//			if(xie_2 != ans_xie_2) return;
//			if(shu[y - 1] != ans_shu[y - 1]) return;
//		}
//	}
//	if(y == 4 && x != 4)
//	{
//		int h = ans_heng[x] - heng[x];
//		if(h == 0) return;
//		if(if_n) return;
//		if(shu[y] + h > ans_shu[y]) return;
//		if(x == y && xie_1 + h > ans_xie_1) return;
//		if(x + y == 5 && xie_2 + h > ans_xie_2) return;
//		t[x][y] = h;
//		heng[x] += h;
//		shu[y] += h;
//		if(x == y) xie_1 += h;
//		if(x + y == 5) xie_2 += h;
//		dfs(step + 1);
//		t[x][y] = 0;
//		heng[x] -= h;
//		shu[y] -= h;
//		if(x == y) xie_1 -= h;
//		if(x + y == 5) xie_2 -= h;
//		return;
//	}
//	if(x == 4 && y != 4)
//	{
//		int h = ans_shu[y] - shu[y];
//		if(h == 0) return;
//		if(if_n) return;
//		if(heng[x] + h > ans_heng[x]) return;
//		if(x == y && xie_1 + h > ans_xie_1) return;
//		if(x + y == 5 && xie_2 + h > ans_xie_2) return;
//		t[x][y] = h;
//		heng[x] += h;
//		shu[y] += h;
//		if(x == y) xie_1 += h;
//		if(x + y == 5) xie_2 += h;
//		dfs(step + 1);
//		t[x][y] = 0;
//		heng[x] -= h;
//		shu[y] -= h;
//		if(x == y) xie_1 -= h;
//		if(x + y == 5) xie_2 -= h;
//		return;
//	}
//	if(x == 4 && y == 4)
//	{
//		int h = ans_heng[x] - heng[x];
//		if(h == 0) return;
//		if(h != ans_shu[y] - shu[y]) return;
//		if(h != ans_xie_1 - xie_1) return;
//		
//		t[x][y] = h;
//		heng[x] += h;
//		shu[y] += h;
//		if(x == y) xie_1 += h;
//		if(x + y == 5) xie_2 += h;
//		dfs(step + 1);
//		t[x][y] = 0;
//		heng[x] -= h;
//		shu[y] -= h;
//		if(x == y) xie_1 -= h;
//		if(x + y == 5) xie_2 -= h;
//		return;
//	}
	int up = min(ans_heng[x] - heng[x],ans_shu[y] - shu[y]);
	up = min(up,que[step].maxn);
	if(up == 0) return;
	int mid = up / 3;
	for(g int i = mid + 1;i <= up / 3 * 2;++i)
	{
		if(i == 0) continue;
		if(if_n) return;
		if(heng[x] + i > ans_heng[x]) continue;
		if(shu[y] + i > ans_shu[y]) continue;
		if(x == y && xie_1 + i > ans_xie_1) continue;
		if(x + y == 5 && xie_2 + i > ans_xie_2) continue;
		t[x][y] = i;
		heng[x] += i;
		shu[y] += i;
		if(x == y) xie_1 += i;
		if(x + y == 5) xie_2 += i;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		t[x][y] = 0;
		heng[x] -= i;
		shu[y] -= i;
		if(x == y) xie_1 -= i;
		if(x + y == 5) xie_2 -= i;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
	}
	for(g int i = mid;i >= 1;--i)
	{
		if(i == 0) continue;
		if(if_n) return;
		if(heng[x] + i > ans_heng[x]) continue;
		if(shu[y] + i > ans_shu[y]) continue;
		if(x == y && xie_1 + i > ans_xie_1) continue;
		if(x + y == 5 && xie_2 + i > ans_xie_2) continue;
		t[x][y] = i;
		heng[x] += i;
		shu[y] += i;
		if(x == y) xie_1 += i;
		if(x + y == 5) xie_2 += i;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		t[x][y] = 0;
		heng[x] -= i;
		shu[y] -= i;
		if(x == y) xie_1 -= i;
		if(x + y == 5) xie_2 -= i;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
	}
	for(g int i = up / 3 * 2 + 1;i <= up;++i)
	{
		if(i == 0) continue;
		if(if_n) return;
		if(heng[x] + i > ans_heng[x]) continue;
		if(shu[y] + i > ans_shu[y]) continue;
		if(x == y && xie_1 + i > ans_xie_1) continue;
		if(x + y == 5 && xie_2 + i > ans_xie_2) continue;
		t[x][y] = i;
		heng[x] += i;
		shu[y] += i;
		if(x == y) xie_1 += i;
		if(x + y == 5) xie_2 += i;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
		
		dfs(step + 1);
		
		t[x][y] = 0;
		heng[x] -= i;
		shu[y] -= i;
		if(x == y) xie_1 -= i;
		if(x + y == 5) xie_2 -= i;
		lst_heng[x]++;
		lst_shu[y]++;
		if(x == y) lst_xie_1++;
		if(x + y == 5) lst_xie_2++;
	}
}
inline bool cmp(node x,node y)
{ 
	return x.maxn > y.maxn;
}
int main()
{
//	freopen("scrab.in","r",stdin);
//	freopen("scrab.out","w",stdout);
	std::ios::sync_with_stdio(false); 
	for(g int i = 1;i <= 4;++i) cin >> ans_heng[i],lst_heng[i] = 4;
	for(g int i = 1;i <= 4;++i) cin >> ans_shu[i],lst_shu[i] = 4;
	lst_xie_1 = lst_xie_2 = 4;
	cin >> ans_xie_1;
	cin >> ans_xie_2;
	for(g int i = 1,x,y,z;i <= 4;++i)
	{
		cin >> x >> y >> z;
		x++;
		y++;
		t[x][y] = z;
		book[x][y] = 1;
		heng[x] += z;
		shu[y] += z;
		if(x == y) xie_1 += z;
		if(x + y == 5) xie_2 += z;
		lst_heng[x]--;
		lst_shu[y]--;
		if(x == y) lst_xie_1--;
		if(x + y == 5) lst_xie_2--;
	}
	for(g int i = 1;i <= 4;++i)
	{
		for(g int i1 = 1;i1 <= 4;++i1)
		{
			int num = (i - 1) * 4 + i1;
			que[num].x = i;
			que[num].y = i1;
			que[num].maxn = max(ans_heng[i] - heng[i],ans_shu[i1] - shu[i1]);
			if(i == i1)
			{
				que[num].maxn = max(que[num].maxn,ans_xie_1 - xie_1);
			}
			if(i + i1 == 5)
			{
				que[num].maxn = max(que[num].maxn,ans_xie_2 - xie_2);
			}
		}
	}
	sort(que + 1,que + 1 + 16,cmp);
	dfs(1);
	return 0;
}

无论如何修改mid都会至少有一个点TLE,还是不一样的点T_T 请求巨巨巨巨巨佬帮助!!!!!QAQ

2024/9/7 15:09
加载中...