基础算法随笔

目录

• 基础算法
  • 分治
    • 分治应用
      • P4423 [BJWC2011] 最小三角形
  • 搜索
    • 折半搜索
      • P10484 送礼物
      • P8906 [USACO22DEC] Breakdown P
    • 迭代加深
      • P2346 四子连棋
  • 倍增
    • 倍增应用
      • P1081 [NOIP 2012 提高组] 开车旅行
  • 贪心
    • 贪心应用
      • P1561 [USACO12JAN] Mountain Climbing S
      • P11323 【MX-S7-T1】「SMOI-R2」Happy Card
    • 反悔贪心
      • P1484 种树
      • AGC018 C Coins
      • P11268 【MX-S5-T2】买东西题
        • Sol 1

基础算法

世界中のすべての人間に好かれるなんて気持ち悪いよ

だけど一つになれない教室で　君と二人　手を繋いでいたいの

数の暴力に白旗をあげて　悪感情を殺してハイチーズ

ポストトゥルースの甘いディープキス　エロく歪んでるラブアンドピース

分治

幸せ自慢はダメ？ 不幸嘆いてもダメ？

図々しい言葉を避け 明るい未来のため

重要的思想。

分治应用

P4423 [BJWC2011] 最小三角形

大概是平面最近点对升级版。

\(\mathcal{O}(n^3)\) 暴力做法显然。考虑优化。

假设现在已经处理出左右两边的最小三角形，已得最小边长至少为 \(d\) ，考虑合并。

显然，到中轴线距离大于 \(d/2\) 的点是没用的，这大大降低了暴力的范围。

将有用的点排序，从小到大地暴力枚举每个点，显然如果枚举到的三个点有两个竖直/水平距离大于 \(d/2\)，构成的三角形是没有贡献的，这又大大降低了暴力的范围。

于是就能过了。

实际上枚举 \(20\) 个点即可，所以很快。时间复杂度是 \(\mathcal{O}(n\log n)\)，带一个比较大的常数。

code

const int N = 2e5 + 5;
const double inf = 1e200;int n;
struct node { double x, y; } a[N];double dist(node i, node j) {double x = abs(i.x - j.x), y = abs(i.y - j.y);return sqrt(x * x + y * y);
}bool cmpy(node a, node b) {return a.y < b.y;
} double solve(int l, int r) {if (r - l + 1 < 3) return inf;if (r - l + 1 == 3) return dist(a[l], a[l + 1]) + dist(a[l + 1], a[r]) + dist(a[l], a[r]);int mid = (l + r) >> 1;double d = min(solve(l, mid), solve(mid + 1, r));vector<node> vec;rep(i, l, r) if (abs(a[i].x - a[mid].x) <= d / 2.0) vec.push_back(a[i]);if (vec.size() == 0) return d;sort(vec.begin(), vec.end(), cmpy);rep(i, 0, vec.size() - 1) rep(j, i + 1, vec.size() - 1) {if (abs(vec[i].y - vec[j].y) > d / 2) break; rep(k, j + 1, vec.size() - 1) {if (i != j && i != k && j != k) {d = min(d, dist(vec[i], vec[j]) + dist(vec[i], vec[k]) + dist(vec[j], vec[k]));}}}return d;
}bool cmp(node a, node b) {return a.x < b.x;
}int main() {read(n);rep(i, 1, n) read(a[i].x, a[i].y);sort(a + 1, a + n + 1, cmp);printf("%0.6lf", solve(1, n));return 0;
}// START AT 2025 / 07 / 07 09 : 13 : 37

搜索

さんはい 「この世には息もできない人が沢山いるんですよ」

さんはい 「この世には息もできない人が沢山いるんですよ」

あちらが立てば　こちらが立たず 譲り　奪い　守り　行き違い

地雷原で立ち止まり 大人しく犬になるんだワン

大概很多题目都能用搜索拿点分，是很有用的算法。

折半搜索

先搜一半，然后根据另一半查找。

P10484 送礼物

折半搜索板子题。

将礼物分为均分两类，对第一类枚举所有情况，统计一下。

然后第二类二分查找。

用 set T了，最好还是卡卡常

code

const int N = 50;int w, n, g[N];
i64 s[1 << 24], cnt;
i64 ans;void dfs(int dep, int goal, int k, i64 sum) {if (dep == goal + 1) {if (k == 1) s[++cnt] = sum;else {int pos = upper_bound(s + 1, s + cnt + 1, w - sum) - s - 1;ans = max(ans, s[pos] + sum);}return;}dfs(dep + 1, goal, k, sum);if (sum + g[dep] > w) return;dfs(dep + 1, goal, k, sum + g[dep]);
}int main() {read(w, n);rep(i, 1, n) read(g[i]);int mid = (1 + n) >> 1;dfs(1, mid, 1, 0);sort(s + 1, s + cnt);dfs(mid + 1, n, 2, 0);write(ans);return 0;
}

P8906 [USACO22DEC] Breakdown P

不容易想到折半搜索吧。我觉得怎么想都不自然

倒序处理，删边变加边，比较好想。考虑处理最短路径。

正序倒序最多分别分到 \(k = 4\)。\(k = 1\) 容易处理。

\(k = 2\) 时考虑全局维护 \(f(i, j)\) ，表示 \(i \rightarrow j\) 经过两条路的最短路径。

这是好处理的也不是很显然，因为加边 \((u, v)\) 只与 \(f(u, i), f(i, v), i\in V\) 有关。\(\mathcal{O}(n)\) 地处理。

\[f(u, i) = w(u, v) + w(v,i)\\ f(v, i) = w(i, u) + w(u, v) \]

则 \(1\rightarrow x\) 的路径长为 \(f(1, x)\)，\(n\) 同理。

然后 \(k = 3\)，\(k = 4\) 同理。对于 \(x\) 来说，\(1\rightarrow x\) 经过 \(3\) 条路径的长最小为 \(\min\{f(1, i) + w(i, x)\}\)。

\(k = 4\) 把 \(w(i, x)\) 换为 \(f(i, x)\) 即可。

处理完合并即可。

时间复杂度比较神奇吧……

code

const int N = 305;int n, k, e[N][N], u[N * N], v[N * N], ans[N * N];struct node {int st, e[N][N], f[N][N], h[N], k;void init() {memset(e, 0x3f, sizeof(e));memset(f, 0x3f, sizeof(f));memset(h, 0x3f, sizeof(h));if (!k) h[st] = 0;}void add(int u, int v, int w) {e[u][v] = w;if (!k) return;if (k == 1) {if (u == st) h[v] = w;return;}rep(i, 1, n) f[u][i] = min(e[u][v] + e[v][i], f[u][i]);rep(i, 1, n) f[i][v] = min(e[i][u] + e[u][v], f[i][v]);if (k == 2) {rep(i, 1, n) h[i] = min(f[st][i], h[i]);return;}auto p = (k == 3 ? e : f);if (u == st) {rep(i, 1, n) rep(j, 1, n) h[j] = min(f[st][i] + p[i][j], h[j]);} else {rep(i, 1, n) h[u] = min(h[u], f[st][i] + p[i][u]),h[v] = min(h[v], f[st][i] + p[i][v]),h[i] = min(h[i], f[st][u] + p[u][i]),h[i] = min(h[i], f[st][v] + p[v][i]);}}
} _1, _n;int main() {read(n, k);rep(i, 1, n) rep(j, 1, n) read(e[i][j]);rep(i, 1, n * n) read(u[i], v[i]);_1.st = 1, _n.st = n;_1.k = k / 2, _n.k = k - k / 2;_1.init(); _n.init();per(i, n * n, 1) {ans[i] = 0x3f3f3f3f;rep(j, 1, n) ans[i] = min(_1.h[j] + _n.h[j], ans[i]);_1.add(u[i], v[i], e[u[i]][v[i]]);_n.add(v[i], u[i], e[u[i]][v[i]]);}rep(i, 1, n * n) {if (ans[i] == 0x3f3f3f3f) write(-1), puts("");else write(ans[i]), puts("");} return 0;
}

迭代加深

限制 DFS 层数的搜索。适用于一些答案不会太大的搜索。

P2346 四子连棋

首先猜测答案不会太大，然后考虑 IDDFS。

剩下的就很基础了。

存在不用动的特殊情况

考虑特殊情况应该也是做题的一环

code

int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
struct node {int x, y;
} a, b;
char s[4][4];bool check(char s[4][4]) {rep(i, 0, 3) if (s[i][0] == s[i][1] && s[i][1] == s[i][2] && s[i][2] == s[i][3]) return 1;rep(i, 0, 3) if (s[0][i] == s[1][i] && s[1][i] == s[2][i] && s[2][i] == s[3][i]) return 1;if (s[1][1] == s[2][2] && s[0][0] == s[1][1] && s[2][2] == s[3][3]) return 1;if (s[0][3] == s[1][2] && s[1][2] == s[2][1] && s[2][1] == s[3][0]) return 1;return 0;
}bool check(int x, int y) {return x >= 0 && x <= 3 && y >= 0 && y <= 3;
}bool dfs(node a, node b, int k, int dep, int goal, char s[4][4]) {if (dep == goal + 1) return check(s);rep(i, 0, 3) {int nx = a.x + dx[i], ny = a.y + dy[i];if (!check(nx, ny)) continue;if (s[nx][ny] == 'O') continue;if (k == 0 && s[nx][ny] == 'B') continue;if (k == 1 && s[nx][ny] == 'W') continue;if (k == 0) s[nx][ny] = 'O', s[a.x][a.y] = 'W';else s[nx][ny] = 'O', s[a.x][a.y] = 'B';if (dfs({nx, ny}, b, 1 - k, dep + 1, goal, s)) return 1;if (k == 0) s[a.x][a.y] = 'O', s[nx][ny] = 'W';else s[a.x][a.y] = 'O', s[nx][ny] = 'B';}rep(i, 0, 3) {int nx = b.x + dx[i], ny = b.y + dy[i];if (!check(nx, ny)) continue;if (s[nx][ny] == 'O') continue;if (k == 0 && s[nx][ny] == 'B') continue;if (k == 1 && s[nx][ny] == 'W') continue;if (k == 0) s[nx][ny] = 'O', s[b.x][b.y] = 'W';else s[nx][ny] = 'O', s[b.x][b.y] = 'B';if (dfs(a, {nx, ny}, 1 - k, dep + 1, goal, s)) return 1;if (k == 0) s[b.x][b.y] = 'O', s[nx][ny] = 'W';else s[b.x][b.y] = 'O', s[nx][ny] = 'B';}return 0;}int main() {rep(i, 0, 3) cin >> s[i];  bool flag = 0;rep(i, 0, 3) rep(j, 0, 3) if (s[i][j] == 'O') {if (!flag) a = {i, j}, flag = 1;else b = {i, j};}if (check(s)) return cout << 0 << endl, 0;for(int i = 1; ; i++) if (dfs(a, b, 0, 1, i, s) || dfs(a, b, 1, 1, i, s)) return cout << i << endl, 0;return 0;
}

倍增

ノンブレス　ノンブレス ノンブレス ノンブレス・オブリージュ

I love you

息苦しい日々の水面下 ゆらゆらと煙る血の花

以成倍增长的方式处理问题。与二进制划分有关。

倍增应用

P1081 [NOIP 2012 提高组] 开车旅行

处理小A小B从某个城市出发下一个目的地是简单的。

因此可以用倍增处理出从某个城市出发 \(x\) 步的目的地。

时间复杂度 \(\mathcal{O}(n\log n)\)。

code

const int N = 1e5 + 5;
const int inf = 2e9 + 1;struct node {int id, h;node(int id = 0, int h = 0) : id(id), h(h) {}friend bool operator< (node a, node b) { return a.h < b.h; }
} a[N];
multiset<node> s;
int n, x0, ga[N], gb[N];
int m, S[N], x[N];
i64 f[20][N][2], da[20][N][2], db[20][N][2], la, lb;void init() {rep(i, 0, 1) s.insert(node(0, -inf)), s.insert(node(0, inf));per(i, n, 1) {node x = a[i];s.insert(x);auto it = s.find(x), _it = it;node pre = *--it, _pre = *--it;node Next = *++_it, _Next = *++_it;if (abs(pre.h - x.h) > abs(Next.h - x.h)) {gb[i] = Next.id;if (abs(pre.h - x.h) > abs(_Next.h - x.h)) ga[i] = _Next.id;else ga[i] = pre.id;} else {gb[i] = pre.id;if (abs(Next.h - x.h) < abs(_pre.h - x.h)) ga[i] = Next.id;else ga[i] = _pre.id;}}
}void query(int s, int x) {la = 0, lb = 0;per(i, 19, 0) {if (f[i][s][0] == 0) continue;if (la + da[i][s][0] + lb + db[i][s][0] <= x) {la += da[i][s][0], lb += db[i][s][0];s = f[i][s][0];}}
}int main() {read(n);rep(i, 1, n) a[i].id = i, read(a[i].h);read(x0, m);rep(i, 1, m) read(S[i], x[i]);init();rep(i, 1, n) {f[0][i][0] = ga[i];f[0][i][1] = gb[i];da[0][i][0] = abs(a[ga[i]].h - a[i].h);db[0][i][1] = abs(a[gb[i]].h - a[i].h);}rep(i, 1, 19) rep(j, 1, n) rep(k, 0, 1) {if (i == 1) {int mid = f[i - 1][j][k];f[i][j][k] = f[i - 1][mid][1 - k];da[i][j][k] = da[i - 1][j][k] + da[i - 1][mid][1 - k];db[i][j][k] = db[i - 1][j][k] + db[i - 1][mid][1 - k];} else {int mid = f[i - 1][j][k];f[i][j][k] = f[i - 1][mid][k];da[i][j][k] = da[i - 1][j][k] + da[i - 1][mid][k];db[i][j][k] = db[i - 1][j][k] + db[i - 1][mid][k];}}double ans = 1e200;bool flag = 1;int p = 0;rep(i, 1, n) {query(i, x0);if (lb == 0) continue;if (ans > la * 1.0 / lb) {ans = la * 1.0 / lb;p = i;flag = 0;}}if (flag) {auto it = s.rbegin(); it++, it++;write((*it).id); puts("");} else write(p), puts("");rep(i, 1, m) {query(S[i], x[i]);write(la); putchar(' '); write(lb); puts("");}return 0;
}

贪心

自己中の光線銃　乱射する　強者のナンセンス

オートクチュールで作る　殺しのライセンス

分断を生んじゃった椅子取りゲーム　無痛分娩で授かるベイブ

壮大な内輪ノリを歴史と呼ぶ

选取局部最优解达到全局最优解的算法。

贪心的正确性需要证明，有如下证明方法：

1. 微扰
2. 范围缩放
3. 决策包容
4. 反证
5. 数学归纳

贪心应用

P1561 [USACO12JAN] Mountain Climbing S

是一道普通贪心题。

贪心策略是使有牛下山时尽可能使山上有牛。

需要将牛分为 \(U(i) \ge D(i)\) 和 \(U(i) \lt D(i)\) 两种情况，让第二类牛先上能满足贪心。

其他比较简单。时间复杂度 \(\mathcal{O}(n)\)。

code

const int N = 2.5e4 + 5;struct node { int up, dw; } a[N];
int n, ut[N], dt[N];bool cmp(node a, node b) {if (a.up < a.dw) {if (b.up < b.dw) return a.up < b.up;else return 1;} else {if (b.up < b.dw) return 0;else return a.dw > b.dw;}
}int main() {read(n);rep(i, 1, n) read(a[i].up, a[i].dw);sort(a + 1, a + n + 1, cmp);rep(i, 1, n) ut[i] = ut[i - 1] + a[i].up;rep(i, 1, n) dt[i] = max(dt[i - 1], ut[i]) + a[i].dw;write(dt[n]);return 0;
}

P11323 【MX-S7-T1】「SMOI-R2」Happy Card

\(\color{#39C5BB}{[EASY]}\)

需要观察到“炸”是三带一，即三张相同的牌可以带任意一张牌。

贪心地尽可能出三带一是对的，这点在模拟出牌后即可发现。

然后将牌分成 \(3\) 个一组，\(2\) 个一组，单独一组，分别讨论答案就好了。

code

const int N = 3e5 + 5;int T, n, v[N];
i64 cnt[4], ans;void init() {cnt[1] = cnt[2] = cnt[3] = 0; ans = 0;
}void solve() {read(n); init();rep(i, 1, n) read(v[i]);rep(i, 1, n) {cnt[3] += v[i] / 3;if (v[i] % 3) cnt[v[i] % 3]++;}if (cnt[3] <= cnt[1]) return write(cnt[3] + (cnt[1] - cnt[3]) + cnt[2], '\n'), void();if (cnt[3] - cnt[1] <= 2 * cnt[2]) return write(cnt[3] + (2 * cnt[2] - (cnt[3] - cnt[1]) + 1) / 2, '\n'), void();ans += cnt[2] * 2 + cnt[1];cnt[3] -= (2 * cnt[2] + cnt[1]);ans += (cnt[3] / 4) * 3; cnt[3] %= 4;if (cnt[3] == 3) ans += 3;else if (cnt[3] == 2 || cnt[3] == 1) ans += 2;write(ans, '\n');
}int main() {read(T);while (T--) solve();return 0;
}

反悔贪心

不需要选最优解，从一个较劣的情况变为最优解。

P1484 种树

反悔贪心板子。

先贪心选最大，然后做一个用于反悔的坑。

变成链表上操作，方便模拟题意。

时间复杂度 \(\mathcal{O}(n\log n)\)。

code

const int N = 6e5 + 5;int n, k, a[N];
int pre[N], Next[N];
priority_queue<pii> que;
bool vis[N];
i64 ans;int main() {read(n, k);rep(i, 1, n) read(a[i]);rep(i, 2, n) pre[i] = i - 1;rep(i, 1, n - 1) Next[i] = i + 1;rep(i, 1, n) que.push({a[i], i});while (k) {while (vis[que.top().second]) que.pop();int val = que.top().first, pos = que.top().second;if (val < 0) break;int pval = a[pre[pos]], nval = a[Next[pos]];a[++n] = pval + nval - val; que.push({a[n], n});ans += val, vis[pos] = 1, vis[pre[pos]] = 1, vis[Next[pos]] = 1;Next[pre[pre[pos]]] = n, pre[n] = pre[pre[pos]];Next[n] = Next[Next[pos]], pre[Next[Next[pos]]] = n; k--;}write(ans);return 0;
}

AGC018 C Coins

开始随便选，然后交换即可。

用六个堆维护每个人换成另外两种币的收益。

显然会有两两互换或三人互换的情况。容易证明多人互换的情况可以用前两种情况表示。

容易证明时间复杂度是 \(\mathcal{O}(n\log n)\)。code。

P11268 【MX-S5-T2】买东西题

Sol 1

50 pts 简单，考虑每个优惠券会对那些商品起作用。

发现作用区间为一段后缀，作用形如替换降价价格，考虑用线段树计算答案。

首先将优惠券按限制从大到小排序。然后对于每个优惠券，令它对它起作用区间内降价最少的替换，这样一定不劣。

因为后缀只会变长，这样处理出了局部最优解。

我的错误

考场上觉得需要按降价对优惠券进行排序。

一个很典的问题，局部最优解不是全局最优解。

因为把后面的位置占了，有后效性，而上面的没有。

code

const int N = 1e6 + 5;struct Node { int a, b; } a[N], b[N];
int n, m, c[N], d[N], tr[N << 2];
i64 ans;void up(int rt) { tr[rt] = d[tr[ls]] > d[tr[rs]] ? tr[rs] : tr[ls]; }void build(int rt, int l, int r) {if (l == r) return tr[rt] = l, void();int mid = (l + r) >> 1;build(ls, l, mid), build(rs, mid + 1, r);up(rt);
}void update(int rt, int l, int r, int p, int v) {if (l == r) return d[p] = v, void();int mid = (l + r) >> 1;if (p <= mid) update(ls, l, mid, p, v);else update(rs, mid + 1, r, p, v);up(rt);
}int query(int rt, int l, int r, int L, int R) {if (L <= l && r <= R) return tr[rt];int mid = (l + r) >> 1, pos, val = 1e9 + 5;if (L <= mid) {int p = query(ls, l, mid, L, R);if (d[p] < val) pos = p, val = d[p];}if (mid < R) {int p = query(rs, mid + 1, r, L, R);if (d[p] < val) pos = p;}return pos;
}int main() {read(n, m);rep(i, 1, n) read(a[i].a, a[i].b);rep(i, 1, m) read(b[i].a, b[i].b);sort(a + 1, a + n + 1, [&](Node a, Node b) { return a.a < b.a; });sort(b + 1, b + m + 1, [&](Node a, Node b) { return a.a > b.a; });rep(i, 1, n) c[i] = a[i].a, d[i] = a[i].a - a[i].b;build(1, 1, n);rep(i, 1, m) {int l = lower_bound(c + 1, c + n + 1, b[i].a) - c;if (l > n) continue;int p = query(1, 1, n, l, n);if (d[p] < b[i].b) update(1, 1, n, p, b[i].b);}rep(i, 1, n) ans += a[i].a - d[i];write(ans);return 0;
}