5-5 集合栈Computer

集合栈计算机(The SetStack Computer, ACM/ICPC NWERC 2006,Uva12096)

 

日前,我校计算机学院ACM/ICPC集训队连获佳绩。,该赴浙江金华参加“2012全国程序设计邀请赛”,由薛斌、符瑞盛、翟尚进组成的water队获得银奖,由黄维、李翔、方易凡组成的simple队获铜奖。此次赛事由浙江师范大学举办,邀请了上海交通大学、浙江大学、哈尔滨工业大学、南京大学等知名高校参赛。我校选手大部分为第一次参赛。

威澳门尼斯人1294cc,http://acm.hust.edu.cn/vjudge/contest/128220\#problem/E
第五题我看了很久,之前就是因为第五题理解不了,才重新看了一边前面的题目,没想到第二次到了这里,还是很困惑。
先说说思路,思路还是非常清晰的
直接分成几个if(else if)—》其中U I
A操作是有重复的—》先将重复的部分写在前面,再进行判断没最后输出结果
但是 这里就遇到了几个问题了
!空集如何表示?
!{} 和{{}}一样吗?
!用什么去储存空集?
!各种操作的函数是什么?
!各个空集之间如何进行区分?
以下为源代码

6月15日,由ACM/ICPC
中国东北地区第二届大学生程序设计竞赛拉开帷幕。此次竞赛,东北赛区共有50多所高校112支队伍参加比赛,其中包括哈尔滨工业大学、哈尔滨工程大学、东北大学、大连理工大学、内蒙古大学、东北师范大学等知名高校。经过吉林省程序设计大赛的选拔,我校共派出3支代表队参加此次竞赛。

题目描述

有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈,并且支持以下操作:
PUSH:空集“{}”入栈
DUP:把当前栈顶元素复制一份后再入栈
UNION:出栈两个集合,然后把两者的并集入栈
INTERSECT:出栈两个集合,然后把二者的交集入栈
ADD:出栈两个集合,然后把先出栈的集合加入到后出栈的集合中,把结果入栈
       每次操作后,输出栈顶集合的大小。例如栈顶元素是A={ {}, {{}} },
下一个元素是B={ {}, {{{}}} },则:
UNION操作将得到{ {}, {{}}, {{{}}} },输出3.
INTERSECT操作将得到{ {} },输出1
ADD操作将得到{ {}, {{{}}}, { {}, {{}} } },输出3.
样例输入

6
PUSH
PUSH
UNION
PUSH
PUSH
ADD

样例输出

0
0
0
0
0
1

ACM/ICPC在线题库集锦:


ACM/ICPC集训队派选手参加了在东南大学举办的“华为杯”南京市程序设计邀请赛。经过激烈角逐,我校参赛队获得一等奖1名,二等奖3名,三等奖3名。获奖选手名单如下:

#include<iostream>//I/O
#include<string>//string
#include<set>//集合
#include<map>映射
#include<stack>栈
#include<vector>vector容器
#include<algorithm>//set_union : 并集 set_intersection : 交集 set_difference : 差集
using namespace std;

typedef set<int> Set;
//定义一个int型集合对象Set,当前没有任何元素.
map<Set,int> IDcache;//把集合映射成ID
vector<Set> Setcache;
//查找集合的ID.如果找不到,分配一个新ID
int ID(Set x)
{
    if(IDcache.count(x)) return IDcache[x];
    Setcache.push_back(x);
    return IDcache[x]=Setcache.size()-1;
}
#define All(x) x.begin(),x.end()//定义了有关于迭代器的宏
#define INS(x) inserter(x,x.begin())
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        stack<int> s;//定义栈
        int i,n;
        cin>>n;
        for(i=0; i<n; i++)
        {
            string op;
            cin>>op;
            if(op[0]=='P') s.push(ID(Set()));//插入ID 
            else if(op[0]=='D') s.push(s.top());
            else
            {
                Set x1=Setcache[s.top()];
                s.pop();
                Set x2=Setcache[s.top()];
                s.pop();
                Set x;
                if(op[0]=='U') set_union(All(x1),All(x2),INS(x));
                if(op[0]=='I') set_intersection(All(x1),All(x2),INS(x));
                if(op[0]=='A')
                {
                    x=x2;
                    x.insert(ID(x1));
                }
                s.push(ID(x));
            }
            cout<<Setcache[s.top()].size()<<endl;//输出ID对应的集合的大小
        }
    }
return 0;
}

经过激烈地现场角逐,我校的北华启航队、北华二队、北华蓝狮队分别取得一等奖、二等奖、三等奖各一项的优异成绩。名列省属高校第一名。北华启航队并获得ACM/ICPC亚洲赛区参赛资格。

代码实现

#define LOCAL#include<set>#include<stack>#include<iostream>#include<map>#include<vector>#include<algorithm> // for set_union set_intersectionusing namespace std;/*push:空集{}入栈union:出栈两个集合,然后把两者的并集入栈intersect:出栈两个集合,然后把二者的交集入栈add:出栈两个集合,然后把先出栈的集合加入到后出栈的集合中,把结果入栈。*/typedef set<int> Set;map<Set,int> IDcache; //set - id  such as:IDcache[set]vector<Set> SetCache; //id - cache such as:SetCache[id]stack<int> s;int ID{ //光一个map数据结构还不够,这是因为有可能一个Set还没有对应的id,所以这个函数应该包括的功能有:1.创建id 2.返回id    if(!IDcache.count{        SetCache.push_back;        IDcache[x]=SetCache.size()-1;//!!!骚操作    }    return IDcache[x];}int n;int main(){    #ifdef LOCAL    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    #endif    cin>>n;    while{        string exec;        cin>>exec;        if(exec[0] == 'P') s.push);        else if(exec[0] == 'D') s.push;        else{            Set x1 = SetCache[s.top()];            s.pop();            Set x2 = SetCache[s.top()];            s.pop();            Set x;            if(exec[0] == 'U') set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin;//!!!inserter            if(exec[0] == 'I') set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin;//!!!inserter            if(exec[0] == 'A'){                x=x2;                x.insert;            }            s.push;        }        cout<<SetCache[s.top<<endl;    }}

网址:
简称: uva
全称: Valladolid Programming Contest Site
所在国:西班牙
提交方式:web方式和email方式
说明:可能是世界上名气最大,最古老的在线题库了。收集了N卷
的题目,许多国家队的高手都是从这里练出来的。题目包括历届
ACM/ICPC分区赛试题、总决赛试题以及很多其他网友自己出的题
目。题目类型比较全面,难度较平均,但是测试数据非常刁钻,
而且经常更新旧的数据,在别的地方能通过的程序到了uva就可能
无法通过。定期有比赛,并且可以利用它的系统主办自己的比赛。
唯一的缺点是系统太烂,比赛的时候经常系统崩溃(不过这和参加
的人太多也有关)。

获奖等级

姓名

一等奖

朱国森

二等奖

方易凡、黄呈伟、薛斌

三等奖

高臻、杨洁、符瑞盛

现在 可以解答了
!空集如何表示?
Set()
!{} 和{{}}一样吗?
并不,所以对应id不同
!用什么去储存空集?
用vector 每个id对应一个集合 每个集合也因为做了id的判断所以只会储存一次
!!那么这里有有个问题 既然只储存一次,那如何进行那些交并集的操作呢?
其实那些操作是通过栈里的整数(id)调用vector中对应的集合,同意集合如果需要,可以进行任意次数的调用
!各种操作的函数是什么?
这个对于小白的我有一些困难,就把标程中的写一些
!!栈 push() pop() top()
!!vector push_back() size()(虽然不只是关于vector容器)
威尼斯人娱乐场官网,!!集合 set_union(迭代1,迭代2,inserter(迭代3))
set_intersection(同上)
!各个空集之间如何进行区分?
用映射给不同集合分配不同id,并存在vector里,随时进行调用

ACM/ICPC(国际大学生程序设计竞赛)是世界上规模最大、历史最长、影响最深的全球性计算机专业竞赛。2007年,经ACM/ICPC国际组委会授权,东北三省及内蒙古地区(黑龙江、吉林、辽宁、内蒙古)联合设立ACM/ICPC中国东北赛区。此竞赛展示了大学生的创新能力、团队精神和在压力下学生独立编写程序、分析和解决问题的能力。竞赛以紧密结合教学实际,着重基础、重视前沿为原则,通过竞赛提高大学生程序设计能力和学校计算机科学教学水平;促进计算机科学与技术及相关专业的专业建设与课程建设;增进高校教师之间以及参赛选手之间的交流与合作;引导高校在教学中注重培养大学生的创新设计能力、综合设计能力和团队协作精神。

网址:
简称: zju/zoj
全称: ZJU Online Judge Contests
所在国:中国
提交方式:web方式
说明:目前国内唯一一个在线题库。NJU的Settler队
主要就在这里训练,因为不要出国,很方便。目前有
6卷题目了,题目大多数是以前的ACM/ICPC分区赛试
题和一些浙大ACM队员自己出的题目。定期有比赛。


为了使更多的学生能在此竞赛中得到锻炼,学院认真进行2008年参赛的组织和准备,举行了210人70个队报名参加的校内预选赛,从中选拔出20个代表队。经过五个多月的培训,在紧张的吉林省ACM/ICPC
大学生程序设计竞赛预选赛中我校有13支队伍进入了现场决赛,并取得了优异成绩,其中三支队伍脱颖而出进入东北三省现场决赛。

网址:
简称: ural
全称: Ural State University Problem Set Archive with Online Judge
System
所在国:俄罗斯
提交方式:web方式和email方式
说明:这也是一个著名的题库,因为是俄罗斯人办的,题目的数
学味道比较浓。定期有比赛。这里的题目风格和ACM/ICPC不太相同,
题目数学趣味浓,有一定难度,很多题目都是那种需要一些小技巧的,
一旦想出来了程序可能只有几十行。中国的很多搞OI的中学生在这里
做题,这里的题目比较适合中学的OIer。

一开始理解不了的地方在

网址:
简称: sgu
全称: Saratov State University :: Online Contester
所在国:俄罗斯
提交方式:web方式
说明:一个比较新的题库,同样因为是俄罗斯人办的,题目的数学
味道很浓。定期有比赛。

Setcache.push_back(x);
    return IDcache[x]=Setcache.size()-1;
 cout<<Setcache[s.top()].size()<<endl;

以上这几个是比较适合参加ACM/ICPC的同学训练用的题库,还有一些
诸如USACO等题库,基本上就是面向中学生的,这里就不提了。

这两句,一直以为是这样的

基本算法与数据结构中文索引:

    0       1      2     3......
0 {}
1 {{}}
2 {{{}}}
...

Data Structures 基本数据结构
Dictionaries 字典
Priority Queues 堆
Graph Data Structures 图
Set Data Structures 集合
Kd-Trees 线段树
Numerical Problems 数值问题
Solving Linear Equations 线性方程组
Bandwidth Reduction 带宽压缩
Matrix Multiplication 矩阵乘法
Determinants and Permanents 行列式
Constrained and Unconstrained Optimization 最值问题
Linear Programming 线性规划
Random Number Generation 随机数生成
Factoring and Primality Testing 因子分解/质数判定
Arbitrary Precision Arithmetic 高精度计算
Knapsack Problem 背包问题
Discrete Fourier Transform 离散Fourier变换
Combinatorial Problems 组合问题
Sorting 排序
Searching 查找
Median and Selection 中位数
Generating Permutations 排列生成
Generating Subsets 子集生成
Generating Partitions 划分生成
Generating Graphs 图的生成
Calendrical Calculations 日期
Job Scheduling 工程安排
Satisfiability 可满足性
Graph Problems — polynomial 图论-多项式算法
Connected Components 连通分支
Topological Sorting 拓扑排序
Minimum Spanning Tree 最小生成树
Shortest Path 最短路径
Transitive Closure and Reduction 传递闭包
Matching 匹配
Eulerian Cycle / Chinese Postman Euler回路/中国邮路
Edge and Vertex Connectivity 割边/割点
Network Flow 网络流
Drawing Graphs Nicely 图的描绘
Drawing Trees 树的描绘
Planarity Detection and Embedding 平面性检测和嵌入
Graph Problems — hard 图论-NP问题
Clique 最大团
Independent Set 独立集
Vertex Cover 点覆盖
Traveling Salesman Problem 旅行商问题
Hamiltonian Cycle Hamilton回路
Graph Partition 图的划分
Vertex Coloring 点染色
Edge Coloring 边染色
Graph Isomorphism 同构
Steiner Tree Steiner树
Feedback Edge/Vertex Set 最大无环子图
Computational Geometry 计算几何
Convex Hull 凸包
Triangulation 三角剖分
Voronoi Diagrams Voronoi图
Nearest Neighbor Search 最近点对查询
Range Search 范围查询
Point Location 位置查询
Intersection Detection 碰撞测试
Bin Packing 装箱问题
Medial-Axis Transformation 中轴变换
Polygon Partitioning 多边形分割
Simplifying Polygons 多边形化简
Shape Similarity 相似多边形
Motion Planning 运动规划
Maintaining Line Arrangements 平面分割
Minkowski Sum Minkowski和
Set and String Problems 集合与串的问题
Set Cover 集合覆盖
Set Packing 集合配置
String Matching 模式匹配
Approximate String Matching 模糊匹配
Text Compression 压缩
Cryptography 密码
Finite State Machine Minimization 有穷自动机简化
Longest Common Substring 最长公共子串
Shortest Common Superstring 最短公共父串

实际上是这样的

书:
算法类:
N. Wirth, Algorithms + Data Structures = Programs, Prentice-Hall,
Englewood Cl
iffs, 1975.

    0      1      2       3
    {}     {{}}   {{{}}}  {{{{}}}}...

N. Wirth, Systematic Programming An Introduction, Prentice Hall, 1973.

而栈里是这样的

A. Engel, Exploring mathematics with your computer, The Mathematical
Associati
on of America, 1993.

  |0|1|3|2|1|0|1|

H. Papadimitriou, K. Steigltz, Combinatorial optimization – Algorithms
and co
mplexity, Dover, PUBNS, 1998.

所以栈里的数字对应的其实就是相应的id,取vector中相应的唯一set,当需要合并的时候
是取set两个变量来以stack里的数值来取出vector里的set

A. Vitek, I. Tvrda i dr., Problems in programming / experience through
practic
e, John Wiley & Sons Ltd., 1991.

下面是网上抄的一段摘要 ——————————————————————————————
这道题是一个编码问题,即将某种数据结构通过一定的方法转化为独特的整数。这样就可以用整数来进行操作,大大简化了程序。
对于这道题中的集合来说,一个集合包含了0或多个集合,并且可能有多层嵌套,无法用STL的set来模拟。但是我们可以给每一种集合分配一个ID。比如我们给{}分配1,{{}}就可以表示成{1},我们给他分配2。{{},{}}就可以表示为{1,
1},我们给他分配3。{ {} , {{}} , {{},{}} }就可以表示为{1, 2,
3},我们可以给这个集合分配4。这样,我们就可以把集合的集合变成整数的集合,即便有再多嵌套,都可以用一个简单的整数来表示。
于是在读入操作的时候,我们判断新生成的集合是否出现过。如果出现过,直接用它对应的ID替换他。如果没出现过,则给他分配一个新的ID,并把它存在数组中ID的位置上
判断最顶部集合的大小,只需要根据ID去数组中找到这个集合,并查看这个集合中多少个元素。
——————————————————————————————————————————
大概就是这样了 至于迭代器,明天再加深了解,今天得做完这章。

T. H. Cormen, C. E. Leiserson, R. L. Rivest, S. Stein, Introduction to
Algorit
hms, The MIT Press, 2001.

D. E. Knuth, The Art of Computer Programming, 2nd Edition,
Addison-Wesley, Vol
ume 1: Fundamental Algorithms, 1997.; Volume 2: Seminumerical
Algorithms, 1997
.; Volume 3: Sorting and Searching, 1998.

Z. Michalewicz, D. B. Fogel, How to Solve It: Modern Heuristics,
Springer-Verl
ag Berlin, 1999.

Steven S. Skiena, The Algorithm Design Manual, Springer-Verlag New York,
Ins.,

A. Shen, Algorithms and Programming – Problems and Solutions, Birkh?user
Bosto
n, 1997.

计算机算法导引 机械

赛题分析类:
ACM 试题分析(一)、(二)、(三) 吴文虎 清华
ACM 国际大学生程序设计比赛入门 郭嵩山(中山) 机械出版
组合数学/图论/奥林匹克信息学国内外赛题分析 吴文虎 王建德
ACM/ICPC 试题分析 王建德

理论类:
M. Sipser, Introduction to Theory of Computation.

H. Lewis & C. Papadimitriou, Elements of the theory of computation.

J. Hopcroft, R. Motwani & J. Ullman. Introduction to Automata
Theory, Languages, and Computation.

原文链接:

相关文章