Educational Codeforces Round 163 (Rated for Div. 2)
A - Special Characters
解题思路:
一个相同的连续段会贡献两个特殊字符，所以答案一定是偶数，找个不同的数分隔开即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
int n;
cin >> n;
if (n & 1)
{
puts("NO");
return;
}
string a = "AA";
string b = "B";
string ans;
n /= 2;
for (int i = 1; i <= n; i++)
{
ans += a + b;
}
puts("YES");
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Array Fix
解题思路:
从左到右找到最后一个\(a_i > a_{i + 1}\)，记录\(idx = i\)。
对于\(1 \sim i\)都进行操作，然后从左到右判断合法即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int idx = -1;
for (int i = 1; i <= n - 1; i++)
{
if (a[i] > a[i + 1])
{
idx = i;
}
}
if (idx == -1)
{
puts("YES");
return;
}
vector<int> ans;
for (int i = 1; i <= idx; i++)
{
int x = a[i];
vector<int> t;
while (x)
{
t.push_back(x % 10);
x /= 10;
}
reverse(t.begin(), t.end());
for (auto c : t)
{
ans.push_back(c);
}
if (a[i] == 0)
{
ans.push_back(0);
}
}
for (int i = idx + 1; i <= n; i++)
{
ans.push_back(a[i]);
}
// cout << ans[0] << endl;
for (int i = 1; i < ans.size(); i++)
{
// cout << ans[i] << endl;
if (ans[i] < ans[i - 1])
{
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Arrow Path
解题思路:
分类讨论:
- 右边为\(>\):向右走两格。
- 右边为\(<\):不动。
- 下边为\(>\):向右下走。
- 下边为\(<\):向左下走。
- 左边为\(<\):向左走两格。尝试举例后发现没必要。
- 左边为\(>\):不动。
从\((1, 1)\)开始合法转移即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
void solve()
{
int n;
cin >> n;
vector<string> g(3);
vector<vector<int>> dp(6, vector<int>(n + 10, 0));
for (int i = 1; i <= 2; i++)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
dp[1][1] = 1;
for (int j = 1; j <= n; j++)
{
for (int i = 1; i <= 2; i++)
{
if (i == 1)
{
if (g[i + 1][j] == '>')
{
dp[i + 1][j + 1] |= dp[i][j];
}
else
{
dp[i + 1][j - 1] |= dp[i][j];
}
if (g[i][j + 1] == '>')
{
dp[i][j + 2] |= dp[i][j];
}
}
else
{
if (g[i - 1][j] == '>')
{
dp[i - 1][j + 1] |= dp[i][j];
}
else
{
dp[i - 1][j - 1] |= dp[i][j];
}
if (g[i][j + 1] == '>')
{
dp[i][j + 2] |= dp[i][j];
}
}
}
}
if (dp[2][n])
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Tandem Repeats?
解题思路:
枚举合法串的长度，然后枚举串的起点。
举例：\(abcabda\)。
假设我们一半长度为\(3\)，对于\(abc,abd\)是不合法的，那么从\(b\)开始，也就是\(bca,bda\)一定也是不合法的。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
void solve()
{
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
int ans = 0;
for (int len = n / 2; len > 0; len--)
{
int cnt = 0;
for (int i = 1; i + len <= n; i++)
{
if (s[i] == '?' || s[i + len] == '?' || s[i] == s[i + len])
{
cnt++;
if (cnt == len)
{
ans = max(ans, cnt);
break;
}
}
else
{
cnt = 0;
}
}
}
cout << ans * 2 << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Clique Partition
解题思路:
因为\((i,j)\)相近的两个数，\(abs(i - j)\)小，所以应该是一个一个连续区间中的数为一个团。
\((1, 2,3,4,5,6,7,8,9,10),k = 8\)。
\(abs(1 - 9)=8,a_1 \neq a_9\)，所以理论上，相隔\(8\)的两个数不会在一个团中。同理可推广到\(k\)。
考虑能否让\(abs(i - j) < k\)的数都在一个团中。
考虑\(abs(i - j)\)较大的点对，由于下标差已经较大，我们需要让点权差尽量小。
对于\((1, 8)\)，\(abs(1-8)=7\)，所以\(a_1 - a_8 = 1\)才能使二者符合连边条件。
尝试后发现，最平衡的方法为
\[\begin{align*} i:\ &1,2,3,4,5,6,7,8 \\ a_i:\ &4,3, 2, 1,8,7,6,5 \end{align*} \]所以，从左到右，每\(k\)个这样进行构造，最后多出不足\(k\)个的，就按照剩余个数进行构造。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int N = 110;
int ans;
int a[N];
int c[N];
void dfs(int i, int n, int k, int id)
{
if (i > n)
{
return;
}
ans = id;
// 当前团中的点数
int num = min(n - i + 1, k);
int cur = i;
// 1 2 3 4
// 4 3 2 1
for (int j = i + num / 2 - 1; j >= i; j--)
{
a[j] = cur++;
c[j] = id;
}
// 5 6 7 8
// 8 7 6 5
for (int j = i + num - 1; j >= i + num / 2; j--)
{
a[j] = cur++;
c[j] = id;
}
dfs(i + num, n, k, id + 1);
}
void solve()
{
int n, k;
cin >> n >> k;
dfs(1, n, k, 1);
for (int i = 1; i <= n; i++)
{
cout << a[i] << " \n"[i == n];
}
cout << ans << "\n";
for (int i = 1; i <= n; i++)
{
cout << c[i] << " \n"[i == n];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
F - Rare Coins
解题思路:
区间内金币有\(g_1\)个，银币有\(s_1\)个。区间外有金币\(g_2\)个，银币\(s_2\)个。
我们设区间内有\(a\)个银币为\(1\)，区间外有\(b\)个银币为\(0\)。
\[\begin{align*} g_1 + a &> g_2 + s_2 - b\\ a + b &> g_2 + s_2 -g_1\\ a + b &\geq g_2 + s_2 - g_1 + 1 \end{align*} \]其中，\((g_2 + s_2-g_1+1 \leq a + b\leq s1 + s2)\)。
\[\sum\limits_{a + b = g_2 + s_2 - g_1 + 1}^{s1 + s2}\sum\limits_{k = 0}^{a + b}C_{s_1}^{k}C_{s_2}^{a + b - k} \]范德蒙德卷积：
\[\sum\limits_{i=0}^{k}C_{a}^i C_b^{k - i} = C_{a + b}^{k} \]所以:
\[\sum\limits_{a + b = g_2 + s_2 - g_1 + 1}^{s1 + s2}\sum\limits_{k = 0}^{a + b}C_{s_1}^{k}C_{s_2}^{a + b - k}=\sum\limits_{a + b = g_2 + s_2 - g_1 + 1}^{s1 + s2}C_{s_1+s_2}^{a+b} \]我们已经求出了所有区间内价值大于区间外价值的情况，最后记得乘上\((\frac{1}{2})^{s_1 + s_2}\)的逆元。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;
const int N = 1e6 + 10;
ll f[N];
ll inv[N];
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a % mod;
}
b >>= 1;
a = a * a % mod;
}
return res;
}
void init()
{
const int n = 1e6;
f[0] = inv[0] = 1;
for (int i = 1; i <= n; i++)
{
f[i] = f[i - 1] * i % mod;
}
inv[n] = qmi(f[n], mod - 2);
for (int i = n - 1; i >= 1; i--)
{
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}
ll C(ll a, ll b)
{
if (a < 0 || b < 0 || a < b)
return 0;
return (f[a] * inv[b] % mod) * (inv[a - b]) % mod;
}
void solve()
{
int n, q;
cin >> n >> q;
vector<array<ll, 2>> s(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> s[i][0];
s[i][0] += s[i - 1][0];
}
for (int i = 1; i <= n; i++)
{
cin >> s[i][1];
s[i][1] += s[i - 1][1];
}
const ll m = s[n][1];
vector<ll> pre(m + 1);
for (int i = 0; i <= m; i++)
{
pre[i] = C(m, i) % mod;
}
for (int i = 1; i <= m; i++)
{
pre[i] = (pre[i] + pre[i - 1]) % mod;
}
ll d = qmi(qmi(2, m), mod - 2) % mod;
auto get = [&](ll l, ll r) -> ll
{
if (l > r)
{
return 0;
}
return pre[m] - (l >= 1 ? pre[l - 1] : 0) + mod;
};
while (q--)
{
int l, r;
cin >> l >> r;
ll g1 = s[r][0] - s[l - 1][0];
ll s1 = s[r][1] - s[l - 1][1];
ll g2 = s[n][0] - g1;
ll s2 = s[n][1] - s1;
// g1 + a > g2 + s2 - b
// a + b >= g2 + s2 - g1 + 1
// g2 + s2 - g1 + 1 ~ s1 + s2
// C(s1, a) * C(s2, b) -> C(s1 + s2, a + b) (g2 + s2 - g1 + 1 <= a + b <= s1 + s2)
// m = s1 + s2
// cout << g2 + s2 - g1 + 1 << ' ' << m << endl;
cout << (get(g2 + s2 - g1 + 1, m) * d) % mod << ' ';
}
cout << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}