这场比赛码量小，思维难度适中，不涉及任何高级算法，相信选手们能够顺利体会到AK AC的快乐：）

不知道由于什么原因，过了J的人都没有过I，难道是为了不AK吗？

欢迎在CF上friend出题人。

注意：B题和I题数据已加强，且B题已rejudge。

A、欧几里得

考虑如果a>b，那么gcd(a,b)转移到的gcd(b,a%b)也满足b>a%b。于是我们相当于要从次数少一的一组a,b，将b加上一个或更多个a，就变成次数加一的了。可以观察出每次加一个a是最佳的，就是斐波那契数列。找规律水平高的选手，也可以使用找规律通过此题。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930010

B、括号序列

使用栈，从左到右处理每一个括号：

• 如果是左括号，那么入栈，然后继续读下一个括号
• 如果是右括号，那么就要看这个右括号和栈顶的括号是否匹配
• 如果匹配，那么弹出栈顶的括号，继续读下一个括号，否则说明不合法
• 最后，如果栈为空，说明此括号序列是合法的。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930024

C、子段乘积

本题可以使用线段树，也可以分治，还可以使用尺取法，维护当前区间中有几个0，同时维护不是0的数字的乘积，这种方法需要使用乘法逆元。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930034

D、子段异或

如果[l,r]是合法的子段，说明前缀和中xorsum[r]^xorsum[l-1] = 0, xorsum[l-1] = xorsum[r]。
求出异或前缀和，然后使用map计数每一个数字有多少个前缀和等于那个数字即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930043

E、最小表达式

我们拥有的可以放数字的数位的权值分别是1,1,1,1,1,...,1,10,10,10,10,...,10,100,...（每种各加号个数加一个），于是只需要贪心的将大的数字放到小权值的数位上即可。

考虑题目中的第四个样例：23984692+238752+2+34+
这个样例的数字排序后为['2', '2', '2', '2', '2', '3', '3', '3', '4', '4', '5', '6', '7', '8', '8', '9', '9']，加号有四个，则意味着我们要建立五个数字。每个数字从后向前添加数位，则先添加个位数，十位数，再添加百位数，等等等等。并且我们一定是按照顺序添加，不可能在个位数尚有未填写的情况去填另一个数字的百位数，因为不优。答案为
2369+2359+248+248+237=5461

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930064

F、树上博弈

首先，注意到输掉的唯一方法是自己的唯一一条边有另一个人，那么自己一定是在叶子上。
令两个人之间的距离为D。请注意，每人行动后D增加1或减少1。 因此，每有人走一步D的奇偶性都会改变。
假设最初，在牛牛移动之前，D是偶数。 那么当牛牛移动时D将始终为偶数，而当牛妹移动时D将始终为奇数。
请注意，只要牛牛和牛妹的令牌位于相邻的节点中，D=1。因此，如果D为偶数，则他们不在相邻的单元格中，并且牛牛始终可以移动。
另一方面，由于牛牛总是可以移动，因此他可以向牛妹的方向移动，将牛妹必然会最终移动到叶子上。同样，如果最初D是奇数，则牛妹获胜。
因此，答案取决于距离的奇偶性：如果是偶数，则牛牛获胜，否则牛妹获胜。
可以发现，只有牛牛的初始位置和牛妹的初始位置距离为偶数时，牛牛获胜。只需要分别求出深度为奇数的点和深度为偶数的点的数量即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930091

G、音乐鉴赏

如果随机占比为 ，一个人分数为 ，那么他优秀的概率为 。

这个概率可以这么计算：首先把分数减90，大于0就优秀，那么就变成，其中y是一个随机的0到90之间的数字。，，这个概率就是上面所写的概率。

，解方程可知答案为。

也可以使用二分求解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930115

H、坐火车

从左向右遍历，使用树状数组维护每种颜色的该车厢左右的对数即可。

如下一个颜色是，应当先减去下一个颜色作为右边的匹配数，再加上当前颜色作为左边的匹配数，注意不要爆long long。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930143

I、匹配星星

这道题目可以使用贪心算法求解。先按照X坐标从小到大排序，然后对于每一个点

• 如果Z = 1，查询比他X坐标小的Y坐标最大的Z= 0的点，进行配对，如果配对成功则将那个点都从候选点中排除。
• 如果Z = 0，将该点加入候选点。

证明

假设最优方案中排序后的第 1 个没有按贪心策略匹配的点 ，在设 在中它能匹配的 最大的点为 ，如果 被点 匹配了，有两种情况：

• 原先 没有和任何匹配，则直接去掉 的匹配，将 和 匹配。
• 原先 和 匹配，则将 改成和 匹配，将 和 匹配，由于， 这样的匹配一定是成立的。并且修改后的匹配数不会变少，因此按照该贪心策略可以得到最优解。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930163

J、二维跑步

首先观察得到所有x坐标相同的位置无论y坐标如何是等价的，然后看出每走一步，如果x坐标增加1则有3种方案，x坐标不变有1种方案，x坐标减小1就有2种方案。

枚举x坐标不变了次，那么就有步x坐标改变。如果有次x坐标增加，则知道,那么就有

那么这种情况下的仅仅走路的方案数就是

考虑这个东西怎么求呢？首先，我们设,则显然有，这是由于。那么我们考虑如何做到地从推出了：我们考虑，如果错位相加，那么就能够正确的得出中的大多数项，而错误的项只在区间的一边，我们只需要消除这些错误影响即可。

而我们又知道当，那么这道题就解决掉了，复杂度为。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42930188

被NTT卡过去了，早就该出1e7 QwQ。