牛客周赛52

Dec 16, 2024 11:44 AM
Dec 17, 2024 4:34 AM

A 两数之和

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

如果不存在这样的 xy ,你只需要输出 NO

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

B 小红装匣子

小红有 a1×2 大小的物块,b1×3 的大小的物块,小红想知道能不能填满 2×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 位的值为 ai 。她想通过以下方式,尽可能地减少数组长度。

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

按照 ai 的+/-/0来分类。

由给出的条件:

ai+aj0

aiaj0

综上:只有 ai0aj0aiaj 才不满足消去的条件。

有贪心的思想:正数是不利于答案的计算的,所以尽量先将正数去掉,即先将 ai=aj>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 条边的无向图,每个节点的权值是 ai
现在小红希望加边把这个图连成连通图,每次连接的代价是新形成的联通块的最大元素值,小红想知道最小需要消耗多少代价可以把这个图连成连通的。

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

按照缩点的思想,每个块的权值是 wj=max(ai),aiBlock

则易得答案就是 wimin(wi)

#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 个数字 a1,a2,,an 和一个空字符串 s ,现在她需要执行 n 次操作:

i 次操作需要将 ai 按照数位的相对顺序、从左到右的取出并依次插入 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 引理:若 i=1mxi=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';
}