比賽鏈接

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;}

B代碼

#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;}

C代碼

#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;}

D代碼

#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;}

E題意

給定一個 \(n\) ，問是否存在 \(k \geq 2 ,s \geq 2\) ，使得 \(\displaystyle n = \sum_{i=0}^s k^i\) 。

題解方法一

知識點：數(shù)學(xué)，枚舉。

(資料圖片僅供參考)

實際上，\(\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，這個函數(shù)精度很差，但是這里是沒有問題的，因為上下界都離得很遠(yuǎn)。

時間復(fù)雜度 \(O(60)\)

空間復(fù)雜度 \(O(1)\)

方法二

知識點：數(shù)學(xué)，二分，枚舉。

注意到， \(s\) 不會太大，最大只可能 \(60\) ，考慮枚舉 \(s\) 。

對于一個 \(s\) ，由于 \(\displaystyle \sum_{i=0}^s k^i\) 是關(guān)于 \(k\) 單調(diào)的，我們可以二分 \(k\) ，找到使得 \(\displaystyle \sum_{i=0}^s k^i\) 小于等于 \(n\) 的最后一個 \(k\) ，隨后驗證這個 \(k\) 是否是答案即可。

注意到， \(k\) 也不會超過 \(10^9\) ，這個結(jié)論能降低常數(shù)。

時間復(fù)雜度 \(O(60 \times \log 10^9)\)

空間復(fù)雜度 \(O(1)\)

方法三

知識點：數(shù)學(xué)，二分，枚舉。

對于 \(s \geq 3\) 的情況， \(k\) 不會超過 \(10^6\) ，因此可以枚舉 \(k \leq 10^6\) ，對每個 \(k\) 預(yù)處理出 \(s \in[3,60]\) 的所有答案。

對于 \(s = 2\) 的情況，和方法一一樣直接二分即可。

時間復(fù)雜度 \(\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)\)

空間復(fù)雜度 \(\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;}

F題意

房間里有 \(n\) 個物品，每個物品的種類為 \(a_i\) 。這些物品中，有一個是模仿者偽裝的。

現(xiàn)在可以進行一場最多 \(5\) 輪的實驗去找出它，每一輪按順序發(fā)生如下事件：

記錄當(dāng)前房間內(nèi)的所有物品的種類。可指出一個物品確定是偽裝的，則試驗結(jié)束。但這個操作只能執(zhí)行一次，若不確定，則要做下一步操作。選出一些物品移出房間（可以不選，但模仿者始終不會被移出房間）并離開房間。隨后房間里的物品會被打亂，模仿者也可以轉(zhuǎn)換成別的物品（即使房間里不存在的物品）。進入房間，繼續(xù)下一輪。模仿者可能不轉(zhuǎn)變，但最多保持兩輪是同一個類型的物品。

給出操作，找到模仿者。

題解

知識點：枚舉。

一開始可以不移出物品，這樣若模仿者發(fā)生變化，則最多兩輪一定有一個類型的物品多了一個。

移出除了多出來物品的類型以外類型的所有物品。

剩下的一定是包括模仿者的同一類型的物品，再最多不超過一輪，一定會出現(xiàn)一個不同類型的物品，就是模仿者。

時間復(fù)雜度 \(O(n)\)

空間復(fù)雜度 \(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;}

G題意

有 \(n\) 種癥狀和 \(m\) 個藥品，癥狀的情況通過一個長為 \(n\) 的 \(01\) 串給出。

每種藥品治療效果是可以使特定的一些癥狀消失，但副作用是使得特定的癥狀出現(xiàn)。

每種藥有一個療程 \(d\) ，療程之內(nèi)不允許使用其他藥。

現(xiàn)在給出初始癥狀情況，問最少需要多少天才能使得癥狀全部消失。

題解

知識點：最短路，狀壓dp，拓?fù)湫騞p。

考慮狀壓，將癥狀壓縮為一個整數(shù)。

隨后，我們將 \(2^n\) 種癥狀情況看作點， \(m\) 種藥看作邊。顯然，每個點都可以有 \(m\) 條出邊。

假設(shè)當(dāng)前的癥狀是 \(st\) ，將要使用的藥品的效果是 \(e\) ，副作用是 \(se\) ，那么使用后的癥狀為 (st & ~e) | se，這樣就構(gòu)建了一條邊，權(quán)值為療程時間。

問題就變成，從初始狀態(tài)到 \(0\) 狀態(tài)的最短路，直接跑最短路即可。

求最短路的本質(zhì)就是在最短路圖這個DAG上進行拓?fù)湫騞p，因此一些dp可以考慮抽象成圖的形式跑最短路。

時間復(fù)雜度 \(O(m2^n \log (m2^n))\)

空間復(fù)雜度 \(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;}

關(guān)鍵詞：