​A The problem is a simple binary conversion , The code implementation is as follows ：

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int
main() { int x = 2022; int a = 1; int res = 0; while(x) { res += (x % 10) * a;
a = a * 9; x /= 10; } cout << res; return 0; }

​B There is a lot of controversy about this question , I think shunzi means from 0 An ascending sequence that starts with at least three numbers . Then the answer is ：14

C Question is a very common thinking question , First, record how many questions you can do every week , Then count the total number of questions you can do divided by the number of questions you can do every week, and then multiply by 7, Add the number of days from Monday to calculate when each day can be greater than the total number of questions .
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int
N = 1e5 + 10; int main() { LL a, b, n, t, res; cin >> a >> b >> n; t = a * 5 +
b * 2; res = n / t * 7; n %= t; if(n > 0) for(int i = 1; i <= 7; i ++ ) { if(i
== 6 || i == 7) n -= b; else n -= a; res ++; if(n <= 0) break; } cout << res;
return 0; }

D The question should be the simplest one , Open one n Array of a[i],a[i] Indicates the maximum height that each shrub can grow , The maximum height is equal to the number of trees on its right multiplied by 2;
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int
N = 1e4 + 10; int a[N], n; int main() { cin >> n; for(int i = 1; i <= (n + 1) /
2; i ++ ) { a[i] = (n - i) * 2; a[n - i + 1] = a[i]; } for(int i = 1; i <= n; i
++ ) { cout << a[i]; if(i != n) cout << "\n"; } return 0; }

​E The question began to be a little interesting , This problem is a simple greed , Focus on reading questions （ In fact, children's shoes that have been exposed to this problem should be understood as well emmm）.

Let's analyze the problem first 65 How did you get out ： The first digit each number represents must be 1, The second digit is derived from the binary of the first digit , So the second digit, each number represents 2, The third digit is the decimal carry of the second digit , So the third digit, each number represents 2
* 10 = 20, So this x(321) = 3 * 20 + 2 * 2 + 1 * 1 = 65;

The title means guarantee x(a) >= x(b) ,
Find the minimum difference between two numbers . Obviously for every digit , The smaller its base is , The smaller the difference between the last digit of two numbers , So the smallest legal base number of each digit is OK .
#include <bits/stdc++.h> #define int long long using namespace std; const int
mod = 1e9 + 7, N = 1e5 + 10; int a[N], b[N]; int ma, mb, n; signed main() { cin
>> n; cin >> ma; for(int i = 1; i <= ma; i ++ ) cin >> a[i]; for(int i = 1; i
<= ma / 2; i ++ ) swap(a[i], a[ma - i + 1]); cin >> mb; for(int i = 1; i <= mb;
i ++ ) cin >> b[i]; for(int i = 1; i <= mb / 2; i ++ ) swap(b[i], b[mb - i +
1]); int t = 1, ans = 0; // Enumerate each digit for(int i = 1; i <= ma; i ++ ) {
// Current digit greedy optimal base int z = max(a[i], b[i]) + 1; if(z < 2) z = 2; ans += a[i] * t -
b[i] * t; ans %= mod; t = t * z % mod; } cout << ans; return 0; }

F The question can be written violently , Find a prefix sum , Then enumerate the submatrix , The time complexity is O(n^4), Obviously not ;

This question tests a double pointer , Enumerate the left and right boundaries in the matrix , In each left and right boundary , Find the value less than or equal to in a sub segment from top to bottom k Number of （ Just sweep it with a double pointer , This step can be done o(n)）;

Time complexity ：O(n ^ 3)
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(fast)
#include <bits/stdc++.h> using namespace std; const int N = 510; typedef long
long LL; int a[N][N]; int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) scanf("%d",
&a[i][j]); for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) a[i][j]
+= a[i][j - 1]; LL cnt = 0; for(int i = 1; i <= m; i ++ ) for(int j = i; j <=
m; j ++ ) { int res = 0; for(int l = 1, r = 1; r <= n; r ++ ) { res += a[r][j]
- a[r][i - 1]; while(res > k && l <= r) { res -= a[l][j] - a[l][i - 1]; l ++; }
if(res <= k && l <= r) cnt += r - l + 1; } } printf("%lld", cnt); return 0; }

This question is a test dp;

State representation : f[i][j] Before representation i Column building blocks , The first i Column status is j Number of cases .

Four situations :j = 0, Indicates that the current column is empty , 1 Indicates that there is a grid above the current column ,2 Indicates that there is a grid under the current column ,3 Indicates that the current column is full .

Due to the large data , Open one 4e8 Your space will explode , Can use p To represent the state of the previous layer ,q To represent the state of the current layer , Rolling array optimization similar to knapsack .

Look at the code for state transition , I think it's easy to understand , If you don't understand, you can ask me in the comment area
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int
N = 1e7 + 10, mod = 1e9 + 7; LL p, q; int main() { int n; cin >> n; p
= 1; for(int i = 1; i <= n; i ++ ) { q = (p + p + p + p) % mod;
q = p % mod; q = (p + p) % mod; q = (p + p) % mod;
for(int i = 0; i <= 3; i ++ ) p[i] = q[i]; } cout << p; return 0; }

ps: You can't use and search the set to do it , Because the explosion of thunder is from the direction ,A A mine explosion can detonate B thunder , however B A mine explosion may not detonate B Thunder （ Different explosion radius ）

ps: I was stuck all day when I made up the question , Finally idx.find Change to idx.count It's over （emm55555）

The positive solution is dfs, In order to avoid the edge getting stuck O(n * n), so that tle, We need to remove duplicate points , Record the position of each point under each coordinate .

Then take each rocket as the root node , Go around r ^ 2 Ray , Just count how many mines you can blow .

O(100 * n + m） The worst-case scenario is that every mine has 100 Strip edge ;
#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; typedef
long long LL; const int N = 2e5 + 10; struct Node { int x, y, r, l; }a[N];
//x,y Mapping to subscript unordered_map<LL, int> idx; bool st[N]; int n, m, cnt; int ans; LL
cal(int x, int y) { return (LL)x * (1000000000 + 1) + y; } bool solve(int x,
int y, int r) { if(x * x + y * y <= r * r) return true; else return false; }
void dfs(int i) { // Mark current point st[i] = true; // Plus the current number of point mines ans += a[i].l; int r =
a[i].r; //printf("%d %d %d\n", a[i].x, a[i].y, a[i].r);
// Traverse whether there are child nodes around the current point , If so, continue dfs for(int x = max(a[i].x - r, 0); x <= min(a[i].x +
r, 1000000000); x ++ ) { for(int y = max(a[i].y - r, 0); y <= min(a[i].y + r,
1000000000); y ++ ) { if(solve(x - a[i].x, y - a[i].y, r)) { LL xy = cal(x, y);
if(idx.count(xy)) { int u = idx[xy]; if(!st[u]) { dfs(u); //printf("%d\n", u);
} } } } } } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) {
int x, y, r; scanf("%d%d%d", &x, &y, &r); LL xy = cal(x, y); // Without this point
if(idx.find(xy) == idx.end()) { // Store this point in idx array idx[xy] = ++cnt; // Store this point in a array
a[cnt] = {x, y, r, 1}; } else { int u = idx[xy];
// This point already exists and has a larger radius , The number under the previous point will be updated r Value of a[u].r = max(a[u].r, r); // The number of occurrences of this point is increased by one ++
a[u].l; } //int u = idx[xy]; //printf("%d %d %d %d\n", a[u].x, a[u].y, a[u].r,
a[u].l); } for(int i = 1; i <= m; i ++ ) { int x, y, r; scanf("%d%d%d", &x, &y,
&r); // Add this point a As the starting point , Go search for other mines a[cnt + 1] = {x, y, r}; dfs(cnt + 1); }
printf("%d", ans); return 0; }

I The question is another one dp, this dp It feels a little simpler than the one above ;

State representation ：f[i][j][k] Indicates before access i At two positions , Just access j There are two stores and the amount of alcohol is exactly k Number of schemes when ;

To be exact, this approach does not maintain all the previous i Access to exactly one location j Number of schemes per store , But the question only asked about the last time I met flowers and just drank up the wine , So for greater than 100 There is no need to change the state of alcohol consumption , Because you're approaching in the back 100 In locations , You can't finish the wine by looking at the flowers .

state transition ; Look at flowers ： f[i][j][k] = f[i - 1][j][k + 1] Yudian ： f[i][j][k] = f[i - 1][j - 1][k
/ 2];// Pay attention to the boundary ! Don't cross the line
#include <bits/stdc++.h> using namespace std; const int N = 110, mod = 1e9 +
7; // front i Visits , visit j What's the capacity of each store long long f[N * 2][N]; int main() { int n, m;
scanf("%d%d", &n, &m); f = 1; for(int i = 1; i < n + m; i ++ ) for(int
j = 0; j <= n; j ++ ) for(int k = 0; k <= 100; k ++ ) { f[i][j][k] =
(f[i][j][k] + f[i - 1][j][k + 1]) % mod; if((k % 2 == 0) && j) f[i][j][k] =
(f[i][j][k] + f[i - 1][j - 1][k / 2]) % mod; } printf("%lld", f[n + m -
1][n]); return 0; }

There are two ways to solve this problem , One is to use set Or heap to maintain a height to interval mapping , The other is to maintain the interval with the join query set , I didn't do this , I used two set To do , Sure enough, I was stuck .

Positive solution ： This problem is essentially a problem of the longest common descent subsequence , For any one h, As long as its altitude drops to the common value during the descent with the previous altitude , Then it doesn't need to cost to continue to decline . If the current altitude it drops has no common value with the previous altitude , It will cost an extra price , To lower your height . We just need to open two arrays and do it .

Time complexity : O(n);
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int
N = 2e5 + 10; LL a[N]; vector<LL> b[N]; int n; LL solve(LL x) { return sqrt(x /
2 + 1); } int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++ )
scanf("%lld", &a[i]); int res = 0; for(int i = 1; i <= n; i ++ ) { while(a[i] >
1) { int flag = 0; for(LL j : b[i - 1]) { if(a[i] == j) { flag = 1; break; } }
if(!flag) res ++; b[i].push_back(a[i]); a[i] = solve(a[i]); } } printf("%d",
res); return 0; }

Technology
Daily Recommendation