牛客周赛52

Dec 16, 2024 11:44 AM

Dec 17, 2024 4:34 AM

A 两数之和

对于给定的正整数 $z$ ，你需要寻找两个不同的正整数 $x$ 和 $y$ ，使得 $x + y = z$ 成立。

如果不存在这样的 $x$ 和 $y$ ，你只需要输出 $N O$ 。

void solve() {
    int z;cin >> z;
    if (z <= 2) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        cout<<"1 "<< z - 1<<'\n';
    }
}

B 小红装匣子

小红有 $a$ 块 $1 \times 2$ 大小的物块， $b$ 块 $1 \times 3$ 的大小的物块，小红想知道能不能填满 $2 \times n$ 大小的匣子。

物块可以旋转使用，可以有剩余。

易得： $b$ 每次一定是使用偶数块且使用的个数有限制，在满足条件的 $b$ 的个数带入计算即可

#define int long long
void solve() {
    int a, b, n;cin >> a >> b >> n;
    int mxb = min(b, n / 3 * 2);
    if (mxb & 1)mxb--;
    if (2 * a + 3 * mxb >= 2 * n) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

C 小红的数字对对碰

红有一个长度为 $n$ 的数组 $a$ ，第 $i$ 位的值为 $a_{i}$ 。她想通过以下方式，尽可能地减少数组长度。

当 $l e n (a) > 1$ 且存在二元组 $(i, j)$ ，满足 $i < j$ 且 $a_{i} + a_{j} \leq 0$ ，则可消去 $a_{i}$ 和 $a_{j}$ 。
当 $l e n (a) > 1$ 且存在二元组 $(i, j)$ ，满足 $i < j$ 且 $a_{i} \oplus a_{j} \leq 0$ ，则可消去 $a_{i}$ 和 $a_{j}$ 。

请你输出最小化后的数组的长度。

按照 $a_{i}$ 的+/-/0来分类。

由给出的条件：

$a_{i} + a_{j} \leq 0$ ：
$⟹$

$(\leq 0, \leq 0)$
$(> 0, < 0)$

$a_{i} \oplus a_{j} \leq 0$ ：
$⟹$

$a_{i} = a_{j}$
$(\geq 0, < 0)$

综上：只有 $a_{i} \geq 0 \cap a_{j} \geq 0 \cap a_{i} \neq a_{j}$ 才不满足消去的条件。

有贪心的思想：正数是不利于答案的计算的，所以尽量先将正数去掉，即先将 $a_{i} = a_{j} > 0$ 的消去。

#define int long long
void solve() {
    int n;cin >> n;
    int pos = 0, neg = 0, z = 0;
    map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        if (x == 0) {
	        z++;
        } else if (x > 0) {
            pos++;mp[x]++;
            if (mp[x] == 2) {
	            pos -= 2, mp[x] = 0;
            } 
        } else {
            neg++;
        }
    }
    if (pos <= neg) {
        cout << (neg - pos + z) % 2 << '\n';
    } else {
        cout << pos - neg + z << '\n';
    }
}

E 小红的图上加边

小红有一张 $n$ 个点 $m$ 条边的无向图，每个节点的权值是 $a_{i}$ 。
现在小红希望加边把这个图连成连通图，每次连接的代价是新形成的联通块的最大元素值，小红想知道最小需要消耗多少代价可以把这个图连成连通的。

这个题目居然是最简单的...

按照缩点的思想，每个块的权值是 $w_{j} = max (a_{i}), a_{i} \in B l o c k$

则易得答案就是 $\sum w_{i} - min (w_{i})$

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> vis(n + 1);
    int sum = 0, mi = 1e18;

    for (int i = 1;i <= n;i++) {
        if (!vis[i]) {
            int mx = a[i];
            queue<int>q;vis[i] = 1;q.push(i);
            while (q.size()) {
                int u = q.front();q.pop();
                for (auto v : g[u]) {
                    if (vis[v])continue;
                    vis[v] = 1;
                    mx = max(mx, a[v]);
                    q.push(v);
                }
            }
            mi = min(mi, mx);
            sum += mx;
        }
    }
    cout << sum - mi << '\n';
}

D 小红的最大字典序

小红有 $n$ 个数字 $a_{1}, a_{2}, \dots, a_{n}$ 和一个空字符串 $s$ ，现在她需要执行 $n$ 次操作：

第 $i$ 次操作需要将 $a_{i}$ 按照数位的相对顺序、从左到右的取出并依次插入 $s$ （在 $s$ 中不需要连续，但需要保持原有相对顺序）。

小红想要构造一个这样的字符串 $s$ ，使得它的字典序是所有合法构造方案中最大的。

Solution

堆+思维

这个题没写出来实在不应该...

看到小学哥写的，太秒了，实在太秒！

void solve() {
    int n;cin >> n;
    priority_queue<pair<char, string>>q;
    for (int i = 1;i <= n;i++) {
        string s;cin >> s;q.push({s[0],s});
    }
    string ans = "";
    while (q.size()) {
        auto [c, s] = q.top();q.pop();
        s.erase(s.begin());
        ans += c;
        if (s.size()) {
            q.push({s[0],s});
        }
    }
    cout << ans << '\n';
}

F 小红的括号串

小红有一个只包含 '(' 、')' 和 '?' 的字符串，小红想知道有多少种将 '?' 替换成 '(' 或 ')' 的方式使得存在一种循环移位、让该字符串为合法的括号串。

假设一个长度为 $n$ 的字符串 $s [k : n] + s [1 : k)$ 是字符串 $s$ 的循环移位，那么，若字符串 $s$ 是合法的括号串， $s [k : n] + s [1 : k)$ 也是合法的括号串。

Solution

可以参考小学哥的题解：题解 | 小红的括号串_牛客博客 ->具体数学 P301

新知识：Raney 引理：若 $\sum_{i = 1}^{m} x_{i} = 1$ ，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。

意在告诉我们只要满足序列和为 0 的均合法。

constexpr int mod = 1e9 + 7;
void solve() {
    int n;cin >> n;
    string s;cin >> s;
    if (n & 1) {
        cout << "0\n";return;
    }
    int x = 0, y = 0;
    for (auto c : s) {
        if (c == '(') x++;
        else if (c == ')') y++;
    }
    cout << C(n - x - y, n / 2 - x) << '\n';
}