Codeforces Round 925 (Div. 3)
A - Recovering a Small String
解题思路:
枚举.
代码:
#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;
cin >> n;
for (int i = 1; i <= 26; i++)
{
for (int j = 1; j <= 26; j++)
{
for (int k = 1; k <= 26; k++)
{
if (i + j + k == n)
{
char a = 'a' + i - 1;
char b = 'a' + j - 1;
char c = 'a' + k - 1;
cout << a << b << c << endl;
return;
}
}
}
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Make Equal
解题思路:
遍历时累计可用水量，如果过程中有缺水的无法补充到均值，则不可均分。
代码:
#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;
cin >> n;
vector<ll> a(n + 1);
ll s = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s += a[i];
}
ll avg = s / n;
ll res = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] > avg)
{
res += a[i] - avg;
}
else
{
if (res >= avg - a[i])
{
res -= avg - a[i];
}
else
{
puts("NO");
return;
}
}
}
puts("YES");
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Make Equal Again
解题思路:
要想一次解决，能保留的只有左段和右段。
判断左右段保留情况即可。
代码:
#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;
cin >> n;
vector<int> a(n + 1);
int ans = 1e9;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
if (i == 1)
{
cnt = 1;
}
else
{
if (a[i] == a[i - 1])
{
cnt++;
}
else
{
ans = min(ans, n - cnt);
break;
}
}
}
ans = min(ans, n - cnt);
if (ans != 0)
{
for (int i = n; i; i--)
{
if (i == n)
{
if (a[i] == a[1])
{
cnt++;
}
else
{
cnt = 1;
}
}
else
{
if (a[i] == a[i + 1])
{
cnt++;
}
else
{
ans = min(ans, n - cnt);
break;
}
}
}
}
ans = min(ans, n - cnt);
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Divisible Pairs
解题思路:
- \(a + b \equiv 0 \mod x\)
- \(a - b \equiv 0 \mod y\)
所以分别记录每个数对\((x,y)\)的余数，然后遍历判断一遍即可。
代码:
#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>>;
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
ll n, x, y;
cin >> n >> x >> y;
ll g = gcd(x, y);
ll ans = 0;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
{
int t;
cin >> t;
a[i] = t % x;
b[i] = t % y;
}
map<pii, int> cnt;
for (int i = 1; i <= n; i++)
{
int m1 = (x - a[i]) % x;
int m2 = b[i];
ans += cnt[{m1, m2}];
cnt[{a[i], b[i]}]++;
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Anna and the Valentine's Day Gift
解题思路:
记录每个数后面有多少个\(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, m;
cin >> n >> m;
vector<int> a(n + 1), v;
ll s = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
int x = a[i];
int cnt = 0;
while (x % 10 == 0)
{
cnt++;
x /= 10;
}
if (cnt)
{
v.push_back(cnt);
}
x = a[i];
cnt = 0;
while (x)
{
cnt++;
x /= 10;
}
s += cnt;
}
sort(v.begin(), v.end());
int cur = 1;
while (v.size())
{
auto t = v.back();
v.pop_back();
if (cur & 1)
{
s -= t;
}
cur ^= 1;
}
if (s > m)
{
puts("Sasha");
}
else
{
puts("Anna");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
F - Chat Screenshots
解题思路:
建图跑拓扑序判环。
代码:
#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, k;
cin >> n >> k;
int last = 0;
vector<vector<int>> e(n + 1, vector<int>());
vector<int> indeg(n + 1, 0);
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= n; j++)
{
int x;
cin >> x;
if (j > 2)
{
e[last].push_back(x);
indeg[x]++;
}
last = x;
}
}
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (indeg[i] == 0)
{
q.push(i);
}
}
while (q.size())
{
auto u = q.front();
q.pop();
for (auto v : e[u])
{
indeg[v]--;
if (indeg[v])
{
continue;
}
q.push(v);
}
}
for (int i = 1; i <= n; i++)
{
if (indeg[i])
{
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
G - One-Dimensional Puzzle
解题思路:
\(1,2\)得交替出现。所以二者数量不能差距过大。
\(3,4\)能无限自拼接。
\(3\)连续段能出现在\(2\)前\(1\)后，\(4\)连续段能出现在\(2\)后\(1\)前。
所以，构建出\((1,2)\)基本的交替情况，然后考虑插入\(3,4\)的方法即可。
代码:
#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 = 2e6;
const int mod = 998244353;
ll f[N + 1];
ll invf[N + 1];
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 init()
{
f[0] = invf[0] = 1;
for (int i = 1; i <= N; i++)
{
f[i] = f[i - 1] * i % mod;
}
invf[N] = qmi(f[N], mod - 2) % mod;
for (int i = N - 1; i; i--)
{
invf[i] = invf[i + 1] * (i + 1) % mod;
}
}
ll C(ll a, ll b)
{
if (a < b || b < 0)
{
return 0;
}
return ((f[a] * invf[b]) % mod * invf[a - b]) % mod;
}
void solve()
{
ll a, b, c, d;
cin >> a >> b >> c >> d;
ll ans = 0;
if (abs(a - b) > 1)
{
ans = 0;
}
else if (a == 0 && b == 0)
{
if (c == 0 || d == 0)
{
ans = 1;
}
}
else if (a == b - 1)
{
ans = (C(b - 1 + d, b - 1) * C(b - 1 + c, b - 1)) % mod;
}
else if (b == a - 1)
{
ans = (C(a - 1 + c, a - 1) * C(a - 1 + d, a - 1)) % mod;
}
else
{
ans = (((C(a + 1 - 1 + c, a) * C(b - 1 + d, b - 1)) % mod) + ((C(b + 1 - 1 + d, b) * C(a - 1 + c, a - 1)) % mod)) % mod;
}
cout << ans << endl;
}
int main()
{
init();
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}