小组队列

思路

看什么思路？你不会队列吗？

主要就是输入和输出很难搞，其他只要你会队列就可以了。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=1e6+10;
int f[tt];
char s[10];
queue<int> q[tt];

int main(){
	int t;
	int id=0;
    while(cin>>t&&t){
    	q[0]=queue<int>();
	    for(int i=1;i<=t;i++){
	        int n;
	        cin >>n;
	        while(n--){
	            int x;
	            cin >>x;
	            f[x]=i;
	        }
	        q[i]=queue<int>();
	    }
	    cout <<"Scenario #"<<++id<<endl;
	    while(cin >>s&&s[0]!='S'){
	        if(s[0]=='E'){
	            int x;
	            cin >>x;
	            if(q[f[x]].empty()) q[0].push(f[x]);
	            q[f[x]].push(x);
	        }else{
	            int x=q[0].front();
	            cout <<q[x].front()<<endl;
	            q[x].pop();
	            if(q[x].empty()) q[0].pop();
	        }
	    }
	    cout <<endl;
	}
    return 0;
}

CSP-S 2016 Day2 T2 蚯蚓

思路

首先，定义$x$，$y$，$z$。初始状态下，$x$中保存的是完全没有被切过的蚯蚓的长度（初始时排个序，最大的在最前面），$y$中保存一条被切开的蚯蚓前半部分的长度，$z$中保存一条被切开的蚯蚓的后半部分的长度。

假设当前时间为$t$，若取出元素入队的时间为$t0$，入队时长度为$x$，则出队长度为$q(t-t0)+x$。我们修改下元素入队的规则，假设当前需要将$x$入队，则在$x$入队前，将$x$减去$q*t0$，再加入队列中。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=2e5+10;
int n,m,q,u,v,t;
int a[tt];
queue<pair<int,int>> p[10];

int get(int time){
	int x=-1e9,y=-1e9,z=-1e9;
	if(!p[1].empty()){
		x=p[1].front().first+q*(time-1-p[1].front().second);
	}
	if(!p[2].empty()){
		y=p[2].front().first+q*(time-1-p[2].front().second);
	}
	if(!p[3].empty()){
		z=p[3].front().first+q*(time-1-p[3].front().second);
	}
	int idx=1ll,res=0ll;
	if(x>=y&&x>=z){
		idx=1;
		res=x;
	}
	if(y>=x&&y>=z){
		idx=2;
		res=y;
	}
	if(z>=x&&z>=y){
		idx=3;
		res=z;
	}
	p[idx].pop();
	return res;
}

signed main(){
	cin >>n>>m>>q>>u>>v>>t;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=n;i>=1;i--){
		p[1].push({a[i],0});
		int num=0;
	}
	for(int i=1;i<=m;i++){
		int len=get(i);
		int x=len*u/v;
		int y=len-x;
		if(i%t==0){
			cout <<len<<" ";
		}
		p[2].push({x,i});
		p[3].push({y,i});
	}
	cout <<endl;
	for(int i=1;;i++){
		if(p[1].empty()&&p[2].empty()&&p[3].empty()){
			break;
		}
		int res=get(m+1);
		if(i%t==0){
			cout <<res<<" ";
		}
	}
	return 0;
}

双端队列

思路

先按值排序。如果连续区间值都相等，求出最小下标，最大下标；与上一个进行比较。最终求出答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=2e5+10;
pair<int,int> a[tt];
vector<int> b[tt];

int main(){
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		int x;
		cin >>x;
		int num=0;
		a[i]={x,i};
	}
	sort(a+1,a+1+n);
	int idx=0;
	for(int i=1;i<=n;i++){
		b[++idx].push_back(a[i].second);
		while(a[i+1].first==a[i].first){
			b[idx].push_back(a[i+1].second);
            i++;
            b[idx].push_back(a[i].second);
		}
	}
	int num=2e9,ans=1;
    bool flag=0;
    for(int i=1;i<=idx;i++){
        if(flag==1){
            if(b[i][0]>num){
            	num=b[i].back();
            	
			}else{
                ans++;
                flag=0;
                num=b[i][0];
            }
        }else{
            if(b[i].back()<num){
            	num=b[i][0];
			}else{
                flag=1;
                num=b[i].back();
            }
        }
    }
    cout <<ans;
	return 0;
}

最大子序和

思路

我们发现如果说有一个位置$k$，这个$k<j<i$。而且$sum[k]≥sum[j]$。

所以$k<j$，也就是说$[k,i]$这个区间的长度，一定是大于$[j,i]$这个区间长度的。

$sum[k]≥sum[j]$，这么说来的话，那么$sum[i]−sum[k]≥sum[i]−sum[j]$，也就是说我们的$[k,j]$区间消耗更大。

既然如此，那么$k$是真的很菜，是真的没有用了。

$j$不仅比$i$更加接近$i$，最主要的是，消耗比$k$小。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=3e5+10;
int a[tt],s[tt];
deque<int> q;

signed main(){
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		cin >>a[i];
		s[i]=s[i-1]+a[i];
	}
	int ans=-2e9;
	q.push_back(0);
	for(int i=1;i<=n;i++){
		while(q.size()!=0&&q.front()<i-m){
			q.pop_front();
		}
		ans=max(ans,s[i]-s[q.front()]);
        while(q.size()!=0&&s[q.back()]>=s[i]){
        	q.pop_back();
		}
        q.push_back(i);
	}
	cout <<ans;
	return 0;
} 

滑动窗口

思路

维护一个单调队列，

假如我们先求最小值，保证队首就是最小值，满足滑动窗口长度时输出队首；

求最大值的话同理。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=3e5+10;
int a[tt],s[tt];
deque<int> q;

signed main(){
	int n,m;
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		cin >>a[i];
		s[i]=s[i-1]+a[i];
	}
	int ans=-2e9;
	q.push_back(0);
	for(int i=1;i<=n;i++){
		while(q.size()!=0&&q.front()<i-m){
			q.pop_front();
		}
		ans=max(ans,s[i]-s[q.front()]);
        while(q.size()!=0&&s[q.back()]>=s[i]){
        	q.pop_back();
		}
        q.push_back(i);
	}
	cout <<ans;
	return 0;
} 

谢谢