个人难度评级
签到:$ABCHI$
简单:$DFG$
中等:$J$
困难:$E$
A 本场比赛灵感来源于树状数组出题组
按照数字从小到大检查即可,注意是其他数字,记得 $-1$ 。
void solve() {
int n;
cin >> n;
map<int, int> cnt;
for (int i = 0, x; i < n; ++i)
cin >> x, cnt[x]++;
int s = 0, ans = 0;
for (auto [u, v] : cnt) {
s += v;
if (s - 1 >= 1.0 * (n - 1) * 0.8)
ans += v * u;
}
cout << ans << endl;
}
B 构造部落
记录每个首领在位的年份计算即可。
void solve() {
int n, q, s;
cin >> n >> q >> s;
vector<int> a(n);
a[0] = s;
for (int i = 0, x; i < n; ++i) {
cin >> x;
if (i + 1 < n)
a[i + 1] = a[i] + x;
}
while (q--) {
int x, y;
cin >> x >> y;
cout << a[x - 1] + y - 1 << endl;
}
}
C 墨提斯的排列
在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码
void solve() {
int n;
cin >> n;
for (int i = 0; i < (1 << n); ++i) {
cout << (i ^ (i >> 1)) << " ";
}
cout << endl;
}
D 东风谷早苗与博丽灵梦
求解 $a\cdot c_1 + s\cdot c_2 = x$ ,且 $max(c_1,c_2)$ 最小。
首先存在解的充要条件是 $\gcd(a,s)|x$ 。我们先用扩展欧几里得求出 $u,v$ 使得 $au+sv = g = gcd(a,s)$ 。然后令 $k=\frac{x}{g}$ 得到一组通解
$$c1 = u\cdot k + \frac{s}{g}t,\quad c2 = v\cdot k – \frac{a}{g}t$$
由于非负,得到 $t$ 的取值范围为 $[\lceil-\frac{u\cdot k}{\frac{s}{g}}\rceil,\lfloor\frac{v\cdot k}{\frac{a}{g}}\rfloor]$ 。由于 $max(c_1,c_2)$ 关于 $t$ 是凸的,因此最优点在使两者尽量接近的位置附近,检查一下即可。
注意中间乘法可能超过 $64$ 位,所以用 $\text{int128}$ 。
template <class T>
T exgcd(T a, T b, T &x, T &y) {
if (!b) {
x = 1, y = 0;
return a;
}
T d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
i128 flr(i128 a, i128 b) {
if (a >= 0)
return a / b;
return -((-a + b - 1) / b);
}
i128 cl(i128 a, i128 b) {
if (a >= 0)
return (a + b - 1) / b;
return -((-a) / b);
}
ostream &operator<<(ostream &os, __int128 n) {
if (n == 0)
return os << 0;
if (n < 0) {
os << '-';
n = -n;
}
string s;
while (n > 0) {
s += char('0' + n % 10);
n /= 10;
}
reverse(s.begin(), s.end());
return os << s;
}
void solve() {
ll x, a, s;
cin >> x >> a >> s;
ll u, v, g = exgcd(a, s, u, v);
if (x % g != 0) {
cout << "No" << endl;
return;
}
i128 k = (i128)(x / g), c10 = (i128)u * k, c20 = (i128)v * k;
i128 s1 = (i128)(s / g), s2 = (i128)(a / g);
i128 tmin = cl(-c10, s1), tmax = flr(c20, s2);
if (tmin > tmax) {
cout << "No" << endl;
return;
}
i128 t0 = flr(c20 - c10, s1 + s2);
vector<i128> cand = {tmin, tmax, t0 - 1, t0, t0 + 1};
sort(all(cand));
cand.erase(unique(all(cand)), cand.end());
bool ok = false;
i128 C1 = 0, C2 = 0, mx = ((i128)1 << 120);
for (i128 t : cand) {
if (t < tmin || t > tmax)
continue;
i128 c1 = c10 + s1 * t, c2 = c20 - s2 * t;
if (c1 < 0 || c2 < 0)
continue;
i128 cur = c1 > c2 ? c1 : c2;
if (cur < mx) {
mx = cur;
C1 = c1;
C2 = c2;
ok = true;
}
}
if (!ok) {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
cout << C1 << " " << C2 << endl;
}
E 立希的扫雷构造
总危险值等价于网格图中连接空地和地雷的边的总数量,是一个典型的最大割问题,我们需要将 $n\times m$ 个点划分为两个集合(大小分别为 $k$ 和 $n\times m−k$ ),使得两个集合之间的连边数量最大。
由于数据范围 $n,m\leq 9$ ,直接暴搜复杂度 $2^{81}$ 显然不行。但宽度很小,可以用状压 $\text{DP}$ 。因为涉及 $8$ 连通,我们需要维护一个轮廓线来确定当前格子与已处理格子的连通情况。当处理到第 $p$ 个格子时,轮廓线需要覆盖从 $p−1$(左)到 $p−m−1$(左上)的范围。因此,我们需要一个长度为 $m+1$ 的二进制掩码来记录。也就是 $dp[p][mask][k]$ 为处理完第 $p$ 个格子,轮廓线状态为 $mask$ ,已放置 $k$ 个地雷时的最大贡献值。只有空地和地雷相邻的时候才有贡献,所以状态转移方程为
$$ndp[nmask][nj]=max(ndp[nmask][nj],dp[mask][j]+\sum\limits(neighbor\oplus v))$$
题目中 $T\leq 10^4$ ,如果对每个询问都跑一遍 $DP$ 会超时。注意到 $n,m\leq 9$ ,所以我们可以缓存每种尺寸 $(n,m)$ 的计算结果。对于新的询问,如果该尺寸已计算过,直接查表并回溯构造答案即可。
bool vis[10][10];
vector<int> mans[10][10], mend[10][10], mtr[10][10];
void solve() {
int n, m, k;
cin >> n >> m >> k;
bool sw = false;
if (n < m) {
swap(n, m);
sw = true;
}
if (!vis[n][m]) {
int len = n * m, lim = 1 << (m + 1), sz = lim * (len + 1);
mtr[n][m].resize(len * sz);
mans[n][m].assign(len + 1, -1);
mend[n][m].assign(len + 1, -1);
vector<int> dp(sz, -1);
dp[0] = 0;
auto id = [&](int s, int k) {
return s * (len + 1) + k;
};
for (int p = 0; p < len; ++p) {
int r = p / m, c = p % m;
vector<int> ndp(sz, -1);
int base = p * sz;
bool hl = c > 0;
bool htl = r > 0 && c > 0;
bool ht = r > 0;
bool htr = r > 0 && c < m - 1;
for (int s = 0; s < lim; ++s) {
for (int j = 0; j <= p; ++j) {
if (dp[id(s, j)] == -1)
continue;
for (int v = 0; v < 2; ++v) {
int nj = j + v;
int add = 0;
if (hl)
add += ((s >> 0) & 1) ^ v;
if (htl)
add += ((s >> m) & 1) ^ v;
if (ht)
add += ((s >> (m - 1)) & 1) ^ v;
if (htr)
add += ((s >> (m - 2)) & 1) ^ v;
int ns = ((s << 1) & (lim - 1)) | v;
int val = dp[id(s, j)] + add;
int nidx = id(ns, nj);
if (val > ndp[nidx]) {
ndp[nidx] = val;
int drop = (s >> m) & 1;
mtr[n][m][base + nidx] = (drop << 1) | v;
}
}
}
}
dp = move(ndp);
}
for (int s = 0; s < lim; ++s) {
for (int j = 0; j <= len; ++j) {
int val = dp[id(s, j)];
if (val > mans[n][m][j]) {
mans[n][m][j] = val;
mend[n][m][j] = s;
}
}
}
vis[n][m] = true;
}
cout << mans[n][m][k] << endl;
vector<string> g(n, string(m, '.'));
int cs = mend[n][m][k], ck = k;
int len = n * m, lim = 1 << (m + 1), sz = lim * (len + 1);
auto id = [&](int s, int k) {
return s * (len + 1) + k;
};
for (int p = len - 1; p >= 0; --p) {
int info = mtr[n][m][p * sz + id(cs, ck)];
int v = info & 1;
int drop = (info >> 1) & 1;
if (v)
g[p / m][p % m] = '*';
cs = (cs >> 1) | (drop << m);
ck -= v;
}
if (sw) {
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i)
cout << g[i][j];
cout << endl;
}
} else {
for (int i = 0; i < n; ++i)
cout << g[i] << endl;
}
}
F 爱音的01串构造
$$score = 2\cdot T_{01} + 1\cdot T_0 + 0\cdot T_1$$
所以我们要最小化 $T_0 + 2T_1$ 。
因此我们应把 $0$ 和 $1$ 分成尽可能多的短块来减小各自的 “只含单一字符子串” 的贡献;但由于 $T_1$ 权重为 $2$ ,比 $T_0$ 更重要,所以优先把 $1$ 分成尽可能多的块(数量上限为 $a+1$ )。同样 $0$ 也要尽量分成多块(上限为 $b+1$ )。
所以策略:
- 设要把 $b$ 个 $1$ 分成 $r_1=\min(b,\;a+1)$ 个块,把 $a$ 个 $0$ 分成 $r_0=\min(a,\;b+1)$ 个块;
- 把每种字符尽量均匀分配到对应的块(大小差 $\leq 1$ );
- 若 $r_1\ge r_0$ 则从 ‘$1$’ 开始交替,否则从 ‘$0$’ 开始交替。
void solve() {
int a, b;
cin >> a >> b;
if (a == 0) {
cout << string(b, '1') << endl;
return;
}
if (b == 0) {
cout << string(a, '0') << endl;
return;
}
int r0 = min(a, b + 1), r1 = min(b, a + 1);
vector<int> A(r0, a / r0);
for (int i = 0; i < a % r0; ++i)
A[i]++;
vector<int> B(r1, b / r1);
for (int i = 0; i < b % r1; ++i)
B[i]++;
string ans = "";
bool f = (r1 >= r0);
int i1 = 0, i0 = 0;
while (i1 < r1 || i0 < r0) {
if (f) {
if (i1 < r1) {
ans.append(B[i1], '1');
++i1;
}
if (i0 < r0) {
ans.append(A[i0], '0');
++i0;
}
} else {
if (i0 < r0) {
ans.append(A[i0], '0');
++i0;
}
if (i1 < r1) {
ans.append(B[i1], '1');
++i1;
}
}
}
cout << ans << endl;
}
G 真白的幻觉
使用 $dfs$ 搜索即可,为了避免重复计算,我们只需要搜索数字非递减的序列。
map<ll, int> memo;
struct res {
ll num, f, g;
bool operator<(const res &other) const {
if (g != other.g) {
return g > other.g;
}
return num < other.num;
}
};
vector<res> cand;
void solve() {
auto calc = [&](ll x) {
ll res = 1;
for (auto v : to_string(x))
res *= isdigit(v) * (v - '0');
return res;
};
function<int(ll)> get = [&](ll x) {
if (x < 10)
return 0;
if (memo.count(x))
return memo[x];
ll nxt = calc(x);
return memo[x] = 1 + get(nxt);
};
function<void(int, ll, ll, int)> dfs = [&](int len, ll cur, ll prod, int lst) {
if (len > 0) {
int p = 0;
if (cur < 10)
p = 0;
else
p = 1 + get(prod);
cand.pb({cur, prod, p});
}
if (len == 18)
return;
for (int d = lst; d <= 9; d++) {
dfs(len + 1, cur * 10 + d, prod * d, d);
}
};
for (int i = 2; i <= 9; i++) {
dfs(1, i, i, i);
}
sort(all(cand));
res A = cand[0];
res B = {0, 0, -1};
for (int i = 1; i < cand.size(); i++) {
if (cand[i].f != A.f) {
B = cand[i];
break;
}
}
cout << A.num << " " << B.num << endl;
}
一组合法的解为
277777788888899 27777789999999999
H 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学
暴力更新,维护最大堆来快速取当前全局最大覆盖和,对于每次对某个中心的增量,我们把新的 $(sum, idx)$ 压入堆,查询时不断弹出堆顶直到堆顶记录与当前 $sum$ 一致。
int dx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2}, dy[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<ll>> g(n, vector<ll>(m));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> g[i][j];
vector<ll> sum(n * m);
auto id = [&](int x, int y) {
return x * m + y;
};
auto check = [&](int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
};
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (g[x][y] == 0)
continue;
ll v = g[x][y];
for (int k = 0; k < 13; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (check(nx, ny)) {
sum[id(nx, ny)] += v;
}
}
}
}
priority_queue<PLL> pq;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
pq.emplace(sum[id(i, j)], id(i, j));
while (q--) {
int x, y;
ll z;
cin >> x >> y >> z;
x--, y--;
g[x][y] += z;
for (int k = 0; k < 13; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (check(nx, ny)) {
sum[id(nx, ny)] += z;
pq.emplace(sum[id(nx, ny)], id(nx, ny));
}
}
while (!pq.empty()) {
auto [v, id] = pq.top();
if (sum[id] == v) {
cout << id / m + 1 << " " << id % m + 1 << endl;
break;
} else
pq.pop();
}
}
}
I 初华的扭蛋机
不要赌博就是从这来的,怎么下注都是亏。
令 $K\sim B(3,\frac{1}{6})$ , $E(x) = 2x\cdot P(K=1)+3x\cdot P(k=2)+10x\cdot P(k=3)$
$P(K=1) = \binom{3}{1}(\frac{1}{6})(\frac{5}{6})^2=\frac{25}{72}\\P(K=2) = \binom{3}{2}(\frac{1}{6})^2(\frac{5}{6})=\frac{5}{72}\\P(K=3) = (\frac{1}{6})^3=\frac{1}{216}\\E(x) = x\cdot (2\cdot \frac{25}{72} + 3\cdot\frac{5}{72}+10\cdot\frac{1}{216}) = \frac{205}{216}x$
设下注总筹码 $S = \sum x_i$ ,$E = h+\sum E(x_i)=(6-S)+S\cdot \frac{206}{216} = 6-S\cdot \frac{11}{216}$ ,单调递减。
######
J 立希坐地铁
并不是网格上所有的点都需要作为图的节点。我们只关心起点、终点以及换乘站。这些点是我们可能停下来、换乘或结束旅程的地方。在每个关键点,我们可能处于不同的线路/方向上。一共有 $6$ 种线路方向:
- 水平东行
- 水平西行
- 竖直南行
- 竖直北行
- 环线顺时针
- 环线逆时针
因此,对于每个关键点 $u$,我们建立 6 个图节点,表示“位于点 $u$ 且正处于/准备乘坐某方向的线路”。记为 $(u,dir)$ 。此外,为了处理换乘,对于每个换乘站 $u$ ,我们还要引入一个虚拟的站厅节点 $H$ 。
对于普通的行驶边,我将所有关键点按照它们所在的线路分组,在同一条线路上相邻的两个关键点 $u,v$ 之间连权值为 $2\times \text{距离}$ 的边。如果是单向线路,则连单向边;如果是双向线路,则分别建立对应的单向边。在换乘站,我们就先连一条到 $H$ 的权值为 $0$ 的边,再连一条从 $H$ 到具体的节点的权值为 $1$ 的边。
然后再图上跑 $\text{Dijkstra}$ ,初始 $6$ 个方向 $\text{dist}$ 均为 $0$ ,取终点处 $6$ 个方向的最小值即可。
constexpr ll INF = 4e18;
struct Pt {
int x, y;
bool tr;
};
void solve() {
int n, m;
cin >> n >> m;
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
vector<Pt> pts;
map<PII, int> pid;
auto get = [&](int x, int y) {
if (pid.find({x, y}) == pid.end()) {
pid[{x, y}] = pts.size();
pts.pb({x, y, false});
}
return pid[{x, y}];
};
int sid = get(sx, sy), eid = get(ex, ey);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
int id = get(u, v);
pts[id].tr = true;
}
int k = pts.size(), virt = 6 * k, tot = 7 * k;
vector<vector<PLL>> g(tot);
for (int i = 0; i < k; ++i) {
if (pts[i].tr) {
int vn = virt + i;
for (int d = 0; d < 6; ++d) {
g[i * 6 + d].pb({vn, 0});
g[vn].pb({i * 6 + d, 1});
}
}
}
vector<vector<PII>> rs(n + 1), cs(n + 1);
vector<vector<PLL>> rgs(n / 2 + 1);
for (int i = 0; i < k; ++i) {
rs[pts[i].x].pb({pts[i].y, i});
cs[pts[i].y].pb({pts[i].x, i});
int k = min({pts[i].x, n - pts[i].x + 1, pts[i].y, n - pts[i].y + 1});
ll s = n - 2 * k + 1;
ll pos = 0;
if (pts[i].x == k)
pos = pts[i].y - k;
else if (pts[i].y == n - k + 1)
pos = s + (pts[i].x - k);
else if (pts[i].x == n - k + 1)
pos = 2 * s + (n - k + 1 - pts[i].y);
else
pos = 3 * s + (n - k + 1 - pts[i].x);
rgs[k].pb({pos, i});
}
for (int i = 1; i <= n; ++i) {
sort(all(rs[i]));
for (int j = 0; j + 1 < rs[i].size(); ++j) {
int u = rs[i][j].se, v = rs[i][j + 1].se;
ll d = 2ll * (rs[i][j + 1].fi - rs[i][j].fi);
g[u * 6 + 0].pb({v * 6 + 0, d});
g[v * 6 + 1].pb({u * 6 + 1, d});
}
}
for (int i = 1; i <= n; ++i) {
sort(all(cs[i]));
for (int j = 0; j + 1 < cs[i].size(); ++j) {
int u = cs[i][j].se, v = cs[i][j + 1].se;
ll d = 2ll * (cs[i][j + 1].fi - cs[i][j].fi);
g[u * 6 + 2].pb({v * 6 + 2, d});
g[v * 6 + 3].pb({u * 6 + 3, d});
}
}
for (int k = 1; k <= n / 2; ++k) {
if (rgs[k].empty())
continue;
sort(all(rgs[k]));
ll len = 4LL * (n - 2 * k + 1);
int sz = rgs[k].size();
for (int i = 0; i < sz; ++i) {
int u = rgs[k][i].se;
int v = rgs[k][(i + 1) % sz].se;
ll d = (rgs[k][(i + 1) % sz].fi - rgs[k][i].fi + len) % len;
if (d == 0 && len > 0)
d = len;
g[u * 6 + 4].pb({v * 6 + 4, 2 * d});
g[v * 6 + 5].pb({u * 6 + 5, 2 * d});
}
}
priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
vector<ll> dist(tot, INF);
vector<int> par(tot, -1);
for (int d = 0; d < 6; ++d) {
dist[sid * 6 + d] = 0;
pq.push({0, sid * 6 + d});
}
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u])
continue;
for (auto &[v, w] : g[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
par[v] = u;
pq.push({dist[v], v});
}
}
}
ll ans = INF;
int edn = -1;
for (int d = 0; d < 6; ++d) {
if (dist[eid * 6 + d] < ans) {
ans = dist[eid * 6 + d];
edn = eid * 6 + d;
}
}
if (ans == INF) {
cout << "Impossible!" << endl;
return;
}
cout << ans << endl;
vector<int> path;
for (int u = edn; u != -1; u = par[u])
path.pb(u);
reverse(all(path));
string ss = "EWSNCI";
vector<pair<char, int>> segs;
int cd = path[0] % 6;
for (int i = 0; i < path.size(); ++i) {
if (path[i] >= virt) {
int u = path[i - 1] / 6;
segs.pb({ss[cd], u});
if (i + 1 < path.size())
cd = path[i + 1] % 6;
}
}
segs.pb({ss[cd], path.back() / 6});
cout << segs.size() << endl;
cout << sx << " " << sy << endl;
for (auto [u, v] : segs) {
cout << u << endl;
cout << pts[v].x << " " << pts[v].y << endl;
}
}
头文件
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;
using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
cout << fixed << setprecision(15);
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}