【题解】牛客网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:配对