Codeforces Round 1033 (Div. 2) and CodeNite 2025 ¶

created: 2025-06-23 02:07:32

这场打的很烂，又快四千名了，-76。最近好多题目没补，博客也没咋写，先把这篇写了吧。最近在考试，但是马上就考完了，24和25还有3场考试然后就可以尽情刷题了。又安上 ubuntu 了，感觉很爽。

绿名表现分闹麻了，C有点糖丸，WA了几次，其实确实挺简单，D不会就原谅自己了。

A¶

挺简单的，要注意是不能翻转的，所以直接枚举几种情况，要么就是两个小的并排，大的在上面或者下面，要么就是两个小的上下放，大的在左边或者右边。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    array<int, 3> l, b;
    for(int i = 0; i < 3; i++)
        cin >> l[i] >> b[i];
    if(l[0] == l[2]){
        if(l[0] == b[0] + b[1] + b[2]){
            cout << "YES\n";
            return;
        }
    }
    if(b[0] == b[2]){
        if(b[0] == l[0] + l[1] + l[2]){
            cout << "YES\n";
            return;
        }
    }
    if(b[1] == b[2]){
        if(b[1] + b[0] == l[0] && l[1] + l[2] == l[0]){
            cout << "YES\n";
            return;
        }
    }
    if(l[1] == l[2]){
        if(l[1] + l[0] == b[0] && b[1] + b[2] == b[0]){
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T; while(T--)
    solve();
    return 0;
}

B¶

哈哈哈，看起来还以为好难，还很耽误了一会，但是观察如果不考虑碰撞，那么除非是在对角线上，且路径是对角线，否则一定会走一个矩形，永远不会到角落。

而考虑碰撞，其实并不影响，相当于是两个小球互换了轨道，所以我们只需要找对角线上且沿着对角线走的小球。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n, s;
    cin >> n >> s;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int dx, dy, x, y;
        cin >> dx >> dy >> x >> y;
        if(x + y == s && dx * dy < 0) ans++;
        else if(x == y && dx * dy > 0) ans++;
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T; while(T--)
    solve();
    return 0;
}

C¶

感觉得把心静下来好好写题解，而不只是把这当做一项任务和一种负担。

首先我们可达到的最大答案一定是 \(\sum_{i=1}^{n} {i}\)，最小的答案是 \(n\)。

那么是否在这个区间内则一定可以有答案呢？

其实可以贪心去考虑，首先我们假设当前的图是 \(n\) 为根节点，从大到小连的一条链，那么这时我们一定是达到我们能达到的最大的值。

接下来就可以贪心的取，每次如果当前答案大于目标，则把 \(i\) 连到 \(1\)，或者是连一个别的能直接使得当前值等于 \(m\)，那么可以退出循环了。

如果当前的答案恰好等于 \(m\)，那么就让 \(root = i\)，小于 \(root\) 的值，只需要能给出等于 \(i\) 的贡献就好，所以全连 \(root\) 就行了。

服了，WA四次都是因为没判断 \(m < n\)，甚至后来发现了有另一个限制，但是加的是 \(m < n - 1\)，想成边权了来着，鉴定为没睡好。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    int n; ll m;
    cin >> n >> m;
    ll now = 1LL * (1 + n) * n / 2;
    if(m > now || m < n - 1){
        cout << "-1\n";
        return;
    }
    int root = 1;
    vector<pair<int, int>> edges;
    for(int i = n; i >= 1; i--){
        if(now == m){
            root = i;
            break;
        }
        // cerr << now << '\n';
        if(i - 1 <= now - m){
            now -= i - 1;
            edges.push_back({1, i});
        }else{
            // 看 i 需要和谁连
            int x = i - (now - m);
            edges.push_back({x, i});
            now -= i - x;
            // now = m;
            assert(now == m);
            // i - x = now - m
            // x = i - (now - m)
        }
        // cerr << edges.size() << '\n';
    }
    for(int i = root - 1; i >= 1; i--)
        edges.push_back({root, i});
    cout << root << '\n';
    for(auto [u, v] : edges){
        cout << u << " " << v << '\n';
        // 2 + 2 + 1 + 1
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T; while(T--)
    solve();
    return 0;
}

D¶

首先 \(n\) 是好想的，因为我们肯定优先保证 \(n\) 小，试样例大概也能试出来，\(n = k(a-1) + 1\)。

怎么来的呢？就是如果有 \(k(a-1) + 1\) 行，那么至少会有一个数字的数量是 \(\ge k\) 的，并且一定要至少这个值，才能满足条件。

先说结论，\(m = \binom{n}{a}(b-1)k + 1\)

\((b-1)k\) 就是能使得每一行有 \(b-1\) 个相同的，然后列的种类是有 \(\binom{n}{a}\) 种，所以我们乘 \((b-1)k\) 就是能使得每种列是出现了 \(b-1\) 次。

其实我可能也没太搞懂

python 挺爽，取模不需要考虑负数，但是其实要考虑的话也就多操作一次。

mod = 1000000007
def solve():
    a, b, k = map(int, input().split())
    n = ((a - 1) * k + 1) % mod
    # (n, a) * (b - 1) * k
    # n * (n - 1) * (n - a + 1)
    # n! / m!
    fz = 1
    for i in range(a):
        fz = fz * (n - i) % mod
    fm = 1
    for i in range(1, a + 1):
        fm = fm * i % mod
    ans = fz * pow(fm, mod - 2, mod) % mod * (b - 1) % mod * k % mod + 1
    print(n, ans % mod)
for _ in range(int(input())):
    solve()

Codeforces Round 1033 (Div. 2) and CodeNite 2025¶

A¶

B¶

C¶

D¶

Codeforces Round 1033 (Div. 2) and CodeNite 2025 ¶