2024.12.18 周三
Q1. 1000
You have an array of zeros a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an of length n n n.
You can perform two types of operations on it:
- Choose an index i i i such that 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n and a i = 0 a_i = 0 ai=0, and assign 1 1 1 to a i a_i ai;
- Choose a pair of indices l l l and r r r such that 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n, a l = 1 a_l = 1 al=1, a r = 1 a_r = 1 ar=1, a l + … + a r ≥ ⌈ r − l + 1 2 ⌉ a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil al+…+ar≥⌈2r−l+1⌉, and assign 1 1 1 to a i a_i ai for all l ≤ i ≤ r l \le i \le r l≤i≤r.
What is the minimum number of operations of the first type needed to make all elements of the array equal to one?
Q2. 1000
Fedya is playing a new game called “The Legend of Link”, in which one of the character’s abilities is to combine two materials into one weapon. Each material has its own strength, which can be represented by a positive integer x x x. The strength of the resulting weapon is determined as the sum of the absolute differences of the digits in the decimal representation of the integers at each position.
Formally, let the first material have strength X = x 1 x 2 … x n ‾ X = \overline{x_{1}x_{2} \ldots x_{n}} X=x1x2…xn, and the second material have strength Y = y 1 y 2 … y n ‾ Y = \overline{y_{1}y_{2} \ldots y_{n}} Y=y1y2…yn. Then the strength of the weapon is calculated as ∣ x 1 − y 1 ∣ + ∣ x 2 − y 2 ∣ + … + ∣ x n − y n ∣ |x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}| ∣x1−y1∣+∣x2−y2∣+…+∣xn−yn∣. If the integers have different lengths, then the shorter integer is padded with leading zeros.
Fedya has an unlimited supply of materials with all possible strengths from L L L to R R R, inclusive. Help him find the maximum possible strength of the weapon he can obtain.
An integer C = c 1 c 2 … c k ‾ C = \overline{c_{1}c_{2} \ldots c_{k}} C=c1c2…ck is defined as an integer obtained by sequentially writing the digits c 1 , c 2 , … , c k c_1, c_2, \ldots, c_k c1,c2,…,ck from left to right, i.e. 1 0 k − 1 ⋅ c 1 + 1 0 k − 2 ⋅ c 2 + … + c k 10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k 10k−1⋅c1+10k−2⋅c2+…+ck.
Q3. 1000
You are given two arrays a a a and b b b both of length n n n.
You will merge † ^\dagger † these arrays forming another array c c c of length 2 ⋅ n 2 \cdot n 2⋅n. You have to find the maximum length of a subarray consisting of equal values across all arrays c c c that could be obtained.
† ^\dagger † A merge of two arrays results in an array c c c composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of c c c. We repeat this operation as long as we can (i.e. at least one array is nonempty).
Q4. 1000
LuoTianyi gave an array b b b of n ⋅ m n \cdot m n⋅m integers. She asks you to construct a table a a a of size n × m n \times m n×m, filled with these n ⋅ m n \cdot m n⋅m numbers, and each element of the array must be used exactly once. Also she asked you to maximize the following value:
∑ i = 1 n ∑ j = 1 m ( max 1 ≤ x ≤ i , 1 ≤ y ≤ j a x , y − min 1 ≤ x ≤ i , 1 ≤ y ≤ j a x , y ) \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left(\max\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}-\min\limits_{1 \le x \le i, 1 \le y \le j}a_{x,y}\right) i=1∑nj=1∑m(1≤x≤i,1≤y≤jmaxax,y−1≤x≤i,1≤y≤jminax,y)
This means that we consider n ⋅ m n \cdot m n⋅m subtables with the upper left corner in ( 1 , 1 ) (1,1) (1,1) and the bottom right corner in ( i , j ) (i, j) (i,j) ( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n, 1 ≤ j ≤ m 1 \le j \le m 1≤j≤m), for each such subtable calculate the difference of the maximum and minimum elements in it, then sum up all these differences. You should maximize the resulting sum.
Help her find the maximal possible value, you don’t need to reconstruct the table itself.
------------------------独自思考分割线------------------------
A1.
- 贪心构造，首先两端必须有，自左向右贪心找中间点，发现其坐标最大为 l a s t + 1 < < 1 last+1<<1 last+1<<1 。
A2.
- 模拟数位发现，在等长度情况下，以第一个不同点为分界线，前面每一位最大贡献就是 b [ i ] − ′ 0 ′ b[i]-'0' b[i]−′0′ ，后面每一位最大贡献就是 9 9 9。
- 本质就是考虑每一位数的取值范围，相同前缀下 a [ i ] a[i] a[i] 只能取 [ 0 , b [ i ] ] [0,b[i]] [0,b[i]] ，否则可取 [ 0 , 9 ] [0,9] [0,9] 。
A3.
- 将连续相同的数看成一块，根据构造方案，同一数组的相同数的2块不可能合并，不同数组则一定可以合并。
- 那答案显而易见，记录每个数所在块的最大值，答案就是每个数在两数组块的和的最大值。
- 写的时候直接枚举 a a a 数组去另一数组找另外的数wa2发，扒数据也没找到原因，果然wa了只有思路/代码有问题，这种情况就是没有考虑一个数没有在两个数组都存在的情况。
A4.
- 贪心构造，将极差最大的几个数放在左上角， ( 2 , 2 ) (2,2) (2,2) 到 ( n , m ) (n,m) (n,m) 一定可以构造出 m a x − m i n max-min max−min ，还剩下第一行和第一列。
- 考虑将 m a x 1 max1 max1 放 ( 1 , 1 ) (1,1) (1,1) m i n 1 / m i n 2 min1/min2 min1/min2 放 ( 2 , 1 ) / ( 1 , 2 ) (2,1)/(1,2) (2,1)/(1,2)，同时最小值也可放左上角，维护最大值、次大值、最小值、次小值。同时考虑行列，设置函数进行4次计算即可。显然没有方案更优。
------------------------代码分割线------------------------
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;
int res = 2;
int st = 4;
for (; st < n; st = st + 1 << 1)
res++;
if (n == 1)
res = 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 _()
{
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
string t(max(n, m) - min(n, m), '0');
if (n < m)
a = t + a;
else
b = t + b;
n = max(n, m);
int f = 0, res = 0;
for (int i = 0; i < n; i++)
{
if (!f && a[i] == b[i])
continue;
res += f ? 9 : abs(b[i] - a[i]);
if (a[i] - b[i])
f = 1;
}
cout << res << 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;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
map<int, int> la, lb;
auto get = [&](vector<int> &a, map<int, int> &la)
{
for (int i = 1; i <= n; i++)
{
int j = i;
for (; j <= n && a[j] == a[i]; j++)
;
la[a[i]] = max(la[a[i]], j - i);
i = j - 1;
}
};
get(a, la);
get(b, lb);
int res = 0;
for (int i = 1; i <= n << 1; i++)
res = max(res, la[i] + lb[i]);
// for (auto [x, v] : la)
// res = max(res, v + lb[x]);
cout << res << 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 n, m;
cin >> n >> m;
vector<int> a(n * m);
for (int &x : a)
cin >> x;
sort(a.begin(), a.end());
int max1 = a.back(), max2 = a[a.size() - 2];
int min1 = a[0], min2 = a[1];
int res = (n - 1) * (m - 1) * (max1 - min1);
auto cal = [&](int a, int b, int c)
{
return (n - 1) * abs(b - a) + (m - 1) * abs(c - a);
};
vector<int> t{cal(max1, min1, min2), cal(max1, min2, min1), cal(min1, max2, max1), cal(min1, max1, max2)};
sort(t.rbegin(), t.rend());
res += t[0];
cout << res << endl;
}