牛客周赛 Round 31
小红小紫替换
代码:
#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;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
string s;
cin >> s;
if (s == "kou")
{
cout << "yukari" << endl;
}
else
{
cout << s << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的因子数
代码:
#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;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
ll x;
cin >> x;
int cnt = 0;
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
cnt++;
while (x % i == 0)
{
x /= i;
}
}
}
if (x > 1)
{
cnt++;
}
cout << cnt << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的字符串中值
解题思路:
对于每一个询问字符，考虑以它为中心能构造多少子串，即尽量往两边扩。
代码:
#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;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
char c;
scanf("%d %c", &n, &c);
string s;
cin >> s;
ll ans = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == c)
{
int l = i - 0;
int r = n - 1 - i;
ans += min(l, r) + 1;
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红数组操作
解题思路:
用\(map\)模拟链表操作。
代码:
#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;
using piii = pair<ll, pair<ll, ll>>;
const int N = 2e5 + 10;
map<ll, int> l, r;
void solve()
{
int q;
cin >> q;
map<int, int> v;
int h = 0;
int cnt = 0;
while (q--)
{
int t;
cin >> t;
if (t == 1)
{
int x, y;
cin >> x >> y;
cnt++;
if (y == 0)
{
r[x] = h;
l[h] = x;
h = x;
}
else
{
l[x] = y;
r[x] = r[y];
r[y] = x;
l[r[x]] = x;
}
}
else
{
int x;
cin >> x;
r[l[x]] = r[x];
l[r[x]] = l[x];
if (x == h)
{
h = r[x];
}
cnt--;
}
}
// if (cnt == 0)
// {
// cout << 0 << endl;
// return;
// }
vector<int> ans;
while (h)
{
ans.push_back(h);
h = r[h];
}
cout << ans.size() << endl;
for (auto c : ans)
{
cout << c << ' ';
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的子集取反
解题思路:
\(dp[i][j]:表示取完前i个数字后，此时总和为j的最小取反数。对于第i个数字我们如果减去就是取反，加上就无需增加操作数。\)
注意值域存在负数，所以我们对初始状态进行偏移。
代码:
#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;
using piii = pair<ll, pair<ll, ll>>;
const int N = 40000;
const int inf = 1 << 30;
int dp[210][2 * N + 10];
void solve()
{
int n;
cin >> n;
memset(dp, 0x3f, sizeof dp);
dp[0][40000] = 0;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
for (int j = 0; j <= 2 * N; j++)
{
if (j + x <= 2 * N)
{
dp[i][j] = min(dp[i][j], dp[i - 1][j + x] + 1);
}
if (j - x >= 0)
{
dp[i][j] = min(dp[i][j], dp[i - 1][j - x]);
}
}
}
if (dp[n][N] > n)
{
dp[n][N] = -1;
}
cout << dp[n][N] << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
小红的连续段
解题思路:
字符总长度总是为\(x + y\)。
我们枚举连续段数量，发现只有两种情况：
- \((a,b,a,b,..)\)，即\(a\)连续段开头，此时\(a\)段的数量必定为\(\lceil\frac{i}{2}\rceil\)
- \((b,a,b,a,...)\)，即\(b\)连续段开头,此时\(b\)段的数量必定为\(\lceil\frac{i}{2}\rceil\)
我们设\(a\)段数量为\(cnta\),\(b\)段数量为\(cntb\)。
将\(x\)个\(a\)分为\(cnta\)个非空集合的方案数为\(\binom{x - 1}{cnta - 1}\)
对\(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;
using piii = pair<ll, pair<ll, ll>>;
const int N = 1010;
const int mod = 1e9 + 7;
ll c[N][N];
void solve()
{
int x, y;
cin >> x >> y;
int n = x + y;
c[0][0] = 1;
for (int i = 1; i <= 1001; i++)
{
for (int j = 0; j <= i; j++)
{
if (j == 0)
{
c[i][j] = 1;
}
else
{
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
}
for (int i = 1; i <= n; i++)
{
ll ans = 0;
int ca = i / 2;
int cb = i - ca;
if (i < 2)
{
cout << 0 << endl;
continue;
}
ll res = 1;
if (ca <= x)
{
res = res * c[x - 1][ca - 1] % mod;
}
else
{
res = 0;
}
if (cb <= y)
{
res = res * c[y - 1][cb - 1] % mod;
}
else
{
res = 0;
}
ans += res;
ans %= mod;
res = 1;
swap(ca, cb);
if (ca <= x)
{
res = res * c[x - 1][ca - 1] % mod;
}
else
{
res = 0;
}
if (cb <= y)
{
res = res * c[y - 1][cb - 1] % mod;
}
else
{
res = 0;
}
ans += res;
ans %= mod;
cout << ans << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}