danihao123's Blog

这题我考试的时候想出各种蜜汁数据结构。

但是正解是：暴力！

好了好了，暴力也是要优化的。首先给消息编号，然后用一个bitset记下来哪个删了哪个没删，这个都能想到。

不过接下来有个挺头疼的问题：操作3阅读的信息可能在操作2中会被再次阅读，如此一来效率就很低了……咋整？

注意大消息队列里的消息编号肯定是升序的，每个程序的消息队列的编号也是升序的，所以说大队列中同一程序的消息的编号和该程序自身队列中的消息编号的顺序是一致的。如此一来，在操作3中可以顺便把程序队列中的消息也删掉，效率大为提升。

代码：

#include <cstdio>
#include <queue>
#include <utility>
#include <cctype>
#include <bitset>
using namespace std;
const int maxn=300001;
typedef pair<int,int> pii;
bitset<maxn> vis;
queue<int> S[maxn];
queue<pii> Q;
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
	register int ans=0,cnt=0;
	register int temp,temp_2,q,u,v;
	int n;
	n=readint();
	q=readint();
	while(q--){
		u=readint();
		v=readint();
		if(u==1){
			cnt++;
			S[v].push(cnt);
			Q.push(make_pair(v,cnt));
			ans++;
		}else{
			if(u==2){
				while(!S[v].empty()){
					temp=S[v].front();
					S[v].pop();
					if(!vis[temp]){
						vis[temp]=true;
						ans--;
					}
				}
			}else{
				while(!Q.empty() && (temp=Q.front().second)<=v){
					temp=Q.front().second;
					temp_2=Q.front().first;
					Q.pop();
					if(!vis[temp]){
						vis[temp]=true;
						S[temp_2].pop();
						ans--;
					}
				}
			}
		}
		writeint(ans);
		putchar('\n');
	}
	return 0;
}

这题可以直接模拟，貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯，然后向下溢出，以此类推，这样复杂度就很优秀了。

代码：

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}