由于牛客的渲染问题，你可以点此链接进入我的博客查看

个人难度评级

签到：

简单：

中等：

A 智乃的二进制

不难发现， 都是好数： ，所以它的二进制最后 位都是 ，又因为 是奇数，所以倒数第 位一定是 。

其次，对于 ，只要满足 ，它就是好数：

如果满足好数定义，就有

也就是

然后化简一下，得到

也就是

现在我们要求 满足什么条件时， 能被 整除。 我们展开得到

我们要 ，也就是 ，就能得到 必须是 ​ 的倍数。

由以上结论也能发现，好数总是被 分割成几个部分，直接计算一下还原即可。

void solve() {
    ll k;
    cin >> k;
    auto check = [&](ll x) {
        if (x < 0)
            return 0ll;
        ll s = 1 + 2 * x;
        for (int i = 1; i <= 62; ++i) {
            ll p = 1ll << (i - 1);
            if (p > x)
                break;
            s += (x - i) / p;
        }
        return s;
    };
    ll l = 0, r = 2e18, n = 0;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid) >= k)
            n = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    ll R = k - check(n - 1);

    if (R == 1)
        cout << ksm(Z(10), n) << endl;
    else if (R == 2)
        cout << ksm(Z(10), n) + 1 << endl;
    else {
        vector<int> D;
        for (int i = 1; i <= 62; ++i) {
            if (i >= n)
                break;
            if ((n - i) % (1ll << (i - 1)) == 0)
                D.pb(i);
        }
        sort(rall(D));
        int d = D[R - 3];
        cout << ksm(Z(10), n) + ksm(Z(10), n - d) << endl;
    }
}

B 智乃的瓷砖

用一个标记记录一下每行的开头是什么，然后每行每一个都和前一个不一样即可。

void solve() {
    bool f1 = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((j & 1) == f1)
                cout << '/';
            else
                cout << '\\';
        }
        f1 = !f1;
        cout << endl;
    }
    cout << endl;
}

C 智乃的草坪

每个点在第 秒的半径为 。对于位于 的圆，当且仅当 时，它在水平方向上存在能覆盖整段竖直区间 的投影区间。具体地，此时在 轴上它能覆盖的整列 满足

因此对应的区间为

要覆盖整个矩形 ，等价于这些区间（从选定的至多 个点产生）能覆盖段 。

于是对给定的时间 ，我们可以把每个点能形成的区间计算出来（如果 则忽略），得到若干区间。然后从当前位置 开始，每步在所有左端 的区间中取右端最远的一个，更新 到该最远右端，计数加 ；若超过 次仍未覆盖到 则失败。（也就是区间线段覆盖问题）

这个判定是显然单调的：时间越大，区间越宽，覆盖更容易，所以我们可以使用二分计算时间。

void solve() {
    int n, k;
    ld r, c;
    cin >> n >> k >> r >> c;
    vector<pair<ld, ld>> pts(n);
    for (int i = 0; i < n; ++i) {
        cin >> pts[i].fi >> pts[i].se;
    }

    auto check = [&](ld t) {
        vector<pair<ld, ld>> segs;
        for (auto [p, v] : pts) {
            ld R = v * t;
            if (R + eps < r)
                continue;
            ld h = sqrt(max(0.0l, R * R - r * r));
            ld L = p - h, Rr = p + h;
            segs.eb(L, Rr);
        }
        if (segs.empty())
            return false;
        sort(all(segs));
        ld cur = 0.0l;
        int used = 0, idx = 0;
        int m = segs.size();
        while (cur + eps < c && used < k) {
            ld mx = cur;
            while (idx < m && segs[idx].fi <= cur + eps) {
                if (segs[idx].se > mx)
                    mx = segs[idx].se;
                ++idx;
            }
            if (mx <= cur + eps)
                break;
            cur = mx;
            ++used;
        }
        return (cur + eps >= c);
    };

    ld lo = 0.0l, hi = INF, ans = hi;
    for (int it = 0; it < 100; ++it) {
        ld mid = (lo + hi) / 2.0l;
        if (check(mid))
            ans = mid, hi = mid;
        else
            lo = mid;
    }
    cout << ans << endl;
}

D 智乃的果子

直觉告诉我们肯定是从小往大合并会比较优。我们用优先队列记录一下果子的重量和数量，每次都取最轻的处理，把其中的一半两两合并；如果这一组只有一个果子，我们就再取一组与它合并。

void solve() {
    int n;
    ll tot = 0;
    cin >> n;
    priority_queue<PLL> pq;
    for (int i = 0; i < n; ++i) {
        ll c, w;
        cin >> c >> w;
        pq.push({-w, c});
        tot += c;
    }
    if (tot <= 1) {
        cout << 0 << endl;
        return;
    }
    Z ans = 0;
    while (tot > 1) {
        auto [w, c] = pq.top();
        pq.pop();
        w = -w;
        if (c >= 2) {
            ll P = c / 2;
            ans += Z(2) * w * P;
            pq.push({-w * 2, P});
            if (c & 1)
                pq.push({-w, 1});
            tot -= P;
        } else {
            auto [tw, tc] = pq.top();
            pq.pop();
            tw = -tw, tc--;
            ans += w + tw;
            pq.push({-w - tw, 1});
            if (tc)
                pq.push({-tw, tc});
            tot--;
        }
    }
    cout << ans << endl;
}

E 智乃的最大子段和取模

模意义下也可以进行前缀和的操作， 的子段和为 ，所以对于每个 ，我们都需要找一个 使得 最大即可。

如果 ，那么找最小 就行；如果 ，也就是原式为 ，所以我们要取最接近 的 。所以对每一个 检查这两类即可。

void solve() {
    int n, p;
    cin >> n >> p;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    vector<ll> pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        pre[i] = (pre[i - 1] + a[i - 1]) % p;
    }
    set<PLL> s;
    s.insert({0, 0});
    ll mx = -1;
    int L = 0, R = 0;

    for (int j = 1; j <= n; ++j) {
        ll cur = pre[j];

        if (s.begin() != s.end()) {
            ll val = (cur - s.begin()->fi + p) % p;
            if (val > mx) {
                mx = val;
                L = s.begin()->se;
                R = j - 1;
            }
        }

        auto it = s.upper_bound({cur, INF});
        if (it != s.end()) {
            ll val = (cur - it->fi + p) % p;
            if (val > mx) {
                mx = val;
                L = it->se;
                R = j - 1;
            }
        }

        s.insert({cur, j});
    }

    cout << L << " " << R << " " << mx << endl;
}

F 智乃的算法竞赛群友

我们设 为 的个数， 为 的个数，当一个 使用 末尾的 的时候，我们就能节省一个字符。

所以：

• ，最小的长度为 。
• ，最小的长度为 。

我们要求的就是满足最小长度 的 ，对于固定的 ，我们只需要检查几个可能取到最值的 即可，也就是 以及周围的一些点。

constexpr ll INF = 2e18;

void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> X;
    X.pb(0);
    auto check = [&](ll x) {
        return 0 <= x && x <= n;
    };
    for (int i = -3; i <= 3; ++i) {
        if (check(n / 8 + i))
            X.pb(n / 8 + i);
        if (check(n / 7 + i))
            X.pb(n / 7 + i);
        if (check((n + 1) / 8 + i))
            X.pb((n + 1) / 8 + i);
    }
    for (int i = 0; i <= 6; ++i)
        if (check(i))
            X.pb(i);
    sort(all(X));
    X.erase(unique(all(X)), X.end());

    auto calc = [&](ll x) {
        ll mx = -1;
        if (x <= n / 8) {
            ll t = (n - 6 * x) / 2;
            if (t >= x) {
                mx = t;
            } else {
                if (n - 7 * x >= 0) {
                    mx = max(x - 1, n - 7 * x);
                } else {
                    return -INF;
                }
            }
        } else {
            if (n - 7 * x >= 0) {
                mx = min(x - 1, n - 7 * x);
            } else {
                return -INF;
            }
        }
        if (mx < 0)
            return -INF;
        return a * x + b * mx;
    };

    ll ans = 0;
    bool f = 0;
    for (auto x : X) {
        ll val = calc(x);
        if (val == -INF)
            continue;
        if (!f || val > ans) {
            ans = val;
            f = 1;
        }
    }
    if (!f)
        cout << 0 << endl;
    else
        cout << ans << endl;
}

G 智乃的箭头魔术

模拟一下即可，模拟的代码如下

void solve() {
    string s = "0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532";
    int c = 0;
    for (auto v : s) {
        if (v == '0')
            c = 3 - c;
        else if (v == '1') {
            if (c == 3)
                c = 1;
            else if (c == 1)
                c = 3;
        } else if (v == '2') {
            if (c == 0)
                c = 1;
            else if (c == 1)
                c = 0;
            else if (c == 3)
                c = 2;
            else if (c == 2)
                c = 3;
        } else if (v == '3') {
            if (c == 0)
                c = 2;
            else if (c == 2)
                c = 0;
        } else if (v == '4') {
            c = (c + 1) % 4;
        } else if (v == '5') {
            c = (c + 3) % 4;
        }
        cout << c;
    }
}

答案为

3132333010010310230010130130330130312312210210010321300120122322322101123223211001003013030031210332

H 智乃的矩阵

首先我们发现，进行一次操作之后，所有元素之和不变，所以最开始元素之和一定要为 的倍数，我们令 。

其次我们发现，对于每种操作，如果把矩阵染成黑白格，即 为奇数的格子染黑， 为偶数的格子染白，那么对于同一种颜色，每种操作都不会改变这个颜色的元素之和，所以令颜色的格子数为 ，该颜色的元素之和为 ，任何一种颜色都要满足 。

然后我们发现，在模 2 的意义下，每次操作（无论是加还是减）相当于给选定的 区域内的 4 个数都 （因为 ）。所以我们需要判断是否能通过若干次 区域的翻转，将矩阵 （其中 ）变成全 矩阵。我们用贪心或者高斯消元都可以解决，这里给出贪心的解法。

设 为模 意义下以 为左上角的操作次数。对于位置 ，只有操作 能影响它。为了使 变为 ，必须有 。对于位置 ，它受到 、 、 、 的影响。当我们遍历到 时，后三者已经确定，因此 被唯一确定。计算出所有 的 后，还需要检查矩阵的边界（第 行和第 列）是否也满足变成了 0。如果不满足，则无法达成。

void solve() {
    int n;
    ll tot = 0, sum = 0, cnt = 0;
    cin >> n;
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j], tot += a[i][j], sum += (i + j & 1) * a[i][j], cnt += i + j & 1;
    if (n == 1) {
        cout << "Yes" << endl;
        return;
    }
    if (tot % (n * n) != 0) {
        cout << "No" << endl;
        return;
    }
    ll T = tot / (n * n);
    if (sum != cnt * T) {
        cout << "No" << endl;
        return;
    }
    vector<vector<int>> b(n + 2, vector<int>(n + 2));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            b[i][j] = ((a[i][j] - T) % 2 + 2) % 2;
        }
    }
    vector<vector<int>> x(n + 2, vector<int>(n + 2));
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            x[i][j] = b[i][j] ^ x[i - 1][j] ^ x[i][j - 1] ^ x[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int cur = 0;
            if (i < n && j < n)
                cur ^= x[i][j];
            if (i > 1 && j < n)
                cur ^= x[i - 1][j];
            if (i < n && j > 1)
                cur ^= x[i][j - 1];
            if (i > 1 && j > 1)
                cur ^= x[i - 1][j - 1];

            if (cur != b[i][j]) {
                cout << "No" << endl;
                return;
            }
        }
    }

    cout << "Yes" << endl;
}

I 智乃挖坑

首先怎么去判定被挖穿，直接模拟肯定会超时，所以我们考虑使用差分。对于每一个坑我们都可以拆成两部分，左半深度增加，右半深度减小，我们维护这两个差分数组，然后做前缀和就可以检查有没有超过 了。

那么对于整个时间轴，肯定能找到一个时间点，前面都没被挖穿，后面都被挖穿了，所以我们使用二分去计算次数，每次 的时候模拟一下即可。

void solve() {
    int n, m;
    ll h;
    cin >> n >> m >> h;
    vector<PII> ops(m);
    for (int i = 0; i < m; ++i) {
        cin >> ops[i].fi >> ops[i].se;
    }
    auto check = [&](int t) {
        vector<ll> A(n + 2), B(n + 2);
        for (int i = 0; i < t; ++i) {
            auto [p, f] = ops[i];
            int L = max(1, p - (f - 1)), R = min(n, p + (f - 1));
            int l1 = L, r1 = min(p, R);
            if (l1 <= r1) {
                A[l1] += 1, A[r1 + 1] -= 1;
                B[l1] += f - p, B[r1 + 1] -= f - p;
            }
            int l2 = max(p + 1, L), r2 = R;
            if (l2 <= r2) {
                A[l2] += -1, A[r2 + 1] -= -1;
                B[l2] += f + p, B[r2 + 1] -= f + p;
            }
        }
        ll a = 0, b = 0;
        for (int j = 1; j <= n; ++j) {
            a += A[j];
            b += B[j];
            if (a * j + b > h)
                return 1;
        }
        return 0;
    };

    if (!check(m)) {
        cout << "No" << endl;
        return;
    }

    int lo = 1, hi = m, ans = m;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            ans = mid;
            hi = mid - 1;
        } else
            lo = mid + 1;
    }
    cout << "Yes" << endl;
    cout << ans << endl;
}

J 智乃的幻方

暴力检查一下即可。

void solve() {
    vector<vector<int>> a(3, vector<int>(3));
    unordered_set<int> st;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j];
            st.insert(a[i][j]);
        }
    }
    if (st.size() != 9) {
        cout << "No" << endl;
        return;
    }
    int S = a[0][0] + a[0][1] + a[0][2];
    for (int i = 0; i < 3; ++i) {
        int s = 0;
        for (int j = 0; j < 3; ++j) {
            s += a[i][j];
        }
        if (s != S) {
            cout << "No" << endl;
            return;
        }
    }
    for (int i = 0; i < 3; ++i) {
        int s = 0;
        for (int j = 0; j < 3; ++j) {
            s += a[j][i];
        }
        if (s != S) {
            cout << "No" << endl;
            return;
        }
    }
    if (a[0][0] + a[1][1] + a[2][2] != S) {
        cout << "No" << endl;
        return;
    }
    if (a[2][0] + a[1][1] + a[0][2] != S) {
        cout << "No" << endl;
        return;
    }
    cout << "Yes" << endl;
}

头文件

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define endl "\n"
using namespace std;

using ll = long long;
using ld = long double;
using ui = unsigned;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;

void init() {
}

void solve() {
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    cout << fixed << setprecision(15);
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}

自动取模

constexpr int MOD = 1e9+7;

template <class T>
constexpr T ksm(T a, ll b) {
    T res = 1;
    while (b) {
        if (b & 1)
            res *= a;
        b >>= 1;
        a *= a;
    }
    return res;
}

template <int P>
struct MInt {
    int x;
    constexpr MInt() : x() {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return ksm(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

using Z = MInt<MOD>;