广州商城网站建设公司,深圳官网,开网络公司需要多少资金,杭州网站改版公司电话本文涉及的基础知识点
本博文代码打包下载
C二分查找
[GDCPC2023] Path Planning
题面翻译
【题目描述】
有一个 n n n 行 m m m 列的网格。网格里的每个格子都写着一个整数#xff0c;其中第 i i i 行第 j j j 列的格子里写着整数 a i , j a_{i, j} ai,j。从 0…本文涉及的基础知识点
本博文代码打包下载
C二分查找
[GDCPC2023] Path Planning
题面翻译
【题目描述】
有一个 n n n 行 m m m 列的网格。网格里的每个格子都写着一个整数其中第 i i i 行第 j j j 列的格子里写着整数 a i , j a_{i, j} ai,j。从 0 0 0 到 ( n × m − 1 ) (n \times m - 1) (n×m−1) 的每个整数含两端在网格里都恰好出现一次。
令 ( i , j ) (i, j) (i,j) 表示位于第 i i i 行第 j j j 列的格子。您现在需要从 ( 1 , 1 ) (1, 1) (1,1) 出发并前往 ( n , m ) (n, m) (n,m)。当您位于格子 ( i , j ) (i, j) (i,j) 时您可以选择走到右方的格子 ( i , j 1 ) (i, j 1) (i,j1)若 j m j m jm也可以选择走到下方的格子 ( i 1 , j ) (i 1, j) (i1,j)若 i n i n in。
令 S \mathbb{S} S 表示路径上每个格子里的整数形成的集合包括 a 1 , 1 a_{1, 1} a1,1 和 a n , m a_{n, m} an,m。令 mex ( S ) \text{mex}(\mathbb{S}) mex(S) 表示不属于 S \mathbb{S} S 的最小非负整数。请找出一条路径以最大化 mex ( S ) \text{mex}(\mathbb{S}) mex(S)并求出这个最大的值。
【输入格式】
有多组测试数据。第一行输入一个整数 T T T 表示测试数据组数。对于每组测试数据
第一行输入两个整数 n n n 和 m m m 1 ≤ n , m ≤ 1 0 6 1 \le n, m \le 10^6 1≤n,m≤106 1 ≤ n × m ≤ 1 0 6 1 \le n \times m \le 10^6 1≤n×m≤106表示网格的行数和列数。
对于接下来 n n n 行第 i i i 行输入 m m m 个整数 a i , 1 , a i , 2 , ⋯ , a i , m a_{i, 1}, a_{i, 2}, \cdots, a_{i, m} ai,1,ai,2,⋯,ai,m 0 ≤ a i , j n × m 0 \le a_{i, j} n \times m 0≤ai,jn×m其中 a i , j a_{i, j} ai,j 表示格子 ( i , j ) (i, j) (i,j) 里的整数。从 0 0 0 到 ( n × m − 1 ) (n \times m - 1) (n×m−1) 的每个整数含两端在网格里都恰好出现一次。
保证所有数据 n × m n \times m n×m 之和不超过 1 0 6 10^6 106。
【输出格式】
每组数据输出一行一个整数表示最大的 mex ( S ) \text{mex}(\mathbb{S}) mex(S)。
【样例解释】
对于第一组样例数据共有 3 3 3 条可能的路径。
第一条路径为 ( 1 , 1 ) → ( 1 , 2 ) → ( 1 , 3 ) → ( 2 , 3 ) (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) (1,1)→(1,2)→(1,3)→(2,3)。 S { 1 , 2 , 4 , 5 } \mathbb{S} \{1, 2, 4, 5\} S{1,2,4,5} 因此 mex ( S ) 0 \text{mex}(\mathbb{S}) 0 mex(S)0。第二条路径为 ( 1 , 1 ) → ( 1 , 2 ) → ( 2 , 2 ) → ( 2 , 3 ) (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) (1,1)→(1,2)→(2,2)→(2,3)。 S { 1 , 2 , 0 , 5 } \mathbb{S} \{1, 2, 0, 5\} S{1,2,0,5} 因此 mex ( S ) 3 \text{mex}(\mathbb{S}) 3 mex(S)3。第三条路径为 ( 1 , 1 ) → ( 2 , 1 ) → ( 2 , 2 ) → ( 2 , 3 ) (1, 1) \to (2, 1) \to (2, 2) \to (2, 3) (1,1)→(2,1)→(2,2)→(2,3)。 S { 1 , 3 , 0 , 5 } \mathbb{S} \{1, 3, 0, 5\} S{1,3,0,5} 因此 mex ( S ) 2 \text{mex}(\mathbb{S}) 2 mex(S)2。
因此答案为 3 3 3。
对于第二组样例数据只有 1 1 1 条可能的路径即 ( 1 , 1 ) → ( 1 , 2 ) → ( 1 , 3 ) → ( 1 , 4 ) → ( 1 , 5 ) (1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5) (1,1)→(1,2)→(1,3)→(1,4)→(1,5)。 S { 1 , 3 , 0 , 4 , 2 } \mathbb{S} \{1, 3, 0, 4, 2\} S{1,3,0,4,2} 因此 mex ( S ) 5 \text{mex}(\mathbb{S}) 5 mex(S)5。
题目描述
There is a grid with n n n rows and m m m columns. Each cell of the grid has an integer in it, where a i , j a_{i, j} ai,j indicates the integer in the cell located at the i i i-th row and the j j j-th column. Each integer from 0 0 0 to ( n × m − 1 ) (n \times m - 1) (n×m−1) (both inclusive) appears exactly once in the grid.
Let ( i , j ) (i, j) (i,j) be the cell located at the i i i-th row and the j j j-th column. You now start from ( 1 , 1 ) (1, 1) (1,1) and need to reach ( n , m ) (n, m) (n,m). When you are in cell ( i , j ) (i, j) (i,j), you can either move to its right cell ( i , j 1 ) (i, j 1) (i,j1) if j m j m jm or move to its bottom cell ( i 1 , j ) (i 1, j) (i1,j) if i n i n in.
Let S \mathbb{S} S be the set consisting of integers in each cell on your path, including a 1 , 1 a_{1, 1} a1,1 and a n , m a_{n, m} an,m. Let mex ( S ) \text{mex}(\mathbb{S}) mex(S) be the smallest non-negative integer which does not belong to S \mathbb{S} S. Find a path to maximize mex ( S ) \text{mex}(\mathbb{S}) mex(S) and calculate this maximum possible value.
输入格式
There are multiple test cases. The first line of the input contains an integer T T T indicating the number of test cases. For each test case:
The first line contains two integers n n n and m m m ( 1 ≤ n , m ≤ 1 0 6 1 \le n, m \le 10^6 1≤n,m≤106, 1 ≤ n × m ≤ 1 0 6 1 \le n \times m \le 10^6 1≤n×m≤106) indicating the number of rows and columns of the grid.
For the following n n n lines, the i i i-th line contains m m m integers a i , 1 , a i , 2 , ⋯ , a i , m a_{i, 1}, a_{i, 2}, \cdots, a_{i, m} ai,1,ai,2,⋯,ai,m ( 0 ≤ a i , j n × m 0 \le a_{i, j} n \times m 0≤ai,jn×m) where a i , j a_{i, j} ai,j indicates the integer in cell ( i , j ) (i, j) (i,j). Each integer from 0 0 0 to ( n × m − 1 ) (n \times m - 1) (n×m−1) (both inclusive) appears exactly once in the grid.
It’s guaranteed that the sum of n × m n \times m n×m of all test cases will not exceed 1 0 6 10^6 106.
输出格式
For each test case output one line containing one integer indicating the maximum possible value of mex ( S ) \text{mex}(\mathbb{S}) mex(S).
样例 #1
样例输入 #1
2
2 3
1 2 4
3 0 5
1 5
1 3 0 4 2样例输出 #1
3
5提示
For the first sample test case there are 3 3 3 possible paths.
The first path is ( 1 , 1 ) → ( 1 , 2 ) → ( 1 , 3 ) → ( 2 , 3 ) (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) (1,1)→(1,2)→(1,3)→(2,3). S { 1 , 2 , 4 , 5 } \mathbb{S} \{1, 2, 4, 5\} S{1,2,4,5} so mex ( S ) 0 \text{mex}(\mathbb{S}) 0 mex(S)0.The second path is ( 1 , 1 ) → ( 1 , 2 ) → ( 2 , 2 ) → ( 2 , 3 ) (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) (1,1)→(1,2)→(2,2)→(2,3). S { 1 , 2 , 0 , 5 } \mathbb{S} \{1, 2, 0, 5\} S{1,2,0,5} so mex ( S ) 3 \text{mex}(\mathbb{S}) 3 mex(S)3.The third path is ( 1 , 1 ) → ( 2 , 1 ) → ( 2 , 2 ) → ( 2 , 3 ) (1, 1) \to (2, 1) \to (2, 2) \to (2, 3) (1,1)→(2,1)→(2,2)→(2,3). S { 1 , 3 , 0 , 5 } \mathbb{S} \{1, 3, 0, 5\} S{1,3,0,5} so mex ( S ) 2 \text{mex}(\mathbb{S}) 2 mex(S)2.
So the answer is 3 3 3.
For the second sample test case there is only 1 1 1 possible path, which is ( 1 , 1 ) → ( 1 , 2 ) → ( 1 , 3 ) → ( 1 , 4 ) → ( 1 , 5 ) (1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5) (1,1)→(1,2)→(1,3)→(1,4)→(1,5). S { 1 , 3 , 0 , 4 , 2 } \mathbb{S} \{1, 3, 0, 4, 2\} S{1,3,0,4,2} so mex ( S ) 5 \text{mex}(\mathbb{S}) 5 mex(S)5.
二分查找
Can(x)函数 是否存在某条路径经过[0…x]所有数字。 将[0…x]的行列号放到v中按先行后列升序排序。 v[i]的行列号一定大于等于v[i-1]的行列号否则返回false。 二分类型寻找尾端求最大x使得Can(x)成立。 参数范围[0,mn-2] 整个路径的长度为mn-1最多[0,mn-2]。 返回值二分返回值1。
代码
核心代码
#include iostream
#include sstream
#include vector
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring#include bitset
using namespace std;templateclass T int
vectorT Read(int n,const char* pFormat %d) {vectorT ret(n);for(int i0;in;i) {scanf(pFormat, ret[i]); }return ret;
}templateclass T int
vectorT Read( const char* pFormat %d) {int n;scanf(%d, n);vectorT ret;T d;while (n--) {scanf(pFormat, d);ret.emplace_back(d);}return ret;
}string ReadChar(int n) {string str;char ch;while (n--) {do{scanf(%c, ch);} while ((\n ch));str ch;}return str;
}
templateclass T1,class T2
void ReadTo(pairT1, T2 pr) {cin pr.first pr.second;
}templateclass INDEX_TYPE
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex) :m_iMin(iMinIndex), m_iMax(iMaxIndex) {}templateclass _PrINDEX_TYPE FindFrist(_Pr pr){auto left m_iMin - 1;auto rightInclue m_iMax;while (rightInclue - left 1){const auto mid left (rightInclue - left) / 2;if (pr(mid)){rightInclue mid;}else{left mid;}}return rightInclue;}templateclass _PrINDEX_TYPE FindEnd(_Pr pr){INDEX_TYPE leftInclude m_iMin;INDEX_TYPE right m_iMax 1;while (right - leftInclude 1){const auto mid leftInclude (right - leftInclude) / 2;if (pr(mid)){leftInclude mid;}else{right mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {
public:int Ans(vectorvectorint mat) {const int R mat.size(), C mat[0].size();const int len R C - 1;vectorpairint, int v(len);for (int r 0; r R; r)for (int c 0; c C; c) {if (mat[r][c] len){v[mat[r][c]] make_pair(r, c);}}auto Cnt [](int x) {vectorpairint, int tmp(v.begin(), v.begin() x 1);sort(tmp.begin(), tmp.end());for (int i 1; i tmp.size(); i) {if ((tmp[i].first tmp[i - 1].first) || (tmp[i].second tmp[i - 1].second)) { return false; }}return true;};return CBinarySearchint(0, len - 1).FindEnd(Cnt) 1;}
};int main() {
#ifdef _DEBUGfreopen(a.in, r, stdin);
#endif // DEBUGint T; cin T;for (int i 0; i T; i){int R, C;cin R C;vectorvectorint mat(R);for (int r 0; r R; r) { mat[r] Readint(C); }
#ifdef _DEBUG //Out(mat, mat);#endif auto res Solution().Ans(mat);cout res std::endl;}return 0;
}单元测试
vectorvectorint mat;TEST_METHOD(TestMethod11){mat { {1,2,4},{3,0,5} } ;auto res Solution().Ans(mat);AssertEx(3, res);}TEST_METHOD(TestMethod12){mat { {1,3,0,4,2} };auto res Solution().Ans(mat);AssertEx(5, res);} 扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
