牛客周赛 Round 30
A 小红的删字符
小红拿到了一个长度为 3 的字符串,请你删除中间的字符后,输出该字符串。
void solve(){
string a; cin>>a;
cout<<a[0]<<a[2]<<'\n';
}
B 小红的正整数
小红拿到了一个正整数,她希望你将该正整数重排,使得最终正整数尽可能小。你能帮帮她吗?
注:不能包含前导零。
例如
先输出第一个非 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 小红构造回文
小红拿到了一个回文串,她希望你将这个回文串重排,使得重排后仍然是回文串且和原串不同。你能帮帮她吗?
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 小红整数操作
小红拿到了两个正整数
- 将两个数同时乘以
。 - 若
既是 的因子,也是 的因子,则将两个数同时除以 。小红希望最终两个数都在 区间内。她想知道最终的 有多少种不同的取值方案?
先将
#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 小红树上染色
小红拿到了一棵树,初始所有节点都是白色。
小红希望染红若干个节点,使得不存在两个白色节点相邻。
小红想知道,共有多少种不同的染色方案?
答案对
Solution
树形 DP
每个节点有两种状态, 为白色/红色
因为限制是不能存在两个相邻节点为白色
所以如果当前节点为白色,其子节点必须都是红色节点
如果当前节点为红色,其子节点红白即可
状态叠加是基于乘法原理的
(待更
#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“有一方卡牌被用完”时结束。
请你计算小红和小紫游戏进行回合数的期望
Solution
期望DP
(待更