2022-05-31每日刷题打卡
代码源——每日一题
最长的 X - 题目 - Daimayuan Online Judge
给定一个由 X 和 . 组成的字符串 S。
你能对字符串 S 做以下操作 0 到 K 次（包括 0 和 K）：
将一个 . 替换为 X
请问操作完的字符串 S 中最多可能有多少个连续的 X？
输入格式
第一行一个字符串 S
第二行一个整数 K
输出格式
一个整数，表示答案
样例输入
XX...X.X.X.
2
样例输出
5
问题解析
双指针写法，为了方便我们这里先预处理一个前缀和数组，我们把字符串的’.'看成1，'X’看成0来计算前缀和。
然后快慢指针遍历前缀和数组，如果快指针r到慢指针l这一段的区间和:
小于等于k，说明这一段的‘.‘我们都可以把他们变成’X’，那么这一段都可以是‘X’，快指针走一步。
如果大于k了，说明这一段的’.‘我们并不能全变成‘k’,即这一段并不是连续的’X’，那么我们慢指针走一步，如果两个指针是在同一个位置，那么快指针也要走一步。
每次计算完一个区间值后，我们更新一下最大区间长度，最后把维护的值输出即可。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include <sstream>
#define endl '\n'
#define int ll
typedef long long ll;
typedef pair<ll, ll>PII;
typedef unsigned long long ull;
string s;
int k, n;
int sum[200005];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> s >> k;
int n=s.size();
if (k > n)
{
cout << n << endl;
return 0;
}
for (int i = 1; i <= n; i++)
{
if (s[i - 1] == 'X')sum[i] = sum[i - 1];
else sum[i] = sum[i - 1] + 1;
}
int res = 0, l = 1, r = 1;
while (r <= n)
{
if (sum[r] - sum[l - 1] <= k)
{
r++;
res = max(r - l, res);
}
else
{
if (l == r)r++;
l++;
}
}
cout << res;
return 0;
}
力扣
699. 掉落的方块
在二维平面上的 x 轴上，放置着一些方块。
给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。
在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。
输入：positions = [[1,2],[2,3],[6,1]]
输出：[2,5,5]
解释：
第 1 个方块掉落后，最高的堆叠由方块 1 组成，堆叠的最高高度为 2 。
第 2 个方块掉落后，最高的堆叠由方块 1 和 2 组成，堆叠的最高高度为 5 。
第 3 个方块掉落后，最高的堆叠仍然由方块 1 和 2 组成，堆叠的最高高度为 5 。
因此，返回 [2, 5, 5] 作为答案。
提示：
1 <= positions.length <= 10001 <= lefti <= 1081 <= sideLengthi <= 106
问题解析
线段树+离散化。
因为放置方块是以lefti为起点放置一个sideLengthi*sideLengthi的方块，我们可以把问题看成是每次给区间lefti~sideLengthi+lefti加上sideLengthi，至于下落在另一个方块上的情况，我们可以求一下这个区间的最大值，我们必然就会落在这个最大值的顶部，那么这段区间的高度就会更新为（sideLengthi+区间最大值）。所以我们需要一个能实现区间赋值+求区间最值的线段树。同时因为值的范围过大，我们要进行一下离散化。
不过有个问题，如果两个方块相邻挨着，那他们是不会叠到一起的，比如一个方块的右边界是5，另一个方块的左边界也是5，那么这两个方块应该是相邻的，而不是一个叠到另一个上。但在我们的线段树里，这个是会叠在一起的（我们算的是一个区间的最值，那么第一个方块的右边界我们也会记上），这样显然是不对的，所以我们可以把每个方块的左边界+1，而右边界不变，这样就可以杜绝这种情况的发生。
AC代码
class Solution {
public:
unordered_map<int,int>mymap;
int f[10000*4],b[10000];
void pushdown(int k,int l,int r)
{
if(b[k]!=0)
{
f[k+k]=b[k];
f[k+k+1]=b[k];
b[k+k]=b[k];
b[k+k+1]=b[k];
b[k]=0;
}
}
void revise(int k,int l,int r,int x,int y,int z)
{
if(l==x&&r==y)
{
f[k]=z;
b[k]=z;
return ;
}
pushdown(k,l,r);
int m=(l+r)/2;
if(y<=m)revise(k+k,l,m,x,y,z);
else
if(x>m)revise(k+k+1,m+1,r,x,y,z);
else
{
revise(k+k,l,m,x,m,z);
revise(k+k+1,m+1,r,m+1,y,z);
}
f[k]=max(f[k+k],f[k+k+1]);
}
int get_max(int k,int l,int r,int x,int y)
{
if(l==x&&r==y)return f[k];
pushdown(k,l,r);
int m=(l+r)/2,res=0;
if(y<=m)res=get_max(k+k,l,m,x,y);
else
if(x>m)res=get_max(k+k+1,m+1,r,x,y);
else
{
res=max(get_max(k+k,l,m,x,m),get_max(k+k+1,m+1,r,m+1,y));
}
f[k]=max(f[k+k],f[k+k+1]);
return res;
}
vector<int> fallingSquares(vector<vector<int>>& positions) {
vector<int>v,res;
vector<vector<int>>ans;
for(auto i:positions)
{
ans.push_back({i[0]+1,i[0]+i[1],i[1]});
v.push_back(i[0]+1);
v.push_back(i[1]);
v.push_back(i[0]+i[1]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int n=v.size();
for(int i=0;i<n;i++)mymap[v[i]]=i+1;
int mx=0;
for(auto i:ans)
{
int nums=get_max(1,1,n,mymap[i[0]],mymap[i[1]])+i[2];
mx=max(mx,nums);
res.push_back(mx);
revise(1,1,n,mymap[i[0]],mymap[i[1]],nums);
}
return res;
}
};
