杭电第一场补题
1008.Maximal submatrix题解
Given a matrix of n rows and m columns,find the largest area submatrix which is non decreasing on each column
就是给定一个n*m的矩阵，找出最大的满足列非递减的区域面积。
这道题我刚开始使用的动态规划，也是先对矩阵进行预处理，然后用dp[i][j]表示以nums[i][j]为右下角的最大的满足题意的矩形面积，本算法的时间复杂度为,经过测试，最终超出了时间限制。这是我的第一次代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int T, N, M;
const int MaxN = 2001, MaxM = 2001;
int m[MaxN][MaxM];
int s[MaxN][MaxM];
int dp[MaxN][MaxM];
int res = 0;
int main(){
cin >> T;
while(T--){
cin >> N;
cin >> M;
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
// cin >> m[i][j];
scanf("%d", &m[i][j]);
if(i == 0){
s[i][j] = 1;
}else{
if(m[i][j] >= m[i-1][j]){
s[i][j] = s[i-1][j] + 1;
}else{
s[i][j] = 1;
}
}
int min_len = s[i][j];
//这里对下标nums[i][j],min_len最大高度，表示在本行中，依次对本行前面的下标进行计算，取最大即可。这也是时间爆掉的原因，这里我们使用单调栈
for(int k = j - 1; k >= 0; k--){
min_len = std::min(min_len, s[i][k]);
dp[i][j] = std::max(dp[i][j], (j-k+1)*min_len);
}
res = max(res, dp[i][j]);
}
}
cout << res << endl;
}
}
经过校队同学的讲解，这道题目应该用单调栈来解决，关于悬线法，OI-WIKI有详细的介绍，其可以采用单调栈的方法来求解。
关于单调栈的使用，我们可以得到如下题解：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
int T, N, M;
const int MaxN = 2001, MaxM = 2001;
int m[MaxN][MaxM];
int s[MaxN][MaxM];
int res = 0;
std::stack<int> st;
int main(){
cin >> T;
while(T--){
res = 0;
st = stack<int>();
cin >> N;
cin >> M;
//预处理
for(unsigned i = 0; i < MaxN; ++i) {
memset(s[i], 0, sizeof(s[i]));
memset(m[i], 0, sizeof(m[i]));
}
for (int i = 0; i < N; ++i){
for (int j = 1; j <= M; ++j){
// cin >> m[i][j];
scanf("%d", &m[i][j]);
if(i == 0){
s[i][j] = 1;
}else{
if(m[i][j] >= m[i-1][j]){
s[i][j] = s[i-1][j] + 1;
}else{
s[i][j] = 1;
}
}
}
}
//计算
for(unsigned i = 0; i < N; ++i) {
st = stack<int>();
int area = 0;
//最后一个为0，相当于增加一个哨兵
for(unsigned j = 0; j <= M+1; ++j) {
while(!st.empty() && s[i][j] < s[i][st.top()]){
int pop_index = st.top();
st.pop();
int pre_index = st.top();
area = (j - pre_index - 1) * s[i][pop_index];
// cout << " ----------" << area << endl;
res = max(res, area);
}
st.push(j);
}
}
cout << res << endl;
}
return 0;
}
关于单调栈的模板，我们可以在首尾增加0来简化特殊情况判断，所以对于本题单调栈，模板为：
vector<int>& v;
stack<int> &st;
v.insert(v.begin(), 0);
v.push_back(0);
for(int i = 0; i < v.size(); i++){
while(!v.empty() && v[i] < v[st.top()]){
int cur = st.top();
st.pop();
res = max(res, (i - st.top()-1)*v[cur] );
}
st.push(i);
}
return res;
1005.Minimum spanning tree
Problem Description
Given n-1 points, numbered from 2 to n, the edge weight between the two points a and b is lcm(a, b). Please find the minimum spanning tree formed by them.
A minimum spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.
lcm(a, b) is the smallest positive integer that is divisible by both a and b.
题意：给n-1个节点，每个节点之间权重为lcm(a,b),最小公倍数，求出最小连通子图的代价。
解题思路：
- 对于素数我们取其到2的权重，就是
- 对于非素数，就是其自身
我们可以使用线性筛来求解素数。
线性筛
const int N = 1e7+7;
int pri[N]; //存储素数
int cnt; //素数的个数
bool ispri[N]; //是否为素数
for(int i = 2; i < N; i++){
ispri[i] = false;
}
for(int i = 2; i < N; i++){
if(ispri[i]){
pri[cnt++] = i;
}
for(int j = 0; j <= cnt; j++){
if(i * cnt >= N) break;
ispri[i * pri[j]] = 0; //不满足条件 剔
if(i % pri[j] == 0) break; //后面的不找了
}
}
由于本题的查询较多，所以应该先把答案数组打印：
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
const int N = 1e7+7;
int pri[N]; //存储素数
int cnt = 0; //素数的个数
bool ispri[N]; //是否为素数
ll ans[N];
int getPri(){
for(int i = 2; i < N; i++){
ispri[i] = true;
}
for(int i = 2; i < N; i++){
if(ispri[i]){
pri[cnt++] = i;
}
for(int j = 0; j <= cnt; j++){
if(i * pri[j] >= N) break;
ispri[i * pri[j]] = 0; //不满足条件 剔
if(i % pri[j] == 0) break; //后面的不找了
}
}
}
int main(int argc, char * argv[]){
getPri();
ms(ans);
int T , m;
cin >> T;
for(int i = 3; i < N; i++){
if(ispri[i]) ans[i] = ans[i-1] + (i << 1);
else ans[i] = ans[i-1] + i;
}
while(T--){
cin >> m;
cout << ans[m] << endl;
}
return 0;
}
线性筛模板：
int getPri(){
const int N = 1e7+7;
int pri[N]; //存储素数
int cnt = 0; //素数的个数
bool ispri[N]; //是否为素数
for(int i = 2; i < N; i++){
ispri[i] = true;
}
for(int i = 2; i < N; i++){
if(ispri[i]){
pri[cnt++] = i;
}
for(int j = 0; j <= cnt; j++){
if(i * pri[j] >= N) break;
ispri[i * pri[j]] = 0; //不满足条件 剔
if(i % pri[j] == 0) break; //后面的不找了
}
}
}