集合 Description 给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ 109，并且每个集合的元素个数不大于105。我们希望求出A、B之间的关系。 任 务 ：给定两个集合的描述，判断它们满足下列关系的哪一种： A是B的一个真子集，输出“A is a proper subset of B” B是A的一个真子集，输出“B is a proper subset of A” A和B是同一个集合，输出“A equals B” A和B的交集为空，输出“A and B are disjoint” 上述情况都不是，输出“I’m confused!” Input 输入有两行，分别表示两个集合，每...

魔板 Description 在成功地发明了魔方之后，拉比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板： 1 2 3 4 8 7 6 5   我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。   这里提供三种基本操作，分别用大写字母“A”，“B”，“C”来表示（可以通过这些操作改变魔板的状态）： “A”：交换上下两行； “B”：将最右边的一列插入最左边； “C...

A-B 数对 题目描述 出题是一件痛苦的事情！ 相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！ 好吧，题目是这样的：给出一串数以及一个数字 C，要求计算出所有A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入格式 输入共两行。 第一行，两个整数 N,C。 第二行，N 个整数，作为要求处理的那串数。 输出格式 一行，表示该串数中包含的满足 A−B=C 的数对的个数。 输入输出样例 输入 #1 4 1 1 1 2 3 输出 #1 3 说明/提示 对于 75% 的数据，1≤N≤2000。 对于 100% 的数据1≤N≤2...

统计数字 Description 某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 Input 输入包含n+1行；   第一行是整数n，表示自然数的个数；   第2~n+1每行一个自然数。 Output 输出包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 Sample Input 8 2 4 2 4 5 100 2 100 Sample Output ...

旅行 Description Z小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N个景点（编号为1,2,3,…,N），这些景点被M条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。 Input 第一行包含两个正整数，N和M。 接下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y...

矩形 Description 在一个平面上有n个矩形。每个矩形的边都平行于坐标轴并且都具有值为整数的顶点。我们用如下的方式来定义块。 每一个矩形都是一个块。 如果两个不同的矩形有公共线段，那么它们就组成了一个新的块来覆盖它们原来的两个块。 例子： 在图1中的矩形组成了两个不同的块。  Input 在输入文件PRO.IN的第一行又一个整数n，1 <= n <=7000，表示矩形的个数。接下来的n行描述矩形的顶点，每个矩形用四个数来描述：左下顶点坐标(x,y)与右上顶点坐标(x,y)。每个矩形的坐标都是不超过10000的非负整数。 Output 在文件PRO.OUT的第一行应当仅有一个...

家谱 Description 现代的人对于本家族血统越来越感兴趣， 现在给出充足的父子关系， 请你编写程序找到 某个人的最早的祖先。 Input 输入文件由多行组成， 首先是一系列有关父子关系的描述， 其中每一组父子关系由二行 组成，用#name 的形式描写一组父子关系中的父亲的名字，用+name 的形式描写一组父子关 系中的儿子的名字；接下来用?name 的形式表示要求该人的最早的祖先；最后用单独的一个 $表示文件结束。规定每个人的名字都有且只有 6 个字符，而且首字母大写，且没有任意两 个人的名字相同。最多可能有 1000 组父子关系，总人数最多可能达到 50000 人，家谱中的 记载不超...

最短网络 Description 农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000 Input**** 第一行： 农场的个数，N（3<=N<=100）。 第二行…结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成...

线段树练习题一 Description 桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？  Sample Input 20 //桌面总宽度 4 //盒子数量 1 5 3 8 7 10 13 19 Sample Output 15 Hint 数据范围 1<=n<=100000,1<=m<=100000,保证坐标范围为[1,n]. 题目分析 这道题目是一个经典的离散化模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总...

图形面积 Description 桌面上放了N个平行于坐标轴的矩形，这N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。 Input 输入第一行为一个数N（1≤N≤100），表示矩形的数量。下面N行，每行四个整数，分别表示每个矩形的左下角和右上角的坐标，坐标范围为–108到108之间的整数。 Output 输出只有一行，一个整数，表示图形的面积。 Sample Input 3 1 1 4 3 2 -1 3 2 4 0 5 2 Sample Output 10 题目分析+解题思路 平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）...

挤牛奶 题目描述 三个农民每天清晨 5 点起床，然后去牛棚给三头牛挤奶。 第一个农民在 300 秒 (从 5 点开始计时) 给他的牛挤奶，一直到 1000 秒。第二个农民在 700 秒开始，在 1200 秒结束。第三个农民在 1500 秒开始，2100 秒结束。 期间最长的至少有一个农民在挤奶的连续时间为 900 秒 (从 300 秒到 1200 秒)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为 300 秒 (从 1200 秒到 1500 秒)。 你的任务是编一个程序，读入一个有 n 个农民挤 n 头牛的工作时间列表，计算以下两点(均以秒为单位): 最长至少有一人在挤奶的时间段。...

涂色 Description 有一根长度为1000000000的棍子，一开始涂成白色。 棍子上有刻度，左端点为0，右端点1000000000。 由于某种原因这根棍子的某些部分被重新涂过了。 重新涂的颜色可能是黑色或着白色。 棍子总共被依次重新涂了N(1<=N<=5000)次。 找出最后最长的白色段。 Input 第1行一个数N。 接下来N行表示一次涂色，格式如下： ai bi ci ai和bi为整数,ci是字母b或w。 表示把ai和bi之间那段涂成ci色(w白***黑色)。 0<=ai<=bi<=1000000000。 Output 一行，两个数x和y(x如果有多...

线段树练习题一 Description 桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？  Sample Input 20 //桌面总宽度 4 //盒子数量 1 5 3 8 7 10 13 19 Sample Output 15 Hint 数据范围 1<=n<=100000,1<=m<=100000,保证坐标范围为[1,n]. 解题思路 线段树 线段树练习题一（离散化） AC代码 #include<cstdio> #include<iostream> u...

线段树练习题二 Description 桌子上零散地放着若干个不同颜色的盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远(输入时,由底向上,从左到右)。  Sample Input 16 //桌子长度 5 // 盒子数量 4 7 12 14 1 5 6 10 11 16 Sample Output 4 Hint 1<=n<=100000,1<=m<=100000,保证坐标范围为[1,n]. 解题思路 线段树 每种箱子为一种颜色，如：1,2,3,4…… 区间初始颜色为0 如果这个区间有多种颜色就标记为-1 否则就标记为初始颜色或箱子颜...