《如 何 速 通 一 套 题》12.0

别问我为什么没有 11.0。补完了 1002 的题我就更 11.0。

邮寄

开场秒掉 AC，用了 1h。

然后开始看 B，死磕了 B 2h 之后磕不动了，然后看 D。

D 忽略了一个关键信息，100 -> 0... 挂大分了。

100+40+75+0=200。

A 旋律的总数

可以固定第一个元素为 \(1\)（因为其他的情况会重掉）。

然后答案就是 \(m^{n - 1}\)。

#include <bits/stdc++.h>
using namespace std;const int kMod = int(1e9) + 7;int t, n, m;int qpow(int x, int y) {int rs = 1;for(; y; y >>= 1) {if(y & 1) {rs = 1ll * rs * x % kMod;}x = 1ll * x * x % kMod;}return rs;
}int main() {freopen("sum.in", "r", stdin);freopen("sum.out", "w", stdout);for(cin >> t; t--; ) {cin >> n >> m;cout << qpow(m, n - 1) << '\n';}return 0;
}

B 水果加工

第十四剪枝。

首先，显然的我们有一个加了可行性剪枝的暴搜：

#include <bits/stdc++.h>
#define int long long
using namespace std;int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;void DFS(int c, int a, int b, int cd, int cu) {//cout << c << ' ' << a << ' ' << b << '\n';if(c > n) {//cout << cd << ' ' << cu << '\n';ans = min(ans, cd + cu);return ;}for(int i = 0; i <= arr[c]; i++) {int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];if(na <= x && nb <= y) {DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));}}
}signed main() {freopen("fruit.in", "r", stdin);freopen("fruit.out", "w", stdout);cin >> n;for(int i = 1; i <= n; i++) {cin >> arr[i];}cin >> x >> y;for(int i = 1; i <= n; i++) {cin >> cx[i];}for(int i = 1; i <= n; i++) {cin >> cy[i];}for(int i = 1; i <= n; i++) {cin >> dx[i];}for(int i = 1; i <= n; i++) {cin >> dy[i];}for(int i = 1; i <= n; i++) {cin >> ux[i];}for(int i = 1; i <= n; i++) {cin >> uy[i];}DFS(1, 0, 0, 0, 0);cout << ans << '\n';return 0;
}

聪明的小同学肯定想到了，我们可以加上简单的最优性剪枝啊！

所以有了 Original + CS11：

#include <bits/stdc++.h>
#define int long long
using namespace std;int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;void DFS(int c, int a, int b, int cd, int cu) {//cout << c << ' ' << a << ' ' << b << '\n';if(cd + cu > ans) {return ;}if(c > n) {//cout << cd << ' ' << cu << '\n';ans = min(ans, cd + cu);return ;}for(int i = 0; i <= arr[c]; i++) {int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];if(na <= x && nb <= y) {DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));}}
}signed main() {freopen("fruit.in", "r", stdin);freopen("fruit.out", "w", stdout);cin >> n;for(int i = 1; i <= n; i++) {cin >> arr[i];}cin >> x >> y;for(int i = 1; i <= n; i++) {cin >> cx[i];}for(int i = 1; i <= n; i++) {cin >> cy[i];}for(int i = 1; i <= n; i++) {cin >> dx[i];}for(int i = 1; i <= n; i++) {cin >> dy[i];}for(int i = 1; i <= n; i++) {cin >> ux[i];}for(int i = 1; i <= n; i++) {cin >> uy[i];}DFS(1, 0, 0, 0, 0);cout << ans << '\n';return 0;
}

然后，更聪明的小伙伴就会发现，这个剪枝力度不够大，还可以再大一点。

于是有了 Original + CS(11 + 21)：

#include <bits/stdc++.h>
#define int long long
using namespace std;int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;void DFS(int c, int a, int b, int cd, int cu) {//cout << c << ' ' << a << ' ' << b << '\n';if(cd + cu >= ans) {return ;}if(c > n) {//cout << cd << ' ' << cu << '\n';ans = min(ans, cd + cu);return ;}for(int i = 0; i <= arr[c]; i++) {int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];if(na <= x && nb <= y) {DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));}}
}signed main() {freopen("fruit.in", "r", stdin);freopen("fruit.out", "w", stdout);cin >> n;for(int i = 1; i <= n; i++) {cin >> arr[i];}cin >> x >> y;for(int i = 1; i <= n; i++) {cin >> cx[i];}for(int i = 1; i <= n; i++) {cin >> cy[i];}for(int i = 1; i <= n; i++) {cin >> dx[i];}for(int i = 1; i <= n; i++) {cin >> dy[i];}for(int i = 1; i <= n; i++) {cin >> ux[i];}for(int i = 1; i <= n; i++) {cin >> uy[i];}DFS(1, 0, 0, 0, 0);cout << ans << '\n';return 0;
}

这个时候，更加聪明的巨佬就会发现，可以剪掉一定不是当前最优的状态！

于是有了 Original + CS(11, 21, 22)，AC：

#include <bits/stdc++.h>
#define int long long
using namespace std;struct node {int c, a, b, cd;bool operator <(const node &x) const {return c == x.c? (a == x.a? (b == x.b? cd < x.cd : b < x.b) : a < x.a) : c < x.c;}
};int n, arr[44], x, y, cx[44], cy[44], dx[44], dy[44], ux[44], uy[44], ans = 1e11;
map<node, int> mpd;void DFS(int c, int a, int b, int cd, int cu) {//cout << c << ' ' << a << ' ' << b << '\n';if(cd + cu >= ans) {return ;}if(mpd.find({c, a, b, cd}) != mpd.end() && mpd[{c, a, b, cd}] <= cu) {return ;}mpd[{c, a, b, cd}] = cu;if(c > n) {//cout << cd << ' ' << cu << '\n';ans = min(ans, cd + cu);return ;}for(int i = 0; i <= arr[c]; i++) {int na = a + (!!i) * cx[c], nb = b + (!!(arr[c] - i)) * cy[c];if(na <= x && nb <= y) {DFS(c + 1, na, nb, max({cd, dx[c] * i, dy[c] * (arr[c] - i)}), max({cu, ux[c] * i, uy[c] * (arr[c] - i)}));}}
}signed main() {freopen("fruit.in", "r", stdin);freopen("fruit.out", "w", stdout);cin >> n;for(int i = 1; i <= n; i++) {cin >> arr[i];}cin >> x >> y;for(int i = 1; i <= n; i++) {cin >> cx[i];}for(int i = 1; i <= n; i++) {cin >> cy[i];}for(int i = 1; i <= n; i++) {cin >> dx[i];}for(int i = 1; i <= n; i++) {cin >> dy[i];}for(int i = 1; i <= n; i++) {cin >> ux[i];}for(int i = 1; i <= n; i++) {cin >> uy[i];}DFS(1, 0, 0, 0, 0);cout << ans << '\n';return 0;
}

C 最佳位置

显然对于每一个人除了前缀后缀之外就只会坐在一个区间的中间位置。

所以可以直接两个 set，一个维护有人进来的，一个维护有人出去的，然后根据对应操作直接干就是了。

#include <bits/stdc++.h>
using namespace std;int n, m, x, ans[300030];int gl(int l, int r) {if(l == 1 || r == n) {return r - l + 1;}int mid = (l + r) >> 1;return min(mid - l, r - mid) + 1;
}int pos(int l, int r) {if(l == 1) {return 1;}if(r == n) {return n;}return (l + r) >> 1;
}struct node {int len, l, r;
};struct cmp1 {bool operator ()(const node &a, const node &b) const {return a.l < b.l;}
};//*
struct cmp2 {bool operator ()(const node &a, const node &b) const {return a.len == b.len? a.l < b.l : a.len > b.len;}
};
//*/set<node, cmp1> st1;
set<node, cmp2> st2;void ins(int l, int r) {if(l > r) {return ;}int tmp = gl(l, r);st1.insert({tmp, l, r});st2.insert({tmp, l, r});
}int main() {freopen("location.in", "r", stdin);freopen("location.out", "w", stdout);cin >> n >> m;st1.insert({-1, -1, -1});st2.insert({-1, -1, -1});st1.insert({-1, n + 2, n + 2});st2.insert({-1, n + 2, n + 2});st1.insert({n, 1, n});st2.insert({n, 1, n});for(int i = 1; i <= 2 * m; i++) {cin >> x;if(!ans[x]) {node tmp = *st2.begin();st2.erase(st2.begin());st1.erase(tmp);ans[x] = pos(tmp.l, tmp.r);ins(tmp.l, ans[x] - 1);ins(ans[x] + 1, tmp.r);}else {node tmpl = *prev(st1.lower_bound({1, ans[x], ans[x]})), tmpr = *st1.lower_bound({1, ans[x], ans[x]});int nl = ans[x], nr = ans[x];if(tmpl.r == ans[x] - 1) {nl = tmpl.l;st1.erase(tmpl);st2.erase(tmpl);}if(tmpr.l == ans[x] + 1) {nr = tmpr.r;st1.erase(tmpr);st2.erase(tmpr);}ins(nl, nr);}/*for(auto i : st1) {cout << i.len << ',' << i.l << ',' << i.r << ' ';}cout << '\n';for(auto i : st2) {cout << i.len << ',' << i.l << ',' << i.r << ' ';}cout << '\n';for(int i = 1; i <= m; i++) {cout << ans[i] << ' ';}cout << '\n';cout << '\n';//*/}for(int i = 1; i <= m; i++) {cout << ans[i] << '\n';}return 0;
}
/*
9 9
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
*/

D 跑步路线

赛时没看到有一个 \(w_i\) 互不相同的条件，死了。

当 \(w_i\) 互不相同，MST 唯一，可以直接求出 MST 然后 MST 上面 LCA 求两点距离。

但是这个题要开 __int128_t qaq

#include <bits/stdc++.h>
#define int long long
using namespace std;struct node {int u, v, w;
}arr[200020];struct eeee {int v, w;
};int n, m, f[200020], k, t, x, y, fa[200020][22], ddp[200020], dep[200020];
__int128_t ans;
vector<eeee> to[200020];void write(__int128_t x) {if(!x) {return ;}write(x / 10);cout << char(x % 10 + '0');
}int findfa(int x) {return f[x] == x? x : (f[x] = findfa(f[x]));
}bool unionn(int x, int y) {x = findfa(x), y = findfa(y);f[y] = x;return x != y;
}void kruskal() {for(int i = 1; i <= n; i++) {f[i] = i;}for(int i = 1; i <= m; i++) {if(unionn(arr[i].u, arr[i].v)) {to[arr[i].u].push_back({arr[i].v, arr[i].w});to[arr[i].v].push_back({arr[i].u, arr[i].w});}}
}void DFS(int x = 1, int pa = 0) {fa[x][0] = pa;for(int i = 1; i <= 20; i++) {fa[x][i] = fa[fa[x][i - 1]][i - 1];}for(auto i : to[x]) {if(i.v != pa) {dep[i.v] = dep[x] + i.w + t;ddp[i.v] = ddp[x] + 1;DFS(i.v, x);}}
}int LCA(int x, int y) {if(ddp[x] < ddp[y]) {swap(x, y);}int tmp = ddp[x] - ddp[y];for(int i = 20; i >= 0; i--) {if((tmp >> i) & 1) {x = fa[x][i];}}if(x == y) {return x;}for(int i = 20; i >= 0; i--) {if(fa[x][i] != fa[y][i]) {x = fa[x][i], y = fa[y][i];}}return fa[x][0];
}signed main() {freopen("run.in", "r", stdin);freopen("run.out", "w", stdout);cin >> n >> m;for(int i = 1; i <= m; i++) {cin >> arr[i].u >> arr[i].v >> arr[i].w;}sort(arr + 1, arr + m + 1, [](node a, node b) {return a.w < b.w;});kruskal();cin >> k >> t;DFS();cin >> x;for(k--; k; k--) {cin >> y;int tmp = LCA(x, y);ans = ans + dep[x] + dep[y] - 2 * dep[tmp];x = y;}//cout << cs << ' ' << cl << ' ' << pk << '\n';if(ans) {ans = ans - t;}write(ans);return 0;
}