牛客周赛 Round 30
A
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
string s;
cin >> s;
for (int i = 0; i < 3; i++)
{
if (i != 1)
{
cout << s[i];
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
int x;
cin >> x;
vector<int> cnt(12);
while (x)
{
int t = x % 10;
cnt[t]++;
x /= 10;
}
ll ans = 0;
for (int i = 1; i <= 9; i++)
{
if (cnt[i] > 0)
{
cnt[i]--;
ans = i;
break;
}
}
for (int i = 0; i <= 9; i++)
{
while (cnt[i] > 0)
{
cnt[i]--;
ans = ans * 10 + i;
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C
解题思路:
找到半边不同的两个字符，两半边对应交换位置。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
void solve()
{
string s;
cin >> s;
int n = s.size();
vector<int> vis(40, -1);
int cnt = 0;
for (int i = 0; i < (n) / 2; i++)
{
if (vis[s[i] - 'a'] == -1)
{
vis[s[i] - 'a'] = i;
cnt++;
}
}
// cout << cnt << endl;
if (cnt > 1)
{
int a = 0;
int b = 0;
for (int i = 0; i < 26; i++)
{
if (!a && !b && vis[i] != -1)
{
a = vis[i];
}
else if (!b && vis[i] != -1)
{
b = vis[i];
break;
}
}
// cout << a << ' ' << b << ' ' << endl;
swap(s[a], s[b]);
swap(s[n - 1 - a], s[n - 1 - b]);
cout << s << endl;
}
else
{
puts("-1");
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D
解题思路:
先统一转换为乘法：\(,g = gcd(x,y),x = x \div g,y = y \div g\)
乘法上边界:\(\lfloor \frac{r}{y}\rfloor\)
乘法下边界:\(\lceil \frac{l}{x} \rceil\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
int x, y, l, r;
cin >> x >> y >> l >> r;
int g = gcd(x, y);
x /= g;
y /= g;
if (x > y)
{
swap(x, y);
}
int ans = max(0, (r / y) - ((l + x - 1) / x) + 1);
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E
解题思路:
\(f[i][0]:以结点i为根节点的子树，结点i染色为白色的方案数\)。
\(f[i][1]:以结点i为根节点的子树，结点i染色为红色的方案数\)。
\(f[u][0] = \prod\limits_{v \in son[u]} f[v][1]\)
\(f[u][1] = \prod\limits_{v \in son[u]}(f[v][0] + f[v][1])\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
ll f[N][2];
void solve()
{
int n;
cin >> n;
vector<vector<int>> adj(n + 1, vector<int>());
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
auto dfs = [&](auto self, int u, int fa) -> void
{
f[u][0] = f[u][1] = 1;
for (auto v : adj[u])
{
if (v == fa)
{
continue;
}
self(self, v, u);
f[u][0] = f[u][0] * f[v][1] % mod;
f[u][1] = f[u][1] * (f[v][1] + f[v][0]) % mod;
}
};
dfs(dfs, 1, -1);
cout << (f[1][0] + f[1][1]) % mod;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
F
解题思路:
注意，\(a,b\)的取值只有\(1,2\)。
\(f[i][j]:小红还有i个1，小紫还有j个1时的期望\)。
四种情况:\((1,1),(1,2),(2,1),(2,2)\)，我们对应概率为\(p_{11},p_{12},p_{21},p_{22}\)
\(f[i][j] = (p_{11} + p_{22}) \times f[i][j] + p_{12}\times f[i - 1][j] + p_{21} \times f[i][j -1] +1\)。
对方程进行化简，即可得到状态转移方程：
\(f[i][j] = \frac{p_{12} \times f[i-1][j] + p_{21} \times f[i][j-1] + 1}{1 - p_{11}-p_{22}}\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
const int mod = 1e9 + 7;
const int N = 55;
ll f[N][N];
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return res;
}
void solve()
{
int n, m;
cin >> n >> m;
int a = 0;
int b = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
a += x == 1;
}
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
b += x == 1;
}
for (int i = 0; i <= a; i++)
{
for (int j = 0; j <= b; j++)
{
if (i == 0 && j == 0)
{
continue;
}
ll pa1 = i * qmi(n - (a - i), mod - 2) % mod;
ll pa2 = (n - a) * qmi(n - (a - i), mod - 2) % mod;
ll pb1 = j * qmi(m - (b - j), mod - 2) % mod;
ll pb2 = (m - b) * qmi(m - (b - j), mod - 2) % mod;
// 11,22
ll p = ((pa1 * pb1 % mod) + (pa2 * pb2 % mod)) % mod;
p = (1 - p + mod) % mod;
p = qmi(p, mod - 2);
f[i][j] = (f[i][j] + p) % mod;
if (i)
{
ll tp = pa1 * pb2 % mod;
f[i][j] = (f[i][j] + ((tp * f[i - 1][j] % mod) * p % mod)) % mod;
}
if (j)
{
ll tp = pa2 * pb1 % mod;
f[i][j] = (f[i][j] + ((tp * f[i][j - 1] % mod) * p % mod)) % mod;
}
}
}
cout << f[a][b] << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}