最近做了两道STL库黑科技的题。
UESTC - 1339
题意：类似一个队列，有push和pop操作，但是他会问你这个队列的中位数（升序后的k/2+1位数）的值。题目保证每个数字不同。
分析：用一个队列和两个set即可。队列的作用就是模拟队列，set的作用就是存储 中位数以前（l） 和 中位数及中位数以后（r） 的数字。
注意一点，我们在根据这个中位数的位置，可以判断出，只有l==r或者l+1==r两种情况。所以操作的时候注意一下判断即可。
#include<cstdio>
#include<iostream>
#include<queue>
#include<set>
using namespace std;
int main()
{
queue<int>q;
set<int>l,r;
int n;
scanf("%d",&n);
set<int>::iterator it;
while(n--){
int op,x;
scanf("%d",&op);
if(op==1){
scanf("%d",&x);
q.push(x);
it=r.begin();
if(l.size()==r.size()){
if(x<(*it)){
l.insert(x);
r.insert(*(--l.end()));
l.erase((--l.end()));
}else{
r.insert(x);
}
}else{
if(x<(*it)){
l.insert(x);
}else{
l.insert(*it);
r.erase(it);
r.insert(x);
}
}
}else if(op==2){
int t=q.front(); q.pop();
int s=l.size()+r.size();
it=r.begin();
if(t>=*it){
if(s%2==0){
r.erase(r.lower_bound(t));
r.insert(*(--l.end()));
l.erase((--l.end()));
}else{
r.erase(r.lower_bound(t));
}
}else{
if(s%2==0){
l.erase(l.lower_bound(t));
}else{
l.insert(*it);
l.erase(l.lower_bound(t));
r.erase(it);
}
}
}else{
printf("%d\n",*(r.begin()));
}
}
return 0;
}
1.我看大佬的代码，有提到用l.rbegin()这种函数，不过我自己感觉没有必要。
2.set中find函数的复杂的是O(n)，而lower_bound函数的复杂度是O(logn)的。
3.set是一个自平衡树，是有默认排序的，为升序。同时，一定要用自带的lower_bound函数，因为set不支持随机访问，lower_bound(l.begin,r.begin,x)其实就是一个线性的访问了，与find类似。
还有一种做法是利用 linux的平板电视（pb_ds），不懂，挖坑X1；
福建工程出的一道题。
题目中文，题意下次补；
它用了两个栈来维护乘积。
我模拟一下过程：
首先读入一个l和r。然后从把r个数字入栈，每一个入栈的数字是前i个数字的积。然后执行pop操作——pop操作就是在s2不为空且s1为空的情况下，像s2中投入s1.size（）个数字，第i个数字是[i,r]的乘积。（全部投入就为0-r的乘积，不过是逆序）当然，每一次调用pop会让s2 pop掉一个数字。这样我们执行l次操作，s2的栈顶即为问题的答案。
第二次我们又读入一个nl和nr，此时我们开始扩展s1，扩展方式就是把[r,nr]的乘积投入，第i个投入数字表示[r,i]的乘积。我们目前的状态，s1维护着[r,nr]正序的乘积，s2维护着[l,r]逆序的乘积，而我们知道nl>l 的，所以我们就要开始pop s2，当pop到[nl,r]的逆序乘积时，答案就是s1的栈顶乘s2的栈顶。
当然，第二次可能出现另外一种情况，即为nl>r，但是不用担心，黑科技无敌！！！当出现这种情况时，s1维护的是[r,(nl),nr]的乘积，执行pop时，会将s2的所有数字pop出去，于是s1就会清空，同时像第一步一样，向s2中就开始投入[r,(nl),nr]的逆序乘积，此时刚好又可以pop掉nl-r个数字，所以答案就又为s2的栈顶元素。
就这样一直循环下去的牛逼东西。
但是这种方法是有限制的，只适用于特定的[l,r]。就当奇淫技巧看看吧。
//s2的作用是扩展r1-r2的乘积，通过pop使得s1的栈顶为来l2-r1。
//pop操作也很有意思，其实有用s1控制数量的意思在里面！
#include<bits/stdc++.h>
#define ll long long
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 1e6+100;
using namespace std;
ll Scan()//读入外挂
{
ll res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
void Out(ll a)//输出外挂
{
if(a>9)
Out(a/10);
putchar(a%10+'0');
}
stack<ll> s1,s2;
ll T,n,p,q;
ll a[maxn];
void pop()
{
if(s2.empty()){
while(!s1.empty()){
if(s2.empty()) s2.push(a[T--]%p);
else s2.push((a[T--]*s2.top())%p);
s1.pop();
}
}
s2.pop();
}
void Solve()
{
n=Scan();
p=Scan();
for(ll i=1;i<=n;i++){
a[i]=Scan();
}
q=Scan();
ll prel=1;
ll prer=0;
T=-1;
for(int i=0;i<q;i++){
ll l,r;
l=Scan();
r=Scan();
for(int j=prer+1;j<=r;j++){
if(s1.empty()) s1.push(a[j]%p);
else s1.push(((a[j]%p)*s1.top())%p);
}
T=r;
for(int j=prel;j<l;j++) pop();
ll ans;
if(s1.empty()) ans=s2.top()%p;
else if(s2.empty()) ans=s1.top()%p;
else ans=s1.top()*s2.top()%p;
prel=l; prer=r;
Out(ans);
putchar('\n');
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
网友评论