A - Equal or Not Equal
General idea of the topic
E means equal to the next value, N means unequal
Ask whether the array expressed by this string is legal
thinking
There are some meanings of merging and searching sets
But there are some special places,
- If all are E, it goes without saying
- If you want to split the string into two or more arrays, when the first two arrays are connected, two N will be generated, and only one N indicates that it is illegal
therefore
As long as there are more than two N's, the string must be legal. On the contrary, when there is only one, it is not legal
code
#include <iostream>
using namespace std;
const int N = 50 + 10;
int n;
string str;
int main() {
int T;
cin >> T;
while (T --) {
cin >> str;
int cnt = 0;
for (auto i : str) if (i == 'N') cnt ++;
if (cnt == 1) puts("NO");
else puts("YES");
}
return 0;
}
B - Triangles on a Rectangle
General idea of the topic
Give you a rectangle W in width and H in height, and points on four sides. What is the area of the largest triangle that can form two points on the same side
The topic is twice the area
thinking
Area of triangle = bottom * height * 2
- If it is high, we can directly select the point on the opposite side, so that the point can be selected arbitrarily, and the height must be the width or height of the rectangle
- At the end, you must choose the farthest point on one side
code
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL w, h;
LL a[4][N];
int main() {
int T;
cin >> T;
while (T --) {
cin >> w >> h;
for (int i = 0; i < 4; i ++) {
cin >> a[i][0];
for (int j = 1; j <= a[i][0]; j ++) cin >> a[i][j];
sort(a[i] + 1, a[i] + a[i][0] + 1);
}
cout << max(
h * max(a[0][a[0][0]] - a[0][1], a[1][a[1][0]] - a[1][1]),
w * max(a[2][a[2][0]] - a[2][1], a[3][a[3][0]] - a[3][1])
) << endl;
}
return 0;
}
C - BA-String
General idea of the topic
Give you a string. You can fill in no more than k b characters at the position of * and ask what is the smaller string x
thinking
Many * strings are separated by A. after simplification, we find that b characters that do not exceed the length of * string can be filled in around a
When the x is small, b must be filled in the last * string first. When the * string reaches the maximum, one will be filled in the previous * string and re filled here
So we found that it is similar to an addition that is different from each base, and what we are looking for is the x - 1 base
code
(the writing is not very good. If there is a better one to share with me)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
LL n, k, x;
string str;
LL a[N], b[N];
int idx, idx2;
void calc(LL n, LL k) {
for (int i = n; i >= 0; i --) {
b[i] = k % (a[i] + 1);
k /= (a[i] + 1);
}
}
int main() {
int T;
cin >> T;
while (T --) {
cin >> n >> k >> x;
cin >> str;
idx = idx2 = 0;
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
for (int i = 0; i < n; i ++) {
if (str[i] == 'a') {
if (a[idx]) idx ++;
}
else a[idx] += k;
}
//for (int i = 0; i <= idx; i++) cout << a[i] << ' ';
calc(idx, x - 1);
//for (int i = 0; i <= idx; i ++) cout << b[i] << ' ';
for (int i = 0; i < n; i ++) {
if (str[i] == 'a') {
if (i != 0 && str[i - 1] == '*') {
for (int i = 0; i < b[idx2]; i ++) cout << 'b';
idx2 ++;
}
cout << 'a';
}
}
if (idx2 <= idx)
while (idx2 <= idx) {
for (int i = 0; i < b[idx2]; i ++) cout << 'b';
idx2 ++;
}
cout << endl;
}
return 0;
}
D - Exact Change
General idea of the topic
You have coins with face values of 1, 2 and 3, and the store has many goods with different prices. Ask the minimum number of coins you need to bring each time you go out to meet different commodity prices
thinking
First of all, greed must be taking the maximum number of 3 coins
Then we'll discuss it in detail
You can refer to it. Please correct the mistakes
code
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int T;
cin >> T;
while (T --) {
int n;
cin >> n;
int a[n];
int t1 = 0, t2 = 0, t3 = 0;
for (int i = 0; i < n; i ++) {
cin >> a[i];
if (a[i] % 3 == 0) t3 = max(t3, a[i]);
if (a[i] % 3 == 1) t1 = 1;
if (a[i] % 3 == 2) t2 = 1;
}
sort(a, a + n);
int ans;
if (a[n - 1] % 3 == 0) {
ans = a[n - 1] / 3 + (t1 || t2);
}
else if (a[n - 1] % 3 == 2) {
ans = a[n - 1] / 3 + 1 + t1;
}
else {
ans = a[n - 1] / 3 + 1 + (t2 && (a[0] == 1 || t3 + 1 == a[n - 1]));
}
cout << ans << endl;
}
return 0;
}
E - Replace the Numbers
General idea of the topic
After many operations, find the last value of the array
- 1 x means insert X
- 2 x y means to change all previous x to y
thinking
It is said that there is a relationship between maintaining numerical values and maintaining positional relationships. Here we use maintaining positional relationships
Can you maintain data without the traditional parallel query set?
Save the list of all positions when the value is int in map < int, list >
list can be easily transferred
code
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <cstdio>
#include <unordered_map>
using namespace std;
const int N = 5e5 + 10;
int n, idx;
int a[N];
unordered_map<int, list<int> > q;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) {
int op;
scanf("%d", &op);
if (op == 1) {
int x;
scanf("%d", &x);
q[x].push_back(idx ++);
}
else {
int x, y;
scanf("%d%d", &x, &y);
if (x == y) continue;
auto it = q.find(x);
if (it != q.end()) {
q[y].splice(q[y].begin(), q[x]);
q.erase(it);
}
}
}
for (auto &i : q) {
for (auto &j : i.second)
a[j] = i.first;
}
for (int i = 0; i < idx; i ++) printf("%d ", a[i]);
return 0;
}