题解 CF1111C 【Creative Snap】

水题 按照题意模拟即可 注意一个剪枝：如果当前处理的区间里一个avenger都没有，就直接返回$A$。 $2^{30}$差不多有十亿，但是$k$只有$10^5$，说明上面这种情况的发生频率还挺高的。因此能过 ```cpp #include <cctype> #include <cstdio> #include <climits> #include <algorithm> template <typename T> inline void read(T& x) { int f = 0, c = getchar(); x = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = x * 10 + c - 48, c = getchar(); if (f) x = -x; } template <typename T, typename... Args> inline void read(T& x, Args&... args) { read(x); read(args...); } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <typename T> void writeln(T x) { write(x); puts(""); } template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; } template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; } typedef long long LL; const int maxn = 1e5 + 207; int a[maxn]; int n, K, A, B; inline LL count(int l, int r) { int pr = std::upper_bound(a + 1, a + K + 1, r) - a; --pr; int pl = std::upper_bound(a + 1, a + K + 1, l - 1) - a; --pl; return pr - pl; } LL solve(int l, int r) { int cnt = count(l, r); if (!cnt) return A; if (l == r) return B * cnt; int mid = (l + r) >> 1; return std::min(1ll * cnt * B * (r - l + 1), solve(l, mid) + solve(mid + 1, r)); } int main() { read(n, K, A, B); for (int i = 1; i <= K; ++i) read(a[i]); std::sort(a + 1, a + K + 1); writeln(solve(1, 1 << n)); return 0; } ```