比賽連結

A

題解

知識點：貪心。

將區間按左端點排序，合併區間，記錄所有區間之間斷開的長度即可。

時間複雜度 \(O(n\log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct node {
    ll l, r;
}a[200007];


int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x, r;
        cin >> x >> r;
        a[i].l = x - r;
        a[i].r = x + r;
    }
    sort(a, a + n, [&](node a, node b) {return a.l < b.l;});
    ll ans = 0, prer = a[0].r;
    for (int i = 1;i < n;i++) {
        if (a[i].l > prer)ans += a[i].l - prer;
        prer = max(prer, a[i].r);
    }
    cout << ans << '\n';
    return 0;
}

C

題解

知識點：列舉，計算幾何。

首先注意到一行中靠右的影響包含於靠左的，因此每行只需要考慮最左側的位置 \(Xrow\)。然後列舉下到上所有行的最左側點 \(Xrow\) 與端點 \((0,1)\) 連成射線算出斜率 \(k\) ，將射線右側（包括射線上）的點都排除，記錄最右可行點的橫座標 \(Xgd0\)，端點 \((0,m)\) 類似。

每次詢問更新起作用的點，分別列舉上下端點的射線，將兩次列舉每行可行橫座標中最小的加起來就是答案，要注意可能會超過 \(n\) ，因此需要 min({n,Xgd0[y],Xgd1[y]}) 。

注意 \(k = 0\) 時特判。

時間複雜度 \(O(q(m+k))\)

空間複雜度 \(O(k+m)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int X[200007], Y[200007], Xrow[200007], Xgd0[200007], Xgdm[200007];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m, k, q;
    cin >> n >> m >> k >> q;
    for (int i = 1;i <= k;i++) cin >> X[i] >> Y[i];
    while (q--) {
        int id;
        cin >> id;
        cin >> X[id] >> Y[id];
        for (int y = 1;y <= m;y++) Xrow[y] = n + 1;
        for (int i = 1;i <= k;i++) Xrow[Y[i]] = min(Xrow[Y[i]], X[i]);///更新某行最靠前的人
        double k = 0;
        for (int y = 1;y <= m;y++) {
            k = max(k, 1.0 * (y - 1) / Xrow[y]);///更新(0,1)射線最大斜率
            if (k == 0) Xgd0[y] = Xrow[y] - 1;///斜率為0
            else Xgd0[y] = 1.0 * (y - 1) / k - 1e-9;///(x,x+1] = x，最大斜率與第y行交點（可能超過n）
        }
        k = 0;
        for (int y = m;y >= 1;y--) {
            k = min(k, 1.0 * (y - m) / Xrow[y]);///更新(0,m)射線最小斜率
            if (k == 0) Xgdm[y] = Xrow[y] - 1;
            else Xgdm[y] = 1.0 * (y - m) / k - 1e-9;
        }
        ll ans = 0;
        for (int y = 1;y <= m;y++) ans += min({ n,Xgd0[y],Xgdm[y] });
        cout << ans << '\n';
    }
    return 0;
}

D

題解

知識點：思維，計算幾何。

可以證明線段平行於線段中點與圓心的連線時，覆蓋弧長最大。

但要注意精度問題，不能操作太多次，儘量將計算過程化簡。

時間複雜度 \(O(t)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    double r, x, y, d;
    cin >> r >> x >> y >> d;
    double len = sqrt(x * x + y * y);
    double radA = acos((len - d) / r);
    double radB = acos((len + d) / r);
    cout << fixed << setprecision(7) << r * (radA - radB) << '\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;
}

G

題解

知識點：思維。

簽到題。可以肯定的是，答案一定是 string(s.length() - 1, '9') 或者其本身。因為前者一定存在，若要大於前者，則長度大於前者，即長度是原串長度，而符合原串長度且數位意義上不超過原串的最大字串一定是其本身。因此只需要構造一個全是 \(9\) 長度為原串長度減一的字串，輸出其和原串較大的一個即可。

時間複雜度 \(O(|S|)\)

空間複雜度 \(O(|S|)\)

程式碼

#include <bits/stdc++.h>

using namespace std;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s1;
    cin >> s1;
    string s2(s1.length() - 1, '9');
    cout << (s1 > s2 ? s1 : s2) << '\n';
    return 0;
}

I

題解

知識點：概率dp。

題面長的離譜。

給出 \(13\) 張牌，相同型別的牌不超過 \(2\) 個，牌堆 \(123\) 張牌，問形成7對子的期望局數。

顯然需要逆推，因為直到剩餘 \(0\) 張牌時期望局數一定為 \(0\) 。因此 \(dp[i][j]\) 表示剩餘 \(i\) 張牌還剩 \(j\) 張單牌的期望局數，轉移方程為：

注意 \(i\geq3j\) 時才可能發生，\(j \leq 2\) 時期望特判為 \(0\) 。

時間複雜度 \(O(t)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;
int dp[14], inv[124];

void inverse(int n) {
    inv[1] = 1;
    for (int i = 2;i <= n;i++)
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
}

bool solve() {
    string s;
    cin >> s;
    set<int> st;
    int cnt = 13;
    for (int i = 0;i < s.size();i += 2) {
        if (!st.count((s[i] - '0') * 100 + (s[i + 1] - 'a')))
            st.insert((s[i] - '0') * 100 + (s[i + 1] - 'a'));
        else
            cnt -= 2;
    }
    cout << dp[cnt] << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    inverse(123);
    for (int i = 1;i <= 123;i++) {///還剩下多少張，不能摸了多少張，因為摸了第0張是要求的，而還剩0張單牌1~13的局數是0
        for (int j = 13;j >= 1;j--) {
            if (i >= 3 * j)
                dp[j] = ((1LL * 3 * j * dp[max(0, j - 2)] +
                    1LL * (i - 3 * j) * dp[j]) % mod * inv[i] + 1) % mod;///概率x期望 = 新期望，j=1時，沒dp[j-2]，但期望是0，因此要特判
        }
    }
    int t = 1;
    cin >> t;
    for (int i = 1;i <= t;i++) {
        cout << "Case #" << i << ": ";
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}