【题解】牛客NOIP暑期七天营-普及组2

A．蘑菇

由于初始蘑菇数是0，根据题意答案应该等于所有蘑菇数量为偶数的采集点的蘑菇数量之和。

所以如果有蘑菇数量为奇数的采集点，就使其中数量最多的加一，如果没有就不使用魔法，然后把所有数量为偶数的采集点数量加起来就是答案。

B．括号

20分，暴力枚举。

40分，暴力搜索。

对于所有的数据都可以直接贪心计算，

循环一次可以算出能够直接消除掉的括号对，设为x。如果将他们全部消除，括号串中任何一个’)’之前都不会有’(’,任何一个’(’之后也不会有’)’，即”))...)(((...(”的形式。我们设此时还有a个’(’和b个’)’,按照贪心的方法，一个”((”的子串可以通过”((”->”()”->“”的方法使用两次操作消除，同理”))”也可以通过两次操作消除，”)(”则要通过三次操作消除。所以如果a,b都是偶数，则答案为a+b+x

如果a,b都是奇数，则答案为(a-1)+(b-1)+3+x,即a+b+x+1.

整个过程可以在O(n)的复杂度内求解。

C．硬币

50分的数据使用特判&枚举可以通过。

100分：

可以O(m)线性算出来

要使用概率dp也可以。

没有卡时间，需要使用滚动数组，否则部分样例可能超内存

D．线段

8分，暴力枚举查询和线段和颜色

36分，同样暴力枚举，可能需要离散化颜色，否则有超时的可能。

60分，考虑n,m为2e5的情况，如果每条线段颜色不同，题目即转化为区间内有多少条完整线段的问题，关于此问题，将线段和查询分别按右端点从小到大排序，依次加入这些线段的左端点并查询区间内包含多少个线段的左端点，因为当前加入的线段的右端点均小于等于当前查询的右端点，区间内左端点的数量就是完整线段的数量。如果颜色只有一种，那么只需要判断数量是不是0，更简单。

80分，由于颜色仅有30种，按照之前的方法加上用线段树可查询区间内有多少种不同颜色的左端点。按位维护颜色即可。