文章
2
粉丝
289
获赞
1
访问
18.3k
根据题意,我们知道,这本身就是一个符合规则的等差矩阵,我们不用考虑推导出的数是否符合矩阵规则(一开始忽略这个前提,想着怎么不匹配怎么逆推撤回……)
那么怎么才能推导呢?很简单,一行或者一列有两个及以上的数字确定,这一行或一列就出来了。
创造一个矩阵,数字序列从[1,1]开始,[i,0]用于标识第i行是否有超过两个数字了,[i,m+1]标识这一行是否已经放入了待处理队列,防止重复处理,列一样的思想。
那么我们在录入数字或者在推到一行的时候,每有一个数字不是0或者被推导出来,就更新这一行和者一列的已知数字个数,达到2个及以上且未放入待处理队列,就放入队列,且标示改变
知道队列变空,也就是没有可以再推导的行或者列了。
这种思想,有比较多的重复扫描,时间复杂度应该是达到了n*n,不过基于数据集,没有超时,有更好的思路或者改进方法,欢迎留言
#include <bits/stdc++.h>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> node;
typedef pair<int, int> lineorcol;
ll dp[1024][1024];//用来存放矩阵
ll resflag[1024][1024];//用来存放可以推出结果的矩阵
queue<lineorcol> nextd;//用来存放可以推断出的行或者列
//queue<node> res;
int n,m;
long long readll(void)
{
ll res;
cin>>res;
return res;
}
void dealLine(int lineNumber)//某一行掌握了超过两个数字,这一行就可以推出所有数字
{
int l1,l2;
for(int j=1; j<=m; ++j)
{
if(dp[lineNumber][j] != 0)
{
l1...
登录后发布评论
麻烦啊