AtCoder Beginner Contest 246 赛时记录

2022/4/3 0:03:45

编程Tag： get sum 答案 cnt frac four Atcoder Beginner 赛时

本文主要是介绍AtCoder Beginner Contest 246 赛时记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

把 \(x_i, y_i\) 分别异或起来输出即可。

没看懂题目啥意思，观察了一下样例，发现答案是

设 \(p = \sqrt {x^2 + y^2}\)，输出的两个数分别为 \(\frac{x}{p}, \frac{y}{p}\)。

贪心即可，做法很多。

设 \(cnt = \sum \left \lfloor \frac{a_i}{X} \right \rfloor, sum = \sum a_i\)。

如果 \(cnt \ge K\) ，答案为 \(sum - KX\)。

否则，从所有的 \(a_i \% X\) 中挑出 \(K-cnt\) 个最大的。

剩下的和就是答案。

发现 \((10^6)^3 = 10^{18}\)，考虑枚举其中一个数 \(a\)，然后二分另外一个数 \(b\)，对合法的答案取最小值即可。

直接 bfs，每次更新向四个方向，能跑多远跑多远，如果遇到不能更新的地方就直接 break 掉。

直接容斥。

拿 bitset 存每一个字符串。

枚举当前状态 \(S\)，取 \(S\) 中所有选了的串的位置交。

设交有 \(x\) 个可用的位置。

答案为

\[ans = \sum (-1)^{|S|} x^L \]

后面那个可以在外面预处理。

总复杂度为 \(\mathcal O(2^{n} \frac{n}{w})\)。

这篇关于AtCoder Beginner Contest 246 赛时记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！