竞赛讨论区 > 【题解】牛客网NOIP赛前集训营-普及组(第一场)
头像
Key酱不是喵
发布于 2019-04-18 18:27
+ 关注

【题解】牛客网NOIP赛前集训营-普及组(第一场)

A:绩点

这道题定位为简单题。前三个点的部分分可以这样做。

第一个点,所有的gpa都相同,因此直接输出任一一门课的gpa即可。

第二个点n=3,只有三门课,暴力输入后手算,为不会数组的同学准备。

第三个数据点,所有科目的学分都是相同的,按照式子计算就与学分无关了,答案就是gpa的平均数。

 

这题的正解是利用数组与for循环,把所有数据读取进来。再按照题目给定的求和式子计算。且考察浮点数计算。

 

B:巨大的棋盘

解决这道题,需要知道,一个既然棋盘是循环的,那么只关心一个操作序列在x坐标与y坐标上走了多少。假设最终走了Lx与Ly,可以把他们分别对n,m取模。T次重复只需要把他们都乘上T即可。对于每次询问,直接坐标加上Lx与Ly。

部分分分别是直接模拟,T次重复没有用乘法而是用加法,以及每次询问重复运算。

 

C:括号

这题的第一档部分分是暴力枚举删掉哪些括号,然后判断是否是合法的括号序列。这个可以使用栈来做,每次遇到一个右括号则弹出左括号,遇到左括号则加入栈中,不合法当且仅当最后有多余的左括号或中途不够左括号弹出。

可以发现只关心中间每一步有多少左括号。可以使用DP。设F[i][j]表示考虑到第i个位置,当前选取的子序列(或删剩的括号序列)结尾恰好为第i个位置。左括号数量为j。那么可以枚举上一个位置i’,以及对应的左括号数量j’。因为i位置必须考虑,则若i为右括号,则j=j’-1,否则j=j’+1。但j要>=0。最后的答案就是F[i][0]的和。这个Dp的复杂度是O(n^3)的。但是可以把i位置不选也加入转移,那么就是F[i][j]->F[i+1][j’]。复杂度O(n^2)。使用滚动数组优化空间即可。

D:配对

直接枚举选择哪些字母配对很慢,可以考虑枚举联通块。当K>7时,显然所有串都能相同了,因为只需要7条边就能让所有字母等价。因此考虑枚举字母的联通块情况。而贪心地想,K肯定用完最好,因此联通块情况就只有S(8,8-K)种情况,其中S为第二类斯特林数。枚举完联通块情况后,每个字符串中,每种字符替代为对应联通块编号,变成等价的字符串。然后计算哈希排序算等价对数。但这样可能超时。可以按字母分别维护每个字母出现位置的哈希值,重新算时复杂度是O(Σ),而不是O(L)的。

std

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐