C

签到题,可以直接BFS。但是贪心能做数据范围更大。

F

题意:输出$\ln 2$的泰勒展开的前$n(n\le10^{1000000})$项的和,要求答案与实际值差距不大于$10^{-6}$

解:不用说。但是从这道题发现了python文本转高精数事实上还是比较慢的,可能是长度平方级别的复杂度。的确啊,高精读入不都是这样?

B

题意:给定$n\le 100000$个点(坐标在$-10000\cdots 10000$),要求所有直角边与坐标轴平行的三角形的面积和乘$2$。

解:讲题时候说是经典普及组题目…我想了半天…是我太菜了吗?我的做法是每次只考虑直角在坐标最大处的情况,通过旋转图形来获得答案。在每一次的寻找中不难发现,某一个点作为直角端点时的所有三角形的面积和即它左边的距离前缀和乘上面的距离前缀和。排序后做的时候稍微维护一下就做完了。

补E

题意:给定无向图,要求其中标号小于等于$k$的点不出现在环中,问最小删边条数。

解:首先可以把两端点都不是小于等于$k$的点的边先添加上,形成许多连通块(并查集维护)。然后可以发现,把这些连通块看成点并不影响正确性。于是类似Kruskal把剩下的边能加的一条条加上形成一个生成树就做完了。

补A

题意:甲取得盘面上每个格子有对应积分$A_{i,j}$,乙也有(与甲不同)。双方轮流占据盘面上的格子,要求格子必须要形成以左上角为直角边的阶梯型。问当双方都采取最优方案时,最终积分差多少。格子最大$10\times 10$。

解:可以通过数学推导或者搜索发现其实局面仅$C(10,20)$种。于是考虑可以记忆化dfs。判重是如何进行状压的呢?容易想到可以把每列情况压进$11$位,表示该列已有$0\cdots10$个方块还未被占据。这样我们就可以把局面情况放进$11^{10}$(一个long long)中了。利用unordered_map存答案即可。

另解:利用轮廓线dp 网上的题解 有时间要研究一下