涨薪【贪心】【快速幂】

>Link

牛客1020普及T3

---

>Description 一共有n个数，第i个数的值为$a_i$。 可以进行m轮操作：选择其中x个数乘3，其中y个数乘2，对于每个$a_i$在每一轮不可以被选择两次。如果一个数连续两轮没被选择，就直接淘汰 求最终剩下的数的总和最大为多少，答案模1e9+7

---

>解题思路 贪心+快速幂

将a数组从大到小排个序，只选择前x+y个数，后面的直接淘汰（m=1的情况除外），并且乘3操作永远只选前x个数，选择的数中剩下的就永远都乘2

---

>代码

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define int long long #define N 100005 using namespace std; const int p = 1e9 + 7; int n, m, x, y, a[N], ans, sum[N]; bool cmp (int aa, int bb) {return aa > bb;} int power (int aa, int bb) { int ret = 1; for (; bb; bb >>= 1, aa = aa * aa % p) if (bb & 1) ret = ret * aa % p; return ret; } signed main() { scanf ("%lld%lld%lld%lld", &n, &m, &x, &y); for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]); sort (a + 1, a + 1 + n, cmp); for (int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + a[i]) % p; ans = sum[x] * power (3, m) % p; ans = (ans + (sum[x + y] - sum[x]) * power (2, m) % p) % p; if (m == 1) ans = (ans + sum[n] - sum[x + y]) % p; printf ("%lld", ans); return 0; }