A. 数的三次方根

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
double ans;
//结果保留六位小数，这里的eps要精确到8位小数
int main()
{
double n;
cin>>n;
double l=-1e4,r=1e4;
while(r-l>eps)
{
double mid=(l+r)/2.0;
if(mid*mid*mid>=n)
{
ans=mid;
r=mid;
}
else l=mid;
}
printf("%.6f",ans);
return 0;
}
/*
思路：
这是一道很典型的浮点二分题目，对于浮点二分，最需要注意的是它的精度。
由于结果保留6位小数，eps的精度应该为答案的后两位
*/

B. 判断子序列

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

int i = 0, j = 0;
while (i < n && j < m)
{
if (a[i] == b[j]) i ++ ;
j ++ ;
}

if (i == n) printf("Yes");
else printf("No");
return 0;
}
/*
思路：
本题考察双指针算法。
分别用两个指针指向两个数组中的元素，依次向后找，就能够做到O(n)的时间复杂度。
具体而言，如果A[i]==B[j], 那么 A[i]这个数是子序列的一部分，i++，j++，继续往后找。
如果 A[i]!=B[j] 那么 A[i]这个数所对应的B中的元素可能还在j之后，故只让j++。
找到最后，如果A中每个元素都与B中元素一一对应了，此时i应该等于n，输出yes，否则输出no
*/

C. 区间合并

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
struct node
{
int l,r;//区间的左右端点
}a[N];
bool cmp(node x,node y)
{
return x.l<y.l;//按左端点排序
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i].l >> a[i].r;
sort(a, a + n, cmp);

int end = a[0].r;
int ans = 1;
//初始化第一个区间的右端点为end
//由于不需要用到start，只需用左端点排序，所以可以不存

for(int i = 1; i < n; i ++)
{
if(a[i].l > end)
{
ans++;
end = a[i].r;
}
else
{
//l<=end，ans不增加
end=max(end,a[i].r);
}
}
cout << ans << endl;

return 0;
}
/*
思路：
先按区间的左端点从小到大排序。
在合并的过程中，后一个区间[l,r]能合并到之前的区间[start,end]的充分必要条件是l<=end。那么：
如果满足l<=end，区间数ans不增加，更新合并之后的区间范围为[start,max{end,r}]
否则，区间数增加1，新的区间的范围为[l,r]
*/

D. 最大全1矩阵

#include <bits/stdc++.h>
using namespace std;

int n,m,ans;
int a[2010][2010],b[2010][2010];
struct Node
{
int val;
int len;
};

//用单调栈方法做第x行
//此处代码与最大矩形相同，可前往那道题复习
stack<Node> s;
void work(int x)
{
Node q;
while(!s.empty()) s.pop();
int temp=0;
int sum=0;
for(int i=0; i<m; i++)
{
q.val=b[x][i];
q.len=1;
temp=0;
if(s.empty())
s.push(q);
else if(q.val<=(s.top()).val)
{
while(!s.empty()&&q.val<=(s.top().val))
{
(s.top()).len+=temp;
sum=(s.top()).val*(s.top()).len;
if(sum>ans) ans=sum;
temp=(s.top()).len;
s.pop();
}
q.len+=temp;
s.push(q);
}
else
s.push(q);
}
temp=0;
while(!s.empty())
{
(s.top()).len+=temp;
sum=(s.top()).val*(s.top()).len;
if(sum>ans) ans=sum;
temp=(s.top()).len;
s.pop();
}
}

int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j];
//预处理b矩阵
for(int j=0;j<m;j++)
{
int sum=0;//到目前为止累积的1的个数
for(int i=0;i<n;i++)
{
if(a[i][j]==1) sum++;
else sum=0;
b[i][j]=sum;
}
}
for(int i=0;i<n;i++) work(i);//对每一行做单调栈
cout<<ans<<endl;
return 0;
}
/*
思路：预处理+单调栈
先对原矩阵进行预处理，
对于第 j 列，从i==1开始依次向下扫描，
若a[i][j]==1，则计算从这个1开始向上能找到多少个连续的1
举例，对于矩阵 ：
0110111
0111110
1111110
1110011
预处理过后，就能得到：
0110111
0221220
1332330
2440041
得到了这个矩阵后，这道题便转换为了我们曾解决过的单调栈求最大矩形问题
如果有所遗忘，建议复习2022年4月双周赛（高级班）C题
总的来说，此时我们矩阵中的每个元素就相当于一个小矩形，元素的值是小矩形的高度，宽度为1，
我们只需要把每一行单独拿出来，依次做一遍最大矩形，便能解决问题。
*/