7.31 比赛总结
B3667 求区间所有后缀最大值的位置
错误代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
const int maxn=1e6+10;
int a[maxn];
deque<int>q;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(!q.empty()&&q.front()<=i-k+1){
q.pop_front();
}
while(!q.empty()&&a[i]>=a[q.back()]){
q.pop_back();
}
q.push_back(i);
if(i>=k){
cout<<q.size()<<endl;
}
}
return 0;
}
//错误代码 题目要求：对于全部的测试点，保证 1≤k≤n≤10 6 ，1≤x i <2 64 。
错因
①所以变量开小了 应该开unsigned long long
②此题判断队首约是否越界 要先入队列 进完后判断是否越界
③并且判断条件出错 减号有风险挂 最好用加法
#define int unsigned long long
for(int i=1;i<=n;i++){
while(!q.empty()&&a[i]>=a[q.back()]){
q.pop_back();
}
q.push_back(i);
if(k+q.front()<=i){
q.pop_front();
}
if(i>=k){
cout<<q.size()<<endl;
}
}正确完整代码
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int n,k;
const int maxn=1e6+10;
int a[maxn];
deque<int>q;
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
while(!q.empty()&&a[i]>=a[q.back()]){
q.pop_back();
}
q.push_back(i);
if(k+q.front()<=i){
q.pop_front();
}
if(i>=k){
cout<<q.size()<<endl;
}
}
return 0;
}
//正确代码
P3467 [POI 2008] PLA-Postering
错误代码如下
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=1e6+10;
int a[maxn];
stack<int>q;
int ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
cin>>a[i];
}
for(int i=1;i<=n;i++){
while(!q.empty()&&a[i]<=a[q.top()]){
if(a[i]==a[q.top()])ans++;
q.pop();
}
if(!q.empty())ans++;
q.push(i);
}
cout<<ans;
return 0;
}
//错误 错因
思路出错
应该cnt初始等于n(最坏情况 每一个高度都不相同)
然后维护一个单调递增的栈 违法后判断是否相等 相等可以连接成一块 即只需要一张报纸 所以总数少一张报纸（cnt--） 最后输出cnt即可
正确代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=1e6+10;
int a[maxn];
stack<int>q;
int ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
cin>>a[i];
}
ans=n;
for(int i=1;i<=n;i++){
while(!q.empty()&&a[i]<a[q.top()]){
q.pop();
}
if(!q.empty()&&a[i]==a[q.top()])ans--;
q.push(i);
}
cout<<ans;
return 0;
}
//正确 P1823 [COI 2007] Patrik 音乐会的等待
错因
①维护单调栈顺序错误 应该维护单调递减的栈
②并且在维护过程中循环内也属于单调递增的效果 所以可以在一个循环内进行 合法结束cnt++
③当两边相等的时候需要a[i].num+=q.top().num;
正确代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
struct S{
int x;
int num=1;
}a[maxn];
stack<S>q;
int n;
int ans;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x;
}
for(int i=1;i<=n;i++){
while(!q.empty()&&a[i].x>=q.top().x){
ans+=q.top().num;
if(a[i].x==q.top().x)a[i].num+=q.top().num;
q.pop();
}
if(!q.empty()){
ans++;
}
q.push(a[i]);
}
cout<<ans;
return 0;
}
//正确 P2564 [SCOI2009] 生日礼物
这道题与上课例题相似
上课专注度需加强
这种类型题目得重新巩固
没理解特别多
正确代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node
{
int pos,id;
}s[N];
bool cmp(node q,node h)
{
return q.pos<h.pos;
}
int n,k,cnt,tot,num[N],minn=1e9;
map<int,int> ma;
deque<int> q;
int main()
{
cin>>n>>k;
for(int i=1;i<=k;i++){
int t;
cin>>t;
while(t--){
int x;
cin>>x;
tot++;
s[tot].pos=x;
s[tot].id=i;
}
}
sort(s+1,s+1+n,cmp);
for(int i=1;i<=n;i++){
q.push_back(i);
int id=s[i].id;
if(num[id]==0)
cnt++;
num[id]++;
while(!q.empty() && cnt>=k){
int j=q.front();
q.pop_front();
int id=s[j].id;
num[id]--;
if(num[id]==0)
{
cnt--;
minn=min(minn,s[i].pos-s[j].pos);
}
}
}
cout<<minn;
return 0;
}