P1850 等差数列 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2023年3月17日 17:45

解题思路：减少循环次数

P1850

回复 0 | 赞 0 | 浏览 2.3k

这个题首先确定一个点：对于任意一行或一列，如果非0数大于等于两个，那么这一行或一列就可以全部推出，否则则无法推出。对于行来说，我们遍历一行，只要找到两个非0数，则可以通过等差数列公式算出第一项a1和等差间距d，自然就可以通过a1和d算出每一项的值。对于列同理，所以时间复杂度是O(N * M)

2022年1月19日 12:36

找不出錯誤求解

P1850

回复 0 | 赞 0 | 浏览 4.3k

説一下我的思路，就是對一行有兩個以上的行，找不爲0的兩項，爲了方便就找了最前面和最後面的兩項，結果始終無法通過。 int lo, hi; for (lo = 0; lo < m; lo++) if (a[i][lo]) break; for (hi = m - 1; hi > lo; hi--) if (a[i][hi]) break; ll x = (a[i][hi] - a[i][lo]) / (hi - lo); 而改換成找一行的前兩個不爲0的項，代碼就瞬間通過，而且對之前沒通過的數據輸出發現...

2021年3月2日 10:40

等待时机，依次处理

P1850

回复 1 | 赞 0 | 浏览 9.4k

根据题意，我们知道，这本身就是一个符合规则的等差矩阵，我们不用考虑推导出的数是否符合矩阵规则（一开始忽略这个前提，想着怎么不匹配怎么逆推撤回……）那么怎么才能推导呢？很简单，一行或者一列有两个及以上的数字确定，这一行或一列就出来了。创造一个矩阵，数字序列从[1,1]开始，[i,0]用于标识第i行是否有超过两个数字了，[i,m+1]标识这一行是否已经放入了待处理队列，防止重复处理，列一样的思想。那么我们在录入数字或者在推到一行的时候，每有一个数字不是0或者被推导出来，就更新这一行和者一列的已知数字个数，达到2个及以上且未放入待处理队列，就...

2021年3月4日 00:22

为什么mle？实在搞不懂

P1850

回复 0 | 赞 0 | 浏览 6.5k

// n1850.cpp : This file contains the 'main' function. Program execution begins and ends there. // #include <iostream> #include <iomanip> #include <fstream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include &...

2021年3月2日 02:02

P1850

回复 0 | 赞 0 | 浏览 8.6k

第一次遍历记录每行每列的公差（若存在）第二次遍历输出 #include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f //写成0x7fffffff就不对了 typedef struct record{ int num; int sit; }rec; int main(){ int n,m,i,j; &nb...

题目等差数列

题解数量5

热门题解

1 暴力解法

2 等待时机，依次处理

3 为什么mle？实在搞不懂

4 解题思路：减少循环次数

5 找不出錯誤求解