注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[Codevs2338]集合堆栈机  

2014-10-24 08:36:00|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2338 集合堆栈机

很早以前测试挂掉的题

复习用

话说我的文章分类为啥不能改了……

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
const int N = 2000+10;
int n,m;
const int seed1 = 713,seed2 = 52191;
typedef long long LL;
struct Data{
Data(){a=2,b=3;}
Data(LL aa,LL bb):a(aa),b(bb){}
LL a,b;
};
bool operator < (Data a,Data b){
if(a.a == b.a)return a.b < b.b;
return a.a < b.a;
}
Data operator + (Data a,Data b){return Data(a.a+b.a,a.b+b.b);}
Data add(Data a,LL b,LL c){return Data(a.a*b,a.b*c);}
bool operator == (Data a,Data b){return a.a==b.a&&a.b==b.b;}
struct node{
node(){len = 0;}
int len;
Data d[N];
};
struct Stack{
int t;node d[N];
Stack(){t=0;}
void push(node a){d[++t] = a;}
node top(){return d[t];}
void pop(){t--;}
}stack;
Data tmp[N*2];
Data pack(node a){
Data re;
for(int i=1;i<=a.len;i++)re = add(re,seed1,seed2) + a.d[i];
return re;
}
node operator | (node a,node b){
node c;
merge(a.d+1,a.d+1+a.len,b.d+1,b.d+1+b.len,tmp+1);
c.len = unique(tmp+1,tmp+1+a.len+b.len)-tmp-1;
for(int i=1;i<=c.len;i++)c.d[i] = tmp[i];
return c;
}
node operator & (node a,node b){
node c;c.len=0;
int i=1,j=1;
while(i<=a.len&&j<=b.len){
if(a.d[i] < b.d[j])i++;
else if(b.d[j] < a.d[i])j++;
else c.d[++c.len] = a.d[i],i++,j++;
}
return c;
}
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j;node a,b;
n = scan();
char str[30];
for(i=1;i<=n;i++){
scanf("%s",str);
if(str[0] == 'P'){
stack.push(node());
}if(str[0] == 'D'){
a = stack.top();
stack.push(a);
}if(str[0] == 'U'){
a = stack.top();stack.pop();
b = stack.top();stack.pop();
a = a|b;
stack.push(a);
}if(str[0] == 'I'){
a = stack.top();stack.pop();
b = stack.top();stack.pop();
a = a&b;
stack.push(a);
}if(str[0] == 'A'){
a = stack.top();stack.pop();
b = stack.top();stack.pop();
b.d[++b.len] = pack(a);
sort(b.d+1,b.d+1+b.len);
b.len = unique(b.d+1,b.d+1+b.len)-b.d-1;
stack.push(b);
}
printf("%d\n",stack.top().len);
}
return 0;
}

题解:

Hash乱搞……没啥好说的

  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017