前言
手速6题,可惜第四题磨了几个小时没磨出来,多做一题就金了,还是实力差了点,最后银牌前列。下面的题解是根据代码回忆大概的题意,主要是给出来赛时的参考代码
A.状压
题意:
学校集训队总的有 \(n\) 个人,保证 \(n\) 是3的倍数,每个人有个人实力 \(a_i\), 每两个人之间有配合程度 \(b_{ij}\),每个人可以选择挂机或者不挂机,队伍有不同的总权值(题目中把所有可能的搭配都给出来了), 问合理安排下,最多使得所有队伍的权值和最大是多少。
分析
看到数据范围很显然是考虑状压DP,二进制状态1表示已经安排好队伍,0表示还没,从小到大枚举状态时候,一次性枚举三个是0的位置,考虑这三个人的最大权值,然后更新dp值。
然后可以稍微预处理一下,有效的状态一定是1的数量是3的倍数的,可以把这些数提前存vector里面,可以少枚举一些状态,而且 \(C(n, 3)\)枚举时候可以先把状态里为0的位置存起来,再3个for循环枚举,也能优化一点点。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = (1 << 22) + 100;
int a[maxn], b[30][30];
int dp[maxn];
int co[30][30][30];
vector<int> vec;
int cal(int x, int y, int z) {
int res = max({a[x], a[y], a[z], b[x][y], b[y][z], b[x][z],
b[x][y] * b[y][z] * b[x][z]});
return res;
}
signed main() {
int n;
cin >> n;
for (int i = 0; i < (1 << n); i++)
if (__builtin_popcount(i) % 3 == 0)
vec.push_back(i);
for (int i = 0; i < (1 << n); i++)
dp[i] = -1e18;
dp[0] = 0;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> b[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
co[i][j][k] = cal(i, j, k);
for (auto u : vec) {
vector<int> tem;
for (int i = 0; i < n; i++)
if (!(u >> i & 1))
tem.push_back(i);
int sz = tem.size();
for (int i = 0; i < sz; i++)
for (int j = i + 1; j < sz; j++)
for (int k = j + 1; k < sz; k++) {
int nxt = u | (1 << tem[i]) | (1 << tem[j]) | (1 << tem[k]);
dp[nxt] = max(dp[nxt], dp[u] + co[tem[i]][tem[j]][tem[k]]);
}
}
cout << dp[(1 << n) - 1] << "\n";
return 0;
}
B.模拟、高精
题意
给定一个n \((n \leq 21)\) 位的二进制数,输出它和十进制数21相乘后的结果的二进制表示
分析
由于乘法不用管进制,所以直接类似高精度乘法一样,对这两个二进制数乘法,并且21比较小已经给定,甚至可以直接取21的二进制为1的那些位,相当于把原来二进制串右移对应位后相加,数据范围比较小,所以随便怎么暴力都可以。
代码
点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn], c[maxn];
signed main() {
string str;
cin >> str;
reverse(all(str));
for (int i = 0; i < str.length(); i++)
a[i] = str[i] - '0';
int tem = 21, cnt = 0;
while (tem) {
b[cnt++] = tem % 2;
tem /= 2;
}
for (int i = 0; i < 5; i++) {
if (b[i]) {
for (int j = 0; j < str.length(); j++) {
c[j + i] += a[j];
}
}
}
int mx = str.length() + 30;
for (int i = 0; i <= mx; i++) {
c[i + 1] += c[i] / 2;
c[i] %= 2;
}
string ans;
for (int i = 0; i <= mx + 31; i++)
ans.push_back(c[i] + '0');
while (!ans.empty() && ans.back() == '0')
ans.pop_back();
reverse(all(ans));
cout << ans << "\n";
return 0;
}
C. 01BFS
题意
有一个二维无限平面,给定起始点 \((x1, y1)\) 和终点 \((x2, y2)\), 平面上有 \(n\) 个障碍物,它们的坐标都是 \(0 \leq x \leq 10^3\), \(0 \leq y \leq 10^3\),问从起点到终点,最少要穿过几个障碍物
分析
这题应该有更简单的方法,但是赛时比较紧张,第一反应是建一个最短路,相邻格点建边,目标有冰块就权值1,否则权值0,然后跑迪杰斯特拉。不过发现评测机跑样例都内存超限了,就被迫考虑优化,发现刚好权值都是0和1,想到01bfs,就不用建边,直接跑最短路,在队列取出来的时候再判断相邻节点有哪些,然后权值是1的放队尾,权值0的放队首。赛后想想,可能普通的最短路也行,只要不显式的建边,可能也不会爆内存。
这题有个坑点,就是建边时候判断边界要是1001,不能只判断到1000,因为虽然那些坐标都在1000以内,但是实际人是可以绕到1000外面再走回去,所以得多往外面判断几格。
点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 1e3 + 10;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int tag[maxn][maxn], dis[maxn * maxn], vis[maxn * maxn];
int trans(int i, int j) {
return (i - 1) * 1005+ j;
}
signed main() {
memset(dis, 0x3f, sizeof dis);
int n, x1, y1, x2, y2;
cin >> n >> x1 >> y1 >> x2 >> y2;
int m = 1e3 + 5;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
tag[x][y] = 1;
}
deque<int> dq;
dis[trans(x1, y1)] = 0;
dq.push_back(trans(x1, y1));
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
if (vis[u]) continue;
vis[u] = 1;
int x = (u - 1) / m + 1, y = u % m;
if (x == x2 && y == y2) {
cout << dis[u] << "\n";
return 0;
}
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > m || yy < 1 || yy > m) continue;
int v = trans(xx, yy);
dis[v] = min(dis[v], dis[u] + tag[xx][yy]);
if (tag[xx][yy]) dq.push_back(v);
else dq.push_front(v);
}
}
return 0;
}
5.二分、倍增
这题我感觉是前六题里面最难的,一开始还读错题了
题意
原题意有点绕,我直接给出形式化题意吧。给定一个数组, 将其分成不超过 \(k\) 个连续子数组, 每一段内的极差 (最大值减最小值)不超过 \(d\)。然后问三个问题:
假如只给定 \(k\) 求最小的 \(d\), 假如只给定 \(d\) 求最小的 \(k\), 假如给定了 \(d\) 和 \(k\) ,问最长能从原数组里取多长的子数组。
分析
- 第一个问题,给定分段数,求最小极差,显然可以二分答案,检验方式也很明显,假设当前二分的答案是mid,从头到尾遍历数组,维护当前分段的最大最小值,如果超了就另起一段。看最后分段的数量有没有超过 \(k\)。
- 第二个问题,给定极差,求最小分段数。发现这不就是第一个问题里的check函数,所以从头扫一遍数组,维护极差,超了另起一段,最后总的段数就是答案。
- 第三个问题比较难一点,给定 \(d\) 和 \(k\) ,求最长的连续子数组满足这两个条件的长度。会发现,假如选定了这个子数组的起始位置,然后就是之前的check函数那样的暴力判断,看什么时候不满足这两个条件,复杂度 \(O(n^2)\)。然后想到,每个位置,往后一直到不合法为止,这个长度是固定的,相当于是一段一段的跳。所以可以预处理,从每个位置开始,往后第一个不合法的地方,枚举起点后就可以连着跳 \(k\) 次,看最后到了哪里。然后发现这个过程可以用倍增维护,直接预处理每个位置往后跳 \(2^i\) 个段的位置,就可以枚举起点后 \(logk\)的判断终点。然后怎么判断第一次跳到哪里会超,可以用st表加二分,看第一次最大值和最小值差超过 \(d\) 的位置就是所求的,然后倍增处理查询即可。
代码
点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define ll long long
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 5e5 + 10;
int arr[maxn], lg[maxn];
int mx[maxn][22], mn[maxn][22];
int st[maxn][22];
int n, k, d;
int qmn(int l, int r) {
int k = lg[r - l + 1];
return min(mn[l][k], mn[r - (1 << k) + 1][k]);
}
int qmx(int l, int r) {
int k = lg[r - l + 1];
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
bool ck1(int mid) {
// 分成 k 段, 求最小 段内极差
int cnt = 1;
int mxx = arr[1], mnn = arr[1];
for (int i = 1; i <= n; i++) {
mxx = max(mxx, arr[i]);
mnn = min(mnn, arr[i]);
if (mxx - mnn > mid) {
cnt++;
mxx = arr[i];
mnn = arr[i];
}
if (cnt > k) return 0;
}
return cnt <= k;
}
signed main() {
for (int i = 2; i < maxn; i++)
lg[i] = lg[i >> 1] + 1;
cin >> n >> k >> d;
for (int i = 1; i <= n; i++)
cin >> arr[i], mn[i][0] = mx[i][0] = arr[i];
for (int j = 1; j < 21; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
{
int l = 0, r = 1e9, ans = 0;
while (l <= r) {
int mid = ((ll)l + r) >> 1;
if (ck1(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << "\n";
}
{
//给定极差 d 求最小段数
int mxx = arr[1], mnn = arr[1], ans = 1;
for (int i = 1; i <= n; i++) {
mxx = max(mxx, arr[i]);
mnn = min(mnn, arr[i]);
if (mxx - mnn > d) {
mxx = arr[i], mnn = arr[i];
ans++;
}
}
cout << ans << "\n";
}
{
// 预处理每个位置开始往后跳第一次越界的地方
for (int i = 1; i <= n; i++) {
int l = i + 1, r = n, ans = n + 1;
while (l <= r) {
int mid = ((ll)l + r) >> 1;
int mxx = qmx(i, mid), mnn = qmn(i, mid);
if (mxx - mnn > d) ans = mid, r = mid - 1;
else l = mid + 1;
}
st[i][0] = ans;
}
st[n + 1][0] = n + 1;
for (int j = 1; j < 21; j++)
for (int i = 1; i <= n + 1; i++)
st[i][j] = st[st[i][j - 1]][j - 1];
int ans = 0;
for (int i = 1; i <= n; i++) { //枚举起点
int s = i;
for (int j = 0; j < 21; j++)
if (k >> j & 1)
s = st[s][j];
ans = max(ans, s - i);
if (n - i + 1 <= ans)
break;
}
cout << ans << "\n";
}
return 0;
}
6. DP,LIS
题意
给定长度为 \(n\) (\(n\)) 的数组,问有多少个子序列是严格山峰的(有且仅有一个最大值,左边严格递增,右边是严格递减)
分析
考虑去枚举山峰的最大值,以它为最大值的贡献,是左侧的严格上升子序列,并且结尾小于当前最大值。右侧的严格下降子序列,并且开头小于中间这个最大值的总和,二者乘积即为当前的贡献。所以就去处理左右两侧,然后就转化为,对每个 \(i\) 求以它结尾的最长上升子序列个数,用树状数组即可处理,是经典dp。再倒着做一遍,然后前后缀两个树状数组,不断维护一下前后缀的那些子数组数量就好。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 3e5 + 10;
struct BIT {
vector<int> v;
int len;
int lowbit(int x) { return x & -x; }
BIT(int n) {
len = n + 3;
v.resize(len);
}
void update(int i, int x) {
i++;
for (int pos = i; pos <= len; pos += lowbit(pos))
v[pos] = ((v[pos] + x) % mod + mod) % mod;
}
int ask(int i) {
int res = 0;
i++;
for (int pos = i; pos; pos -= lowbit(pos))
res = ((res + v[pos]) % mod + mod) % mod;
return res;
}
void clear() {
for (int i = 0; i < len; i++)
v[i] = 0;
}
};
int arr[maxn], b[maxn];
int predp[maxn], sufdp[maxn];
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
b[i] = arr[i];
}
sort(b + 1, b + 1 + n);
int len = unique(b + 1, b + 1 + n) - b - 1;
for (int i = 1; i <= n; i++) {
arr[i] = lower_bound(b + 1, b + 1 + len, arr[i]) - b;
}
BIT pre(len), suf(len);
pre.update(0, 1);
for (int i = 1; i <= n; i++) {
predp[i] = pre.ask(arr[i] - 1);
pre.update(arr[i], predp[i]);
}
suf.update(0, 1);
for (int i = n; i >= 1; i--) {
sufdp[i] = suf.ask(arr[i] - 1);
suf.update(arr[i], sufdp[i]);
}
pre.clear();
pre.update(0, 1);
int ans = 0;
for (int i = 1; i <= n; i++) {
suf.update(arr[i], -sufdp[i]);
ans = ((ans + pre.ask(arr[i] - 1) * suf.ask(arr[i] - 1) % mod) % mod + mod) % mod;
pre.update(arr[i], predp[i]);
}
cout << ans << "\n";
return 0;
}
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define db double
#define tii tuple<int, int, int>
#define all(a) a.begin(), a.end()
using namespace std;
const int mod = 998244353;
const int maxn = 6e5 + 10;
vector<pii> G[maxn];
int lg[maxn], fa[maxn][23], dep[maxn];
int xu[maxn], val[maxn], sub[maxn];
struct Node {
int a, b;
Node(int a1, int b1) {a = a1, b = b1;}
};
void dfs(int u, int f, int deep) {
fa[u][0] = f, dep[u] = deep;
for (int i = 1; i <= lg[dep[u]]; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (auto [v, w] : G[u]) {
if (v == f) continue;
val[v] = w;
dfs(v, u, deep + 1);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
while (dep[u] > dep[v])
u = fa[u][lg[dep[u] - dep[v]]];
if (u == v) return u;
for (int i = lg[dep[u]]; ~i; i--)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
void dfs1(int u, int f) {
for (auto[v, w] : G[u]) {
if (v == f) continue;
dfs1(v, u);
sub[u] += sub[v];
}
}
bool operator < (Node a, Node b) {
auto [x, y] = a;
int res1 = x * y - (x / 2) * y;
auto [c, d] = b;
int res2 = c * d - (c / 2) * d;
return res1 < res2;
}
signed main() {
for (int i = 2; i < maxn; i++)
lg[i] = lg[i >> 1] + 1;
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
for (int i = 1; i <= m; i++)
cin >> xu[i];
xu[0] = 1;
dfs(1, 0, 0);
for (int i = 1; i <= m; i++) {
int u = xu[i - 1], v = xu[i];
sub[u]++, sub[v]++;
sub[lca(u, v)] -= 2;
}
dfs1(1, 0);
priority_queue<Node> q;
for (int i = 2; i <= n; i++) {
q.push(Node(val[i], sub[i]));
}
while (k-- && !q.empty()) {
auto [w, cnt] = q.top();
q.pop();
w /= 2;
if (cnt)
q.push(Node(w, cnt));
}
int ans = 0;
while (!q.empty()) {
auto [w, cnt] = q.top();
q.pop();
ans += cnt * w;
}
cout << ans << "\n";
return 0;
}
后记
第四题不会做可惜了,这里放个题意,感兴趣的可以想想。给一个长度为 \(n\) 的环形字符串,每个位置有一个权值。然后多次操作,第一种操作是修改单点权值。第二种操作是选择一个区间,然后从左到右开始,每有两个同样的字符,就删去这两个字符以及中间的字符。求最后剩下的字符的位置上的权值和。
再练一年希望明年拿个金,加训!