G - Division
解法一：位运算+状压枚举（赛时思路）
范围显然，可以跑 \(2^n\) 的算法，考虑位运算状态压缩。以 \(\mathcal O(2^n \cdot 2^n)\) 的复杂度分别枚举位于第一组、第二组中的人，随后计算每一种分组的快乐值，代码较长，赛时敲了半个小时，不过好在一发过了。
总结：其实代码里面的剪枝完全可以不要的，先一口气枚举，随后再计算快乐值会比较容易写一些。随后，下方代码中补全了给定数组的另一半（刚开始没补打算用特判的，这里花费了一些不必要的时间），这样做也能方便后续计算快乐值。
signed main() {
int n;
cin >> n;
vector ver(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
ver[i][j] = ver[j][i];
}
for (int j = i + 1; j < n; j++) {
cin >> ver[i][j];
}
}
int Max = -numeric_limits<int>::max();
for (int i = 0; i < (1 << n); i++) { // 枚举：O(1024)
bitset<10> val = i;
vector<int> g1, g23;
for (int j = 0; j < n; j++) {
if (val[j]) g1.push_back(j);
else g23.push_back(j);
}
// 剪枝：先计算第一组人的haapy
int pre = 0;
for (auto it : g1) {
for (auto jt : g1) {
pre += ver[it][jt];
}
}
int m = g23.size();
for (int j = 0; j < (1 << m); j++) { // 枚举：O(1024)
int num = pre;
bitset<10> val = j;
vector<int> g2, g3;
for (int k = 0; k < m; k++) {
if (val[k]) g2.push_back(k);
else g3.push_back(k);
}
// 至此三组人已经分出，分别计算第二、三组人的happy
for (auto it : g2) {
for (auto jt : g2) {
int It = g23[it];
int Jt = g23[jt];
num += ver[It][Jt];
}
}
for (auto it : g3) {
for (auto jt : g3) {
int It = g23[it];
int Jt = g23[jt];
num += ver[It][Jt];
}
}
Max = max(Max, num);
}
}
cout << Max / 2 << endl;
搜索枚举（官方思路）
这个思路就简便很多了，主体和“八皇后问题”很像，先操作后回溯。平时写这种搜索比较少，赛时确实没想到。
signed main() {
int n;
cin >> n;
vector ver(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
cin >> ver[i][j];
ver[j][i] = ver[i][j];
}
}
vector<vector<int>> group(4);
int ans = -numeric_limits<int>::max();
auto dfs = [&](auto self, int x, int val) -> void {
if (x == n + 1) {
ans = max(ans, val);
return;
}
for (int i = 1; i <= 3; i++) { // 暴力枚举应该放到哪一组里去
int add = 0;
for (auto it : group[i]) {
add += ver[x][it];
}
group[i].push_back(x);
self(self, x + 1, val + add);
group[i].pop_back(); // 回溯
}
};
dfs(dfs, 1, 0);
cout << ans << endl;
}
H - Bulk Selling
解法一：线段树（赛时思路）
显然，这是一道线段树能够解决的题目，问题在于有一个操作是对奇数位置进行的，显然，传统的线段树难以区分叶子节点的奇偶性——所以，我在这题中建立了两棵线段树，分别负责奇数、偶数位置。
实现难度并不高，只需要修改使得其能够实现“修改、查询区间最小值”即可，但是要注意细节。赛时敲了四十分钟，然后调BUG调了二十分钟，略显逊色……
总结：需要留心的地方在于，如果不存在偶数位置，我们需要特判建一棵只含有一个极大值节点的偶数线段树。
如果不为一个节点，有可能在
build函数中出现build(1, 0);这样的越界情况（导致RE）；如果不包含一个极大值节点，在计算操作三的最小值时可能出现 \(0\) 的情况。
signed main() {
int n;
cin >> n;
int ne = n / 2, no = (n + 1) / 2; // 分别计算两棵线段树的节点数目
int flag = 0;
if (ne == 0) { // 偶数可能不存在，导致建树时RE
ne = 1;
flag = 1;
}
Segt eve(ne), odd(no);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i % 2) {
odd.w[(i + 1) / 2] = x;
} else {
eve.w[i / 2] = x;
}
}
if (flag) { // 需要塞一个极大值节点
eve.w[1] = INF;
}
eve.build(1, ne);
odd.build(1, no);
int q, ans = 0;
cin >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x, a;
cin >> x >> a;
if (x % 2) {
x = (x + 1) / 2;
if (odd.ask(x, x) >= a) {
odd.modify(x, x, -a);
ans += a;
}
} else {
x = x / 2;
if (eve.ask(x, x) >= a) {
eve.modify(x, x, -a);
ans += a;
}
}
} else if (op == 2) {
int a;
cin >> a;
if (odd.ask(1, no) >= a) {
odd.modify(1, no, -a);
ans += no * a;
}
} else {
int a;
cin >> a;
if (min(odd.ask(1, no), eve.ask(1, ne)) >= a) {
odd.modify(1, no, -a);
eve.modify(1, ne, -a);
ans += n * a;
}
}
}
cout << ans << endl;
}
我的线段树封装参考（2023.07.10封装）：
struct Segt {
struct node {
int l, r;
int w, Min;
int lazy;
};
vector<int> w;
vector<node> t;
#define GL (k << 1)
#define GR (k << 1 | 1)
Segt(int n) : w(n + 1), t((n << 2) + 1) {}
void pushdown(node &p, int lazy) { // 在此更新下递函数
p.w += (p.r - p.l + 1) * lazy;
p.Min += lazy;
p.lazy += lazy;
}
void pushup(node &p, node &l, node &r) { // 在此更新上传函数
p.w = l.w + r.w;
p.Min = min(l.Min, r.Min);
}
void pushdown(int k) { // 不需要动
if (!t[k].lazy) return;
pushdown(t[GL], t[k].lazy);
pushdown(t[GR], t[k].lazy);
t[k].lazy = 0;
}
void pushup(int k) { // 不需要动
pushup(t[k], t[GL], t[GR]);
}
void build(int l, int r, int k = 1) {
if (l == r) {
t[k] = {l, r, w[l], w[l], 0};
return;
}
t[k] = {l, r, 0, 0, 0};
int mid = (l + r) / 2;
build(l, mid, GL);
build(mid + 1, r, GR);
pushup(k);
}
void modify(int l, int r, int val, int k = 1) { //区间修改
if (l <= t[k].l && t[k].r <= r) {
pushdown(t[k], val);
return;
}
pushdown(k);
int mid = (t[k].l + t[k].r) / 2;
if (l <= mid) modify(l, r, val, GL);
if (mid < r) modify(l, r, val, GR);
pushup(k);
}
int ask(int l, int r, int k = 1) { //区间询问，不合并
if (l <= t[k].l && t[k].r <= r) {
return t[k].Min;
}
pushdown(k);
int mid = (t[k].l + t[k].r) / 2;
int ans = INF;
if (l <= mid) ans = min(ans, ask(l, r, GL));
if (mid < r) ans = min(ans, ask(l, r, GR));
return ans;
}
void debug(int k = 1) {
cout << "[" << t[k].l << ", " << t[k].r << "]: ";
cout << "Min = " << t[k].Min << ", ";
cout << "w = " << t[k].w << ", ";
cout << endl;
if (t[k].l == t[k].r) return;
debug(GL), debug(GR);
}
#undef GL
#undef GR
};
解法二：模拟（官方思路）
细细想来好像确实是用不到线段树维护。
标签：Atcoder,ver,14,int,auto,eve,过题,vector,odd From： https://www.cnblogs.com/WIDA/p/17555207.html