比赛链接

A

代码

#include <bits/stdc++.h>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;}

B

代码

#include <bits/stdc++.h>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;}

C

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; pair<int, ll> res[200007];bool solve() {    int n, m, h;    cin >> n >> m >> h;    for (int i = 1;i <= n;i++) {        priority_queue<int, vector<int>, greater<int>> 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<int, ll> a, pair<int, ll> b) {return a.first == b.first ? a.second<b.second : a.first>b.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;}

D

代码

#include <bits/stdc++.h>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<int>());     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;}

E

题意

给定一个 $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 <bits/stdc++.h>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 <bits/stdc++.h>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 <bits/stdc++.h>using namespace std;using ll = long long; const ll INF = 1e18;set<ll> 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;}

F

题意

房间里有 $n$ 个物品，每个物品的种类为 $a_i$ 。这些物品中，有一个是模仿者伪装的。

现在可以进行一场最多 $5$ 轮的实验去找出它，每一轮按顺序发生如下事件：

1. 记录当前房间内的所有物品的种类。
2. 可指出一个物品确定是伪装的，则试验结束。但这个操作只能执行一次，若不确定，则要做下一步操作。
3. 选出一些物品移出房间（可以不选，但模仿者始终不会被移出房间）并离开房间。随后房间里的物品会被打乱，模仿者也可以转换成别的物品（即使房间里不存在的物品）。
4. 进入房间，继续下一轮。模仿者可能不转变，但最多保持两轮是同一个类型的物品。

给出操作，找到模仿者。

题解

知识点：枚举。

一开始可以不移出物品，这样若模仿者发生变化，则最多两轮一定有一个类型的物品多了一个。

移出除了多出来物品的类型以外类型的所有物品。

剩下的一定是包括模仿者的同一类型的物品，再最多不超过一轮，一定会出现一个不同类型的物品，就是模仿者。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int n;int a[207];int cnt1[10], cnt2[10]; void query(const vector<int> &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<int> 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;}

G

题意

有 $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 <bits/stdc++.h>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<node> 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;}