A. 排队

题目类型：双向队列或双链表

思路

这道题目从题目描述很明显可以看出来需要用一个双向的数据结构，那像双向队列或双链表的这种双向的数据结构就都可以用上来，只要好好学这种双向的数据结构，将模版改一下，应该都能做对。

代码

双链表

#include<bits/stdc++.h>
using namespace std;
int idx,e[100010],r[100010],l[100010],head,talt,cnt;
void init(){
	head=0,talt=100010;
    r[head]=talt;
    l[talt]=head;
    idx=1; 
}
void se(int k){
	r[l[k]]=r[k];
    l[r[k]]=l[k];
}
void add(int k,int cnt){
	e[idx]=cnt;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}
int main(){
	freopen("pd.in","r",stdin);
	freopen("pd.out","w",stdout);
	init();
	int n;
	cin>>n;
	while(n--){
		char a,b;
		cin>>a>>b;
		int t;
		if(a=='A'&&b=='L'){
			cnt++;
			add(head,cnt);
		}
		if(a=='A'&&b=='R'){
			cnt++;
			add(l[talt],cnt);
		}
		if(a=='D'&&b=='L'){
			cin>>t;
			while(t--) se(r[head]);
		}
		if(a=='D'&&b=='R'){
			cin>>t;
			while(t--) se(l[talt]);
		}
	}
	for(int i=r[head];i!=talt;i=r[i]) cout<<e[i]<<endl;
	return 0;
}

本题代码已AC，下一次继续保持。

B. 插入删除

题目类型：哈希表与双链表

思路

这道题目从题目描述很明显可以看出来需要用双链表，而因为要找元素k会费时间，所以要用哈希表，只要将模版改一下就行了。

代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
const int N=4e5+10;
int e[N],r[N],l[N],idx;
void init(){
	r[0]=1;
	l[1]=0;
	idx=2;
}
void add(int k,int x){
	mp[x]=idx;
	e[idx]=x;
	l[idx]=k;
	r[idx]=r[k];
	l[r[k]]=idx;
	r[k]=idx++;
}
void remove(int k){
	r[l[k]]=r[k];
	l[r[k]]=l[k];
}
int main(){
	freopen("insdel.in","r",stdin);
	freopen("insdel.out","w",stdout);
	init();
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(i==1) add(0,a);
		else add(idx-1,a);
	}
	int q;
	cin>>q;
	while(q--){
		int b;
		cin>>b;
		if(b==1){
			int x,y;
			cin>>x>>y;
			add(mp[x],y);
		}
		else{
			int x;
			cin>>x;
			remove(mp[x]);
		}
	}
	for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
	return 0;
}

这道题目我在写的时候只写了双链表，没写哈希表，所以没过，下一次要将各种数据结构结合起来写。

C. 拍照

题目类型：双指针

思路

对于这道题目我们可以双指针遍历一下，若全种族都在，再压缩一下，若也可以，就继续压缩，同时更新最大值，直到不能压缩为止。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
pair<int,int> a[N];
unordered_map<int,int> b,c;
using namespace std;
signed main(){
	freopen("photo.in","r",stdin);
	freopen("photo.out","w",stdout);
	int n,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].first>>a[i].second;
		if(!b[a[i].second]) cnt++;
		b[a[i].second]++;
	}
	sort(a+1,a+1+n);
	int l=1,r=1,ans=0x3f3f3f3f;
	while(l<=n&&r<=n){
		if(c[a[r].second]==0) cnt--;
		c[a[r].second]++;
		if(cnt) r++;
		else{
			int d=a[r].first-a[l].first;
			ans=min(ans,d);
			if(c[a[l].second]==1) cnt++,l++;
			else l++;
			c[a[l-1].second]--;
		}
	}
	cout<<ans;
	return 0;
}

这道题目完全没有思路，所以就放弃了，下一次不能轻易放弃。

D. 小马要做最棒的牛

题目类型：栈或DP

思路

若用DP，则遍历每一层，若用栈，直接模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long a[N],mod=12345678910,b;
int main(){
	freopen("horse.in","r",stdin);
	freopen("horse.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int c;
		cin>>c;
		if(c==0) b++;
		else{
			if(!a[b]) a[b-1]=(a[b-1]+1)%mod,b--;
			else a[b-1]=(a[b-1]+a[b]*2)%mod,a[b--]=0;
		}
	}
	cout<<(a[0]+mod)%mod;
	return 0;
}

没有时间了，所以没做这题，下次提高做题速度。

E. 小田在努力切割木板

题目类型：堆

思路

用小根堆来加入数据，每次选最小的两个数字加起来再加入小根堆即可，这不过每一次ans都要加最小的两个数字，注意：要开long long。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
signed main(){
	freopen("qg.in","r",stdin);
    freopen("qg.out","w",stdout);
	int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		q.push(a);
	}
	while(q.size()>=2){
		int A=q.top();
		q.pop();
		int B=q.top();
		q.pop();
		q.push(A+B);
		ans+=A+B;
	}
	cout<<ans;
	return 0;
}

没有时间了，所以没做这题，下次要提高做题速度。