当前位置：首页 > news >正文

洛谷刷题7.23

news 2025/7/25 11:46:46

P2422 良好的感觉 - 洛谷

这题可用贪心+二分来实现，注意一个区间的舒适度是由区间最小值和区间和两个要素决定的，我们要控制变量，从1-n进行遍历，将a[i]作为这个区间的最小值，那么我们希望这个区间和尽可能地大才能让舒适度达到最大，同时我们要保证这个区间的最小值是a[i]。我们从i向两边延伸，找到小于a[i]的值就是这个区间的边界。我们可以用单调队列和ST表+二分实现。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,sum[100005],st[100005][30],ans=0; 
ll ask(int l,int r){int x=log2(r-l+1);return min(st[l][x],st[r-(1<<x)+1][x]);
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){cin>>st[i][0];sum[i]=sum[i-1]+st[i][0];
}
for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
for(int i=1;i<=n;i++){int l=0,r=i+1,l1,r1;while(l+1<r){int mid=(l+r)/2;if(ask(mid,i)<st[i][0]) l=mid;else r=mid;}l1=r;l=i-1,r=n+1;while(l+1<r){int mid=(l+r)/2;if(ask(i,mid)<st[i][0]) r=mid;else l=mid;}r1=l;ans=max(ans,st[i][0]*(sum[r1]-sum[l1-1]));
}
cout<<ans;return 0;
}

P1725 琪露诺 - 洛谷

动态规划+单调队列优化。

很明显，到达一个点的冰冻值是由[i-r,i-l]区间的冰冻值转移过来的，我们要的是区间的最大值，就用单调队列维护。注意DP数组要初始化为负无穷，因为有些点是不可能到达的。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,l,r,dp[400005],a[400005],ans=-2147483648;
deque<int>q;
void put(int x){while(!q.empty()&&dp[q.front()]<dp[x]){q.pop_back();}q.push_back(x);
} 
void out(int x){while(!q.empty()&&q.front()<=x){q.pop_front();}
}
int main() {
cin>>n>>l>>r;
for(int i=0;i<=n;i++){cin>>a[i];
}
memset(dp,-0x3f,sizeof(dp));
dp[0]=0;
for(int i=l;i<=n+r;i++){if(i-l>=0) put(i-l);if(i-r-1>=0) out(i-r-1);if(!q.empty()) dp[i]=dp[q.front()]+a[i];if(i>n) ans=max(ans,dp[i]);
}
cout<<ans;return 0;
}

P2776 [SDOI2007] 小组队列 - 洛谷

二维队列，依照题意模拟就行。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
queue<int>team[305];
queue<int>q;
int n,m,a[100005],t,x;
string s;
int main() {
cin>>n>>m;
for(int i=0;i<n;i++){cin>>a[i];
}
cin>>t;
while(t--){cin>>s;if(s=="push"){cin>>x;if(team[a[x]].empty()){q.push(a[x]);}team[a[x]].push(x);}else{cout<<team[q.front()].front()<<endl;team[q.front()].pop();if(team[q.front()].empty()){q.pop();}}
}return 0;
}

P2947 [USACO09MAR] Look Up S - 洛谷

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[1000005],ans[1000005];
stack<int>q; 
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--){while(!q.empty()&&a[q.top()]<=a[i]){q.pop();}if(!q.empty()) ans[i]=q.top();q.push(i);
}
for(int i=1;i<=n;i++){cout<<ans[i]<<endl;
}return 0;
}

P5788 【模板】单调栈 - 洛谷

单调栈是单调队列阉割版

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[3000005],ans[3000005];
stack<ll>q; 
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--){while(!q.empty()&&a[q.top()]<=a[i]){q.pop();}if(!q.empty()) ans[i]=q.top();q.push(i);
}
for(int i=1;i<=n;i++){cout<<ans[i]<<" ";
}return 0;
}

P1449 后缀表达式 - 洛谷

依旧单调栈

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char ch;
stack<ll>q;
ll temp;
int main() {
while(cin>>ch){if(ch=='@') break;else if(ch=='.') q.push(temp),temp=0;else if(ch>='0'&&ch<='9') temp=temp*10+ch-'0';else{int x=q.top();q.pop();int y=q.top();q.pop();if(ch=='+') q.push(x+y);if(ch=='-') q.push(y-x);if(ch=='*') q.push(y*x);if(ch=='/') q.push(y/x);//cout<<y<<"  "<<x<<"  "<<q.top()<<endl; }
}
cout<<q.top();return 0;
}

P1739 表达式括号匹配 - 洛谷

依旧模拟

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[300],sum=0;
int main() {
string s;
cin>>s;
for(int i=0;i<s.length();i++){if(s[i]=='(') a[i]=1;else if(s[i]==')') a[i]=-1;
}
for(int i=0;i<s.length();i++){sum+=a[i];if(sum<0){cout<<"NO";return 0;}
}
if(sum==0) cout<<"YES";
else  cout<<"NO";return 0;
}

P1981 [NOIP 2013 普及组] 表达式求值 - 洛谷

依旧单调栈或模拟

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,sum=0,temp;
char ch;
vector<ll>arr;
int main() {
cin>>temp;
while(cin>>ch>>a){//if(ch=='@') break;if(ch=='+') arr.push_back(temp%10000),temp=a%10000;else temp=((temp%10000)*(a%10000))%10000;
}
arr.push_back(temp);
for(auto it:arr){sum=(sum+it)%10000;
}
cout<<sum;return 0;
}

P2880 [USACO07JAN] Balanced Lineup G - 洛谷

依旧ST表

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,stmin[50005][30],stmax[50005][30];
int main() {
cin>>n>>q;
for (int i = 1; i <= n; i++)  cin >> stmax[i][0],stmin[i][0]=stmax[i][0];//建表
for (int j = 1; (1 << j) <= n; j++)//总包含数字不超过n{for (int i = 1; i + (1 << j) - 1 <= n; i++)//确保是子区间，不越界{stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << j - 1)][j - 1]);stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << j - 1)][j - 1]);}}
int l, r;//查询
while(q--){cin >> l >> r;
int x = log2(r - l + 1);
cout << max(stmax[l][x], stmax[r - (1 << x) + 1][x] )-min(stmin[l][x], stmin[r - (1 << x) + 1][x] )<< endl;
}return 0;
}

查看全文

http://www.lryc.cn/news/597474.html