Preface: The difficulty of this challenge has increased compared to the previous ones, mainly because of the training, the members of the question writing team didn't have enough time to come up with original questions (so, they had to carry a certain ABC exam in its original form.). Anyway, AK is fine.
Note: Due to the large size of Python's constants, this solution is not synchronized with the Python version of the solution.
Question 1 - Intersection
Title Jump:intersection (symbol ∩) (set theory)。
This question can be done violently or with a little bit of brainstorming. Seeing as the amount of data is small, just hit the violence straight away, there's no need to spend time finding the relationship between the two line segments.
perceive\(0 \le L_1 R_1, L_2, R_2 \le 100\)If a coordinate belongs to one of the line segments, then the markers at the corresponding indexes are increased by one. Finally, iterate through the array of markers one more time, and if there exists a coordinate that is marked twice, then it proves that the coordinate is covered by both line segments at the same time.
Finally, note the output of the\(-1\), denotes the length of the interval. (If there are not any overlapping intervals, i.e.ans == 0 When the special judgment is directly output\(0\) That's all.
Code time complexity:\(O(N)\)。
The AC code for this question is as follows:
#include <iostream>
using namespace std;
int a, b, c, d;
int arr[1005], ans;
int main(){
cin >> a >> b >> c >> d;
for (int i=a; i<=b; i++)
arr[i]++;
for (int i=c; i<=d; i++)
arr[i]++;
for (int i=0; i<=100; i++)
ans += (arr[i] == 2);
cout << max(0, ans-1) << endl;
return 0;
}
Question 2 - Tournament Result
Title Jump:results of a competition。
The second question is also a purely violent simulation, with a double-layerfor Cycle through the points in accordance with the requirements of the title of the question\((i, j)\) draw a line at\((j, i)\)It's just a matter of whether or not there is a conflict between the stored values. Here I use acheck function to check if there is a conflict. If there is a conflict, just return the result.
This side is judging the conflict.check Functions I think are worth talking about, categorizing and discussing:
- If both sides have the same win/loss status and it's not a tie, then return
false。 - If one side is a tie two the other is not a tie, return the
false。 - It can be proved that the rest of the cases must be legal and return directly to the
trueYou don't need to go through the same trouble of writing conditional branching statements as you would for any other solution.
Code time complexity:\(O(N^2)\)。
The AC code for this question is as follows:
#include <iostream>
#include <algorithm>
using namespace std;
int n;
char arr[1005][1005];
bool check(char a, char b){
if (a == b && a != 'D')
return false;
if (a == 'D' && b != a)
return false;
return true;
}
int main(){
cin >> n;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
cin >> arr[i][j];
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
// (coll.) fail (a student) i == j when，Skip Enumeration。
if (i == j) continue;
if (!check(arr[i][j], arr[j][i])){
cout << "incorrect" << endl;
return 0;
}
}
}
cout << "correct" << endl;
return 0;
}
Question 3 - NewFolder(1)
Title Jump:New folder(1)。
Also a water question, using STL'sunordered_map/ map Just store the number of times a particular string appears. Since the\(N\) It's quite large, so it will definitely time out if you traverse it directly with a double loop.
However, it is important to note thatmap The time complexity of a single insertion/query is about\(O(\log_2 N)\). Thus the combined time complexity of this problem is approximately\(O(N \log_2 N)\)。
The AC code for this question is as follows:
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
int n;
string str[200005];
unordered_map<string, int> map;
int main(){
cin >> n;
for (int i=1; i<=n; i++){
cin >> str[i];
map[str[i]] += 1;
int cnt = map[str[i]];
if (cnt == 1)
cout << str[i] << endl;
else
cout << str[i] << "(" << cnt-1 << ")" << endl;
}
return 0;
}
Question 4 - Flipping and Bonus
Title Jump:insert a coin。
Moving on to the main event of the tournament, where the difficulty of the questions took a quantum leap (I'm not sure why the difficulty of ABC jumped so much this time).
Consider using dynamic programming to define the state\(dp_i\) denote\(i\) The maximum amount of money that can be obtained in a single coin toss. (There are actually a variety of state definitions for this problem, using the two-dimensionaldp (It is also possible to pass this question, the solution of which is tentatively available only for prefixes and dynamic programming)
We can enumerate the values in the first\(j\) The value of heads and tails is chosen and maximized for each coin toss. So, for each coin toss there are two possible decisions, which are:
- The final state of the coin is heads when getting the first\(i\) times the coin is tossed for money, the counter increments itself. So the result is to get\(x_1 + x_2 + x_3 + \cdots + x_{i-1} + x_i\) dollars and\(y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i)\) The bonus.
- The final state of the coin is tails, then the counter starts counting from the beginning. So the final result that can be obtained will be the number of coins counted from the first\(j\) Maximum amount of money that can be obtained at the next coin toss\(dp_j\) Plus in the interval\([j+2, i]\) The amount of money gained from a coin toss that is all heads (because the first\(j+1\) (No bonus will be awarded for the second coin toss)\((x_1 + x_2 + x_3 + \dots + x_{i-1} + x_i) - (x_1 + x_2 + x_3 + \cdots + x_j + x_{j+1})\) Plus the former\(i-j-1\) Sub-Counter Reward Amount\((y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i-j-1)\) 。
It can be found that we can optimize the algorithm by opening two prefixes and arrays with the respective conventions\(\mathtt{suma, sumb}\) respectively, before\(i\) All of the coin tosses are for the positive amount and the counter's reward amount. Therefore the final state transfer equation can be written as:
Remarks: Ten years of OI, one empty, not openlong long Meet the Ancestors. Please be sure to openlong long. The time complexity of this problem is\(\Theta(\dfrac{N+N^2}{2})\)。
After weeks, the AC code for this question is as follows:
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long dp[5005],x[5005],c[5005],y[5005],suma[5005],sumb[5005],m,n,cnt;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x[i];
suma[i]=suma[i-1]+x[i];
}
for(int i=1;i<=m;i++){
int a, b;
cin >> a >> b;
c[a] = b;
}
for (int i=1; i<=5000; i++){
sumb[i]=sumb[i-1]+c[i];
}
for(int i=1;i<=n;i++){
dp[i]=suma[i]+sumb[i];
for(int j=1;j<i;j++){
// See the original article for the derivation of the state transfer equation。
dp[i]=max(dp[i],dp[j]+suma[i]-suma[j+1]+sumb[i-j-1]);
}
}
cout<<dp[n];
return 0;
}
Question 5 - Many Operations
Title Jump:macroscopic operation。
A nasty question on bitwise arithmetic which, like the previous one, can be solved using prefixes and dynamic programming ideas. Since each bit is independent of each other, it is only necessary to perform bitwise\(\mathtt{dp}\) Preprocessing is all it takes. Defining the state\(dp_{i, j(0/1), k}\) Indicates that for the first\(i\) bit, the value at the beginning of the\(j(0/1)\)After the former\(k\) value of this bit after the next operation. And the state transfer equation is\(dp_{i, j, k} = dp_{i, j, k-1}\). After that constant iterations will lead to the final solution.
The main difficulty of this question is some operations of bitwise arithmetic, some students are not familiar with the operation of bitwise arithmetic, here provide some common bitwise arithmetic operations:
- Get the first digit of a number\(j\) Bit:
(x >> j) & 1。 - Determine if a number is odd:
x & 1。 - Multiply a number by\(2^j\)：
(1 << j) * x。
The time complexity of this problem is approximately\(\Theta(60N)\)。
Therefore, the AC code for this question is as follows:
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int n, c;
int dp[50][5][N];
int t[N], a[N];
signed main(){
cin >> n >> c;
for (int i=1; i<=n; i++)
cin >> t[i] >> a[i];
// cout << log2(1e9) << endl;
for (int i=0; i<30; i++){
for (int j=0; j<2; j++){
dp[i][j][0] = j;
for (int k=1; k<=n; k++){
// three states，Just judge them separately.。
bool x = a[k] & (1 << i);
if (t[k] == 1) dp[i][j][k] = dp[i][j][k-1] & x;
else if (t[k] == 2) dp[i][j][k] = dp[i][j][k-1] | x;
else dp[i][j][k] = dp[i][j][k-1] ^ x;
}
}
}
for (int i=1; i<=n; i++){
int ans = 0, k = c;
for (int j=0; j<30; j++) {
// basic bitwise operation。
ans += dp[j][k & 1][i] * (1 << j);
k >>= 1;
}
cout << ans << endl;
c = ans;
}
return 0;
}
Question 6 - Sorting Color Balls
Title Jump:Color ball sorting。
A reverse order pairs question, because I was too lazy to use a subsumption sort to do it, so I used theTree Array + map The way to win the running time of 44.9s. Actually, this question should be easier than the fifth question, Based on my opinion.
A common question on inverse pairs, where removing inverse pairs of the same color when calculating inverse pairs is enough, similar to a template question. I used two tree arrays to count the number of times each number appears and the number of times each color appears.
The AC code for this problem is as follows, with a time complexity of about\(O(N \log_2 N)\)：
#include <iostream>
#include <vector>
#include <unordered_map>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, c[N], x[N];
int cnt[N], tot[N];
unordered_map<int, int> cnt2[N];
// Record the number of times a number appears。
void add_n(int x){
while(x <= n){
cnt[x] += 1;
x += x & (-x);
}
}
// Record the number of times a color appears。
void add_c(int x, int c){
while(x <= n){
cnt2[x][c] += 1;
x += x & (-x);
}
}
// Query the number of times a number occurs。
int query_n(int x){
int ans = 0;
while(x){
ans += cnt[x];
x -= x & (-x);
}
return ans;
}
// Query the number of times a color appears。
int query_c(int x, int c){
int ans = 0;
while(x){
ans += cnt2[x][c];
x -= x & (-x);
}
return ans;
}
signed main(){
cin >> n;
for (int i=1; i<=n; i++) cin >> c[i];
for (int j=1; j<=n; j++) cin >> x[j];
int result = 0;
for (int i=1; i<=n; i++){
// Just subtract the number of times the same color appears。
result += (i - 1) - tot[c[i]] - query_n(x[i]) + query_c(x[i], c[i]);
tot[c[i]] += 1;
add_c(x[i], c[i]); add_n(x[i]);
}
cout << result << endl;
return 0;
}