A.Who Ate the Cake?(思維)

題意

已知有三個嫌疑人，有兩個證人，每個證人可以指出其中一個嫌疑人不是罪犯，如果可以排除兩個嫌疑人來確定犯人，輸出犯人的身份，如果無法確定，輸出"-1"。

分析

如果輸入兩個人的編號相同，則無法確定犯人，如果不同，則$6?A?B$為犯人的編號。

代碼

#include <bits/stdc++.h>
using namespace std;void solve() {int a, b;cin >> a >> b;if (a == b) cout << -1 << endl;else cout << 6 - a - b << endl;
}
int main () {solve();return 0;
}

B.Piano 2(桶數組)

題意

給出一個包含$n$個數字的數組$A$以及一個包含$m$個數字的數組$B$，將$A$數組和$B$數組中的數字放入數組$C$中，并對放入的數字進行排序。

問：數組$C$中是否存在相鄰兩項，這兩項均屬于數組$A$（保證數組$A$和數組$B$中所有數字均是獨立的，即不會出現相同的數字）。

分析

使用標記數組對出現在$A$數組中的數字進行標記，然后將數組$A$和數組$B$中元素放入vector中并排序。

然后依次檢查vector中相鄰兩項是否均被標記，如果均被標記，輸出Yes，如果結束循環還是沒找到，輸出No。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5e2;int n, m,a[N], b[N], vis[N];
vector<int> C;void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];C.emplace_back(a[i]);vis[a[i]] = 1;}for (int i = 1; i <= m; i++) {cin >> b[i];C.emplace_back(b[i]);}sort(C.begin(), C.end());for (int i = 1; i < n + m; i++) {if (vis[C[i - 1]] == 1 && vis[C[i]] == 1) {cout << "Yes" << endl;return;}}cout << "No" << endl;
}
int main () {solve();return 0;
}

C.Bingo 2(模擬)

題意

給出一個$N\times N$的網格，將對這個網格執行$T$個回合操作，每個回合會選擇網格上的一個點（使用一個數字代表坐標）進行標記。

當滿足以下幾種條件之一，即獲得了勝利：

• 存在某一行上所有的格子均被標記

• 存在某一列上所有的格子均被標記

• 兩條對角線上所有的格子均被標記

問：最早執行多少個回合后，就贏下了這場比賽，如果結束所有操作后還未獲勝，輸出-1.

分析

為了便于處理，將輸入的數字$A_i$先減去$1$，然后通過$A_i/n,A_i$ % $n$的方式即可得到行號和列號（此時的行號和列號從$0$開始）。

然后考慮三個條件怎么進行判斷：

• 行和列：使用數組記錄每行每列被標記的節點數量

• 主對角線：主對角線元素行號和列號均相等，判斷當前網格的行號和列號，如果相同即進行標記

• 副對角線：副對角線的行列號之和為$n?1$，判斷當前網格的行列號之和是否為$n?1$，如果是就進行標記

每輪標記完成后，判斷是否滿足以上三個條件，如果滿足則輸出當前輪次，并結束程序。

如果循環正常結束，輸出-1。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5e2;int n, k, r[N], c[N], d[5], a[N];void solve() {cin >> n >> k;for (int i = 1; i <= k; i++) {cin >> a[i];a[i]--;int row = a[i] / n, colum = a[i] % n;r[row]++;c[colum]++;if (row == colum) d[0]++;if (row + colum == n - 1) d[1]++;if (r[row] == n || c[colum] == n || d[0] == n || d[1] == n) {cout << i << endl;return;}}cout << -1 << endl;
}
int main () {solve();return 0;
}

D.Intersecting Intervals(雙指針)

題意

給出$N$個區間$[l_i,r_i]$，問存在多少對區間相交。

分析

考慮相交比較困難，但考慮不相交就很容易了。

不難想到，只要是右邊界小于當前區間的左邊界的所有區間，那么必然不會與當前區間相交，此時不在乎這個區間的左邊界到底是多少，因此，可以使用兩個數字存儲左右邊界，并單獨對兩個數組排序。

然后從小往大遍歷左邊界數組，使用雙指針在右邊界數組中維護所有小于當前左邊界的數量，這個數量就是不會與當前區間相交的區間數量。

使用區間總對數減去每個區間不會相交的區間數量即可。

hint： 本題$n$較大，需要使用long long類型存儲答案。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5e2;int l[N], r[N]; void solve() {ll n;cin >> n;for (int i = 0; i < n; i++) {cin >> l[i] >> r[i];}sort(l, l + n);sort(r, r + n);int j = 0;ll ans = (n - 1) * n / 2;for (int i = 0; i < n; i++) {while (r[j] < l[i]) {j++;}ans -= j;}cout << ans << endl;
}
int main () {solve();return 0;
}

E.Guess the Sum(BFS)

題意

本題是一個交互題

給出一個數字$N$和區間$l,r$，題目隱藏了一個數組$A=(A_0,A_1,\dots ,A_{2^n?1}$，你的目標是知道$(A_l+A_{l+1}+\dots +A_r)$ % $100$的結果。

你可以按以下要求進行詢問：

• 選擇兩個非負整數$i,j$，需要保證$2^i(j+1)\le 2^N$，然后取$L=2^{i}j,R=2^i(j+1)?1$，將$i,j$告訴題目后，題目會返回$(A_L+A_{L+1}+\dots +A_R)$ % $100$的結果

你需要在保證詢問次數最小的情況下，找到要求的答案。

分析

由于可以通過查詢大區間減去小區間的方式獲得結果，因此直接通過倍增的方式進行查找不能保證操作次數最少。

例：當要查詢的區間為$2^k～2^{k+1}?2$時，通過查詢區間$2^k～2^{k+1}?1$減去區間$2^{k+1}?1～2^{k+1}?1$的方式只需要兩次詢問，而直接使用倍增進行詢問所需的次數無法保證兩次詢問即查詢完整個區間數字總和。

因此，可以將本題中所有可能的詢問包含的兩個點之間建雙向邊，那么問題就被轉化為了$L～R+1$之間的最短路(這里為什么取$R+1$呢？因為當移動到$R+1$時，才能保證第$R$個元素也被計算到了)，使用$BFS$搜索最短路，然后通過記錄的移動步數反推出最短路徑，將最短路徑上經過的所有路徑上的連接的點作為詢問，即可獲得最后的答案。

hint: 注意最優走法并不一定都是從左往右走的，可能通過先向右走一大步再回頭的方式完成，對于往回走的詢問，需要從結果中減去。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5e2;
int ask(int i, int j) {int sign = 1;if (i > j) {swap(i, j);sign *= -1;}int l = log2(j - i), r = i >> l;cout << "? " << l << ' ' << r << endl;cout.flush();int ans;cin >> ans;return sign * ans;
}
int n, l, r, dist[N];
vector<int> G[N];queue<int> Q;
void bfs(int start) {Q.push(start);dist[start] = 1;while (!Q.empty()) {int u = Q.front();Q.pop();for (auto v : G[u]) {if (dist[v] == 0) {dist[v] = dist[u] + 1;Q.push(v);}}}
}void solve() {cin >> n >> l >> r;r++;for (int i = 0; i <= n; i++) {for (int j = 0; j < (1 << n); j += (1 << i)) {G[j].push_back(j + (1 << i));G[j + (1 << i)].push_back(j);}}bfs(l);int ans = 0;while (r != l) {for (auto v : G[r]) {if (dist[r] == dist[v] + 1) {ans = (ans + ask(v, r) + 100) % 100;r = v;break;}}}cout << "! " << ans << endl;
}int main () {solve();return 0;
}

F.MST Query(并查集)

題意

給出一個包含$N$個點和$N?1$條邊的帶權無向連通圖，你將對這個圖進行$Q$次操作，每次的操作如下：

• 給出三個數字$u_i,v_i,w_i$，在點$u_i$和$v_i$之間連一條邊權為$w_i$的邊。

• 計算當前圖上的最小生成樹權值

分析

由于圖上邊權的范圍很小$(w_i\le 10)$，因此，可以維護權值為$1～10$的$10$張圖，每張圖上邊權相等。

將每次加邊操作視為往對應邊權(以及更高的邊權)的圖上建邊，如果建邊之前該圖上這兩個點不屬于同一個集合，那么當前邊建立后，最小生成樹的權值就會減少，減少多少呢？就得看最低多少權值，對應的圖上這兩個點才屬于同一個集合。

從當前權值開始遍歷到$10$，執行到第一個連通的權值對應的圖后，即可從維護的權值中減去這個遍歷到的權值，然后加上當前建邊的權值，即得到了最新的最小生成樹權值。

hint: 每次建邊時，需要在所有權值大于等于當前邊權的圖中建邊。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5e2;int n, q, f[15][N];int find(int w, int x) {return f[w][x] == x ? x : f[w][x] = find(w, f[w][x]);
}int merge(int u, int v, int w) {int fu = find(w, u),fv = find(w, v);if (fu == fv) return 1;f[w][fu] = fv;return 0;
}void solve() {cin >> n >> q;for (int i = 1; i <= n; i++) {for (int j = 0; j <= 10; j++) {f[j][i] = i;}}int sum = 0;for (int i = 1; i < n; i++) {int u, v, w;cin >> u >> v >> w;for (int j = w; j <= 10; j++) {merge(u, v, j);}sum += w;}while (q--) {int u, v, w;cin >> u >> v >> w;sum += w;for (int j = w; j <= 10; j++) {if (merge(u, v, j)) {sum -= j;break;}}cout << sum << endl;}
}int main () {solve();return 0;
}

賽后交流

在比賽結束后，會在交流群中給出比賽題解，同學們可以在賽后查看題解進行補題。

群號： 704572101，賽后大家可以一起交流做題思路，分享做題技巧，歡迎大家的加入。