第二场初赛

rk77，其中1003问了gsq，发挥还算可以吧

1001

签到，漏考虑负数情况wa了三发

签到。贪心。少考虑一种情况 wa了一发

题意：

给一张无向完全图，每条边有一个颜色，为黑色或者白色。你初始在点 s 上，你每次可以从当前的点经过一条边走到另一个点上，并将走过的边的颜色翻转。你想要把图中所有的边全都变为黑色，要求最小化走过的边的条数，求这个最小值，或者判断无解。n1000

解：

考虑把所有白边处理成一张图，即形成多个连通块。最优走法显然应该是起点->走完初始连通块->经过一条黑边->走连通块1->经过刚才染白的边回来->走连通块2->…

如果需要这样的方案能走成功，则除了起点所在连通块外所有连通块必定存在欧拉回路。起点所在连通块必定存在欧拉路径，且s可以作为起点。

比赛时由于没有想清楚欧拉路的判定以及把黑白颜色搞反导致wa三发

题意：

初始有a[i]=i的数列，给一个数列，问该数列是进行3n次随机交换的还是7n次的。

解：

显然不动点个数会有很大差异，利用本地随机数据跑出来大致范围即可。

简单思维题。由于交到1007去了wa了一发，没开longlong wa了一发。

题意：

给一棵以 1 为根的树，初始树上若干个点上有人，一个人一秒可以选择不动或走向父亲节点，问 k 秒后最少有几个节点上有人。

解：

考虑贪心。若某个点的k重儿子上有人且该点的>k重儿子上的人都被处理掉了，则将子树k层内的人都集中到该点必定是最优方案的一种。比较难说清楚，但是感受一下就是比较显然的。

五百名出头，与T恤无缘了

签到，由于没考虑全情况wa了3发

有一个数字 x 和若干个操作，每个操作是 +a_i 或者乘 ×a_i 中的一种。你可以重新排列这些操作的顺序，然后对数字 x 执行这些操作。

比如说三个操作是 +a_1, +a_2, ×a_3。如果按顺序执行这三个操作，那么得到的结果是 ((x+a_1)+a_2) ×a_3。如果排列成 +a_2, × a_3, +a_1，那么得到的结果是 ((x+a_2)× a_3)+a_1。

我们会发现，有一些操作顺序计算出来的结果是本质相同的，比如说+a_1, +a_2, ×a_3和+a_2, +a_1, ×a_3这样运算下来结果是一样的。我们认为两个操作顺序计算的结果本质相同，当且仅当无论代入什么数，计算出来的结果都是一样的。

请问有多少种本质不同的操作序列。换句话说就是最多能找到多少个操作序列，使得这些操作序列任意两个都不是本质相同的。由于答案很大，输出对10^9+7取模的结果。

在这个题目中，我们只会给出加法操作和乘法操作的个数，分别是n, m，并不会给出具体的顺序和数字。容易发现，答案与具体的顺序和数字无关。

解：

第二类斯特林数，O(maxn*maxm)预处理,O(T*min(n,m))回答询问。

题意：

与1002一样的操作，给定a数组，问得到的结果中对1e9+7取模最小是多少。n=10,数据完全随机生成，T=1000

TLE解：

考虑乘法操作5个、加法操作5个时的本质不同情况也只有大约3e5个，1000组数据似乎恰能卡过。直接暴力dfs，本机10s，TLE。

卡常ac解：

dfs时压位，减小常数

正解（摘自题解）：

注意到，假设我们枚举完乘法的顺序，那么我们每个加法操作的贡献只和它们的位置相关，也就是插在哪几个乘法之间，并且是独立的。所以等价于每个加法操作有若干种选择，你要选择数字加起来使得 mod p最小。那么可以用 meet in middle 的方法解决。

然后如果乘法个数大于7的情况，可以直接搜索，会比 meet in middle 快。