题目传送门🛫

A 排队

B 插入删除

C 拍照

D 小马要做最棒的牛

E 小田在努力切割木板

F 小田的花盆

T1 排队

思路

我们可以用双向队列来模拟

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000010],h=100000,t=99999,w=1,s,c;
int main(){
	freopen("pd.in","r",stdin);
	freopen("pd.out","w",stdout);
	cin>>s;
	for(int i=1;i<=s;i++){
		char x,y;
		cin>>x>>y;
		if(x=='A'&&y=='L'){a[--h]=w,w++;}
		if(x=='A'&&y=='R'){a[++t]=w,w++;}
		if(x=='D'&&y=='L'){
			cin>>c;
			h+=c;
		}
		if(x=='D'&&y=='R'){
			cin>>c;
			t-=c;
		}
	//	for(int j=h;j<=t;j++)cout<<a[j]<<' ';
	}
	for(int j=h;j<=t;j++)cout<<a[j]<<"\n";
}

T2 插入删除

错的点

1.用的是单链表，而且写的复杂，这题本来要用双链表的，以后要加强熟练度

思路

双链表模板

代码

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
unordered_map<int,int> m;
int l[N],r[N],e[N],idx,n,q;
void init() {
	r[0]=1;
	l[1]=0;
	idx=2;
}
void add(int k, int x) {
	m[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();
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(i==1)add(0,x);
		else add(i,x);
	}
	cin>>q;
	while(q--){
		int x,y,z;
		cin>>x;
		if(x==1){
			cin>>y>>z;
			add(m[y],z);
		}
		else{
			cin>>y;
			remove(m[y]);
		}
		cout<<"\n";
	}
	for(int i=r[0];e[i]!=0;i=r[i])cout<<e[i]<<" ";	
}

T3 拍照

错的点

比赛时骗的分，而再写时最小值设制极大值时设小了

思路

可以用二分来做，用两个变量维护区间，如果可以就l++直到不行为止，如果不可以j++，这里判断是还要加哈希来标记，前面记得排序

代码

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,long long>m,j;
long long n,an=100000;
struct P{
	long long w,p;
}a[50010];
bool cmp(P a,P b){
	return a.w<b.w;
}
int main(){

	freopen("photo.in","r",stdin);  
	freopen("photo.out","w",stdout);	
	long long s=0,h=1000000010,l=1,r=1;
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>a[i].w>>a[i].p;
		if(j[a[i].p]==0)s++;
		j[a[i].p]++;
	}
	sort(a+1,a+1+n,cmp);
	while(l<=n&&r<=n){
		if(m[a[r].p]==0)s--;
		m[a[r].p]++;
		if(s!=0)r++;
		if(s==0){
			h=min(h,a[r].w-a[l].w);
			if(m[a[l].p]==1)s++,l++;	
			else l++;
			m[a[l-1].p]--;
		}
	}
	cout<<h;
}

T4 小马要做最棒的牛

错的点

十年OI一场空，不开longlong见祖宗

思路

用表达式求值的思路，遇到左括号压入，右括号算分

代码

#include<bits/stdc++.h>
using namespace std;
long long f[100010],h=-1,e=12345678910;
int main(){
	freopen("horse.in","r",stdin);  
	freopen("horse.out","w",stdout);
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++){
		long long x;
		cin>>x;
		if(x==0)f[++h]=-1;
		if(x==1){
			if(f[h]>-1){
				long long j=0;
				while(f[h]!=-1){
					j%=e;
					j=(j+f[h])%e;
					h--;
				}
				h--;
				f[++h]=((j%e)*2)%e;
			}
			else{
				h--;
				f[++h]=1;
			}
		}
		cout<<"\n";
	}
	long long  s=0;
	for(long long i=0;i<=h;i++)s=(s+f[i])%e;
	cout<<s%e;
}

T5 小田在努力切割木板

错的点

纯暴力，以后要多思考

思路

这道题我们可以反着想，然后又会发现每次两个最小的和，合会最小，所以可以用堆

代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long>>k;
int main(){
	freopen("qg.in","r",stdin);  
	freopen("qg.out","w",stdout);	
	long long n,z=0,h=0;
	cin>>n;
	for(long long i=1;i<=n;i++){
		int x;
		cin>>x;
		k.push(x);
	}
	for(long long i=1;i<n;i++){
		h=k.top();
		k.pop();
		h+=k.top();
		k.pop();
		z+=h;
		k.push(h);
	}
	cout<<z;
}