ACM校赛

第一次参加ACM比赛,发现自己好菜啊!!!!!!(当然初赛都没过)

通过比赛发现我的算法真的一言难尽,题目能做出来,只是算法的问题了,每次提交都是超时。

看来后面要好好学习一下算法了。

下面附上比赛的题目,供以后学习:


问题 A: 括号序列!
时间限制: 1 秒
内存限制: 128 MB

题目描述

给你一个括号序列,让你看看它对不对劲!
(一个括号序列如果是回文的,它就是对劲的

输出

多组数据,第一行是一个t,代表数据组数(括号序列长度<=100,t<=100)
如果这个括号序列很对劲,就输出"Yes",
如果这个括号序列不对劲,就输出"Nope"(不加双引号)

样例输入

2
()()
())(

样例输出

Nope
Yes

提示

仔细读题!


问题 B: 快速排序!
时间限制: 0 秒
内存限制: 128 MB

题目描述

给出一个长度为n的序列,要求出现过的找出第二大的值,数据保证不会所有数相同

输出

第一行一个数n,代表序列长度。
第二行为n个数A_i,为序列中的数。
(n<=1e7,0<=A_i<=1e9)

输出

输出一个数,为序列中的第二大的值

样例输入

6
1 5 5 5 4 3

样例输出

4

提示

读入量可能很大,建议不要使用cin,使用scanf即可


问题 C: 二重循环!
时间限制: 1 秒
内存限制: 128 M

题目描述

给出两个长度为n(n<=1e6)的数组,求出ans

输入

第一行一个数字n代表两个序列的长度
第二行为长度为n的序列,代表A_i数组
第三行为长度为n的序列,代表B_i数组
(n<=1e6;0<=A_i,B_i<=10)

输出

输出一个数字为ans的值

样例输入

4
1 2 3 4
4 3 2 1

样例输出

85

提示

样例解释:
1*4+2*4+2*3+3*4+3*3+3*2+4*4+4*3+4*2+4*1=85


注意:答案可能会超过int的范围


问题 D: 中位数!
时间限制: 1 秒
>内存限制: 128 MB

题目描述

给出长度为n的序列,考虑它的2^n-1个非空子集中,f(S)为当前集合中包含的元素和。
求出2^n-1个f(S)的中位数(显然2^n-1是个奇数)

输入

第一行一个整数n,代表序列长度
第二行n个整数A_i,代表序列元素。
(n<=500,A_i<=500)

输出

输出一个数字,为f{S)的中位数。

样例输入

3
1 2 1

样例输出

2

提示

在样例中,2^n-1个f(S)为{1,1,2,2,3,3,4},中位数为2.


问题 E: 玩游戏!
时间限制: 1 秒
内存限制: 128 MB

题目描述

lzh和zbr在玩游戏!规则如下:

现在又n堆石子,双方轮流进行取石子操作,由lzh先手,每次当前操作的人可以选择以下两种操作的一种:
1.选择一堆数量最多的石子,将其全部拿走(有多堆数量最多的石子只选择一堆拿走)
2.在所有堆中拿走一个石子

拿走最后一颗石子的人输


由于lzh太聪明了!总会选择最优操作!zbr想知道,自己还有没有机会能赢呢。

输入

第一行是一个数n,代表石子的堆数
第二行有n个数A_i,代表每堆石子的数量。
(n<=1e5,1<=A_i<=1e9)

输出

如果lzh必胜,输出一行"GG"
否则输出一行"Ohhh!"(不包含双引号)

样例输入

3
1 2 1

样例输出

GG

提示

样例二
3
1 2 3
输出:Ohhh!


问题 F: 大型同性交友平台
时间限制: 6 秒
内存限制: 128 MB

题目描述

先抑云一波
其实,这世界本没有什么同性恋、异性恋、双性恋、姐弟恋、师生恋、神马恋等等.——只是两个人相爱了,就这么简单。
——《There For You》
现在有N个人,他们不是0就是1,现在交友平台想让他们凑成对的数量尽可能多
配对的条件如下
i<j
a[i]= 1 且 a[j]=0
这样i和j就可以凑成一对
已经凑成一对的不能再和其他人凑成一对,
现在给你一个长度为N的序列 a
一个整数q,代表q次询问
每次询问给定一个L,R ,问[L,R]区间最多可以凑成多少对

输入

第一行一个整数N 代表数组长度
第二行N个整数  代表数组的值  每个数为0或1
第三行一个整数q 代表询问次数   N, q <= 300000
下面q行,每行两个整数L,R ,表示询问的区间

输出

输出q行,每行输出区间[L,R]的人所能凑成的最多对数

样例输入

10
0 1 0 1 0 0 1 0 1 0
1
1 10

样例输出

4

点赞
  1. 星座占卜说道:
    Firefox Windows 10

    文章写的很好啊,赞(ㆆᴗㆆ),每日打卡~~

    1. 苏泽 苏泽说道:
      Google Chrome Windows 10

      阿里嘎多! ୧(๑•̀⌄•́๑)૭

      1. 路过打酒说道:
        Google Chrome Windows 10

        啦啦啦啦啦

  2. 路过打酒说道:
    Google Chrome Windows 10

    啦啦啦啦啦

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00