洛谷刷题7..22
P1160 队列安排 - 洛谷
这是一道链表模拟题，竞赛中我们通常使用静态链表来快速编码，也就是用l[n]来存储节点的左手，r[n]来存储节点的右手。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int l[100005],r[100005],n,m,k,p;
bool vis[100005];
int main()
{
cin>>n;
l[1]=0,r[1]=n+1;
r[0]=1,l[n+1]=1;
for(int i=2;i<=n;i++){cin>>k>>p;if(p==0){l[i]=l[k];r[i]=k;r[l[k]]=i;l[k]=i;}else{l[i]=k;r[i]=r[k];l[r[k]]=i;r[k]=i;}
}
memset(vis,true,sizeof(vis));
cin>>m;
while(m--){cin>>k;if(vis[k]){r[l[k]]=r[k];l[r[k]]=l[k];vis[k]=false;}
}
int now=0;
while(r[now]!=n+1){now=r[now];cout<<now<<" ";
}return 0;
}P1540 [NOIP 2010 提高组] 机器翻译 - 洛谷
纯队列模拟题
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool vis[1005];
queue<int>r;
int n,m,a,sum=0;
int main()
{
cin>>n>>m;
while(m--){cin>>a;if(!vis[a]){sum++;r.push(a);vis[a]=true;if(r.size()>n){vis[r.front()]=false;r.pop();}}
}
cout<<sum;return 0;
}P1440 求m区间内的最小值 - 洛谷
滑动窗口
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,arr[2000005];
deque<int>r;
void put(int x){while(!r.empty()&&arr[r.back()]>=arr[x]){r.pop_back();}r.push_back(x);while(r.front()<x-k+1) r.pop_front();
}
int main() {
scanf("%d%d",&n,&k);
for(int i=2;i<=n+1;i++)scanf("%d",&arr[i]);
printf("0\n");
for(int i=2;i<=n;i++){put(i);printf("%d\n",arr[r.front()]);
}return 0;
}P2032 扫描 - 洛谷
滑动窗口
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,arr[2000005];
deque<int>r;
void put(int x){while(!r.empty()&&arr[r.back()]<=arr[x]){r.pop_back();}r.push_back(x);while(r.front()<x-k+1) r.pop_front();
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
for(int i=1;i<k;i++){put(i);
}
for(int i=k;i<=n;i++){put(i);printf("%d\n",arr[r.front()]);
}return 0;
}P1714 切蛋糕 - 洛谷
这里用到前缀和，我们想一下从前往后遍历该数组，找到以第i个元素为结尾且长度不超过m的最大字段和，j到i的和为sum[i]-sum[j-1]。那么我们就要快速找到max(0,i-m)到i-1的sum的最小值，这也就是滑动窗口，而我是用ST表来实现O（1）查询。注意要特判全为负数的情况。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,a,st[500005][30],ans=-2147483647,ans1=-2147483647;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){cin>>a;ans1=max(ans1,a);st[i][0]=st[i-1][0]+a;
}
if(ans1<0){cout<<ans1;return 0;
}
for(int j=1;(1<<j)<=m+1;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=max(0,i-m),x=log2(i-l);//cout<<st[i][0]<<" "<<min(st[l][x],st[i-(1<<x)+1][x])<<endl;ans=max(ans,st[i][0]-min(st[l][x],st[i-(1<<x)+1][x]));
}
cout<<ans;return 0;
}P2629 好消息，坏消息 - 洛谷
这道题和湖南大学25年校赛题一样，而我之前做过这个题，而在校赛中用set被卡很长时间。深刻感受到我举一反三，触类旁通的能力还不够，以后还要多思考，多总结，避免无效刷题。
湖南大学校赛的题是每次都让第一个数移动到数组最后一个，这样循环下来会得到n个序列，一个序列的前缀和都不小于0称这个序列为好序列，求好序列的个数。
这道题用到前缀和，每次遍历到i，是指从i+1-n，1-i这样遍历。也就是相当于把1-i移动到序列的后面，这时我们肯定不能每次都把前缀和去减去sum[i]，而我们可以把sum[i]当作水准，地平线。sum[i+1]——sum[n]都要大于sum[i]，而1——i移动到后面后他们的sum相对是多少呢，其实就是sum[n]+sum[i]，很好理解不管序列怎么变，所有数的总和是不变的为sum[n]，而我们的水准变为sum[i]，那么相对的就变为sum[n]+sum[i]。
也就是我们有一个长度为2N的序列，为
sum[1],sum[2],sum[3]——sum[n-1],sum[n],sum[n]+sum[1],sum[n]+sum[2]——sum[n]+sum[n]
有一个长度为n的窗口，从1——n,2——n+1，，，n——2n-1，我们要确定窗口的最小值是不是大于等于sum[i]（i是窗口开始下标）。可以用滑动窗口解决，因为这题的特殊性，窗口的长度等于数列长度的一半，可以用后缀最小值数组来实现。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,sum[1000005],a[1000005],now=99999999,ans=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){cin>>x;sum[i]=sum[i-1]+x;
}
a[n]=sum[n];
for(int i=n-1;i>=1;i--){a[i]=min(sum[i],a[i+1]);
}
if(a[1]>=0) ans++;
for(int i=1;i<n;i++){now=min(now,sum[n]+sum[i]);if(min(now,a[i+1])>=sum[i]) ans++;
}
cout<<ans;return 0;
}