2022.10.06考试总结

得分:\(175/300\)

总结：今天考试的题目非常有区分度，第一题因为没有发现结论，导致最后只拿到了部分分，第二题是一道比较简单的背包，第三题的题目意思描述的非常的模糊，读错了题目导致代码实现出现了问题

T1

题目大意：

给你 \(n\) 个点，现在依次加入 \(m\) 条边，每加入一条边，你都需要求出当前的图有多少非空子图是欧拉回路森林。

欧拉回路森林指每个点的度数均为非零偶数的图。

\(1\leq n\leq 2\times 10^5,1\leq m\leq 3\times 10^5\)。

得分：\(30/100\)

观察数据我们可以得到如下结论

设\(fa[i]\)表示第\(i\)个点所在的联通块

设当前加入到的边为\((u,v)\)

• \(fa[u]!=fa[v]\),\(fa[u] = fa[v]\)

• \(fa[u]=fa[v],answer=answer+siz[fa[u]] \times 2 +1\)

根据如上结论完善代码即可

T2

题目大意：

给你 \(n\) 个物品，每个物品有两个属性 \(p\) 和 \(v\)。
你最开始的得分为 \(k\)，你有 \(p_i\) 的概率拿走第 \(i\) 个物品，并且你的得分会加上 \(v_i\)。

求你最终拿到至少 \(l\) 个物品，并且得分为非负数的概率，保留六位小数。

\(0\leq k\leq 2\times 10^3,0\leq n\leq 200,-1\leq v_i\leq 10^3,0\leq l\leq n,0\leq p_i\leq 100\)。

得分：\(100/100\)

总结：分\(-1\)和正代价考虑，然后使用背包求出概率最后统计答案即可

T3

题目大意：

给你 \(n\) 个区间，对于数字 \(1\sim9\) 中的两个不同的数 \(u,v\)，若在这 \(n\) 个区间中任意选择一个数 \(a\)，将其低 \(k\) 位中的某一位的 \(u\) 换成 \(v\)（或者 \(v\) 换成 \(u\)）均都能落在这 \(n\) 个区间内，则称 \(u\) 和 \(v\) 是 \(\text{k-equal}\) 的。

若一个集合 \(S\) 内的元素都是互相 \(\text{k-equal}\) 的，则称集合 \(S\) 是 \(\text{k-equivalence class}\)。

按照元素的最小值排序所有 \(\text{k-equivalence class}\) 后输出。

\(1\leq n\leq 10^4,1\leq k\leq 19,1\leq l_1\leq r_1<l_2\leq r_2<\dots<l_n\leq r_n\leq 10^{18}\)。

得分：\(45/100\)

总结：考虑对于每一位考虑，设当前考虑的为第\(i\)位

根据后面\(i-1\)位的情况，我们可以得到\(l[i]-r[i]\)的第\(i\)位的取值范围，并且我们可以得到对于每一个使得\(l[i]-r[i]\)的第\(i\)位取值变化的后\(i-1\)位的值

然后根据从小到大依次判断，最后判断出所有不能再同一个等价类的情况

之后输出在同一等价类的数即可