奶牛排队（双端队列）

思路没想到的原因

忘记处理数组边界了，以后要注意一下判断边界。

思路

双端队列模版题，按题目要求来模拟即可。

代码

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

const int N=2e5+10;
int a[2*N],h=N+1,l=1,s=N;

int main(){
	freopen("pd.in","r",stdin);
	freopen("pd.out","w",stdout);
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		char q,b;
		int k;
		cin >>q>>b;
		if(q=='A'&&b=='L'){
			a[--h]=l;
			l++;
		}else if(q=='A'&&b=='R'){
			a[++s]=l;
			l++;
		}else if(q=='D'&&b=='L'){
			cin >>k;
			h+=k;
		}else if(q=='D'&&b=='R'){
			cin >>k;
			s-=k;
		}
	}
	for(int i=h;i<=s;i++){
		cout <<a[i]<<endl;
	}
	return 0;
}

插入删除（链表+哈希表优化）

思路没想到的原因

只想到了链表，没有想到哈希表的优化，所以没有做出来。

思路

一道链表模板题，只需用哈希表来储存位置，剩余用双链表做。

代码

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

const int N=4e5+10;
int l[N],r[N],e[N],idx;
unordered_map<int,int> mp;

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 s;
	cin >>s;
	for(int i=1;i<=s;i++){
		int x;
		cin >>x;
		if(i==1) add(0,x);
		else add(i,x);
	}
	int q;
	cin >>q;
	while(q--){
		int op,x,y;
		cin >>op;
		if(op==1){
			cin >>x>>y;
			add(mp[x],y);
		}else{
			cin >>x;
			remove(mp[x]);
		}
	}
	for(int i=r[0];e[i]!=0;i=r[i]) cout <<e[i]<<" ";
	return 0;
}

奶牛拍照（二分）

思路没想到的原因

当时并没有想到是一道二分的题目，只想到了暴力的做法。

思路

可以用二分来做，还要记得排序。用两个变量维护拍照区间，如果可以移动就$l++$，直到遇上边界，如果不可以$j++$，就要去判断是还要加哈希来标记。

代码

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

const int tt=5e4+10;
long long n,an=100000;
pair<int,int> a[tt];

unordered_map<long long,long long> b,c;

bool cmp(pair<int,int> a,pair<int,int> b){
	return a.first<b.first;
}

int main(){
	freopen("photo.in","r",stdin);
	freopen("photo.out","w",stdout);
	long long s=0,ans=0x3f3f3f3f,l=1,r=1;
	cin >>n;
	for(long long i=1;i<=n;i++){
		cin >>a[i].first>>a[i].second;
		if(c[a[i].second]==0){
			s++;
		}
		c[a[i].second]++;
	}
	sort(a+1,a+1+n,cmp);
	while(l<=n&&r<=n){
		if(b[a[r].second]==0){
			s--;
		}
		b[a[r].second]++;
		if(s!=0){
			r++;
		}else{
			long long k=a[r].first-a[l].first;
			ans=min(ans,k);
			if(b[a[l].second]==1){
				s++,l++;
			}else{
				l++;
			}
			b[a[l-1].second]--;
		}
	}
	cout <<ans;
	return 0;
}

小马要做最棒的牛（DP）

思路没想到的原因

当时用栈写了一遍，发现没对，只骗了5分。

思路

做$DP$的题，就要找到“状态表示”与“状态计算”，具体见下：

状态表示：$f[i]$表示第$i$层括号的贡献值。

状态计算：

• 如果满足$f[tt]==0$，那么$f[tt-1]=(f[tt-1]+1)$，并且$tt--$；
• 否则$f[tt-1]=(f[tt-1]+f[tt]*2)$，并且$f[tt--]=0$。

代码

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

const int N=1e5+10;
long long mod=12345678910;
long long a[N];

int main(){
    freopen("horse.in","r",stdin);
    freopen("horse.out","w",stdout);
    int n;
    long long tt=0;
    cin >>n;
    for(long long i=1;i<=n;i++){
    	long long z;
    	cin >>z;
     	if(z==0) tt++;
	   	else{
	    	if(a[tt]==0){
	    		a[tt-1]=(a[tt-1]+1)%mod;
				tt--;
			}else{
				a[tt-1]=(a[tt-1]+a[tt]*2)%mod;
				a[tt--]=0;
			}
		}
	}
	cout <<(a[0]+mod)%mod;
    return 0;
}

小田的木板（堆）

思路没想到的原因

没有一点思路，以后要多想一想。

思路

一道小根堆模板题，先取出小根堆的前两个数相加，再放入小根堆并存入$cnt$。

代码

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

const int N=2e5+50;
long long a[N];

priority_queue<long long,vector<long long>,greater<long long>> q;

int main(){
	freopen("qg.in","r",stdin);
    freopen("qg.out","w",stdout);
    int n;
    long long cnt=0;
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >>a[i];
        q.push(a[i]);
    }
    for(int i=1;i<n;i++){
        long long aa;
		aa=q.top();
        q.pop();
        long long bb;
		bb=q.top();
        q.pop();
        q.push(aa+bb);
        cnt=cnt+aa+bb;
    }
    cout <<cnt;
	return 0;
}

小田的花盆

待更新……

谢谢