T1
推倒骨牌
多维护几个东西就能直接倍增了。不要开 long long。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;
int n, q;
struct BIT {pair<int, int> bit[500005];void add(int x, int y) { for (int tx = x; x <= n; x += lowbit(x)) bit[x] = max(bit[x], make_pair(y, tx)); }pair<int, int> query(int x) {pair<int, int> ret = { 0, 0 };for (; x; x -= lowbit(x)) ret = max(ret, bit[x]);return ret;}
} bit;
int p[500005], l[500005];
int f[21][500005][4];
signed main() {freopen("dominoes.in", "r", stdin);freopen("dominoes.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> p[i] >> l[i];for (int i = n; i; i--) {pair<int, int> tmp = bit.query(upper_bound(p + 1, p + n + 1, p[i] + l[i]) - p - 1);f[0][i][1] = max(tmp.first, p[i] + l[i]);bit.add(i, f[0][i][1]);f[0][i][0] = upper_bound(p + 1, p + n + 1, f[0][i][1]) - p - 1;f[0][n + 1][1] = max(f[0][n + 1][1], p[i] + l[i]);f[0][i][3] = bit.query(upper_bound(p + 1, p + n + 1, f[0][i][1]) - p - 1).second;}f[0][n + 1][0] = n;for (int i = 1; i < 21; i++) {for (int j = 1; j <= n + 1; j++) {int *g = f[i - 1][j];f[i][j][0] = f[i - 1][g[0] + 1][0];f[i][j][1] = f[i - 1][g[0] + 1][1];f[i][j][2] = f[i - 1][g[0] + 1][2] + g[2] + max(0, p[g[0] + 1] - g[1]);f[i][j][3] = f[i - 1][g[0] + 1][3];}}cin >> q;while (q--) {int x, y;cin >> x >> y;int ans = 0;for (int i = 20; ~i; i--) {if (f[i][f[0][x][0] + 1][0] < y) ans += f[1][x][2] + f[i][f[0][x][0] + 1][2], x = f[i][f[0][x][0] + 1][3];}if (f[0][x][0] < y) ans += f[1][x][2];cout << ans << "\n";}return 0;
}
T2
购买装饰品
枚举两个的交选了多少，剩下的只有一个要的选最小的那些，再剩下的再选最小的那些。随便拿个比如说权值线段树维护一下前 \(k\) 小和就好了。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, K, X, Y;
int ad[200005];
int v[200005];
vector<int> vec[4];
int d[200005], dcnt;
struct Segment_Tree {int s[800005], sv[800005];void Add(int o, int l, int r, int x, int y) {if (l == r) return s[o] += y, sv[o] += d[x] * y, void();int mid = (l + r) >> 1;if (x <= mid) Add(o << 1, l, mid, x, y);else Add(o << 1 | 1, mid + 1, r, x, y);s[o] = s[o << 1] + s[o << 1 | 1];sv[o] = sv[o << 1] + sv[o << 1 | 1];}int Query(int o, int l, int r, int k) {if (l == r) return s[o] >= k ? d[r] * k : inf;int mid = (l + r) >> 1;if (s[o << 1] >= k) return Query(o << 1, l, mid, k);else return Query(o << 1 | 1, mid + 1, r, k - s[o << 1]) + sv[o << 1];}
} seg;
signed main() {freopen("decoration.in", "r", stdin);freopen("decoration.out", "w", stdout);int ans = inf;cin >> n >> m >> K;for (int i = 1; i <= n; i++) cin >> v[i], d[i] = v[i];sort(d + 1, d + n + 1), dcnt = unique(d + 1, d + n + 1) - d - 1;cin >> X; for (int i = 1, x; i <= X; i++) cin >> x, ad[x] |= 2;cin >> Y; for (int i = 1, x; i <= Y; i++) cin >> x, ad[x] |= 1;for (int i = 1; i <= n; i++) vec[ad[i]].emplace_back(v[i] = lower_bound(d + 1, d + dcnt + 1, v[i]) - d);for (int i : { 0, 1, 2, 3 }) sort(vec[i].begin(), vec[i].end());for (int i = 1; i <= n; i++) seg.Add(1, 1, dcnt, v[i], 1);int cs = 0;for (int i = 0; i < (int)vec[3].size(); i++) {seg.Add(1, 1, dcnt, vec[3][i], -1); cs += d[vec[3][i]];if (i >= K - 1 && m >= i + 1) ans = min(ans, cs + seg.Query(1, 1, dcnt, m - i - 1));}for (int i = 0; i < (int)vec[3].size(); i++) seg.Add(1, 1, dcnt, vec[3][i], 1);cs = 0;int cur = min(K, (int)vec[3].size());for (int i = 0; i < cur; i++) seg.Add(1, 1, dcnt, vec[3][i], -1), cs += d[vec[3][i]];if ((int)vec[1].size() < K - cur || (int)vec[2].size() < K - cur) return cout << (ans == inf ? -1 : ans) << "\n", 0;if (cur + (K - cur) * 2 > m) return cout << (ans == inf ? -1 : ans) << "\n", 0;for (int i = 0; i < K - cur; i++) seg.Add(1, 1, dcnt, vec[1][i], -1), cs += d[vec[1][i]];for (int i = 0; i < K - cur; i++) seg.Add(1, 1, dcnt, vec[2][i], -1), cs += d[vec[2][i]];for (int i = cur - 1; i >= -1; i--, cur--) {if (m - cur - 2 * (K - cur) < 0) break;ans = min(ans, cs + seg.Query(1, 1, dcnt, m - cur - 2 * (K - cur)));if (i == -1) break;if ((int)vec[1].size() < K - i || (int)vec[2].size() < K - i) break;cs -= d[vec[3][i]], cs += d[vec[1][K - cur]], cs += d[vec[2][K - cur]];seg.Add(1, 1, dcnt, vec[3][i], 1);seg.Add(1, 1, dcnt, vec[1][K - cur], -1);seg.Add(1, 1, dcnt, vec[2][K - cur], -1);}cout << ans << "\n";return 0;
}
T3
耍望节
处理出 \(f_{i, j}\) 表示做完前 \(i - 1\) 位到了 \(j\) 状态的情况下，后面有多少合法方案。如果单次询问只需要从高到低枚举每一位填啥就好了。
多次询问，显然只需要考虑最后一个匹配的中的问号和前面的 18 个问号，再前面的一定都是 0。暴力做完这部分剩下的后缀，其中的问号依次把剩下的 \(k\) 的每一位从高到低填进去即可。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#define int long long
using namespace std;
const int inf = 1000000000000000001;
const int P = 1000000007;
int n, m, q, K;
string S, T;
queue<int> Q;
int son[25][10];
void Insert(string str) {int p = 0;for (auto v : str) {int t = v - '0';if (!son[p][t]) son[p][t] = ++m;p = son[p][t];}
}
int fail[25];
void Build() {for (int i = 0; i < 10; i++) if (son[0][i]) Q.push(son[0][i]);while (!Q.empty()) {int x = Q.front();Q.pop();for (int i = 0; i < 10; i++) {if (son[x][i]) Q.push(son[x][i]), fail[son[x][i]] = son[fail[x]][i];else son[x][i] = son[fail[x]][i];}}for (int i = 0; i < 10; i++) son[m][i] = m;
}
int f[50005][21];
int g[50005][21];
int h[50005], pw[50005];
int to[50005];
int l0[50005], l0cnt;
signed main() {freopen("shuawang.in", "r", stdin);freopen("shuawang.out", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);pw[0] = 1;for (int i = 1; i <= 50000; i++) pw[i] = pw[i - 1] * 10 % P;int tc;cin >> tc;while (tc--) {l0cnt = -1; m = 0; memset(son, 0, sizeof son);memset(f, 0, sizeof f);memset(g, 0, sizeof g);memset(h, 0, sizeof h);memset(to, 0, sizeof to);memset(fail, 0, sizeof fail);cin >> n >> q;cin >> S >> T; K = T.size();Insert(S), Build(); S = ' ' + S, T = ' ' + T;f[K + 1][m] = 1;for (int i = K; i; i--) {for (int j = 0; j <= m; j++) {if (T[i] != '?') f[i][j] = f[i + 1][son[j][T[i] - '0']];else for (int k = 0; k < 10; k++) f[i][j] = min(inf, f[i][j] + f[i + 1][son[j][k]]);}}int p = -1;for (int t, i = K - m + 1; i; i--) {for (int j = t = 1; j <= m; j++) t &= (T[i + j - 1] == '?' || S[j] == T[i + j - 1]);if (!t) continue;p = i; break;}if (p == -1) {while (q--) cin >> n, cout << "-1\n";continue;}int cnt = 0, s = p;for (; s && cnt <= 20; --s) cnt += (T[s] == '?');while (T[s] != '?') ++s;for (int i = 1; i <= K; i++) {if (T[i] == '?') {to[i] = i + 1;for (int j = 0; j <= m; j++) {g[i][j] = j;for (int k = i + 1; k <= K && T[k] != '?'; k++) g[i][j] = son[g[i][j]][T[k] - '0'];}for (int k = i + 1; k <= K && T[k] != '?'; k++) {h[i] = (h[i] + (T[k] - '0') * pw[K - k]) % P;to[i] = k + 1;}} else to[i] = to[i - 1];}l0cnt = -1;for (int i = K; i >= p + m; i--) if (T[i] == '?') l0[++l0cnt] = i;int _base = 0, _State = 0;for (int i = 1; i < s; i++) {_base = (_base + (T[i] == '?' ? 0 : T[i] - '0') * pw[K - i]) % P;_State = son[_State][T[i] == '?' ? 0 : T[i] - '0'];}for (int i = to[p + m - 1]; i <= K; i++) _base = (_base + (T[i] == '?' ? 0 : T[i] - '0') * pw[K - i]) % P;while (q--) {int k, ans = _base, cur = _State;cin >> k;if (k > f[1][0]) {cout << "-1\n";continue;}for (int i = s; i <= p + m - 1; i = to[i]) {for (int j = 0; j < 10; j++) {if (f[i + 1][son[cur][j]] >= k) {cur = son[cur][j];ans = (ans + pw[K - i] * j) % P;break;} else k -= f[i + 1][son[cur][j]];}cur = g[i][cur];ans = (ans + h[i]) % P;}--k;int c = 0;while (k) {ans = (ans + (k % 10) * pw[K - l0[c]]) % P;k /= 10; ++c;}cout << ans << "\n";}}return 0;
}T4
学习算法
把所有东西按权值排序，然后相当于按顺序走完每个点，要求走的总距离最小。然后还有一些限制，要求某些点必须在某些点前面走。将限制连边，则边有前向和后向两种。考虑到限制的形式，发现每段区间至多走两次就可以走完里面的点并满足限制。于是观察路径的形态，必然形如 \(s \rightarrow 1 \rightarrow n \rightarrow e\)（或反过来）。这个时候所有正向限制自然容易在正着走的时候满足，只需要考虑逆向限制带来的额外代价。显然从 \(s \rightarrow 1\) 和 \(n \rightarrow e\) 这两段各走两遍，中间的可能会有一些区间由于逆向限制一共要被走三遍。那么固定 \(s, e\) 过后，容易求出中间到底有哪些间隔要被算三次。于是枚举 \(s\)，维护最优的 \(e\) 即可。构造方案，就，对着搞一搞。注意 \(s\) 和 \(e\) 不能被逆向限制覆盖，即使这样不优。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <array>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, Ans = inf, ans[1000005], sz;
int w[1000005], o[1000005], d[1000005];
int _o[1000005], re[1000005];
void work() {memset(d, 0, sizeof d);for (int i = 1; i <= n; i++) _o[o[i]] = i;for (int i = m + 1; i <= n; i++) if (_o[i] < _o[re[i]]) ++d[_o[i]], --d[_o[re[i]]];for (int i = 1; i <= n; i++) d[i] += d[i - 1];array<int, 2> tmp = { inf, 0 };array<int, 3> f = { inf, 0, 0 };for (int i = n; i; i--) {tmp[0] += (d[i] ? 3 : 1) * (w[o[i + 1]] - w[o[i]]);tmp = min(tmp, (array<int, 2>) { (w[o[n]] - w[o[i]]) * 2, i });f = min(f, (array<int, 3>) { 2 * (w[o[i]] - w[o[1]]) + tmp[0], i, tmp[1] });}if (f[0] < Ans) {Ans = f[0], sz = 0;int S = f[1], E = f[2];if (S == E) S = 0, E = 1;for (int i = S; i; i--) if (o[i] <= m) ans[++sz] = o[i];for (int i = 1; i <= S; i++) if (o[i] > m) ans[++sz] = o[i];for (int i = S + 1; i < E; i++) {if (!d[i]) ans[++sz] = o[i];else {int j = i; while (j < E - 1 && d[j]) ++j;for (int k = j; k >= i; k--) if (o[k] <= m) ans[++sz] = o[k];for (int k = i; k <= j; k++) if (o[k] > m) ans[++sz] = o[k];i = j;}}for (int i = E; i <= n; i++) if (o[i] <= m) ans[++sz] = o[i];for (int i = n; i >= E; i--) if (o[i] > m) ans[++sz] = o[i];}
}
signed main() {freopen("learn.in", "r", stdin);freopen("learn.out", "w", stdout);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> w[i], o[i] = i;sort(o + 1, o + n + 1, [](int x, int y) { return w[x] < w[y]; });for (int i = m + 1; i <= n; i++) cin >> re[i];work();for (int i = 1; i <= n; i++) w[i] = -w[i]; reverse(o + 1, o + n + 1);work();cout << Ans << "\n";for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];return 0;
}
T4，类 adhoc 状物。但看起来可能也又有点道理。
场上 T1 开 long long MLE 了。应当造极限数据测空间，想清楚到底有无必要开 long long。算空间时记清楚空间限制。
T3 场上代码只写错了一个地方（一个自增运算符的参数写错），但是大样例过了。无论如何还是应该仔细检查代码，而不是相信大样例。
