L2-052 吉利矩阵

本题传送门

被卡掉一个点的代码

#include<iostream>
#include<vector>
using namespace std;
int L,N,ans;
int col_sum[5];
vector<vector<int>> valid_rows;
vector<int> temp_row;

void  yuchuli(int cur_sum,int count)
{
	if(count == N)
	{
		if(cur_sum == L)
		{
			valid_rows.push_back(temp_row);
		}
		return ;
	}
	
	for(int i = 0 ; i <= L - cur_sum ; i ++)
	{
		temp_row.push_back(i);
		yuchuli(cur_sum + i , count + 1);
		temp_row.pop_back();
	}
}

void dfs(int row_idx)
{
	if(row_idx == )
	{
		for(int i = 0 ; i < N ; i++)
		{
			//行一定是符合要求的，所以这里得检查列
			if(col_sum[i] != L)
			{
				return ;
			}
		}
		ans++ ;
		return ;		
	}
	
	for(const auto& row : valid_rows)
	{
		bool ok = true;
		
		for(int i = 0 ; i < N ; i++)
		{
			if(col_sum[i] + row[i] > L)
			{
				ok = false;
				break;
			}
		}
		
		if(ok)
		{
			for(int i = 0 ; i < N ; i ++)
			{
				col_sum[i] += row[i];
			}
			
			dfs(row_idx + 1);
			
			for(int i = 0 ; i < N ; i++)
			{
				col_sum[i] -= row[i];
			}
			
		}
	}
}

int main()
{
	if(!(cin>>L>>N)) return 0;
	
	yuchuli(0,0);
	
	dfs(0);
	
	cout<<ans<<endl;
	
	return 0;
}

ac✅️代码 ac代码的优化是，当前几行确定之后，最后一行可以直接通过L - 列和 算出，如果合法就加入到最后一行的行和，否则直接return，如果最后行和等于L，答案加一。

#include<iostream>
#include<vector>
using namespace std;
int L,N,ans;
int col_sum[5];
vector<vector<int>> valid_rows;
vector<int> temp_row;

void  yuchuli(int cur_sum,int count)
{
	if(count == N)
	{
		if(cur_sum == L)
		{
			valid_rows.push_back(temp_row);
		}
		return ;
	}
	
	for(int i = 0 ; i <= L - cur_sum ; i ++)
	{
		temp_row.push_back(i);
		yuchuli(cur_sum + i , count + 1);
		temp_row.pop_back();
	}
}

void dfs(int row_idx)
{
	if(row_idx == N - 1)
	{
		
		int last_row_sum = 0;
		for(int i = 0 ; i < N ; i++)
		{
			int lie = L - col_sum[i];
			if(lie < 0) return ;
			last_row_sum += lie;
		}
		
		if(last_row_sum == L)
		{
			ans++;
		}
		return ;
	}
	
	for(const auto& row : valid_rows)
	{
		bool ok = true;
		
		for(int i = 0 ; i < N ; i++)
		{
			if(col_sum[i] + row[i] > L)
			{
				ok = false;
				break;
			}
		}
		
		if(ok)
		{
			for(int i = 0 ; i < N ; i ++)
			{
				col_sum[i] += row[i];
			}
			
			dfs(row_idx + 1);
			
			for(int i = 0 ; i < N ; i++)
			{
				col_sum[i] -= row[i];
			}
			
		}
	}	
}

int main()
{
	if(!(cin>>L>>N)) return 0;
	
	yuchuli(0,0);
	
	dfs(0);
	
	cout<<ans<<endl;
	
	return 0;
}

如果在赛场上是因为超时，并且知道超时的测试点的输入，可以在本地编译器上算出输出，然后打表（数据别打错就行了）；如果压根不会写，只知道一个最暴力的写法，那只能全部打表了，用最朴素的写法算出所有的数据，然后输出。

#include<iostream>
#include<vector>
using namespace std;

int col_sum[5] ;
int row_sum[5] ;
int ans;
int L,N;

void solve(int i,int j)
{
	if(i == N)
	{
		ans++;
		return ;
	}
	
	//接下来是对每一个格子填数字,但是需要提前计算下一个格子的坐标
	int ni = i , nj = j + 1;//每一行填的时候，下一个位置就是行不变，列加一，然后末尾特判一下
	if(j == N - 1) ni = i + 1 , nj = 0;

	//填数字
	for(int num = 0 ; num <= L ; num ++)
	{
		if(col_sum[j] + num > L) break;
		if(row_sum[i] + num > L) break;
		
		if(i == N - 1 && col_sum[j] + num != L) continue;//每一行
		if(j == N - 1 && row_sum[i] + num != L) continue;//每一列
		
		row_sum[i] += num;
		col_sum[j] += num;
		
		solve(ni,nj);
		
		row_sum[i] -= num;
		col_sum[j] -= num;
		
	}
}

int main()
{
	L = 7 , N = 3;
	solve(0,0);
	
	cout<<ans<<endl;
	return 0;
}