有本事就学死我（被后面两题气的直冒汗）
1 Alyone and spreadsheet{
-
题意：有一个二维的表格，现有q次询问，包含l和r，表示只保留表格中的第l行到第r行，请你判断区间中是否有至少一列满足元素不递减排列，如果有，输出YES,否则输出NO
-
思路：因为我们只要求判断是否有一列满足即可，因此我们可以先将每一列的最长不递减子序列的长度先求出来，然后再判断，如果当前区间的长度仍大于全局的最长不递减子序列的长度，则输出NO,否则一定有答案，输出YES
}
核心代码：
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i>0&&mp[i][j]>=mp[i-1][j]){
pos[j]=pos[j]+1;//最长长度+1
}
else pos[j]=1;//没有的话长度就是1
maxlen[i]=max(maxlen[i],pos[j]);//取全局最大值
}
}
2 Valient’s New map{
-
题意：有一个二维地图，你需要找出一个边长最大的正方形使得正方形覆盖的区域内的元素都不小于正方形的边长
-
思路：我们可以枚举正方形的边长。但是我们不能只是一个个枚举，因为此题正方形的边长最大能到1e6，一个一个枚举肯定会超时。因此我们可以在1到
min(n,m)，也就是地图的最短边中二分边长。
为什么能够二分？是因为这题让我们求边长的最大值，而如果一旦边长大的正方形能满足条件说明边长小的也一定能满足条件，变量具有单调性，因此我们可以二分边长，在check函数中，我们可以枚举二维地图中的每一项，如果有大于mid长度的则加入答案。
那么是不是这样就能解决问题了呢？如果我们还是一个一个去判断这里面的元素是否都能填充满整个正方形那么时间复杂度就又会变成O(n^2).所以我们只需要算出每个长度为mid的正方形部分的二维差分，判断内部元素总和是否大于mid*mid即可。
- 算法：二维前缀和差分，二分
}
核心代码：
bool check(int mid){
vector<vector<int>> sum(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(mp[i][j]>=mid);
}//计算每个大于mid的前缀和
}
for(int i=mid;i<=n;i++){
for(int j=mid;j<=m;j++){//枚举可能长度
int x=i-mid+1,y=j-mid+1;
int tot=sum[i][j]-sum[x-1][j]-sum[i][y-1]+sum[x-1][y-1];
if(tot>=mid*mid){//总和大于面积说明可行
return true;
}
}
}
return false;
}
3 To become Max{
1.题意：有一个数组，你可以选择任意一个下标，并对其对应的元素+1，前提是它的前面一个元素不小于当前元素，求经过最多k次操作后的数组中的最大可能值
- 思路：我们可以假设我们当前选择了第a[i]个元素，并假设我们要达到或超过的最大值为mid,那么如果前面的这个元素如果还是不到mid的话那么其前面一个元素就必须到达他再前面一个元素+1，如果还是小于mid的话再递推下去，直到操作次数大于限制k:
3.算法：二分
}
bool check(ll mid){
for(int i=0;i<n;i++){
ll need=mid;
ll op=0;
bool ok=true;
for(int j=i;j<n;j++){
if(a[j]>=need) break;
if(j==n-1){
ok=false;
break;
}
op+=need-a[j];
need--;
if(op>m){
ok=false;
break;
}
}
if(ok&&op<=m) return true;
}
return false;
}
4 Rudolf and k bridges{
-
题意：从第一个位置1出发，要想到达为m的位置，期间建立的节点之间的距离不能超过d-1,求最小路径值
-
思路：拆解题意，我们可以知道全局的最优解取决于每一行的最优解，因此我们可以利用线性dp+单调队列维护解决这道题
首先是状态定义：dp[j]表示当前第j位的最小花费，初始化：dp[1]=1(从起点开始),因为第1列和第m列都必须要装，因此每一行的初始花费为a[i][1]+1。
为什么要用单调队列维护？直接取一个最小值不好吗？
举个例子，假设我们目前已经选到了第j个位置，而他的上一个位置t所处的范围一定是[j-d-1,j-1]之间，而我们的dp转移则是min(dp[t])+m[i]+dp[j]//m[i]指当前深度，而min(dp[t])则是指的[j-d-1,j-1]这一范围内的最小值，因此光是标记无法满足区间的多次动态移动，而像这种动态窗口我们就需要用单调队列来维护区间最小值。最后将每一行的dp[n]作为答案计入最终的cost[i]，最后用前缀和求解
- 算法：线性dp，单调队列
}
for(int i=0;i<n;i++){
vector<ll> dp(m,INF);
deque<int> q;
dp[0]=1;
q.push_back(0);
for(int j=1;j<m;j++){
while(!q.empty()&&j-q.front()-1>d) q.pop_front();//间隔超限
dp[j]=dp[q.front()]+mp[i][j]+1;//当前最小花费
while(!q.empty()&&dp[j]<=dp[q.back()]) q.pop_back();//保证当前值最小
q.push_back(j);//继续枚举深度
}
cost[i]=dp[m-1];
}
5 Messenger in MAC{
-
题意：有一组消息，你可以选择任意几个消息，规定阅读这些消息所要花的时间为
sum(a)+sum(|b[i+1]-b[i]|),你需要告知用户，在不超过l的时间范围内最多能阅读多少条消息 -
思路：首先要对计算时间的公式进行拆解。Sum(a)就是求已选择的信息a之和就行，关键在于如何拆解sum(|b[i+1]-b[i]|)。
我们先列一下完整的式子：|b[i]-b[i+1]|+|b[i+1]-b[i+2]|+...+|b[n]-b[n-1]|。通过观察不难发现，这就是在求b的每一项在数轴上的距离，而如果我们要是对b数组进行排序的话则原式可以简化成：max(b)-min(b)
但因为我们这题要求我们告诉用户在不超过规定时间能读的最多消息数，所以我们在时间超限时，直接删除所占的a最多的消息就行了，b是最大值和最小值相减，不会受影响。因此这题我们还要用大跟堆来维护所选消息中所占a最大的消息，一旦时间超限，循环删去堆顶元素即可
- 算法：优先队列
}
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
cin >> t;
while(t--){
ll n,l;
cin >> n >> l;
vector<pair<ll,ll>> temp(n);
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
temp[i]={b,a};
}
sort(temp.begin(),temp.end());//要以b按升序排，好计算max(b)-min(b)
int ans=0;
for(int i=0;i<n;i++){
ll suma=0;
priority_queue<ll> pq;//大根堆维护a的值按最大值的顺序排
for(int j=i;j<n;j++){
suma+=temp[j].second;//计算sum(a)
pq.push(temp[j].second);
ll s=temp[j].first-temp[i].first;//计算max(b)-min(b)
while(!pq.empty()&&suma+s>l){
suma-=pq.top();
pq.pop();
}
ans=max(ans,(int)pq.size());
}
}
cout<<ans<<endl;
}
}
6 Set to Max{
-
题意：有两个数组，对于第一个数组，你可以选择任意区间[l,r]并将区间内的所有元素都赋值为当前区间的最大值，求数组a最终是否能变成数组b,输出YES,NO
-
思路：这题的数组长度一度达到2e5,一个一个遍历枚举区间再算区间内的最大值是一定超时的，所以我们最先应该想到的算法就是ST表，实现
O(1)级别的区间最值查询。然后就是怎么判断当前区间内的最大值可以成为答案。我们可以假设我们现在枚举到了第i位，令v为b[i],也就是第二个数组的第i项，那么我们当前的值a[i]是不能大于v的，因为如果当前值更大，那么之后覆盖过来的值就永远不可能更小，因此直接判NO.如果不满足a[i]>v,那么等于的情况可以直接不用管，如果是小于就先将其下标存起来，避免之后进行不必要的遍历。遍历时，如果是需要进行改变的下标，我们可以选择遍历寻找第一个不小于当前下标的下标。当然那是不可能的，当然是直接二分查找第一个大于当前下标的下标，令l等于当前下标的值，令r等于当前下标的下一位的值。
查询l到r之间的最值的事情我们可以交给ST表，关键是怎么判断当前最大值可行的问题
我们可以假设当前的b[i]值为v,枚举每个可能的区间。如果我们当前区间[l,i]或者是[r,i]中的最大值大于v,则我们无法将整个区间内的所有值给赋值为b[i],也就意味着无法与b数组实现相等。同理，如果b数组中的当前区间的最小值不是v，而是比v更小，则赋值过后的v会变的比预期值更大，也无法将数组a变成数组b,
因此我们的判定条件为max(a)>=v&&max(b)<=v
- 算法：ST表，二分，贪心
}
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int LOG=20;
int lg[N],st1[N][LOG],st2[N][LOG];
int query1(int l,int r){//查询区间最大值
int k=lg[r-l+1];
return max(st1[l][k],st1[r-(1<<k)+1][k]);
}
int query2(int l,int r){//查询区间最小值
int k=lg[r-l+1];
return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
int main(){
int t;
cin >> t;
lg[1]=0;
for(int i=2;i<N;i++) lg[i]=lg[i/2]+1;
while(t--){
int n;
cin >> n;
vector<int> a(n+1),b(n+1);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i];
bool ok=true;
for(int i=1;i<=n;i++){
if(a[i]>b[i]){ ok=false; break;}
}
if(!ok){
cout<<"NO"<<endl;
continue;
}//构建ST表
for(int i=1;i<=n;i++) st1[i][0]=a[i];
for(int i=1;i<=n;i++) st2[i][0]=b[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
}
}
vector<vector<int>> pos(n+1);
for(int i=1;i<=n;i++){
if(a[i]<=n) pos[a[i]].push_back(i);//标记需要改变的
}
for(int i=1;i<=n&&ok;i++){
if(a[i]==b[i]) continue;
int v=b[i];
auto &vos=pos[v];
if(vos.empty()){
ok=false;
break;
}
int l=-1,r=-1;
auto it=lower_bound(vos.begin(),vos.end(),i);
if(it!=vos.begin()) l=*prev(it); //最近左端点
if(it!=vos.end()) r=*it;//最近右端点
bool can=false;
if(l!=-1&&query1(l,i)<=v&&query2(l,i)>=v) can=true;//满足贪心策略
if(!can&&r!=-1&&query1(i,r)<=v&&query2(i,r)>=v) can=true;
if(!can){
ok=false;
break;
}
}
cout<<(ok?"YES":"NO")<<endl;
}
}
评论
0