竞赛试题汇总

ACM程序设计普及大赛

如果没有特殊说明，每个测试点时限均为1000ms，内存限制256Mb。

A.谁是主角

B.投票统计

C.分享巧克力

D.弹幕过滤器

E.春假

F.红豆的故事

G.立迪的n维数组

H.ACM组队须知

I.立迪的信号覆盖

J.立迪的2048
 

A.谁是主角

题目描述

    出题常常是大家互黑的最好时机，传说中被出题人选为题目的主角，不仅可能在题目描述部分节操全无，赛后还会有很长一段时间人品低到爆。

    那么问题来了，如何选择题目的主角呢？立迪想了一个好办法：举办数场训练赛，缺勤次数最多的就会荣登主角的宝座。

    由于时间紧迫，训练赛只举办了两场。但即使如此，仍有恰好一人缺勤一次，于是不幸中招成为主角。

    每次训练时，每位参与者的标识符（一个整数）会被系统记录下来。然而由于各种奇葩问题，记录的顺序被打乱。你的任务时，找出谁只参加了一次训练赛，并输出他的标识符。

输入格式

    第一行1个整数N (1 <= N <= 100,000,001，且为奇数) ，代表训练赛参赛纪录的条数。

    第二行N个整数A1 .. AN (1 <= Ai <= 1,000,000,000) ，代表N条乱序的参赛纪录，值为参赛者的标识符。保证有且只有一个标识符在序列中仅出现1次，其余所有标识符恰出现两次。

输出格式

    一个整数，被选中的主角的标识符 。

样例输入

11

1 2 3 1 3 2 2333333 4 5 4 5

样例输出

2333333

样例解释

2333333仅出现了一次，输出之。

提示

1.    不要把所有数据全部读入内存。

2.    对C++用户，请使用scanf而不是cin读入数据。

3.    不要想复杂了。

B.投票统计

题目描述

    ruc信息学院要求学生们给心目中最佳老师投票。学生们把心中最佳老师的编号写在了票上，最后交给了你。因为学生人数太多，所以需要你统计出今年最佳的老师的编号是多少。

    另外，如果有两位老师的票并列第一，则输出nobody。

输入格式

第一行包含一个整数N（1≤N≤1000）。下一行包含N个整数ai，表示每个同学选的老师的编号（1≤ai≤1000）。

输出格式

一行，nobody或者老师的编号。

样例1

5

1 1 2 2 3

答案

nobody

样例2

5

2 2 2 1 1

答案

2

C.分享巧克力

题目描述

    DD是一个爱吃巧克力的孩子，每年要买一吨左右的巧克力。不过他是一个乐于分享的好孩子，他常常会沿着格子把巧克力掰成小块分享给大家。

    掰的巧克力多了，DD开始思考一个问题，假设他手上有一片巧克力是NxM的矩形，横竖由格子分开，每掰一次，巧克力都会变成更小的两块。

    由于DD有强迫症，所以他一定会沿着横线或者竖线小心地掰开。如下图：

   v

变成

和

    DD想知道最少需要掰几次才能把这一片巧克力全掰成1x1的小方块？

输入格式

两个正整数N和M，代表巧克力的长和宽。

0 < N, M <= 1000

输出格式

一个整数，代表最小步数。

样例输入

2 2

样例输出

3

样例解释

Step 1: 2x2->1x2, 1x2 沿横线掰开

Step 2: 1x2->1x1, 1x1 沿竖线掰开

Step 3: 1x2->1x1, 1x1 沿竖线掰开

D.弹幕过滤器

问题描述

输入一个弹幕列表（每条弹幕包含发送时间、发送者和内容），以及一个过滤列表（包括若干个用户名），请输出所有发送者不在过滤列表中的所有弹幕，并按照时间排序。

输入格式

第一行包含2个整数N, M(N, M <= 1,000)，弹幕的条数和过滤清单的条数；

接下来N行，包含一个整数Ti (Ti <= 1,000,000,000)和两个不间断的字符串Si、Ci，分别表示发送时间相对视频开始时间的毫秒数（保证同一时刻只会有一条弹幕），发送者和弹幕内容；

接下来M行，每行一个不间断的字符Ni，为过滤列表中的每一项。

所有字符串保证长度不超过100个字符。

输出格式

过滤并排好序的弹幕，每行一个，格式同输入中的弹幕。

样例输入

3 1

12 Zhazha yoooooo

11 Zhazha 2333333

10 Lidi 2333333

Lidi

样例输出

11 Zhazha 2333333

12 Zhazha yoooooo

E.春假

Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

题目描述

       inksink来自一个国际一流的著名大学RUC，这所学校每年临近五一都会有一段神奇的春假。

    据传，每年春假的长度是跟rp正相关的（真的吗？并没有任何证明）。然而，这并没有什么luan用。

       RUC的正式春假是5.1-5.5。

    但是，每年都会有一些神奇的事情发生。比如说，还记得，那是2017年的五月，RUC竟然放了九天春假！这是为什么呢？因为5.1-5.5恰好是周一到周五，所以跟前后两个周末恰好能连起来。是的，RUC的春假会跟前后的周末连在一起。但就像2015年的五月，5.1是周五，所以春假只有5天，因为春假不会跟任何周末连在一起。

    值得庆幸的是，RUC并不会因为春假占用了时间而进行补课，也就是说前后的周末都不会被占用（活在梦里）。      现在问题来了。

    inksink想要知道他每年可以拥有几天春假可以粗去浪（说得就跟有女朋友一样）～

       作为报酬，inksink叫兽会送给第一个解决这个问题的队伍一只可爱羊驼玩偶（这是真的）。这道题很水的!讲真.

输入格式

          每个测试点会有多个样例输入。

          第一行是一个整数T，代表将会由T个测试数据。

          接下来T行,每行是一个整数x（1928<=x<=9999）。    

输出格式

          对于每个测试数据，输出这一年春假有几天。

样例输入

3

2015

2016

2017

样例输出

5

6

9       

F.红豆的故事

问题描述

    勇者被大魔王打败后失去了视力并来到了一个未知的世界，这里只有羊驼，猴子，和章鱼老师。

    勇者只能用手摸了解这个世界，所以你只知道他们四肢的长短，头和尾巴长度，请判断他们都是什么。

    其中羊驼的头和尾巴一样长，猴子的尾巴比头长/

    除了章鱼老师他们四肢都一样长

输入格式：

    6个数字，乱序代表勇者摸到的长度

输出格式：

    你觉得他是什么，羊驼（Alpaca）,猴子（Monkey）,章鱼老师（Octopus）

样例：

input:

4 2 5 4 4 4

output:

Monkey

input:

4 4 5 4 4 5

output:

Alpaca

input:

1 2 3 4 4 4

output:

Octopus

G.立迪的n维数组

题目描述

        立迪有一个n维的数组a[d1][d2]...[dn],第i维的变化范围是0～di-1,这个数组中从a[0][0]...[0]到a[d1-1][d2-1]...[dn-1]存储了m=d1*d2*...*dn个整数。

        输入数据会按照a数组在内存中的存储顺序依次给出这m个数。

       比如当n=3时：

       for(i=0;i<d1;i++)

              for(j=0;j<d2;j++)

                     for(k=0;k<d3;k++)

                            cin>>a[i][j][k]

       即可实现将m个整数导入数组当中。

        然而此时我们的问题才刚刚开始。在这个n维数组当中，某两个位置是相邻的，当且仅当这两个位置只有某一维相差1，而其他维度均相同。比如当n=3时，a[0][0][0]和a[0][1][0]相邻，a[0][1][0]和a[0][2][0]相邻，但需要注意的是a[0][d2-1][0]和a[0][0][0]并不相邻。

        立迪每次可以选择两个相邻的位置，将这两个位置上储存的数字，同时加上或减去一个任意大小的整数。我们想知道，立迪是否可能通过若干次的上述操作，将数组中所有的数字都变为0.因为一旦立迪发现所有数字都变成0，就会去做别的事情，那样我们就可能找不到他了。

输入格式：

        第一行一个整数n，1<=n<=6。

        第二行n个整数，依次为d1,d2,...,dn。1<=di<=10

        接下来m行，每行一个整数，按内存中存储顺序给出n维数组里的m个数。如前文所述m=d1*d2*...*dn，每个数的绝对值均小于等于100

输出格式：

        仅一行，”Yes”表示立迪可能将数组中的所有数字都变成0，”No”表示不可能所有的数字同时为0。

样例输入1：

2

2 3

1

0

0

1

0

0

样例输出1:

Yes

样例1解释：

a[0][0]=1      a[0][1]=0      a[0][2]=0

a[1][0]=1      a[1][1]=0      a[1][2]=0

a[0][0]与a[1][0]第一维相差1，第二维相同，所以二者相邻。同时减去1，则所有数字同时为0。

样例输入2

2

2 3

1

0

0

0

1

0

样例输出2:

No

提示：可以先在一维和二维的情况中寻找规律，然后再将规律推广到高维的情况即可。

H.ACM组队须知

Time Limit:3000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu

题目描述

          是的，我是标题党。         ——inksink

          事情是这样的，RUC要办一个ACM比赛，比赛以团队对抗的形式举行。每个团队有两个人。

          有很多同学对于组队的问题十分苦恼，于是他们来找大师。

          “大师，为什么我觉得我和队友的水平都很高，但是比赛成绩却总是不高呢？”

       大师指了指经书上的‘摩诃’二字。

          一位同学说：“何名摩诃。摩诃是大。心量广大犹如虚空无有边畔。亦无方圆大小。亦非青黄赤白。亦无上下长短。亦无嗔无喜。无是无非。无善无恶。无有头尾。诸佛刹土尽同虚空。世人妙性本空无有一法可得。自性真空亦复如是。善知识。莫闻吾说空便即着空。第一莫着空。若空心静坐。即着无记空。大师的意思是我们的水平并没有想象中的高，还缺乏很多东西，我们应该多加训练是吗？”

          大师说：“唉……我的意思是你们队友之间需要多磨♂合♀磨♂合♀呀～”

          （这是什么奇怪的东西！sorry，剧本载入有误……）（原创剧本，欢迎转载）。

          最后他们找到了靠谱的inksink叫兽。

           Inksink叫兽有一个伟大的发现。

          假设一个ACM团队有两个人，他们的能力分别是A和B。那么这个团队的能力就是A⊕B。⊕是按位异或（对于每一位，值不相同，则异或结果为1；值相同，异或结果为0），比如111⊕000=111，111⊕101=10， 111⊕111=0。

          据此，inksink叫兽做了更深入的研究。他发现，只有一个团队的总体水平比团队里两个人的水平都要高，这个团队才是合适的；否则这两个人就不应该在一起！即满足条件A⊕B>max{A, B}。

          同学们恍然大悟。

          现在inksink叫兽想知道，面前的同学们有多少种不同的组队的可能。只要有至少一个人是不一样的，两个团队就被认为是不同的。可是inksink叫兽并没有时间去做这件事，所以亲爱的同学们能帮inksink叫兽解决这个问题吗？

          作为报酬，inksink叫兽会送给第一个解决这个问题的队伍一只可爱羊驼玩偶（这是真的）。但显然inksink叫兽是个严谨的人(一本正经的胡说八道),为了防止自己的羊驼送不出去,如果这道题没有任何人做出来,那么羊驼将会送给顽强拼搏奖队伍(最后十分钟之内的最后一个AC的非一二三等奖队伍).但显然这还是不严谨的,如果以上条件都不成立.那么羊驼将会送给提交这个题目最多的队伍(若次数相等,AC题目少的队伍优先).最后,若都不成立,那么看inksink叫兽的心情了QAQ.

       PS:inksink叫兽相信,聪明的你一定可以发现答案是可能超过int表示范围的.printf 输出long long 请用%lld.(只能帮到这了^_^)

输入格式

       每个测试点会有多个样例输入。

          第一行是一个整数T(1<=T<=3)，代表将会由T组测试数据。

          接下来是T组测试数据。

       对于每组测试数据，第一行是一个整数N（2 <=N<= 100000），表示有N个同学。接下来一行有N个数，每个数代表了第x个人的水平Dx。（Dx<=10^9）   

输出格式

       对于每组数据，输出一个答案。每个答案占一行。

样例输入

2

3

1 2 3

5

1 2 3 4 5

样例输出

1

6

I.立迪的信号覆盖

题目描述

       立迪的家乡有n个基站，在这个问题中我们只考虑它们的平面位置。每一个基站有一个服务区域：到第i个基站(xi,yi)距离小于等于其服务半径ri的地方均能收到i号基站的信号。这n个基站的服务区域互不重叠（但边界上可以有重叠的点）。

       立迪想要通过一个基站来控制所有的基站。他可以选择任意一个基站作为主站，用自己的念力使主站的服务半径匀速增加，直到所有的基站均能被主站的信号覆盖。一旦某个基站可以接收到主站的信号，主站就可以通过基站将信号传播至该基站的服务范围。

       但这样会导致一个坏处，就是主站的服务区域面积并不是连续变化的。在某些时刻，因为新的基站被控制，主站的服务区域面积将会发生跳变。如果服务区域面积瞬间的增量过大，将会对立迪造成无法挽回的伤害。对于立迪选择第i个基站作为主站，其危险程度定义为上述过程中服务区域面积跳变的最大值。

       例如：

              [0s,3s)，面积从2连续增加到4；

              [3s,4s)，面积从7连续增加到10；

              [4s,...)面积从12开始连续增加。

       第3秒的跳变量为7-4=3，第4秒的跳变量为12-10=2，所以危险程度为最大的跳变量3。

       我们想知道，立迪选择哪一个基站作为主站的危险性最小。如果两个选择的危险程度相同，我们倾向于选择编号更小的基站作为主站。

输入格式：

       第一行一个整数n，代表基站的个数。2<=n<=100

       接下来n行，每行三个整数，xi，yi，ri，依次表示第i个基站的横坐标，纵坐标，服务半径。