牛客周赛 Round 30

A 小红的删字符

小红拿到了一个长度为 3 的字符串，请你删除中间的字符后，输出该字符串。

void solve(){
    string a; cin>>a;
    cout<<a[0]<<a[2]<<'\n';
}

B 小红的正整数

小红拿到了一个正整数，她希望你将该正整数重排，使得最终正整数尽可能小。你能帮帮她吗？注：不能包含前导零。例如 \(1230\to1023\)

先输出第一个非 0 的数字，然后将所有 0 放进去，再放入其他数字

void solve(){
    int n;
    cin >> n;

    string s = to_string(n);

    sort(s.begin(), s.end());
    int idx=0;
    for(int i=0;i<s.size();i++)
        if(s[i]=='0')
            idx=i+1;

    s.erase(0, s.find_first_not_of('0'));
    cout<<s[0];
    while(idx--)
        cout<<'0';
    for(int i=1;i<s.size();i++)
	    cout<<s[i];
}

C 小红构造回文

小红拿到了一个回文串，她希望你将这个回文串重排，使得重排后仍然是回文串且和原串不同。你能帮帮她吗？

GPT

string find(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    string half;
    char oddChar = '\0';
    for (auto it = freq.begin(); it != freq.end(); it++) {
        if (it->second % 2 != 0) {
            if (oddChar != '\0') {
                return "-1"; // 无解
            }
            oddChar = it->first;
            it->second--;
        }
        while (it->second > 0) {
            half.push_back(it->first);
            it->second -= 2;
        }
    }

    string rearranged = half;
    reverse(rearranged.begin(), rearranged.end());
    if (oddChar != '\0') {
        rearranged = half + oddChar + rearranged;
    } else {
        rearranged = half + rearranged;
    }

    return rearranged;
}

int main() {
    string s;
    cin >> s;
    if(find(s)==s)
        cout<<-1;
    else
        cout << find(s) << std::endl;
}

#include<bits/stdc++.h>
using namespace std;
int num[26];
int ans;
int main()
{
    string a,b;
    cin >> a;
    int len=a.size();
    for (int i = 0; i < len; i++)num[a[i] - 'a']++;
    for (int i = 0; i < 26; i++)if (num[i] > 1)ans++;
    if (ans < 2)cout << "-1";
    else {
        swap(a[0], a[1]);
        swap(a[len-2], a[len-1]);
        for (int i = 0; i < len; i++) {
            cout << a[i];
        }
    }
}

D 小红整数操作

小红拿到了两个正整数 \(x\)，\(y\)，她可以进行以下两种操作：

将两个数同时乘以 \(a\)。
若 \(a\) 既是 \(x\) 的因子，也是 \(y\) 的因子，则将两个数同时除以 \(a\)。小红希望最终两个数都在 \([l, r]\) 区间内。她想知道最终的 \(x\) 有多少种不同的取值方案？

先将 \(x,y\) 置为互质，依次枚举 \((x,y)\times c(c=1,2,3\dots)\) 不过比较耗时间

#define int long long
void solve()
{
    int x, y, l, r;
    cin >> x >> y >> l >> r;
    int g = __gcd(x, y), ans = 0;
    x /= g, y /= g;
    int c = 1;
    while (x * c <= r && y * c <= r)
    {
        x *= c, y *= c;
        if (x >= l && x <= r && y >= l && y <= r)
            ans++;
        x /= c, y /= c;
        c++;
    }
    cout << ans << '\n';
}

一点不同：(FAST)

void solve()
{
	int x, y, l, r;
	cin >> x >> y >> l >> r;
	if (x > y) swap(x, y);
	int g = __gcd(x, y), ans;
	x /= g, y /= g;
	int mn = (l + x - 1) / x * x, mx = r / y * x;
	ans = mx >= mn ? (mx - mn) / x + 1 : 0;
	cout << ans << '\n';
}

E 小红树上染色

小红拿到了一棵树，初始所有节点都是白色。

小红希望染红若干个节点，使得不存在两个白色节点相邻。

小红想知道，共有多少种不同的染色方案？

答案对 \(10^9+7\) 取模。

Solution

树形 DP

每个节点有两种状态, 为白色/红色

因为限制是不能存在两个相邻节点为白色

所以如果当前节点为白色，其子节点必须都是红色节点

如果当前节点为红色，其子节点红白即可

状态叠加是基于乘法原理的

$white[u]=\prod\limits_{v\in u的子节点}red[v]$

$red[u]=\prod\limits_{v\in u的子节点}(red[v]\oplus white[v])$

(待更 \(\dots\))

#define MOD 1000000007
vector<int> graph[100005];
long long dp[100005][2];

void dfs(int u, int parent) {
    dp[u][0] = dp[u][1] = 1;
    for (int v : graph[u]) {
        if (v != parent) {
            dfs(v, u);
            dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1]) % MOD;
            dp[u][1] = dp[u][1] * dp[v][0] % MOD;
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    memset(dp, 0, sizeof(dp));
    dfs(1, -1);
    cout << (dp[1][0] + dp[1][1]) % MOD << endl;
}

F 小红叒战小紫

给出两人每张怪兽卡的战力，对战的规则如下：

两人各有一些怪兽卡。每回合两人随机的从自己当前存活的怪兽卡中抽取一张发起决斗

战斗力低的怪兽卡死亡。
战斗力相同，则无事发生。

游戏进行到“如果抽卡，则 100%的概率无事发生”OR“有一方卡牌被用完”时结束。

请你计算小红和小紫游戏进行回合数的期望\(\text{MOD}\ 10^9+7\)。

Solution

期望DP

(待更 \(\dots\))