文章

2

粉丝

289

获赞

1

访问

17.3k

头像
等待时机,依次处理
P1850 清华大学2020年机试题
发布于2021年3月2日 10:40
阅读数 9.0k

根据题意,我们知道,这本身就是一个符合规则的等差矩阵,我们不用考虑推导出的数是否符合矩阵规则(一开始忽略这个前提,想着怎么不匹配怎么逆推撤回……)

那么怎么才能推导呢?很简单,一行或者一列有两个及以上的数字确定,这一行或一列就出来了。

创造一个矩阵,数字序列从[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...
登录查看完整内容


登录后发布评论

1 条评论
chenziyi
2021年9月11日 21:18

麻烦啊

赞(0)