比赛链接
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;} 关键词：
凡注有"环球传媒网"或电头为"环球传媒网"的稿件，均为环球传媒网独家版权所有，未经许可不得转载或镜像；授权转载必须注明来源为"环球传媒网"，并保留"环球传媒网"的电头。