Question address
/contest/2093
Sharp comments
When all the questions are understood correctly, the overall difficulty is not too difficult. But there is such a disgusting question as F, and the examples are not explained, so I can't understand the question at all. Question D is also disgusting, because the splitting of the recursive process requires math, just like printing recursively defined figures, it’s awkward to write, but fortunately it’s passed. E-question actually has double card\(log\)The practice constant is also disgusting. On the contrary, the G question is very classic and too naked, but unfortunately I was blocked by D and I didn’t see the G question at all. I fell into the curse of "I can't write after reading all the questions, but I can write after reading all the questions." The main reason is that I am too mean and cannot break this curse, so the big guys will not have this trouble.
Question explanation
Problem A. Ideal Generator
The main idea of the topic
Depend on\(k\)Array of positive integers\(a\)exist\([a_1, a_2, \dots, a_k] = [a_k, a_{k-1}, \dots, a_1]\)In the case of , it is called palindrome array (in fact, it is the same when reading forward and reading reversely). For example, arrays\([1, 2, 1]\)and\([5, 1, 1, 5]\)is a palindrome array, and array\([1, 2, 3]\)and\([21, 12]\)Not a palindrome array.
If any integer\(n\) ( \(n \geq k\)) can be expressed as a length exactly\(k\)We call this number the sum of elements of the palindrome array\(k\)Generate numbers for ideals. Each element in the array must be greater than\(0\) 。
For example, numbers\(1\)is an ideal number because any natural number\(n\)All can use arrays\([n]\)generate. However, the numbers\(2\)Not an ideal generation number, because there is no length\(2\)The sum of\(3\)palindrome array.
Please judge the given number\(k\)Is it an ideal number to generate.
Question solution: Thinking
First observe through the example and find that odd numbers are OK but even numbers are not OK. Start verification, if the sum is\(k\), then all array elements are\(1\)That's right, if the\(k + 1\), then all array elements are\(1\)Based on, there is a number to be added\(1\)If it is a palindrome array, it can only be placed in the middle position, otherwise the position where the position is placed is symmetrical will not be equal. Again because\(n\)It is continuous, so the difference is\(1\)Only if the array length is an odd number can it be satisfied, and it will be added at the middle position every time.\(1\). Time complexity is\(O(1)\) 。
Reference Code (C++)
#include <bits/stdc++.h>
using namespace std;
int n;
void solve() {
cin >> n;
cout << ((n & 1) ? "YES\n" : "NO\n");
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Problem B. Expensive Number
The main idea of the topic
Positive integer\(n\)The cost is defined as a number\(n\)The result of dividing by the sum of its digits.
For example, numbers\(104\)The price is\(\frac{104}{1 + 0 + 4} = 20.8\),number\(111\)The price is\(\frac{111}{1 + 1 + 1} = 37\) 。
Give you a positive integer that does not contain leading zeros\(n\). You can get from the numbers\(n\)delete any digit (including not deleted), so that the remaining digits contain at least one digit, andStrictly greater than zero. The remaining numbersCan't be rearranged. Therefore, youpossibleGet a number with leading zero.
For example, give you a number\(103554\). If removed\(1\) 、 \(4\)and a number\(5\), the final number is\(035\), the price is\(\frac{035}{0 + 3 + 5} = 4.375\) 。
To minimize the cost, how many minimum numbers do you need to remove from this number?
Question answering: Greedy
First of all, the sum of digits of a number cannot be greater than this number, at most equal to it. So what does the minimum cost mean? Obviously equality. So only one digital age has the lowest price, and the price is\(1\). Because the question is allowed to have a leading one after deleting the digits\(0\), so select the preceding number\(0\)Can not be deleted. Also, because the number composed after deletion must be strictly greater than\(0\), so we want to find a non\(0\)Digital. Because the leading\(0\)Can be retained, guided\(0\)Can't be retained (reservation is not single digits), so we enumerate backwards and find the first non\(0\)Digital position, the non-in front of this position\(0\)Digital deletion and subsequent digital deletion, the number of deleted digital digits is the answer. Time complexity is\(O(n)\) 。
Reference Code (C++)
#include <bits/stdc++.h>
using namespace std;
string str;
void solve() {
cin >> str;
int n = ();
int id = n - 1;
for (int i = n - 1; i >= 0; --i)
if (str[i] != '0') {
id = i;
break;
}
int ans = n - 1 - id;
for (int i = id - 1; i >= 0; --i)
if (str[i] != '0')
++ans;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Problem C. Simple Repetition
The main idea of the topic
Pasha likes prime numbers! In order to find a new way to generate prime numbers, he once again became interested in an algorithm on the Internet:
- To get a new number\(y\),repeat\(k\)Number\(x\)Decimal representation of\(x\)(Excluding leading zeros).
For example,\(x = 52\)and\(k = 3\)Can get\(y = 525252\) ， \(x = 6\)and\(k = 7\)Can get\(y = 6666666\) 。
The numbers Pasha really hopes to get\(y\)It is a prime number, but he does not know how to test the qualitativeness of the numbers generated by this algorithm. Please help Pasha and tell him\(y\)Is it a prime number?
If an integer x has only 2 different divisors 1 and x , then this integer x is a prime number. For example, 13 is a prime number because it has only 2 divisors: 1 and 13 . Note that the number 1 is not a prime number because it has only one divisor.
Question solution: Thinking/Classification discussion
Let’s analyze it one by one.
- \(k = 1\)Obviously only need to be judged\(x\)Whether it is a prime number.
- \(k \gt 1\),Right now\(x\)At least it's repeated\(2\)Time, set\(x\)have\(n\)digits, then\(y\)Obviously there is a divisor\(x\), make\(\frac{y}{x} = a_1 \underbrace{0 \cdots 0}_{n - 1} a_2 \underbrace{0 \cdots 0}_{n - 1} \dots a_k\),in\(a_i = 1, 1 \leq i \leq k\). Then just\(1 \lt x \lt y\) ， \(y\)It must not be a prime number, obviously\(x \lt y\)It must be true, so you just need to make a separate judgment\(x\)for\(1\)Just in the case of
Based on the above analysis, the problem is solved. Time complexity is\(O(1)\) 。
Reference Code (C++)
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool check(int x) {
if (x < 2)
return false;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
void solve() {
cin >> n >> m;
if (m == 1)
cout << (check(n) ? "YES\n" : "NO\n");
else if (n == 1) {
int x = 0;
for (int i = 0; i < m; ++i)
x = x * 10 + 1;
cout << (check(x) ? "YES\n" : "NO\n");
} else
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Problem D. Skibidi Table
The main idea of the topic
Wadium likes to fill square tables with integers. But today he thought of a fun way! In size\(2 \times 2\)For example, the rows of the table are numbered from top to bottom and the columns are numbered from left to right. we will\(1\)Place in the upper left cell,\(2\)Place in the cell in the lower right corner,\(3\)Place in the lower left cell,\(4\)Place in the upper right cell. That's all he needs to have fun!
Fortunately, Vadim has a size of\(2^n \times 2^n\)form. He plans to use\(1\)arrive\(2^{2n}\)The integer fills it in ascending order. To fill such a big table, Vadim will divide it into\(4\)For an equal square table, first fill the table in the upper left corner, then fill the table in the lower right corner, then fill the table in the lower left corner, and finally fill the table in the upper right corner. In the process of filling each small square table, he will divide each small square table into smaller tables until it is filled\(2 \times 2\)until the square table of size.
Now Vadim can't wait to start filling out the form, but he has two types of\(q\)A question:
- The\(x\)Go to the next\(y\)What are the numbers in the cell of the column
- number\(d\)Which cell coordinate is located
Help answer Vadim's question.
Question solution: DFS
The meaning of the question is very direct and the idea is very clear, which is to constantly reduce the area by DFS. But how to design this area is really disgusting. It’s very good at knowing it. If you don’t know it, it will really get stuck for a long time. It’s obvious that the group members have been stuck for two hours.
First of all, for the size of the block, if it is currently in the\(n\)The size of the layer is\(2^{n - 1} \times 2^{n - 1}\), that is, each width and height are reduced by half. Secondly, for the coordinate step size, according to the previous analysis (diminishing the width and height by half), we can see that the step size is\(2^{n - 1}\). It is easy to know these two properties. You only need to know which layer you are currently in and the upper left coordinates of the current layer, and you can narrow the scope step by step until you can no longer shrink. That is the answer, see the code for details. Time complexity is\(O(nq)\) 。
Reference Code (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, q;
ll dfs1(int cur, int l, int r, int x, int y) {
// cout << "dfs1:" << cur << ':' << l << ':' << r << ':' << x << ':' << y << '\n';
if (l == x && r == y)
return 1;
ll dt = 1LL << (cur - 1);
ll dd = dt * dt;
if (x >= l + dt && y >= r + dt)
return dd + dfs1(cur - 1, l + dt, r + dt, x, y);
if (x >= l + dt)
return (dd << 1) + dfs1(cur - 1, l + dt, r, x, y);
if (y >= r + dt)
return 3 * dd + dfs1(cur - 1, l, r + dt, x, y);
return dfs1(cur - 1, l, r, x, y);
}
pii dfs2(int cur, int l, int r, ll d) {
// cout << "dfs2:" << cur << ':' << l << ':' << r << ':' << d << '\n';
if (d == 1)
return {l, r};
ll dt = 1LL << (cur - 1);
ll dd = dt * dt;
if (d > 3 * dd)
return dfs2(cur - 1, l, r + dt, d - 3 * dd);
if (d > (dd << 1))
return dfs2(cur - 1, l + dt, r, d - (dd << 1));
if (d > dd)
return dfs2(cur - 1, l + dt, r + dt, d - dd);
return dfs2(cur - 1, l, r, d);
}
void solve() {
cin >> n >> q;
string op;
int x, y;
ll d;
while (q--) {
cin >> op;
if (op == "->") {
cin >> x >> y;
cout << dfs1(n, 1, 1, x, y) << '\n';
} else {
cin >> d;
pii ans = dfs2(n, 1, 1, d);
cout << << ' ' << << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Problem E. Min Max MEX
The main idea of the topic
Give you a length\(n\)Array of\(a\)and a number\(k\) 。
The definition of a subarray is a sequence of one or more consecutive elements in an array. You need to add the array\(a\)Split into\(k\)A non-overlapping subarray\(b_1, b_2, \dots, b_k\), such that the collection of these subarrays is equal to the entire array. Also, you need to maximize\(x\)The value of\(x = \min(MEX(b_i)), 1 \leq i \leq k\) 。
\(MEX(v)\)Represents an array\(v\)The smallest non-negative integer that is not in it.
Question solution: two points
for\(u = MEX(v)\), if selected array\(v\)part of array\(vt\), then for all\(w \lt u\), can you find it\(w = MEX(vt)\)? The answer is yes. So we consider the two-point, the lower limit\(l = 0\), upper limit\(r = n\)(Because the array is at most\([0, 1, \dots, n - 1]\)). So how do we check? for\(MEX\)for\(u\), we only need to maintain a collection, and then iterate through the entire array, for each element, satisfy\(a_i \lt u, 0 \leq i \lt n\), add it to the set, when the number of elements of the set reaches\(u\), then count plus one (represents that it can be divided into a subarray, satisfying\(MEX \geq u\)) and clear the current collection. In the end, as long as the count is greater than or equal to\(k\), means that it can be divided reasonably. Time complexity is\(O(nlognlogn)\)(check uses set, and replace it with an array and you can reduce it every time you turn it invert.\(O(nlogn)\) ）。
PS: This question actually got double\(log\)The method of constants is really speechless!
Reference Code (C++)
pair\(log\)Timeout code.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
int a[maxn];
int n, m;
bool check(int x) {
set<int> st;
for (int i = 0; i < x; ++i)
(i);
if (())
return true;
set<int> stc;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < x)
(a[i]);
if (() == ()) {
++cnt;
();
if (cnt >= m)
return true;
}
}
return cnt >= m;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i];
int l = 0, r = n + 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
pair\(log\)Pass the code.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
int a[maxn];
int n, m;
bool check(int x) {
set<int> st;
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < x)
(a[i]);
if (() == x) {
++cnt;
();
if (cnt >= m)
return true;
}
}
return cnt >= m;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i];
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
one\(log\)Pass the code.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
int a[maxn];
bool vis[maxn];
int n, m;
bool check(int x) {
for (int i = 0; i < x; ++i)
vis[i] = false;
bool f = true;
int cnt = 0, cur = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < x) {
if (vis[a[i]] != f) {
++cur;
vis[a[i]] = f;
}
}
if (cur == x) {
++cnt;
cur = 0;
f = !f;
if (cnt >= m)
return true;
}
}
return cnt >= m;
}
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i];
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Problem F. Hackers and Neural Networks
The main idea of the topic
Hackers once again try to create entertainment phrases using the output of neural networks. This time, they want to get the length of\(n\)array of strings\(a\) 。
Initially, they had a length of\(n\)Array of\(c\), full of blank spaces, with symbols\(*\)express. Therefore, if\(n = 4\), then the initial value is\(c=[*, *, *, *]\) 。
Hackers can access\(m\)Each neural network has its own version of the request answer-length\(n\)array of strings\(b_i\) 。
The hacker tries to use the following operations from the array\(c\)Get array in\(a\) ：
-
Select a neural network\(i\), to array\(c\)Perform the next step: Select onerandomofblank, for example in location\(j\)Where,\(c_j\)Replace with\(b_{i, j}\) 。
For example, if the first neural network is selected\(b_1 = [\text{«I»}, \text{«love»}, \text{«apples»}]\),current\(c = [*, \text{«like»}, *]\), then after operating the first neural network,\(c\)It may become\([\text{«I»}, \text{«like»}, *]\)or\([*, \text{«like»}, \text{«apples»}]\) 。
-
Select a location\(j\)And\(c_j\)Replace with blank.
Unfortunately, due to the way hackers access neural networks, they can only see the modified array after all operations are completed\(c\), so they must specify the entire sequence of operations in advance.
However, the random behavior of neural networks can lead to never being able to get the required array, or it takes too much operation to get the required array.
Therefore, hackers hope you can help them select an action sequence to ensure that they get an array within the minimum number of actions\(a\) 。
More specifically, if there is an operation sequenceensureFrom an array\(c\)Get array in\(a\), then in all such sequences, find a number of operationsleastand output the number of operations in it.
If the array is not\(c\)Convert to an array\(a\)The operation sequence of\(-1\) 。
Question answering: Greedy
The question is really long and very thrilling. I really don’t know what to ask for after reading it? Let's taste it carefully! Anyway, you just do two operations. As long as the string in the corresponding position is incorrect, you must continue to operate. As long as you operate, the number of operations will inevitably increase.
If a certain position is already correct after an operation, will you change it in the next operation? Obviously not, otherwise you have to do operation two at least once and at least random operation one at a time, and it may not be right after randomness, so why bother?
If all positions are empty, will you do the operation 2? Obviously not, either, it's a waste of operation. So the first operation must be operation one, this is a random process.
Through the above analysis, the only thing we can decide is which neural network we can choose to run on. From a probability theory perspective, we certainly hope to choose one with a higher probability of hitting, so that the greater the expectations we get, the fewer operations needed in the future. So the first operation is crucial. We choose the neural network with the highest probability of hitting, so that we can guarantee\(n\)After the operation, the correct position is the largest at random. In this way, all positions are filled. Finally, for the incorrect position, we only need to perform operation two at one time, and then find a neural network. The corresponding position has the correct string, because only the blank position will be random, and there is only one blank position at the moment. Obviously, this is an inevitable event.
Is the above operation the best? Sure. Suppose you choose a neural network hit rate is\(\frac{x}{y}\), you combine all other neural networks, and the hit rate is like\(\frac{x + a}{y + b}\), it cannot be bigger.
For cases where it does not exist, it is obvious that all corresponding positions do not have a target string, so it cannot be done. Time complexity is\(O(mn \max(|b_{i, j}|))\) 。
Reference Code (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 505;
string p[maxn], str[maxn][maxn];
int cntr[maxn], cntc[maxn];
int n, m;
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> p[i];
cntc[i] = 0;
}
for (int i = 0; i < m; ++i) {
cntr[i] = 0;
for (int j = 0; j < n; ++j) {
cin >> str[i][j];
if (str[i][j] == p[j]) {
++cntc[j];
++cntr[i];
}
}
}
for (int i = 0; i < n; ++i)
if (cntc[i] == 0) {
cout << "-1\n";
return;
}
int maxc = 0;
for (int i = 0; i < m; ++i)
maxc = max(maxc, cntr[i]);
cout << (n + ((n - maxc) << 1)) << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
Problem G. Shorten the Array
The main idea of the topic
The length is\(m\)Array of\(b\)The aesthetics of all possible pairs\(1 \leq i \leq j \leq m\)In-house\(\max(b_i \oplus b_j)\),in\(x \oplus y\)It's a number\(x\)and\(y\)ofbitwise XOR. We will array\(b\)The beauty of\(f(b)\) 。
If array\(b\)There is\(f(b) \geq k\), then this array\(b\)It's called a beautiful array.
Recently, Cosja bought a length from the store\(n\)Array of\(a\). He thought this array was too long, so he planned to cut out some beautiful subarrays from it. That is, he wants to choose a number\(l\)and\(r\) ( \(1 \leq l \leq r \leq n\)), such an array\(a_{l \dots r}\)It's very beautiful. The length of such a sub-array is\(r - l + 1\). The entire array\(a\)Also considered as a subarray (including\(l = 1\)and\(r = n\) )。
Your task is to find out the array\(a\)The length of the shortest beautiful sub-array. If none of the subarrays are beautiful, then you should output numbers\(-1\) 。
Question solution: Double pointer + dictionary tree Trie
First, for each\(l\), if the first one meets the condition is found\(r(r \geq l)\), then obviously\(r + 1(r \lt n)\)That's OK. In this case, we maintain a double pointer. For each left pointer, constantly expand the right pointer until we find the first position that meets the condition and update the answer. So how to quickly calculate whether the current interval can meet the conditions? It's easy to think ofDictionary TreeFind the maximum XOR value that can be obtained in the current interval. Time complexity is\(O(n)\)(The number of calculations is actually\(30n\), constants are ignored, but the actual running time still needs to be considered).
Reference Code (C++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int maxn = 200'005;
const int maxnode = 6'000'005;
const int sigma_size = 2;
struct trie {
int child[maxnode][sigma_size];
int value[maxnode];
int size;
void init() {
size = 1;
memset(child[0], 0, sizeof(child[0]));
}
void insert(int x, int y) {
int pos = 0;
for (int i = 29; i >= 0; --i) {
int id = (x >> i) & 1;
if (!child[pos][id]) {
memset(child[size], 0, sizeof(child[size]));
value[size] = 0;
child[pos][id] = size++;
}
pos = child[pos][id];
value[pos] += y;
}
}
int query(int x) {
// cout << "query: " << x << '\n';
int pos = 0, ans = 0;
for (int i = 29; i >= 0; --i) {
int id = (x >> i) & 1;
int idx = id ^ 1;
int p = child[pos][idx];
if (p && value[p]) {
ans |= 1 << i;
pos = p;
} else {
p = child[pos][id];
if (p && value[p])
pos = p;
else
return -1;
}
}
// cout << "query: ans = " << ans << '\n';
return ans;
}
} tr;
int a[maxn];
int n, m;
void solve() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
cin >> a[i];
if (m == 0) {
cout << "1\n";
return;
}
();
int l = 0, r = 0, ans = n + 1;
while (r < n) {
// cout << l << ", " << r << endl;
while (r < n && (a[r]) < m)
(a[r++], 1);
if (r < n)
ans = min(ans, r - l + 1);
(a[l++], -1);
if (l > r)
r = l;
}
cout << (ans == n + 1 ? -1 : ans) << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}