7.16做题总结

今日也是让我看到了繁神的ACM历程，确实，我觉得繁神的历程里面确实有一句很好

不想打算法竞赛了。这是因为有别的事情要做，不是因为我打不动。
  
不想打比赛凌晨两点才睡了。因为我会困。
  
不想在群里和高水平选手水群了，因为我想独处。
  
不想去打区域赛，和 ICPC 选手多交流什么了，因为感觉中国选手都没几个好好打的。
  
不想出题了，一是因为我菜，二是因为我没有时间。
  
不想一年拉着队友训练三百场，因为我更想读读论文。
  
不想把过多意义投入到比赛中，因为这不是我想看到自己的样子，也不会让我成为我想看到的未来自己的样子。

 好了，话不多说，进入正题

P4653 [CEOI2017] Sure Bet

 题意：就是说给你a，b两组灯泡，然后问你什么时候才有最大的最小可能收益

思路：先从大到小排序，因为你价值越大，你的最小可能收益才会越大，因此，我们排序之后，先将，L指针指向a数组，R指针指向b数组，然后，我们现将b数组的最大值加进来，然后如果a的总价值小于b，然后就加进来一个a的灯泡，然后依次让指针往后走，然后找出这个过程中的最大的最小权值即可，灰常的简单

#include<bits/stdc++.h>
using namespace std;
#define int long longint n;
double a[100005];
double b[100005];
double suma,sumb;
int l,r;
double ans;
bool cmp(double a,double b)
{return a>b;
}double Max(double a,double b)
{return a>b?a:b;
}double Min(double a,double b)
{return a<b?a:b;
}signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp);for(r=1;r<=n;r++){sumb+=b[r];ans=Max(ans,Min(sumb-l-r,suma-l-r));while(suma<sumb&&l<=n){suma+=a[++l];ans=Max(ans,Min(sumb-l-r,suma-l-r));}}printf("%.4lf\n",ans);return 0;
}

P2216 [HAOI2007] 理想的正方形

题意：就是说给你一个矩阵，然后问你找出一个n*n的矩阵，然后找出每块矩阵的最大值和最小的差的小值

思路：二维单调队列秒了，先用单调递增队列先对行进行求单调递增队列，然后再对已经变换过的行的数组再对列进行求最大值，反正就是先对行变化，再对列变换

最小值同理，二维单调队列就解决了

#include<bits/stdc++.h>
using namespace std;
#define int long longint n,m,k;
int a[1005][1005];
deque<int> q;
int premax_x[1005][1005];
int premax_y[1005][1005];
int premin_x[1005][1005];
int premin_y[1005][1005];signed main()
{cin>>n>>m>>k;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}//先求极大值//先在行求最大值 for(int i=1;i<=n;i++){q.clear();for(int j=1;j<=m;j++){if(!q.empty()&&j-q.front()>=k){q.pop_front();}while(!q.empty()&&a[i][j]>a[i][q.back()]){q.pop_back();}q.push_back(j);if(j>=k){premax_x[i][j]=a[i][q.front()];}}}//列也求最大值for(int i=1;i<=m;i++){q.clear();for(int j=1;j<=n;j++){if(!q.empty()&&j-q.front()>=k){q.pop_front();}while(!q.empty()&&premax_x[j][i]>premax_x[q.back()][i]){q.pop_back();}q.push_back(j);if(j>=k){premax_y[j][i]=premax_x[q.front()][i];}}} //再求极小值 //先在行求最小值 for(int i=1;i<=n;i++){q.clear();for(int j=1;j<=m;j++){if(!q.empty()&&j-q.front()>=k){q.pop_front();}while(!q.empty()&&a[i][j]<a[i][q.back()]){q.pop_back();}q.push_back(j);if(j>=k){premin_x[i][j]=a[i][q.front()];}}}//列也求最小值for(int i=1;i<=m;i++){q.clear();for(int j=1;j<=n;j++){if(!q.empty()&&j-q.front()>=k){q.pop_front();}while(!q.empty()&&premin_x[j][i]<premin_x[q.back()][i]){q.pop_back();}q.push_back(j);if(j>=k){premin_y[j][i]=premin_x[q.front()][i];}}} int ans=0x3f3f3f3f;for(int i=k;i<=n;i++){for(int j=k;j<=m;j++){ans=min(ans,premax_y[i][j]-premin_y[i][j]);}}cout<<ans;return 0;
}

 P1725 琪露诺

题意：就是说对于一个坐标i，他只能移动到i+L~i+R这个区间范围内，然后问你最大手机到的冰冻指数是多少

思路：一开始我以为这就是个简单的动态规划，因为

dp[i]=max(dp[i-k])+a[i]    (   L<=k<=R   )

然后枚举L到R里面找到最大的即可，我也想这个也配绿题，降成橙题感觉还差不多，果然四个T也是成功打脸了我的这种感觉，因为需要优化，但是维护区间的最值，我们可以想到哪些方法呢，一个是老朋友线段树，还有一个是老朋友单调队列，那么我们该用哪个方法呢？那肯定是单调队列啊

O(N)的时间复杂度，比线段树快多了，

因此此题就为单调队列优化dp

 

#include<bits/stdc++.h>
using namespace std;
#define int long longint n,l,r;
int a[200005];
deque<int> que;
int dp[200005];
int ans=-0x3f3f3f3f;
signed main()
{cin>>n>>l>>r;int k=r-l+1;for(int i=0;i<=n;i++){cin>>a[i];}memset(dp,128,sizeof(dp));dp[0]=0;for(int i=0;i<=n-l;i++){if(!que.empty()&&i-que.front()>=k){que.pop_front();}while(!que.empty()&&dp[que.back()]<dp[i]){que.pop_back();}que.push_back(i);dp[i+l]=dp[que.front()]+a[i+l];}for(int i=n-r+1;i<=n;i++){ans=max(ans,dp[i]);}cout<<ans;return 0;
}