比賽鏈接
A代碼#include using namespace std;using ll = long long;bool solve() { int n; cin >> n; int cnt = 0; for (int i = 1;i <= n;i++) { int a, b; cin >> a >> b; if (a > b) cnt++; } cout << cnt << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} #include using namespace std;using ll = long long;char dt[4][4];bool solve() { for (int i = 1;i <= 3;i++) for (int j = 1;j <= 3;j++) cin >> dt[i][j]; for (int i = 1;i <= 3;i++) { if (dt[i][1] == ".") continue; bool ok = 1; for (int j = 1;j <= 3;j++) ok &= dt[i][1] == dt[i][j]; if (ok) { cout << dt[i][1] << "\n"; return true; } } for (int j = 1;j <= 3;j++) { if (dt[1][j] == ".") continue; bool ok = 1; for (int i = 1;i <= 3;i++) ok &= dt[1][j] == dt[i][j]; if (ok) { cout << dt[1][j] << "\n"; return true; } } if (dt[1][1] != ".") { bool ok = 1; for (int i = 1;i <= 3;i++) ok &= dt[1][1] == dt[i][i]; if (ok) { cout << dt[1][1] << "\n"; return true; } } if (dt[1][3] != ".") { bool ok = 1; for (int i = 1;i <= 3;i++) ok &= dt[1][3] == dt[i][3 - i + 1]; if (ok) { cout << dt[1][3] << "\n"; return true; } } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "DRAW" << "\n"; } return 0;} #include using namespace std;using ll = long long;pair res[200007];bool solve() { int n, m, h; cin >> n >> m >> h; for (int i = 1;i <= n;i++) { priority_queue, greater> pq; for (int j = 1;j <= m;j++) { int x; cin >> x; pq.push(x); } int sum = 0; int point = 0; ll penalty = 0; while (pq.size()) { int t = pq.top(); pq.pop(); if (sum + t > h) break; sum += t; point++; penalty += sum; } res[i] = { point,penalty }; } auto tar = res[1]; auto cmp = [&](pair a, pair b) {return a.first == b.first ? a.secondb.first;}; sort(res + 1, res + n + 1, cmp); int id = lower_bound(res + 1, res + n + 1, tar, cmp) - res; cout << id << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} #include using namespace std;using ll = long long;int y[200007] = { (int)2e9 };bool solve() { int n; double d, h; cin >> n >> d >> h; for (int i = 1;i <= n;i++) cin >> y[i]; sort(y + 1, y + n + 1, greater()); double ans = 0; for (int i = 1;i <= n;i++) { double delta = min(h, 0.0 + y[i - 1] - y[i]); ans += (2 - delta / h) * d * delta / 2; } cout << fixed << setprecision(6) << ans << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} 給定一個 \(n\) ，問是否存在 \(k \geq 2 ,s \geq 2\) ，使得 \(\displaystyle n = \sum_{i=0}^s k^i\) 。
題解方法一知識點：數學，枚舉。
(資料圖片僅供參考)
實際上，\(\displaystyle k^s < \sum_{i=0}^s k^i < (k+1)^{s}\) ，因此一定有 \(\displaystyle\left\lfloor \sqrt[s]{\sum_{i=0}^s k^i} \right\rfloor = k\) 。
因此，我們枚舉 \(s\) ，令 \(k = \left\lfloor \sqrt[s]{n} \right\rfloor\) ，然后驗證這一對 \(s,k\) 。若 \(n\) 可行，那么一定有 \(\displaystyle \sum_{i=0}^s k^i = n\) 。
其中開根號用的是 pow，這個函數精度很差，但是這里是沒有問題的，因為上下界都離得很遠。
時間復雜度 \(O(60)\)
空間復雜度 \(O(1)\)
方法二知識點：數學，二分，枚舉。
注意到， \(s\) 不會太大，最大只可能 \(60\) ，考慮枚舉 \(s\) 。
對于一個 \(s\) ，由于 \(\displaystyle \sum_{i=0}^s k^i\) 是關于 \(k\) 單調的，我們可以二分 \(k\) ，找到使得 \(\displaystyle \sum_{i=0}^s k^i\) 小于等于 \(n\) 的最后一個 \(k\) ，隨后驗證這個 \(k\) 是否是答案即可。
注意到， \(k\) 也不會超過 \(10^9\) ，這個結論能降低常數。
時間復雜度 \(O(60 \times \log 10^9)\)
空間復雜度 \(O(1)\)
方法三知識點：數學，二分，枚舉。
對于 \(s \geq 3\) 的情況， \(k\) 不會超過 \(10^6\) ，因此可以枚舉 \(k \leq 10^6\) ，對每個 \(k\) 預處理出 \(s \in[3,60]\) 的所有答案。
對于 \(s = 2\) 的情況，和方法一一樣直接二分即可。
時間復雜度 \(\displaystyle O\left( \left(\sum_{k=2}^{10^6}\log_k 10^{18}\right) \cdot \log \left(\sum_{k=2}^{10^6}\log_k 10^{18}\right) + \log 10^9 \right)\)
空間復雜度 \(\displaystyle O\left(\sum_{k=2}^{10^6}\log_k 10^{18}\right)\)
代碼方法一#include using namespace std;using ll = long long;using i128 = __int128_t;i128 qpow(i128 a, ll k) { i128 ans = 1; while (k) { if (k & 1) ans *= a; k >>= 1; a *= a; } return ans;}bool solve() { ll n; cin >> n; for (int i = 2, k;(k = pow(n, 1.0 / i)) >= 2;i++) { i128 res = (1 - qpow(k, i + 1)) / (1 - k); if (res == n) { cout << "YES" << "\n"; return true; } } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;} #include using namespace std;using ll = long long;const ll INF = 2e18;ll calc(int x, int s) { ll sum = 0; __int128_t mul = 1; for (int i = 0;i <= s;i++) { if (sum + mul > INF) return INF; sum += mul; mul *= x; } return sum;}bool solve() { ll n; cin >> n; for (int i = 2;i <= 60;i++) { int l = 2, r = 1e9; while (l <= r) { int mid = l + r >> 1; if (calc(mid, i) <= n) l = mid + 1; else r = mid - 1; } if (r >= 2 && calc(r, i) == n) { cout << "YES" << "\n"; return true; } } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;} #include using namespace std;using ll = long long;const ll INF = 1e18;set st;void init() { for (int i = 2;i <= 1000000;i++) { ll sum = 1 + i + 1LL * i * i; while (1 + (__int128_t)sum * i <= INF) { sum = 1 + sum * i; st.insert(sum); } }}ll calc(int x) { return 1 + x + 1LL * x * x;}bool solve() { ll n; cin >> n; if (st.count(n)) { cout << "YES" << "\n"; return true; } int l = 2, r = 1e9; while (l <= r) { int mid = l + r >> 1; if (calc(mid) <= n) l = mid + 1; else r = mid - 1; } if (r >= 2 && calc(r) == n) { cout << "YES" << "\n"; return true; } return false;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; init(); while (t--) { if (!solve()) cout << "NO" << "\n"; } return 0;} 房間里有 \(n\) 個物品，每個物品的種類為 \(a_i\) 。這些物品中，有一個是模仿者偽裝的。
現在可以進行一場最多 \(5\) 輪的實驗去找出它，每一輪按順序發生如下事件：
記錄當前房間內的所有物品的種類?？芍赋鲆粋€物品確定是偽裝的，則試驗結束。但這個操作只能執行一次，若不確定，則要做下一步操作。選出一些物品移出房間（可以不選，但模仿者始終不會被移出房間）并離開房間。隨后房間里的物品會被打亂，模仿者也可以轉換成別的物品（即使房間里不存在的物品）。進入房間，繼續下一輪。模仿者可能不轉變，但最多保持兩輪是同一個類型的物品。給出操作，找到模仿者。
題解知識點：枚舉。
一開始可以不移出物品，這樣若模仿者發生變化，則最多兩輪一定有一個類型的物品多了一個。
移出除了多出來物品的類型以外類型的所有物品。
剩下的一定是包括模仿者的同一類型的物品，再最多不超過一輪，一定會出現一個不同類型的物品，就是模仿者。
時間復雜度 \(O(n)\)
空間復雜度 \(O(n)\)
代碼#include using namespace std;using ll = long long;int n;int a[207];int cnt1[10], cnt2[10];void query(const vector &del) { cout << "- " << del.size() << " "; for (auto x : del) cout << x << " "; cout << endl; n -= del.size(); for (int i = 1;i <= n;i++) cin >> a[i];}void answer(int x) { cout << "! " << x << endl;}bool solve() { for (int i = 1;i <= 9;i++) cnt1[i] = cnt2[i] = 0; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i], cnt1[a[i]]++; query({}); for (int i = 1;i <= n;i++) cnt2[a[i]]++; int type = 0; for (int i = 1;i <= 9;i++) { if (cnt1[i] < cnt2[i]) { type = i; break; } } if (!type) { for (int i = 1;i <= 9;i++) cnt2[i] = 0; query({}); for (int i = 1;i <= n;i++) cnt2[a[i]]++; for (int i = 1;i <= 9;i++) { if (cnt1[i] < cnt2[i]) { type = i; break; } } } vector del; for (int i = 1;i <= n;i++) if (a[i] != type) del.push_back(i); query(del); bool ok = 0; for (int i = 1;i <= n;i++) { if (a[i] != type) { answer(i); ok = 1; break; } } if (!ok) { query({}); for (int i = 1;i <= n;i++) { if (a[i] != type) { answer(i); ok = 1; break; } } } return true;}int main() { //std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} 有 \(n\) 種癥狀和 \(m\) 個藥品，癥狀的情況通過一個長為 \(n\) 的 \(01\) 串給出。
每種藥品治療效果是可以使特定的一些癥狀消失，但副作用是使得特定的癥狀出現。
每種藥有一個療程 \(d\) ，療程之內不允許使用其他藥。
現在給出初始癥狀情況，問最少需要多少天才能使得癥狀全部消失。
題解知識點：最短路，狀壓dp，拓撲序dp。
考慮狀壓，將癥狀壓縮為一個整數。
隨后，我們將 \(2^n\) 種癥狀情況看作點， \(m\) 種藥看作邊。顯然，每個點都可以有 \(m\) 條出邊。
假設當前的癥狀是 \(st\) ，將要使用的藥品的效果是 \(e\) ，副作用是 \(se\) ，那么使用后的癥狀為 (st & ~e) | se，這樣就構建了一條邊，權值為療程時間。
問題就變成，從初始狀態到 \(0\) 狀態的最短路，直接跑最短路即可。
求最短路的本質就是在最短路圖這個DAG上進行拓撲序dp，因此一些dp可以考慮抽象成圖的形式跑最短路。
時間復雜度 \(O(m2^n \log (m2^n))\)
空間復雜度 \(O(2^n + m)\)
代碼#include using namespace std;using ll = long long;int n, m;int d[1007], e[1007], se[1007];bool vis[1 << 10 + 1];int dis[1 << 10 + 1];struct node { int v, w; friend bool operator<(const node &a, const node &b) { return a.w > b.w; }};priority_queue pq;void dijkstra(int st) { for (int i = 0;i < (1 << n);i++) dis[i] = 1e9, vis[i] = 0; dis[st] = 0; pq.push({ st,0 }); while (!pq.empty()) { int u = pq.top().v; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (int i = 1;i <= m;i++) { int v = (u & ~e[i]) | se[i]; int w = d[i]; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.push({ v,dis[v] }); } } }}bool solve() { cin >> n >> m; int st = 0; for (int i = 0;i < n;i++) { char ch; cin >> ch; st |= (ch == "1") << i; } for (int i = 1;i <= m;i++) { cin >> d[i]; e[i] = 0, se[i] = 0; for (int j = 0;j < n;j++) { char ch; cin >> ch; e[i] |= (ch == "1") << j; } for (int j = 0;j < n;j++) { char ch; cin >> ch; se[i] |= (ch == "1") << j; } } dijkstra(st); cout << (dis[0] >= 1e9 ? -1 : dis[0]) << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} 關鍵詞：
凡注有"環球傳媒網"或電頭為"環球傳媒網"的稿件，均為環球傳媒網獨家版權所有，未經許可不得轉載或鏡像；授權轉載必須注明來源為"環球傳媒網"，并保留"環球傳媒網"的電頭。