真是无语了，T1、T2还是很水，但是T3太神了，看了题解还做了半天。我讨厌数学题！
T1 无线网络发射器选址
这题就是大暴力，暴力枚举发射器的位置，再暴力计算能覆盖的公共场所数量，连前缀和什么的都不用。要注意的一点就只边界处理，发射器可以放在边界附近，覆盖区域超出边界也没关系，我刚开始以为覆盖区域不能超出边界WA了一次。。
代码在此。
T2 寻找道路
我的做法是计算图的转置，然后从终点开始dfs，跑出所有符合题目要求的点，在这些点上做一遍SPFA就行了。
代码在此。
T3 解方程
在5道水题后，神题终于出现了。
首先，因为5次以上方程没有求根公式，所以要枚举m并验根。但是如果暴力验根，显然是要TLE的。正确的做法是取模。设$f_x$为题目给出的方程的左边部分，可以发现当$f_x=0$时，$f_x \equiv 0 \pmod p$。那么如果p取得好，$f_x \equiv 0 \pmod p$可以近似地看作$f_x=0$。所以可以在计算时模p，免去了高精度的复杂度。这样据说可以过官方数据，但还有复杂度更优的做法。
易知$f_{x \bmod p} \equiv f_x \pmod p$，那么可以取小一些的p预处理出x为1~p-1时的结果，枚举m时就可以用模p后的结果了。但是如果p取小了会WA，所以要多取几个p，分别计算在它们的模域下的$f_x$，如果都为0，才认为是原方程的解。
代码在此。
评论 (0)
