# The fourth training match in the summer vacation of level 19

## Question A: 1165A Input

```11 5 2
11010100101
```

Output

```1
```

Input

```11 5 1
11010100101
```

Output

```3
```

Because we only focus on taking the modulus of \ (10^x \) to the power of \ (10^y \), we only focus on how to operate only the last x bits of n-bit numbers. Except that the penultimate y+1 bit should be set to 1, everything else should be set to 0. We record the number of 1 in the last y digits as time. If the number at the position of 1 is 0, the operand time+1. If the number at the position of 1 is 1, repeat the operation and output time-1

```#include<bits/stdc++.h>
using namespace std;
int n, x, y, res, cnt;
string s;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> x >> y;
cin >> s;
for (int i = n - 1, cnt = 0; cnt < x; i--) {
if (cnt == y)res += s[i] != '1';
else res += s[i] != '0';
cnt++;
}
cout << res << endl;
}
```

## Question B: 1165B Input

```4
3 1 4 1
```

Output

```3
```

Input

```3
1 1 1
```

Output

```1
```

Input

```5
1 1 1 2 2
```

Output

```2
```

### thinking

There are two ways to solve this problem. I feel a little dull when I see the method of another classmate.
The first is to sort from small to large, and then traverse the array. For each competition that can meet the number of questions, the number of days will be increased by one.
The second is to use the array to record the number of matches with n questions, and then traverse the array once, which can be regarded as cardinal sorting.

```#include<bits/stdc++.h>
using namespace std;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
int n, i, p = 0;
cin >> n; int arr[n];
for (i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
for (i = 0; i < n; i++)
if (arr[i] > p)
p++;
cout << p;
}
```

## Question C: 1165C Input

```4
good
```

Output

```0
good
```

Input

```4
aabc
```

Output

```2
ab
```

Input

```3
aaa
```

Output

```3
```

### thinking

The method of this problem is greedy. We know that a string like ABCD can become a good string by deleting one. It can be one of ab or c. For continuous repeated strings, as long as they comply with the rules of good strings, that is, the former is in the even position and the latter is in the odd position, there is no need for special treatment. Of course, if there are more than two, they must be deleted.
We can adopt a greedy strategy to recombine a string. When we take the odd position, we can take it at will. When we take the even position, if it is the same as the odd position, we don't take it.

```#include<bits/stdc++.h>
using namespace std;
int main() {
int  n, i; cin >> n;
string s, ss; cin >> s;
for (i = 0; i < n - 1;) {
if (s[i] != s[i + 1]) {
ss += s[i];
ss += s[i + 1];
i += 2;
}
else i++;
}
cout << n - ss.size() << endl << ss;
}
```

## Question D: 1165D ### thinking

Simulation, using the nature of set to store the input factors (with sorting),

sort

If the array meets the requirements, then this X must be the maximum and minimum value multiplied

Try to find the factor of tmp. If all the factors match, it can be output.

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll>s, ss;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
ll t, n, tmp; cin >> t;
while (t--) {
cin >> n;
s.clear(); ss.clear();
for (ll i = 1; i <= n; ++i) {
cin >> tmp;
s.insert(tmp);
}
tmp = (*s.begin()) * (*s.rbegin());
for (ll i = 2; i * i <= tmp; ++i) {
if (tmp % i == 0) {
ss.insert(i);
ss.insert(tmp / i);
}
}
if (s == ss)cout << tmp << endl;
else cout << -1 << endl;
}
}
```

## Question E: 1165E  input

```5
1 8 7 2 4
9 7 2 9 3
```

output

```646
```

input

```1
1000000
1000000
```

output

```757402647
```

input

```2
1 3
4 2
```

output

```20
```

### thinking

We know that for two arrays with the same number of elements, how to sort and minimize the value of multiplication and summation of their bits can only be

An array is in positive order, an array is in reverse order, and then multiplied and summed one by one.

For this problem, a and b can only move the order of the b array, so it is actually the same, as long as the number with the largest i of b corresponds to the number with the smallest i of A

All right. But the title gives the function of \$f (l, r) \$and adds all the functions. It is not difficult to see that in an array of n elements, for the ith element, there must be \$I * (n-i+1) \$intervals to include this element, that is, the product related to the \$I \$element will accumulate for the above times.

For the array a, it cannot move. Why not multiply these cumulative times by the elements in a first.

We multiply the elements in a by the corresponding cumulative times to get the new array, p in positive order and b in reverse order, and then multiply and add bit by bit to take a module,

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int N = 2e5 + 100;
ll n, ans, a[N], b[N], q[N], k;//Use long long to prevent overflow
bool cmp(int x, int y) {
return a[x] > a[y];
}
int main() {
freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
//For the ith element, there must be I * (n-i+1) intervals to include this element
for (int i = 0; i < n; i++)cin >> a[i],a[i] *= (i + 1) * (n - i),q[i] = i;
for (int i = 0; i < n; ++i)cin >> b[i];
sort(q, q + n,cmp); sort(b, b + n);
ans = 0;
for (int i = 0; i < n; i++){
k = (a[q[i]] % MOD * b[i]) % MOD;
ans = (ans + k) % MOD;
}
cout << ans << endl;
}
```

## Question F:

CodeForces - 1165F1

F1, F2 ideas and AC codes are from Daniu Jfeng666

### meaning of the title

The difference between the simple version and the difficult version is only in the data range.
The protagonist Ivan, playing a computer game, including many micro transactions, can get accessories that make the character more handsome. He wants his character to look cooler. He wants to use these micro transactions to get accessories, and he starts playing the game after he gets everything.
Every morning, Ivan can earn a unit of Burre in the game
There are n kinds of micro transactions. For the cost of each micro transaction, each jewelry costs 1 unit of Burre at discount and 2 units of Burre at ordinary times. For the i-th jewelry, he wants to make ki transaction, and the order will be completed in the evening.
The game store has m discounts, and the j-th input (dj,tj) represents that the t-th commodity is discounted on day d.
Ivan wants to get all the items as soon as possible. Your task is to calculate the minimum time he can buy all the accessories he wants and start the game.
...... Some people say they still don't understand. Let me briefly say
The protagonist wants to buy something, and then gets a dollar a day from the first day
Usually, there are two pieces of everything, one piece on the day of discount for some kinds.
I gave you a discount day and what he wanted to buy. Here are the types and quantities
The discount day also indicates the date and type
How soon can you buy these things

### thinking

For the results, the most important is the number of days. If the protagonist wants n items, the number of days required must be within n~2n. We only need to find the smallest number of days to buy things.
For a fixed number of days, the discount activities we can contact must be available on or before the day. Then for the same item, the later the discount time, the more quantity you can buy at one time. We might as well buy as much as we need on this day. However, please note that the discount activities held before the day cannot use day currencies, that is, we cannot consume ahead of time. Then, for the remaining currency bday on the day and the activities held on the day fday (fday < day), we can only use fday currencies, and bday fday currencies must only be used to buy items in two currencies.
Similarly, for the discounts on day 5 and day 3, if there are five currencies on day 5 and I buy three to meet the demand, I can only buy two at most for the discount on day 3. If there are also three discounts on day 3, the remaining one must be purchased at the original price of two yuan each. So such greed does not affect the result.

```#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 200010
//The algorithm can solve both range difficulty problems.
int lf, rt, b[maxn];
int ned[maxn], da[maxn], tp[maxn];
int k, p[maxn], n, m;
int cmp(int x, int y) {
return da[x] < da[y];
}
int min(int a, int b) {
return a < b ? a : b;
}
bool check(int v) {//Test whether v yuan can be bought
for (int i = 1; i <= n; i++)
b[i] = 1;
//Items that have passed the last discount day will not be purchased on the previous discount day, because they must be purchased, or the remaining needs cannot be met
int mon = v, cost = 0;
for (int i = m; i > 0; i--)
if (b[tp[p[i]]] && da[p[i]] <= v) {
b[tp[p[i]]] = 0;
mon = min(mon, da[p[i]]);
cost += min(mon, ned[tp[p[i]]]);
mon -= min(mon, ned[tp[p[i]]]);;
} //As long as the discount is lower than v, you can get access to it, but the maximum quantity you can buy is limited to the discount time and demand.
return cost + (v - cost) / 2 >= lf;
}
int divide(int lf, int rf) {
int mid;
while (lf < rf) {
mid = (lf + rf) / 2;
if (check(mid)) rf = mid - 1;
else lf = mid + 1;
}
//In order to optimize the number of greedy answers, I use dichotomy.
return check(rf) ? rf : rf+1;
//Because there is the possibility of rf=lf and rf=lf-1 when exiting the loop
}
int main()
{
cin >> n >> m;
lf=0;
for (int i = 1; i <= n; i++){
cin >> ned[i];
lf += ned[i];
} rt = lf * 2;
for (int i = 1; i <= m; i++) {
cin >> da[i] >> tp[i];
p[i] = i;
}
sort(p + 1, p + 1 + m, cmp);
cout << divide(lf, rt) << endl;
return 0;
}
```

Posted by SoulSensus on Mon, 23 May 2022 05:54:17 +0300