算法训练营题目合集-已转档.pdf-资料库

最大红矩形时间限制：10 sec 空间限制：256 MB 问题描述有一个 n*m 的棋盘，棋盘上的每个点都是红的或绿的。你需要找出一个面积最大的矩形区域，使得其中没有绿的格子。输入格式第一行 2 个正整数 n,m，描述棋盘尺寸。接下来 n 行描述这个棋盘，每行 m 个字符，每个字符为 . 或 X，其中 . 表示这个位置是红色的，X 表示这个位置是绿色的。输出格式一行一个整数，表示最大面积。样例输入 4 5 ..... XXXXX .X... ..... 样例输出 6 1

样例解释以第 3 行第 3 列的方格为左上角，第 4 行第 5 列的方格为右下角的矩形区域是全红的矩形中面积最大的。数据范围对于 30% 的数据，n,m<=100；对于 60% 的数据，n,m<=400；对于 85% 的数据，n,m<=1,000；对于 100% 的数据，n,m<=1,500。提示 [这道题与“直方图最大面积”一题有什么关系呢？] 代码: #include #include using namespace std; /*此题可用直方图最大面积的题目中的方法来计算最大红矩形面积即将此题中的数据构造为直方图，例如.X. ... ... 则(0,0)的直方图高度为1,(0,1)为0,(1,0)为2,(1,1)为1(当前行'.'减去上一个'X'所在行数所形成的高度) */ int main() { int n, m; cin >> n >> m;//读入行数和列数 stack* N_X = new stack[m]; /*新建一组堆栈，用于构造当前行中某列所构造的直方图的高度堆栈顶部存有当前列最近遇到的'X’字符所在的行数n'，当读入字符为'.'时，使用当前行数 n减去n'即可得到用于构造当前行中某列所构造的直方图的高度 2

*/ for (int i = 0; i < m; i++) N_X[i].push(-1);//栈的初始化，将-1压入栈(例如第0行高度为1，0-(-1)=1) stack TEMP;//初始栈，用于上面所获得的存储直方图的高度 char** matrix = new char*[n];//建立一个char型n*m的二维矩阵并初始化 for (int i = 0; i < n; i++) { } matrix[i] = new char[m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> matrix[i][j];//将数据读入二维矩阵中 //'.'表示红，'X'表示绿 if (matrix[i][j] == '.')//若遇到红点，则直接将该行该列的直方图的高度压入初始栈TEMP中 { } int height = i - N_X[j].top();//获得直方图高度 TEMP.push(height); else if (matrix[i][j] == 'X')//若遇到绿点，则将高度0压入栈中，并向N_X栈压入当前列中X所处的行数 TEMP.push(0); N_X[j].push(i); { } } TEMP.push(0);/*当用于在下面中打印输出每一行的直方图高度，若无此句，则有可能会将多行的直方图高度加在一起进行输出例如: ..... XXXXX .X... ..... 由于栈是先进后出，故下面的代码会认为最大高度为8(即从第20个~13个元素均为直方图面积，高度为1) } 而正确的答案是6 */ //以下为原直方图最大面积中的源代码 stack H;//用于存储高度 3

stack N;//用于存储下标 int maxRect = 0; int tempRect = 0; H.push(-1);//压入一个哨位节点，用于卡位 int temp;//用于读取最初的数据 int num = n * m + n;//由于每一行多一个0，所需读取的数目为n*m+n for (int k = 0; k < num; k = k) { if (N.empty() || H.top() <= TEMP.top())//若TEMP中栈顶所存在的直方图的高度比H中栈顶的高度小，说明可以压入栈，即点是普通点，非Low或High点（卡位点) { } H.push(TEMP.top()); N.push(k); TEMP.pop(); k++; else//若H.top() > TEMP.top()，说明遇到了卡位点（High点）,此时应将H和N中的元素弹出一个（是否弹出多个等待下一轮循环再进行检测) { temp = N.top(); N.pop(); if (!N.empty()) { tempRect = (k - N.top() - 1)*H.top();//需要先弹出一个N中的栈顶元素然后再乘以H.top()，因为原先N中栈顶元素的左边可能存在应该加上的直方图面积 //具体原因请见附件Excel演示 } else//如果弹出一个元素后为空，说明N原先栈顶中左边的直方图面积为 H.top()*N.top()，即原先N栈顶元素左边直方图面积的长为N.top一直到0 { } tempRect = k * H.top(); H.pop(); if (tempRect > maxRect) maxRect = tempRect; } } while (!N.empty())//当遍历完所有直方图时，需要再次清空N，若N中存在元素，则有可能所获得错误的直方图面积最大值 //以下代码类似于上面for循环中的else代码 { 4

temp = N.top(); N.pop(); if (!N.empty()) { tempRect = (num - N.top() - 1)*H.top();//需要先弹出一个N中的栈顶元素然后再乘以H.top()，因为原先N中栈顶元素的左边可能存在应该加上的直方图面积 //具体原因请见附件Excel演示 } else//如果弹出一个元素后为空，说明N原先栈顶中左边的直方图面积为 H.top()*(N.top()-1)，即原先N栈顶元素左边直方图面积的长为N.top一直到0 { } tempRect = num * H.top(); H.pop(); if (tempRect > maxRect) maxRect = tempRect; } cout << maxRect << endl; return 0; } 数字盒子问题描述你有一个盒子，你可以往里面放数，也可以从里面取出数。初始时，盒子是空的，你会依次做 Q 个操作，操作分为两类： 1. 插入操作：询问盒子中是否存在数 x，如果不存在则把数 x 丢到盒子里。 2. 删除操作：询问盒子中是否存在数 x，如果存在则取出 x。对于每个操作，你需要输出是否成功插入或删除。输入第一行一个正整数 Q，表示操作个数。接下来 Q 行依次描述每个操作。每行 2 个用空格隔开的非负整数 op,x 描述一个操作： op 表示操作类型，op=1 则表示这是一个插入操作，op=2 则表示这是一个删除操作；x 的意义与操作类型有关，具体见题目描述。 5

输出按顺序对所有操作输出，对于每个操作输出一行，如果成功则输出“Succeeded”（不含引号），如果失败则输出“Failed”（不含引号）。样例输入 6 1 100 1 100 2 100 1 200 2 100 2 200 样例输出 Succeeded Failed Succeeded Succeeded Failed Succeeded 数据范围对于 60% 的数据，保证 x<10^5。对于 100% 的数据，保证 x<10^18，Q≤5*10^5。对于所有数据，保证 op∈{1,2}。时间限制：10 sec 空间限制：256 MB 6

提示 [对于 x 较小的情况，我们只需要用数组记录每个数是否在盒子里即可。] [对于 x 较大的情况，我们可不可以用什么方法把它们“变小”呢？可以想想哈希表哦！] 代码 #include #include #include #include using namespace std; int main() { unordered_map HashMap_0; unordered_map ::iterator iter; int n; cin >> n; string* str=new string[n];//用于存储输出的Succeeded或Failed int choic;//用于选择功能 string key; for (int i = 0; i < n; i++) { cin >> choic; if (choic == 1)//向map中插入key { } getline(cin, key);//获取输入的字符串 iter = HashMap_0.find(key);//查找map中是否存在相同的key if (iter != HashMap_0.end())//若存在相同的key则不进行操作并返回Failed { } str[i] = "Failed"; else//若不存在相同的key则放入并提示Succeeded { } HashMap_0.emplace(key, 1); str[i] = "Succeeded"; else if(choic == 2)//从map中删除key { 7

getline(cin, key);//获取输入的字符串 iter = HashMap_0.find(key);//查找map中是否存在相同的key if (iter != HashMap_0.end())//若存在相同的key则进行删除并返回Succeeded { } HashMap_0.erase(iter); str[i] = "Succeeded"; else//若不存在相同的key则返回Failed { } str[i] = "Failed"; } } for (int i = 0; i < n; i++) { } cout << str[i] << endl; return 0; 重编码 } 问题描述有一篇文章，文章包含 nn 种单词，单词的编号从 11 至 nn，第 i 种单词的出现次数为 wiwi。现在，我们要用一个 2 进制串（即只包含 0 或 1 的串） sisi 来替换第 i 种单词，使其满足如下要求：对于任意的 1≤i,j≤n,i≠j1≤i,j≤n,i≠j，都有 sisi 不是 sjsj 的前缀。（这个要求是为了避免二义性）你的任务是对每个单词选择合适的 sisi，使得替换后的文章总长度（定义为所有单词出现次数与替换它的二进制串的长度乘积的总和）最小。求这个最小长度。字符串 S1S1（不妨假设长度为 nn）被称为字符串 S2S2 的前缀，当且仅当：S2S2 的长度不小于 nn，且 S1S1 与 S2S2 前 nn 个字符组组成的字符串完全相同。输入格式第一行一个整数 nn，表示单词种数。第 2 行到第 n+1n+1 行，第 i+1i+1 行包含一个正整数 wiwi，表示第 ii 种单词的出现次数。 8

资料库

算法训练营题目合集-已转档.pdf

相关推荐

课程资源

热门标签

最新资料