2024.12.13 周五
Q1. 1000
Polycarp has a problem — his laptop keyboard is broken.
Now, when he presses the 'b' key, it acts like an unusual backspace: it deletes the last (rightmost) lowercase letter in the typed string. If there are no lowercase letters in the typed string, then the press is completely ignored.
Similarly, when he presses the 'B' key, it deletes the last (rightmost) uppercase letter in the typed string. If there are no uppercase letters in the typed string, then the press is completely ignored.
In both cases, the letters 'b' and 'B' are not added to the typed string when these keys are pressed.
Given a sequence of pressed keys, output the typed string after processing all key presses.
Q2. 1000
You are given an array $a_1, a_2, \ldots, a_n$. You need to find an array $b_1, b_2, \ldots, b_n$ consisting of numbers $1$, $2$, $3$ such that exactly two out of the following three conditions are satisfied:
- There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 1$, $b_j = 2$.
- There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 1$, $b_j = 3$.
- There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 2$, $b_j = 3$.
If such an array does not exist, you should report it.
Q3. 1000
You are given an array of integers $a_1, a_2, \ldots, a_n$ and a number $k$ ($2 \leq k \leq 5$). In one operation, you can do the following:
- Choose an index $1 \leq i \leq n$,
- Set $a_i = a_i + 1$.
Find the minimum number of operations needed to make the product of all the numbers in the array $a_1 \cdot a_2 \cdot \ldots \cdot a_n$ divisible by $k$.
------------------------独自思考分割线------------------------
-
这分段的题，构造，数论，位运算比较有挑战性，其他的题对码力有点要求。果然codeforces的题目质量都很高，没有浪费时间这一说。
A1.
- 模拟，set/map/stack/倒叙统计个数模拟均可。
A2.
- 结论构造，需要发现至少有两个块有至少2个相同的数构造任意2种情况即可。过程需要点技巧性。
- 注意i,j没有大小关系，如果有，一个块有3个相同的数即可构造。
A3.
- 若被2,3,5整除，就必须有一个数包含其作为质因子，将一个数改为其倍数即可。
- 被4整除时，考虑2种情况：1.将一个数改为4的倍数，2.将2个数改为2的倍数。取最小代价即可。
------------------------代码分割线------------------------
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
string s;
cin >> s;
set<int> low, high;
vector<int> del(s.size());
for (int i = 0; i < s.size(); i++)
if (s[i] == 'b')
{
if (low.size())
{
int x = *(low.rbegin());
del[x] = 1,
low.erase(x);
}
}
else if (s[i] == 'B')
{
if (high.size())
{
int x = *(high.rbegin());
del[x] = 1;
high.erase(x);
}
}
else
{
if (islower(s[i]))
low.insert(i);
else
high.insert(i);
}
for (int i = 0; i < s.size(); i++)
if (s[i] != 'b' && s[i] - 'B' && !del[i])
cout << s[i];
cout << endl;
}
A2.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
struct Node
{
/* data */
int a, b = 1, i;
};
vector<Node> A(n);
int id = 0;
for (auto &[a, b, i] : A)
{
cin >> a;
i = id++;
}
sort(A.begin(), A.end(), [](Node &a, Node &b)
{ return a.a < b.a; });
int f2 = 0, f3 = 0;
for (int i = 0; i < n; i++)
{
if (i && A[i - 1].a == A[i].a)
{
if (!f2)
A[i].b = 2, f2 = A[i].a;
else if (f2 - A[i].a)
A[i].b = 3, f3 = 1;
}
}
sort(A.begin(), A.end(), [](Node &a, Node &b)
{ return a.i < b.i; });
if (f2 && f3)
for (auto [a, b, i] : A)
cout << b << ' ';
else
cout << -1;
cout << endl;
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
int even = 0;
for (auto &v : a)
{
cin >> v;
if (v % 2 == 0)
even++;
}
auto get = [&](int k)
{
int res = 1e9;
for (auto v : a)
res = min(res, (k - v % k) % k);
return res;
};
int res = get(k);
if (k == 4)
res = min(res, 2 - min(2ll, even)); // the range of even
cout << res << endl;
}