1001 战斗爽
题解：
纯模拟，用一个heap和set去记录剩下的怪物中的攻击力最高的和还没有收到超过k次伤害的
struct enemy{int atk, hp, cnt, id;bool operator> (const struct enemy& w) const {if (hp == w.hp) {if (atk == w.atk) {return id > w.id;} else {return atk > w.atk;}} else {return hp > w.hp;}}
};void solve()
{int n, u, k, hq;cin >> n >> u >> k >> hq;vector<enemy> e(n + 1);priority_queue<enemy, vector<enemy>, greater<enemy>> heap;set<PII> S;for (int i = 1; i <= n; i++) {int a, b;cin >> a >> b;e[i] = {a, b, 0, i};heap.push(e[i]);S.insert({a, i});}int ans = 0;while(S.size() && heap.size()) {if (hq <= 0) break;auto [atk, hp, cnt, id] = heap.top();heap.pop();hp -= (cnt == 0 ? (int)u : u / 2);if (hp <= 0) {S.erase({atk, id});ans++;} else if (cnt + 1 == k) {} else {heap.push({atk, hp, cnt + 1, id});}if (!S.empty()) {auto it = S.end();it--;hq -= it->first;}}cout << ans << endl;
}
1003 洞察
题解：
跟上一场的位运算题目的思考方式好像，都是从高位向低位进行枚举去划分。
首先明确一个性质：a ^ b = c ——> a = b ^ c
依据上述性质，我们可以把不等式 px ^ c <= v 转化为 px <= v ^ c，这里不要考虑不等式，需要考虑的是对于每一个 px ^ c 总有一个 v ^ c 来进行映射，所以可以这么转化。
然后，我们的任务就转化成了，求出有多少个 px 是在 1 ~ v ^ c 的范围内的，这里应该怎么计算呢？？
跟上一场的1001一样，我们从高位到低位枚举，假设目前枚举到 i 位，则按照从 i ~ 最高位 都贴近上界的方式来进行集合的划分，如果第i位为1，则这一位取0，然后低位随便取，一定满足在 1 ~ v^c 的范围内。
知道了一个范围，知道了x的表达式，我们按照等差数列的求和公式，以及前缀和的公式，就可以知道一个区间内的 x 的个数。
void solve()
{int k, b, c, v;cin >> k >> b >> c >> v;int led = 0, ans = 0;if ((v ^ c) - b >= 0 && ((v ^ c) - b) % k == 0) ans++;for (int i = 59; i >= 0; i--){if (v >> i & 1) {int u = (led ^ c) & ((1LL << 60) - (1LL << i));int l = u - 1, r = u + ((1LL << i) - 1);if (r >= b) {ans += (r - b) / k + 1;} if (l >= b) {ans -= (l - b) / k + 1;}}led |= (v >> i & 1) << i;}cout << ans << endl;
}
这里有几个位运算的操作解释一下
int u = (led ^ c) & ((1LL << 60) - (1LL << i));
led 表示的就是之前位全部贴近上界的值
((1LL << 60) - (1LL << i)) 表示二进制表示下，当前位及高位都为1，低位均为0的一个数字，然后和之前的数字取&就表示低位全部取0，高位保留。
而且由于led还没有更新，所以本位i也是取0的，则当前区间就是 [u, u + (1LL << i ) - 1]，后者就是后面所有位都取1的情况，然后计算就行了。
1005 持家
感觉最签的一题
题解：
先用打折券肯定更优，然后直接枚举所有方案就行了，用一个前缀积和一个前缀和来加速枚举过程
void solve()
{ double p;int n, k;cin >> p >> n >> k;vector<double> a(1), b(1);for (int i = 1; i <= n; i++) {int op, x;cin >> op >> x;if (op == 0) {a.push_back(x);} else {b.push_back(x);}}sort(a.begin() + 1, a.end());sort(b.begin() + 1, b.end(), greater<double>());vector<double> prea(n + 1), preb(n + 1, 0);prea[0] = 1;for (int i = 1; i < b.size(); i++) {preb[i] = preb[i - 1] + b[i];}for (int i = 1; i < a.size(); i++) {prea[i] = prea[i - 1] * a[i] / 10.0;}double ans = max(p - preb[min((int)b.size() - 1LL, (int)k)], 0.00);for (int i = 0; i <= k; i++) {if (i >= a.size()) break;ans = min(ans, max((double)p * prea[i] - preb[min((int)(b.size() - 1LL), (int)k - i)], 0.00));}printf("%.2lf\n", ans);
}
1006 进步
题解：
树状数组模板题
template <typename T>
class Fenwick {
public:int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n + 1, T{});}void add(int x, const T &v) {for (int i = x; i <= n; i += i & -i) {a[i] = (a[i] + v);}}// 查询位置 [1, x] 的前缀和T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = (ans + a[i]);}return ans;}// 查询区间 [l, r] 的区间和T rangeSum(int l, int r) {return sum(r) - sum(l - 1);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i] <= k) {x += i;cur = cur + a[x];}}return x;}
};void solve()
{int n, q;cin >> n >> q;vector<int> a(n + 1);Fenwick<int> fen(n);for (int i = 1; i <= n; i++) {cin >> a[i];fen.add(i, a[i]);}int ans = 0, cnt = 1;for (int i = 1; i <= q; i++) {int op, x, y;cin >> op >> x >> y;if (op == 1) {fen.add(x, -(a[x]));a[x] = y;fen.add(x, a[x]);} else if (op == 2) {int sl = fen.sum(x - 1), sr = fen.sum(y);int res = sr / 100 - sl / 100;ans ^= (cnt * res);cnt++;}}cout << ans << endl;
}1008 制衡
题解：
WA了三发的DP
void solve()
{int n, k;cin >> n >> k;vector<vector<int>> a(n + 1, vector<int>(k + 1));for (int i = 1; i <= n; i++) {for (int j = 1; j <= k; j++) {cin >> a[i][j];}}vector<vector<int>> f(n + 1, vector<int>(k + 1, -INF));f[0][0] = f[0][1] = 0;for (int i = 1; i <= n; i++) f[i][1] = f[i - 1][1] + a[i][1];for (int i = 1; i <= n; i++) {vector<int> pre(k + 1, -INF);for (int j = 1; j <= k; j++) {pre[j] = max(pre[j - 1], f[i - 1][j]);}for (int j = 2; j <= k; j++) {f[i][j] = pre[j] + a[i][j];}}int ans = 0;for (int i = 1; i <= k; i++) {ans = max(ans, f[n][i]);}cout << ans << endl;
}
1010 图之图
题解：
这种题之前基本没有见过，思路就感觉很……假。
考察的是根号分块方面的知识。
void solve()
{int n, m, c;cin >> n >> c;vector<int> a(n + 1);for (int i = 1; i <= n; i++) cin >> a[i];vector<int> g(c + 1, 0), f(n + 1, 0), w(c + 1, 0);vector<vector<int>> e(c + 1), eh(c + 1);f[1] = 1;cin >> m;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;e[u].push_back(v);if (u != v) e[v].push_back(u);}int S = sqrt(m);for (int u = 1; u <= c; u++) {for (auto v : e[u]) {if (e[v].size() > S) {eh[u].push_back(v);}}}for (int i = 1; i <= n; i++) {(f[i] += w[a[i]]) %= mod;for (auto v : eh[a[i]]) {(f[i] += g[v]) %= mod;}(g[a[i]] += f[i]) %= mod;if (e[a[i]].size() <= S) {for (auto v : e[a[i]]) {(w[v] += f[i]) %= mod; // 出度，所有指向的边都++}}}cout << f[n] << endl;
}
