AtCoder ABC 250 總結

總體

連續(xù)若干次一樣的結果：30min 切前 4 題，剩下卡在 T5

這幾次卡在 T5 都是一次比一次接近，

什么 dp 前綴和打掛，精度被卡，能水過的題連水法都沒寫出來

確實是思維上的缺陷，畢竟 atc 全程都是緊張的

等下一場吧。。

前 4 題較易，不再贅述。

E- Prefix Equality

長度為 \(n\) 的數組 \(A,B\) ，每次詢問 \(A\) 的前 \(x\) 項和 \(B\) 的前 \(y\) 項組成的集合是否相同

• 即排序、去重后判斷相等

\(n,Q\le 2\times 10^5\) ， \(a_i,b_i\le 10^9\)

考場水法

機房其他大佬都這樣做。

大力莫隊，記錄一個變量 \(now\) ，兩個桶記錄

若移動指針時，把數加入兩個桶

若加入這個數，出現矛盾，則 \(now\leftarrow now-1\) ，若滿足條件，則 \(now\leftarrow now+1\)

• 矛盾：指一個數只在一個數組中出現

對于詢問，\(now=0\) 時是 Yes ，否則 No

• 若兩個前綴相同，則所有位置矛盾和滿足條件的貢獻抵消。最終 \(now=0\)

由于不保證 \(x<y\) ，所以復雜度也無法保證。

但是，大力出奇跡。

code

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 4e5 + 5; int n, a[N], b[N], c[N], le, Ti, t[N][2], Bsz, now; bool ans[N]; struct qry { int x, y, id; } q[N]; inline bool cmp(qry A, qry B) {if (A.x / Bsz != B.x / Bsz) return A.x / Bsz < B.x / Bsz;if ((A.x / Bsz) & 1) return A.y < B.y;return A.y > B.y; } inline void add(int x, int o) {if (!t[x][o]) {if (t[x][o ^ 1]) ++now;else --now;}++t[x][o]; } inline void del(int x, int o) {--t[x][o];if (!t[x][o]) {if (t[x][o ^ 1]) --now;else ++now;} } inline void solve() {int X = 0, Y = 0;for (int i = 1, qx, qy; i <= Ti; i++) {qx = q[i].x, qy = q[i].y;while (X < qx) add(a[++X], 0);while (X > qx) del(a[X--], 0);while (Y < qy) add(b[++Y], 1);while (Y > qy) del(b[Y--], 1);ans[q[i].id] = (now == 0);} } int main() {scanf("%d", &n);Bsz = sqrt(n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]), c[++le] = a[i];for (int i = 1; i <= n; i++) scanf("%d", &b[i]), c[++le] = b[i];sort(c + 1, c + le + 1);le = unique(c + 1, c + le + 1) - c - 1;for (int i = 1; i <= n; i++) {a[i] = lower_bound(c + 1, c + le + 1, a[i]) - c;b[i] = lower_bound(c + 1, c + le + 1, b[i]) - c;}scanf("%d", &Ti);for (int i = 1; i <= Ti; i++) scanf("%d%d", &q[i].x, &q[i].y), q[i].id = i;sort(q + 1, q + Ti + 1, cmp);solve();for (int i = 1; i <= Ti; i++) puts(ans[i] ? "Yes" : "No"); }

正解

part 1

首先明確(我考場也想到了)：對于每一個 \(x\)，滿足條件的 \(y\) 是在一個區(qū)間 \([L_x,R_x]\) 里的。

所以考慮求 \(L_x,R_x\) 。

離散化是自然的。

接著記錄 \(A\) 中元素在 \(B\) 中第一次出現位置 \(p\) ，即 \(p_{a_i}=\min\{j\mid b_j=a_i\}\)

設 \(S_i\) 為 \(A\) 前 \(i\) 項的集合，有 \(S_0=\varnothing\) 。可得

\[L_i=\max_{t\in S_i} p_t,R_i=\min_{t\in S_n-S_i} p_t-1 \]

其中 \(S-T=\{a\mid a\in S,a\notin T\}\)

可以用前綴最大值、后綴最小值 \(O(n)\) 計算，\(O(1)\) 回答詢問。

復雜度為離散化的復雜度 \(O(n\log n)\)

part 2

更具體地實現：記錄 \(add_i\) 表示 \(A_i\) 在 \(S_i\) 中是否第一次出現

\(L_i\) 可以直接求，求 \(R_i\) 需要注意：

如果 \(B\) 中有 \(A\) 中沒有的元素，若這個位置最小為 \(pos\) ，則 \(R\) 都要要小于 \(pos\)

可以記錄 \(suf_i\) 為后綴最小值

\[suf_i=\min_{t\in S_n-S_{i-1}} p_t-1 \]

從后往前掃，若 \(add_i=1\) ，則說明 \(a_i\notin S_{i-1}\) ，可用 \(p_{a_i}-1\) 更新 \(R_i\)

從前往后掃，通過 \(suf\) 數組和 \(pos\) 求出 \(R\) 數組

code

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 4e5 + 5; int n, a[N], b[N], c[N], le, Ti, L[N], R[N]; int pos[N], vis[N], add[N], mn[N], tmn; bool ans[N]; int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]), c[++le] = a[i];for (int i = 1; i <= n; i++) scanf("%d", &b[i]), c[++le] = b[i];sort(c + 1, c + le + 1);le = unique(c + 1, c + le + 1) - c - 1;for (int i = 1; i <= n; i++) {a[i] = lower_bound(c + 1, c + le + 1, a[i]) - c;b[i] = lower_bound(c + 1, c + le + 1, b[i]) - c;}for (int i = 1; i <= n; i++) if (!pos[b[i]]) pos[b[i]] = i;for (int i = 1; i <= n; i++) if (!pos[a[i]]) pos[a[i]] = n + 1;for (int i = 1; i <= n; i++) if (!vis[a[i]]) vis[a[i]] = 1, add[i] = 1;for (int i = 1; i <= n; i++) {L[i] = L[i - 1];if (add[i]) L[i] = max(L[i], pos[a[i]]);}mn[n + 1] = n + 1;for (int i = n; i; i--) {mn[i] = mn[i + 1];if (add[i]) mn[i] = min(mn[i], pos[a[i]]);}tmn = n + 1;for (int i = n; i; i--) if (!vis[b[i]]) tmn = min(tmn, i);for (int i = 1; i <= n; i++) {if (!add[i]) R[i] = R[i - 1];else R[i] = min(mn[i + 1], tmn) - 1;}scanf("%d", &Ti);for (int i = 1, x, y; i <= Ti; i++) {scanf("%d%d", &x, &y);puts(L[x] <= y && y <= R[x] ? "Yes" : "No");} }

F - One Fourth

一個 \(n\) 個點的凸多邊形，逆時針給出這 \(n\) 個點 \(P_i=(x_i,y_i)\) 。

設這個凸多邊形面積為 \(S\) ，現在要選出兩個不相鄰的點，

沿兩點所在直線將凸多邊形切成兩部分，

選出一部分，設其面積為 \(b\) ，求 \(\min 8\times|\dfrac{1}{4}S-b|\)

\(n\le 10^5\) ，\(|x_i|,|y_i|\le 4\times 10^8\)

sol

• 轉換所求：\(8\times|\dfrac{1}{4}S-b|=|2S-8b|=|2S-4\times 2b|\)

• 求面積：用向量叉乘，求得兩個向量所形成的平行四邊形面積，

  \[S=\dfrac{1}{2}\sum_{i=2}^N\overrightarrow{P_1P_{i-1}}\times\overrightarrow{P_1 P_i} \]

• 凸多邊形是一個環(huán)，此處定義點 \(N+i\) 為點 \(i\) ，即破環(huán)成鏈

• \(O(n^2)\) ：很顯然對于 \(p\) 枚舉 \(q=(p+1),(p+2),\cdots,(p+N-2)\) ，

  每次直接加上 \(p,q,(q+1)\) 圍成的三角形的面積，可以做到 \(n^2\)

• \(O(n)\) ：用到雙指針：對于每個 \(p\) ，若當前面積 \(now<\dfrac{S}{4}\) ，則 \(q\) 一直加，加上 \(p,q,(q+1)\) 的面積

  然后 \(p\) 后移，減去 \(p,(p+1),q\) 的面積。

• 實現時：可以不用真的破環(huán)成鏈。由于轉換，求面積時的 \(\dfrac{1}{2}\) 都可以消掉

code

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 1e5 + 5; int n; struct P {LL x, y;P(LL _x = 0, LL _y = 0) : x(_x), y(_y) { }P operator + (P A) { return P(x + A.x, y + A.y); }P operator - (P A) { return P(x - A.x, y - A.y); } } a[N]; LL sm, ans = 9e18, nw; inline LL mul(P A, P B) { return A.x * B.y - A.y * B.x; } // A is origin // vector AB and AC inline LL area(P A, P B, P C) { return abs(mul(B - A, C - A)); } int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y);for (int i = 3; i <= n; i++) sm += area(a[1], a[i - 1], a[i]);for (int i = 1, j = 2; i <= n; i++) {while (4 * nw < sm) {nw += area(a[i], a[j], a[j % n + 1]);j = j % n + 1;ans = min(ans, abs(sm - 4 * nw));}nw -= area(a[j], a[i], a[i % n + 1]);ans = min(ans, abs(sm - 4 * nw));}printf("%lld", ans); }

G - Stonks

作 \(n\) 天股票交易，初始有無限錢，第 \(i\) 天股票價格為 \(P_i\) ，一天進行以下操作之一

• 買進股票，花費 \(P_i\) 元
• 賣出股票，增加 \(P_i\)
• 什么也不做

求最大利潤

\(n\le 2\times 10^5\)

sol

反悔貪心，思路巧妙

遇到當前價格高于最低股票價時就賣掉，

如果之后有一個更高價格的呢，就買入此時賣出的，達到反悔的效果

即對于 \(a<b<c\) ，以 \(a\) 的價格買入，以 \(b\) 的價格貪心賣出，再以 \(b\) 的價格買入，\(c\) 的價格賣出

就相當于 \(a\) 的價格買入， \(c\) 的價格賣出，實現了反悔

用優(yōu)先隊列實現

code

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 2e5 + 5; int n; LL a[N], ans; priority_queue<LL, vector<LL>, greater<LL> > Q; int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);Q.push(a[1]);for (int i = 2; i <= n; i++) {if (Q.top() < a[i]) {ans += a[i] - Q.top();Q.pop(), Q.push(a[i]);}Q.push(a[i]);}printf("%lld", ans); }

Ex - Trespassing Takahashi

\(n\) 點 \(m\) 邊的無向圖，點 \(1,2,\cdots,K\) 為房子，第 \(i\) 條邊連接 \(a_i,b_i\) ，通過時間為 \(c_i\)

保證原圖是聯(lián)通的，無重邊、自環(huán)

\(Q\) 次詢問，第 \(i\) 次詢問 \(x_i,y_i,t_i\) ，問能否從房子 \(x_i\) 到房子 \(y_i\) ，移動過程中離開房子的時間不能大于 \(t_i\)

\(K\le n\le 2\times 10^5\) ，\(Q,m\le 2\times 10^5\) ， \(1\le t_1\le\cdots\le t_Q\le 10^{15}\) ， \(c_i\le 10^9\)

sol

另 \(d_i\) 為從點 \(i\) 到最近的房子的距離，對每條邊，另 \(c'_i=c_i+d_{a_i}+d_{b_i}\)

結論：答案為 Yes 當且僅當只用 \(c'_i\le t\) 的邊能從 \(x\) 到 \(y\)

證明如下：

首先，\(c'_i\) 表示必須經過邊 \(i\) 從一個房子到另一個房子的最短距離

如果不能只用 \(c'_i\le t\) 的邊從房子 \(x\) 到房子 \(y\) ，答案是否定的

另外，如果可以只用滿足 \(c'_i\le t\) 的路徑從 \(x\) 到 \(y\)

若 \(p_1,\cdots,p_k\) 為 \(x\) 到 \(y\) 路徑上的點，考慮路徑

\[p_1,(\text{Nearest house from }p_1),p_1, p_2,(\text{Nearest house from }p_2),p_2,\cdots,p_k \]

其中

\[(\text{Nearest house from }p_i),p_i, p_{i+1},(\text{Nearest house from }p_{i+1}) \]

之間的長度等于連接 \(p_i,p_{i+1}\) 的 \(c'\) 邊，是滿足條件的。

所以這次詢問的答案是 Yes

\(d_i\) 可以用有 \(K\) 個起點的 dijkstra 在 \(O(n\log n)\) 的時間復雜度內解決。

由于 \(t\) 單調不減，將所有 \(c'_i\) 排序，每次將滿足 \(c'_i\le t\) 的邊加入 DSU ，判斷 \(x,y\) 是否聯(lián)通即可

code

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 2e5 + 5; int n, m, lst[N], Ecnt, K, ff[N], vis[N], Ti; LL dis[N]; struct Ed { int to, nxt; LL qz; } e[N << 1]; struct Edge { int u, v; LL w; } ed[N]; inline void Ae(int fr, int go, int vl) {e[++Ecnt] = (Ed){ go, lst[fr], 1ll * vl }, lst[fr] = Ecnt; } int fd(int x) { return ff[x] == x ? x : ff[x] = fd(ff[x]); } priority_queue< pair<LL, int> > Q; inline bool cmp(Edge A, Edge B) {return A.w < B.w; } int main() {scanf("%d%d%d", &n, &m, &K);for (int i = 1; i <= n; i++) {dis[i] = 1e16;ff[i] = i;}for (int i = 1, u, v, w; i <= m; i++) {scanf("%d%d%d", &u, &v, &w);Ae(u, v, w), Ae(v, u, w);ed[i].u = u, ed[i].v = v, ed[i].w = w;}for (int i = 1; i <= K; i++) {dis[i] = 0;Q.push(make_pair(0, i));}while (!Q.empty()) {register int u = Q.top().second;Q.pop();if (vis[u]) continue;vis[u] = 1;for (int i = lst[u], v; i; i = e[i].nxt)if (dis[u] + e[i].qz < dis[v = e[i].to]) {dis[v] = dis[u] + e[i].qz;Q.push(make_pair(-dis[v], v));}}for (int i = 1; i <= m; i++) ed[i].w += dis[ed[i].u] + dis[ed[i].v];sort(ed + 1, ed + m + 1, cmp);scanf("%d", &Ti);for (int x, y, p, q, i = 1; Ti--; ) {register LL t;scanf("%d%d%lld", &x, &y, &t);while (i <= m && ed[i].w <= t) {p = fd(ed[i].u), q = fd(ed[i].v);if (p ^ q) ff[p] = q;i++;}puts(fd(x) == fd(y) ? "Yes" : "No");} }

總結

以上是生活随笔為你收集整理的AtCoder ABC 250 总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。