F
https://acm.hdu.edu.cn/showproblem.php?pid=7996
题意
有两场比赛，统计对于每个 \(i\) ，有多少个人排在 \(i\) 的前面，需要去重。
思路
第一思路是统计每个位置 \(i\) 前面有多少人数，发现有个小容斥在这里，两场比赛排名前的总人数减去两场都在排名前的人数。
用树状数组统计第二场比赛在排名前的人数，也就是同时排在前面的人数。
代码
#include<bits/stdc++.h>
using namespace std;using ll = long long;void solve(){int n;cin >> n;vector<int> a(n + 1);vector<int> pos(n + 1);for(int i = 1; i <= n; i++){cin >> a[i];}for(int i = 1; i <= n; i++){int x;cin >> x;pos[x] = i;}vector<int> c(n + 5);auto lowbit = [&](int x){return x & -x;};auto add = [&](int k, int x){while(k <= n){c[k] += x;k += lowbit(k);}};auto find = [&](int k){int res = 0;while(k != 0){res += c[k];k -= lowbit(k);}return res;};vector<int> ans(n + 1);for(int i = 1; i <= n; i++){ans[a[i]] = i - 1 + pos[a[i]] - 1;ans[a[i]] -= find(pos[a[i]]);add(pos[a[i]], 1);}for(int i = 1; i <= n; i++){cout << ans[i] << " ";}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cin >> t;while(t--)solve();
}
H
https://acm.hdu.edu.cn/showproblem.php?pid=7998
思路
先检查对角线，翻出 \(1\) 的概率为 \(1/n(1 + 2 + ... + n) = (n + 1)/2\), 翻出后花费两次确定方向，即 \((1 + 2)/2\)，最后有 \(n - 2\) 次填充，共 \(3n/2\).
代码就不贴了，输出记得一定只能输出四位小数。
I
https://acm.hdu.edu.cn/showproblem.php?pid=7999
思路
题目求一颗树上 \(u\) 到 \(v\) 路径上的最大值，并且要支持修改，那么自然想到重链剖分再加上线段树修改，查询。
但这里的修改并不是修改该点，而是该点周围的点，考虑到重链剖分的查询，我们发现链上的部分是已经在线段树上处理好的，修改需要 \(O(log\;n)\) 的时间复杂度。
而链头的部分可以单独的处理其新的增加，这里多开一个数组，记录链头的父亲有多少额外的增加，在查询时 \(O(1)\) 的时间复杂度就可以处理这个点。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e5 + 5;
struct node{int sum;int ma;node operator+(const node& b){node res;res.sum = sum + b.sum;res.ma = max(ma, b.ma);return res;}};node s[N<<2];void push_up(int n){s[n] = s[n<<1] + s[n<<1|1];
}void update(int ql, int qr, int x, int l, int r, int n){if(l == r && ql == l){s[n].sum = x;s[n].ma = x;return ;}int mid = (l + r) / 2;if(ql <= mid)update(ql, qr, x, l, mid, n<<1);if(qr > mid)update(ql, qr, x, mid+1, r, n<<1|1);push_up(n);
}node query(int ql, int qr, int l, int r, int n){if(ql <= l && r <= qr){return s[n];}int mid = (l + r) / 2;node res;res.ma = -1e9;res.sum = 0;if(ql <= mid)res = res + query(ql, qr, l, mid, n<<1);if(qr > mid)res = res + query(ql, qr, mid+1, r, n<<1|1);return res;
}void solve(){int n, m;cin >> n >> m;vector<int> a(n + 1);vector<int> f(n + 1);vector<int> dfn(n + 1);vector<int> top(n + 1);vector<int> big(n + 1);vector<int> r(n + 1);vector<int> dep(n + 1);vector<int> sz(n + 1);vector<int> ad(n + 1);int idx = 0;vector<vector<int>> e(n + 1);for(int i = 1; i <= n; i++){cin >> a[i];}for(int i = 1; i < n; i++){int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}auto dfs1 = [&](auto&& dfs1, int u, int fa) -> void {sz[u] = 1;for(auto v : e[u]){if(v == f[u])continue;f[v] = u;dep[v] = dep[u] + 1;dfs1(dfs1, v, u);sz[u] += sz[v];if(sz[big[u]] < sz[v])big[u] = v;}};auto dfs2 = [&](auto&& dfs2, int u, int tp) -> void {dfn[u] = ++idx;r[idx] = u;top[u] = tp;if(big[u] != 0)dfs2(dfs2, big[u], tp);for(auto v : e[u]){if(v == big[u] || v == f[u])continue;dfs2(dfs2, v, v);}};f[1] = 0;dep[1] = 1;dfs1(dfs1, 1, 0);dfs2(dfs2, 1, 1);auto pre_query = [&](int u, int v) {node res;res.sum = 0;res.ma = -1e9;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]])swap(u, v);res = res + query(dfn[top[u]], dfn[u], 1, n, 1);res.ma = max(res.ma, query(dfn[top[u]], dfn[top[u]], 1, n, 1).ma + ad[f[top[u]]]);u = f[top[u]];}if(dfn[u] > dfn[v])swap(u, v);res = res + query(dfn[u], dfn[v], 1, n, 1);if(u == top[u]){res.ma = max(res.ma, query(dfn[u], dfn[u], 1, n, 1).ma + ad[f[u]]);}return res;};for(int i = 1; i <= n; i++){update(dfn[i], dfn[i], a[i], 1, n, 1);}for(int i = 1; i <= m; i++){int op;cin >> op;if(op == 1){int x, y;cin >> x >> y;cout << pre_query(x, y).ma << "\n";}else{int x, y;cin >> x >> y; ad[x] += y;if(f[x] != 0){int num = pre_query(f[x], f[x]).sum;update(dfn[f[x]], dfn[f[x]], y + num, 1, n, 1);}if(big[x] != 0){int num = pre_query(big[x], big[x]).sum;update(dfn[big[x]], dfn[big[x]], y + num, 1, n, 1);}}}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();return 0;
}
K
https://acm.hdu.edu.cn/showproblem.php?pid=8001
思路
对题意解读之后发现我们对于给定的 \(l\) 到 \(r\) 区间，我们把 \(1\) 中间的 \(0\) 的个数记作一个数列，那么答案就是从最右边向左求一个尽可能长的一个公差为 \(1\) 的等差数列。
让找到的数列从右到左呈现 \(l_1,\;l_2,\;...,\;l_i\), 答案为 \(2 * (i - 1) + l_i\) .
最后我们用线段树维护等差数列即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 5.1e5 + 10;
struct node{int l0, r0, len, cnt, over, st, ed;node(){};node(int x){len = 1;over = 0;st = ed = -1;if(x == 1){l0 = r0 = 0;cnt = 1;}else {l0 = r0 = 1;cnt = 0;}}
};node s[N << 2];int a[N];node merge(node l, node r){node ans;ans.l0 = l.l0;if(l.l0 == l.len)ans.l0 += r.l0;ans.r0 = r.r0;if(r.r0 == r.len)ans.r0 += l.r0;ans.len = l.len + r.len;ans.cnt = l.cnt + r.cnt;if(ans.cnt <= 1){ans.over = 0;ans.st = -1;ans.ed = -1;return ans;}if(r.over || l.cnt == 0){ans.over = r.over;ans.st = r.st;ans.ed = r.ed;return ans;}if(r.cnt == 0){ans.over = l.over;ans.st = l.st;ans.ed = l.ed;return ans;}int lnk = l.r0 + r.l0;if(l.cnt != 1 && r.cnt != 1){if(l.ed == lnk + 1 && r.st == lnk - 1){ans.st = l.st;ans.ed = r.ed;ans.over = l.over;}else if(r.st == lnk - 1){ans.over = 1;ans.st = lnk;ans.ed = r.ed;}else {ans.over = 1;ans.st = r.st;ans.ed = r.ed;}return ans;}if(l.cnt == 1 && r.cnt == 1){ans.over = 0;ans.st = ans.ed = lnk;return ans;}if(l.cnt == 1){if(lnk == r.st + 1){ans.over = 0;ans.st = lnk;ans.ed = r.ed;}else {ans.over = 1;ans.st = r.st;ans.ed = r.ed;}return ans;}if(r.cnt == 1){if(lnk + 1 == l.ed ){ans.over = 0;ans.ed = lnk;ans.st = l.st;}else {ans.over = 1;ans.ed = lnk;ans.st = lnk;}return ans;}return ans;
}void push_up(int n){s[n] = merge(s[n<<1], s[n<<1|1]);
}void build(int l, int r, int n){if(l == r){s[n] = node(a[l]);return ;}int mid = (l + r) / 2;build(l, mid, n<<1);build(mid+1, r, n<<1|1);push_up(n);
}void update(int pos, int l, int r, int n){if(l == r && l == pos){s[n].l0 ^= 1;s[n].r0 ^= 1;s[n].cnt ^= 1;return ;}int mid = (l + r) / 2;if(pos <= mid)update(pos, l, mid, n<<1);else update(pos, mid+1, r, n<<1|1);push_up(n);
}node query(int ql, int qr, int l, int r, int n){if(ql <= l && r <= qr){return s[n];}int mid = (l + r) / 2;if(qr <= mid)return query(ql, qr, l, mid, n<<1);if(ql > mid)return query(ql, qr, mid+1, r, n<<1|1);return merge(query(ql, qr, l, mid, n<<1), query(ql, qr, mid+1, r, n<<1|1));
}void solve(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){char c;cin >> c;a[i] = c - '0';}build(1, n, 1);for(int i = 1; i <= m; i++){int op;cin >> op;if(op == 1){int l, r;cin >> l >> r;node num = query(l, r, 1, n, 1);if(num.cnt == 0){cout << "0\n";}else if(num.cnt == 1 || num.ed != num.r0 + 1){cout << num.r0 << "\n";}else {cout << num.st + 2 * (num.st - num.ed + 1) << "\n";}}else {int x;cin >> x;update(x, 1, n, 1);}}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();return 0;
}
L
https://acm.hdu.edu.cn/showproblem.php?pid=8002
题意
给定 \(n\) 个非负整数 \(a_i\)，不选相邻的数，使得选取的所有数的异或和最大。 （ \(n <= 50\)， 内存限制 \(3MB\) )
思路
答案需要统计的异或和最大，想到线性基，然后模拟所有可能的选取情况，选取 \(i\) 之后 考虑选取 \(i + 2\) 和 \(i + 3\)， 同时由于线性基的性质，在中间本来不选的情况下，选取中间值是不会变劣的。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;void solve(){vector<ll> p(61);auto insert = [&](vector<ll>& p, ull x){for(int i = 60; ~i; --i){if(!(x >> i))continue;if(!p[i]){p[i] = x;break;}x ^= p[i];}};int n;cin >> n;vector<ll> a(n + 1);for(int i = 1; i <= n; i++){cin >> a[i];}ll ans = 0;auto dfs = [&](auto&& dfs, vector<ll> p, int id) -> void {if(id > n){ll temp = 0;for(int i = 60; ~i; --i){if((p[i] ^ temp) > temp){temp ^= p[i]; }}ans = max(ans, temp);return ;}insert(p, a[id]);dfs(dfs, p, id + 2);dfs(dfs, p, id + 3);};dfs(dfs, p, 1);// er();dfs(dfs, p, 2);cout << ans << "\n";}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();return 0;
}
