2024.12.12 周四
Q1. 1000
You have an array $a$ of $n$ integers.
You can no more than once apply the following operation: select three integers $i$, $j$, $x$ ($1 \le i \le j \le n$) and assign all elements of the array with indexes from $i$ to $j$ the value $x$. The price of this operation depends on the selected indices and is equal to $(j - i + 1)$ burles.
What is the least amount of burles you need to spend to make all the elements of the array equal?
Q2. 1000
You are given a positive integer $n$.
Find a permutation$^\dagger$ $p$ of length $n$ such that there do not exist two distinct indices $i$ and $j$ such that $p_i$ divides $p_j$ and $p_{i+1}$ divides $p_{j+1}$.
Under the constraints of this problem, it can be proven that at least one $p$ exists.
Q3. 1000
Given an array $a$ of $n$ integers, an array $b$ of $m$ integers, and an even number $k$.
Your task is to determine whether it is possible to choose exactly $\frac{k}{2}$ elements from both arrays in such a way that among the chosen elements, every integer from $1$ to $k$ is included.
Q4. 1000
A certain number $1 \le x \le 10^9$ is chosen. You are given two integers $a$ and $b$, which are the two largest divisors of the number $x$. At the same time, the condition $1<=a<b<x$ is satisfied.
For the given numbers $a$, $b$, you need to find the value of $x$.
Q5. 1000
You are given a binary string $s$.
You can perform two types of operations on $s$:
- delete one character from $s$. This operation costs $1$ coin;
- swap any pair of characters in $s$. This operation is free (costs $0$ coins).
You can perform these operations any number of times and in any order.
Let's name a string you've got after performing operations above as $t$. The string $t$ is good if for each $i$ from $1$ to $|t|$ $t_i \neq s_i$ ($|t|$ is the length of the string $t$). The empty string is always good. Note that you are comparing the resulting string $t$ with the initial string $s$.
What is the minimum total cost to make the string $t$ good?
------------------------独自思考分割线------------------------
-
Q2构造 Q4数论 比较有意思
A1.
- 发现只有3种情况，找边界枚举即可。
A2.
- 倍数就一定相差至少一倍。
- 如何构造使相邻的2个数都无法找到倍数，1~n存在一半的数无法找到其倍数，因此考虑存在倍数与不存在倍数的数相邻。如：1 n 2 n-1 3 n-2...
A3.
- 变量维护两数组选的数的个数，map维护两数组有的数。
- 遍历1~k：考虑独有的，直接加入，若不能加入/都没有则无解。共有的不需要考虑，因为只要二者选的数次数满足，最后一定可以满足。
A4.
- 对 $x$ 因式分解，b=x/p1,a=x/p1 $or$ x/p2，...嗯..是道好题。
A5.
- 任意交换代表任意安排，贪心从前向后构造，直到不能构造，删除剩下的。
------------------------代码分割线------------------------
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 _()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
int res = n;
int l = 1;
for (; l + 1 <= n && a[l + 1] == a[1]; l++)
;
res = min(res, n - l);
int r = n;
for (; r > 1 && a[r - 1] == a[n]; r--)
;
res = min(res, r - 1);
if (a[1] == a[n])
{
if (l >= r)
res = 0;
else
res = min(res, r - l - 1);
}
cout << res << 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;
int l = 1, r = n;
int f = 1;
while (l <= r)
{
if (f)
cout << l << ' ', l++;
else
cout << r << ' ', r--;
f ^= 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, m, k;
cin >> n >> m >> k;
map<int, int> ka, kb;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
ka[x] = 1;
}
for (int i = 0; i < m; i++)
{
int x;
cin >> x;
kb[x] = 1;
}
bool ans = 1;
int cnta = 0, cntb = 0;
for (int i = 1; i <= k; i++)
if (ka[i] + kb[i] == 1)
{
int f = 0;
if (ka[i] && cnta < k / 2)
cnta++, f = 1;
if (kb[i] && cntb < k / 2)
f = 1, cntb++;
if (!f)
ans = f;
}
else if (ka[i] + kb[i] == 0)
ans = 0;
cout << (ans ? "YES" : "NO") << endl;
}
// void _()
// {
// int n, m, k;
// cin >> n >> m >> k;
// map<int, int> ka, kb;
// for (int i = 0; i < n; i++)
// {
// int x;
// cin >> x;
// ka[x]++;
// }
// for (int i = 0; i < m; i++)
// {
// int x;
// cin >> x;
// kb[x]++;
// }
// set<int> K;
// int cnta = 0, cntb = 0;
// for (int i = 1; i <= k; i++)
// if (ka[i] + kb[i] == 1)
// {
// if (ka[i] && cnta < k / 2)
// K.insert(i), cnta++;
// if (kb[i] && cntb < k / 2)
// K.insert(i), cntb++;
// }
// for (int i = 1; i <= k; i++)
// if (ka[i] + kb[i] > 1)
// {
// if (cnta < k / 2)
// {
// if (ka[i])
// {
// K.insert(i), cnta++;
// continue;
// }
// }
// if (cntb < k / 2)
// {
// if (kb[i])
// {
// K.insert(i), cntb++;
// continue;
// }
// }
// }
// cout << (K.size() == k ? "YES" : "NO") << endl;
// }
A4.
#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 a, b;
cin >> a >> b;
auto get = [](int n)
{
for (int i = 2; i <= n / i; i++)
if (n % i == 0)
return i;
return n;
};
int res = b * b / a;
if (b % a)
res = b * get(a);
cout << res << endl;
}
A5
#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;
int n = s.size();
s = " " + s;
int cnt0 = 0;
for (int i = 1; i <= n; i++)
cnt0 += s[i] == '0';
int cnt1 = n - cnt0;
int res = 0;
// bug2(cnt0, cnt1);
for (int i = 1; i <= n; i++)
{
if (s[i] == '0')
{
if (!cnt1)
{
res = n - (i - 1);
break;
}
cnt1--;
}
else
{
if (!cnt0)
{
res = n - (i - 1);
break;
}
cnt0--;
}
}
cout << res << endl;
}