<>2022 The 13th Blue Bridge Cup provincial competition C++B Group personal problem solving
<> test questions A: Decimal to nine
#include <iostream> #include <cmath> using namespace std; int main() { cout <<
2 * pow(9, 0) + 2 * pow(9, 1) + 0 * pow(9, 2) + 2 * pow(9, 3) << endl; return
0; }
answer ：1478
<> test questions B: Shunzi date
There are many disputes at present , Divided into 3 Kinds of answers ：4,5,14
The answer I wrote in the exam was 5
However, I have observed that more netizens' answers are 4
The blue bridge cloud class that night after the game said 14（ unofficial ）
Let me summarize ：
The first answer ：5
Look at the question , In the description 20220123 Time , Said it had a shunzi ：123.
So it can be considered that only 123 This is a shunzi , and 012 It's not easy .
Then in the description 20221023 When it comes to 210 This contrarian shunzi , But it says it's not a shunzi date . So I think it's more clear here 0
Can't be included , And those in reverse order can be regarded as shunzi .
20220123 20220321 20221123 20221230 20221231
The second answer ：4
That is to say 012 And inverse CIS （ as 210） Are not shunzi , So put the above 20220321 Remove
20220123 20221123 20221230 20221231
The third answer ：14
The title says shunzi is ： Three consecutive numbers , Not three digits . therefore 012 It's also shunzi . Then from the second example 20221023 hear ：210 This reverse order is not a straight son .
If you want to count 012, So the second example is 210 Is this in reverse order lost
20220120 20220121 20220122 20220123 20220124 20220125 20220126 20220127
20220128 20220129 20221012 20221123 20221230 20221231
I don't know the right answer at the moment , We can only wait for the official explanation
orz
<> test questions C: Brush question statistics
<>【 sample input 】
10 20 99
<>【 sample output 】
8
trap ： be careful a, b, n To use long long Save
Code written during the exam ： Only considering n To use long long Save , It's useless long long Save a, b, I haven't considered that the time may exceed the limit
#include <iostream> using namespace std; int main() { int cnt = 1; long long
n; int a, b; cin >> a >> b >> n; long long sum = 0; while (sum < n) { if (cnt %
7 == 0 || cnt % 7 == 6) { sum += b; } else { sum += a; } cnt++; } //
Exit when exceeded while loop , So the answer needs to be minus one . cout << cnt - 1 << endl; return 0; }
Post game optimization code ： Take the surplus before violence
#include <iostream> using namespace std; int main() { long long a, b, n; cin
>> a >> b >> n; int week = 5 * a + 2 * b; long long ans = n / week * 7; n %=
week; int sum = 0; for (int i = 1; i <= 7 && sum < n; i++) { if (i % 7 == 6 ||
i % 7 == 0) { sum += b; } else { sum += a; } ans++; } cout << ans << endl;
return 0; }
<> test questions D: Pruning shrubs
<>【 sample input 】
3
<>【 sample output 】
4 2 4
First, use violence to find rules , Then simplify the code according to the law
// Violence code ： Walk back and forth twice . Note that the two boundaries should be removed when returning . #include <iostream> #include <cstring> using
namespace std; const int maxn = 1e4 + 100; int a[maxn]; int maxHeight[maxn];
int main() { int n; while (cin >> n) { memset(a, 0, sizeof(a));
memset(maxHeight, 0, sizeof(maxHeight)); // Walk back and forth twice for (int today = 0; today <
n; today++) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] > maxHeight[i]) {
maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for (int today = n -
2; today > 0; today--) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] >
maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for
(int today = 0; today < n; today++) { for (int i = 0; i < n; i++) { a[i]++; if
(a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } }
} for (int today = n - 2; today > 0; today--) { for (int i = 0; i < n; i++) {
a[i]++; if (a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) {
a[i] = 0; } } } for (int i = 0; i < n; i++) { cout << maxHeight[i] << " "; }
cout << endl << endl; } return 0; }
give the result as follows ：
Code can be simplified by finding rules ：
#include <iostream> using namespace std; const int maxn = 1e4 + 10; int
ans[maxn]; int main() { int n; cin >> n; for (int i = 0; i < n / 2; i++) {
ans[i] = ans[n - i - 1] = (n - i - 1) * 2; } // Odd cases are handled separately ans[n / 2] = n / 2 *
2; for (int i = 0; i < n; i++) { cout << ans[i] << endl; } return 0; }
<> test questions E: X Binary subtraction
<>【 sample input 】
11 3 10 4 0 3 1 2 0
<>【 sample output 】
94
I watched it for an hour , Can't read questions orz…
<> test questions F: Statistical submatrix
<>【 sample input 】
3 4 10 1 2 3 4 5 6 7 8 9 10 11 12
<>【 sample output 】
19
be careful k It's over int Range （ Although I can't get there, it's already overtime , But we should pay attention ）,int The scope is -21 4748 3648 ～ 21 4748 3647
(21*10^8)
Can not do , Direct violence ,6 individual for !
#include <iostream> using namespace std; int mat[550][550]; int main() { int
n, m; long long k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int
j = 1; j <= m; j++) { cin >> mat[i][j]; } } long long sum = 0; long long cnt =
0; for (int h1 = 1; h1 <= n; h1++) { for (int h2 = h1; h2 <= n; h2++) { for
(int l1 = 1; l1 <= m; l1++) { for (int l2 = l1; l2 <= m; l2++) { sum = 0; for
(int h = h1; h <= h2; h++) { for (int l = l1; l <= l2; l++) { sum += mat[h][l];
} } if (sum <= k) { cnt++; } } } } } cout << cnt << endl; return 0; }
<> test questions G: Building block painting
<>【 sample input 】
3
<>【 sample output 】
5
trap ： Pay attention to take mold take mold take mold , People often forget this !!!
（ yes , for instance , I forgot to take the module after the penultimate question .....
This problem took me three blank sheets of paper , I from n = 1 Here it is n = 6, For an hour .
in my submission dp Is to find rules , however , Damn it, it's me n = 6 I missed a situation when I was （ Three columns are placed horizontally ）, So that we can't find the law all the time ...
The law of this problem is , The first n The front column can be arranged through , Plus the arrangement of those foundations .
First case ：
dp[n] Can pass dp[n - 1] Add an ordinary column to get
The second case ：
dp[n] Can pass dp[n - 2] Add two horizontal pieces to get
The third case ：
dp[n] Can pass dp[n - 3] Add two triangles and pile them up , But it should be noted that , There are two ways to stack the two triangles , So double it dp[n - 3]
The fourth case ：（ I missed the exam 555
dp[n] Can pass dp[n - 4]
Plus a triangle from the left and right , The combination of several horizontal blocks in the middle is obtained , The same as the third case , This combination can be reversed , That is, there are two stacking methods , So double that dp[n - 4]
To sum up ：dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3] * 2 + dp[n - 4] * 2
#include <iostream> using namespace std; const long long MOD = 1e9 + 7; const
int maxn = 1e7 + 100; long long dp[maxn]; int main() { int n; cin >> n; dp[0] =
1; dp[1] = 1; dp[2] = 2; dp[3] = 5; for (int i = 4; i <= n; i++) { //
Note that the remainder should be taken after each addition dp[i] = (((((dp[i - 1] + dp[i - 2]) % MOD) + dp[i - 3] * 2) % MOD)
+ dp[i - 4] * 2) % MOD; } cout << dp[n] << endl; return 0; }
<> test questions H: mine clearance
<>【 sample input 】
2 1 2 2 4 4 4 2 0 0 5
<>【 sample output 】
2
Half an hour before the game, I took a special look BFS, Yes !
trap ： Multiple mine blasting and demining rockets can exist at one point . When the mine is located on the boundary of the explosion range, it will also be detonated .
#include <iostream> #include <queue> #include <cmath> #include <map> using
namespace std; const int maxn = 50100; // Record coordinates and radius int x_pos[maxn]; int
y_pos[maxn]; int radius[maxn]; bool vis[maxn]; // Used to record whether this point exploded // be used for bfs of
struct, More convenient to handle struct point { int x, y, r; // Put the structure into map in , You need to write one yourself operator
To sort , because map Itself is orderly bool operator < (const point& p) const { if (x == p.x) { if
(y == p.y) { return r < p.y; } return y < p.y; } return x < p.x; } };
map<point, int> all; double getDis(int x1, int y1, int x2, int y2) { return
sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } int bfs(point begin, int
n) { int cnt = 0; queue<point> q; q.push(begin); while (!q.empty()) { point cur
= q.front(); q.pop(); // Traverse to 2 A square whose radius is twice the side length , Find the mine involved in its explosion for (int i = cur.y -
cur.r; i <= cur.y + cur.r; i++) { for (int j = cur.x - cur.r; j <= cur.x +
cur.r; j++) { if(getDis(j, i, cur.x, cur.y) > cur.r) { continue; } point temp;
temp.y = i, temp.x = j; for (int k = 0; k < n; k++) { if (!vis[k] && x_pos[k]
== temp.x && y_pos[k] == temp.y) { temp.r = radius[k]; q.push(temp); cnt++;
all[temp]--; vis[k] = true; // Marked to explode } } } } } return cnt; } int main() { int
n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> x_pos[i] >> y_pos[i]
>> radius[i]; vis[i] = false; // Initialization hasn't exploded yet } int x, y, r; for (int i = 0; i <
m; i++) { point p; cin >> p.x >> p.y >> p.r; cout << bfs(p, n) << '\n'; //
dev Debugging is not working yet endl, Otherwise, you can't go to the next step } return 0; }
<> test questions I: Li Bai's enhanced version
<>【 sample input 】
5 10
<>【 sample output 】
14
Tears in my eyes , Writing problem solving discovery I unexpectedly however Forget to take the mold forget to take the mold forget to take the mold 5555555555
We must remember to take the mold !!!
Practice 1 ： Backtracking method （ Method used in competition ）
Years ago and years later, I practiced backtracking for a period of time , I think it's very interesting .
I took a special look half an hour before the game !! Then it took the last half hour of the exam 20min Just write it out .
I wrote the framework at once , But I'm in a hurry , Many questions and conditions are not clear , Led to a long-time error , But it's okay , If the answer to this question is wrong, it is larger than the correct answer , It's easy to find mistakes .
The main errors are as follows ：
① A total of must and only have to go through N Secondary store ,M Secondary flower
② The last encounter must be flowers
③ After finally meeting flowers , The wine must be drunk
④ When you meet flowers on the way , Wine cannot be empty
#include <iostream> #include <string> #include <vector> using namespace std;
const int MOD = 1e9 + 7; void backTrack(vector<char>& temp, vector<vector<char>
>& ans, int n, int m, int nn, int mm, int jiu) { if (jiu < 0) return; //
If you encounter flowers but no wine , Then it does not meet the conditions if (nn > n || mm > m) return; // If more than N Secondary store ,M Secondary flower , Then it does not meet the conditions if
(temp.size() == n + m) { if (jiu == 0 && temp.back() == '0') { //
If you finally arrive at the store, it doesn't meet the conditions ans.push_back(temp); } return; } temp.push_back('0');
backTrack(temp, ans, n, m, nn, mm + 1, jiu - 1); temp.pop_back();
temp.push_back('1'); backTrack(temp, ans, n, m, nn + 1, mm, jiu * 2);
temp.pop_back(); } int main() { int n, m; cin >> n >> m; int jiu = 2;
vector<char> temp; vector<vector<char> > ans; backTrack(temp, ans, n, m, 0, 0,
jiu); cout << ans.size() % MOD << endl; return 0; }
Practice 2 ： three-dimensional dp（ Optimization method of post game learning ）
The three dimensions correspond to each other ： How many steps have you taken , How many pubs have you passed , How much wine is left in the jug
At the end of the n Step time , He may have come from flowers , It could have come from the pub , So add all the possible ways to encounter flowers in the next step , Plus all the possible ways to meet the tavern in the last step .
#include <iostream> using namespace std; const int MOD = 1e9 + 7; const int
maxn = 105; long long dp[maxn][maxn][maxn] = { 0 }; int main() { int n, m; cin
>> n >> m; // initialization dp dp[0][0][2] = 1; for (int i = 1; i <= n + m; i++) { for
(int j = 0; j <= i; j++) { for (int k = 0; k <= 100; k++) { // After meeting flowers, we arrived at No i step
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k + 1]) % MOD; // Meet the tavern and arrive at No i step // When
k % 2 == 0 It could have come from the pub , Because the wine doubles after passing the pub if (j != 0 && k % 2 == 0) { dp[i][j][k] =
(dp[i][j][k] + dp[i - 1][j - 1][k / 2]) % MOD; } } } } cout << dp[n + m -
1][n][1] << endl; return 0; }
<> test questions J: Chop bamboo
<>【 sample input 】
6 2 1 4 2 6 7
<>【 sample output 】
5
Last ten minutes left , There's no time to do it , I really can't do it after reading the eye questions .
<> summary
① Attention to topic requirements , Remember to take the mold !
② Attention range , May need to use long long
③ Don't spend too long on a question card , Like I'm here E I haven't understood the problem card for an hour , You should change questions early , Finally, change your mind and come back. Maybe you can understand it instead
Technology