<> The 12th Blue Bridge Cup C++B Group true questions
<> test questions A. space
Xiaolan is ready to use 256MB Open an array in the memory space of , Each element of the array is 32 Bit binary integer .
If the space occupied by the program and the auxiliary space required for maintaining memory are not considered , Excuse me? 256MB How many can be stored in the space of 32 Bit binary integer ?
1MB= 1024KB 1KB= 1024B 1B= 1b
#include <iostream> using namespace std; int main() { cout << 256 * 1024 *
1024 / 4; return 0; }
<> test questions B card
Xiaolan has a lot of digital cards , There are numbers on every card 0 reach 9.
Xiao Lan is going to use these cards to spell some numbers , He wants to 1 Start spelling positive integers , Each one , Just keep it , Cards can't be used to spell other numbers .
Xiaolan wants to know that she can 1 How much .
for example , When Xiaolan has 30 Cards , among 0 reach 9 various 3 Zhang , Then Xiaolan can spell 1 reach 10, But spell 11 Time card 1 There's only one , Not enough to spell 11.
Now Xiaolan has 0 reach 9 Cards of 2021 Zhang , common 20210 Zhang , Excuse me, can Xiao Lan 1 How much ?
Tips ： Computer programming is recommended to solve the problem .
Take out each digit of each number in turn ,
be careful : When less than 0 It means that the current number has been calculated i, therefore i Need to reduce 1, You can simulate it with a decimal
#include <iostream> using namespace std; int a[11]; bool check(int n) {
while(n) { int t = n % 10; if(-- a[t] < 0) return true; n /= 10; } return
false; } int main() { for(int i = 0; i < 10; i ++) a[i] = 2021; for(int i = 1;
; i ++) { if(check(i)) { cout << i - 1; return 0; } } }
<> test questions C straight line
In plane rectangular coordinate system , Two points can determine a straight line .
If there are multiple points on a straight line , Then any two of these points determine the same straight line .
On a given plane 2 × 3 Hours {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z},
That is, the abscissa is 0 reach 1 ( contain 0 and 1) Integer between , The ordinate is 0 reach 2 ( contain 0 and 2) Points between integers .
These points have been determined 11 Different lines .
On a given plane 20 × 21 Hours {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z},
That is, the abscissa is 0 reach 19 ( contain 0 and 19) Integer between , The ordinate is 0 reach 20 ( contain 0 and 20) Points between integers .
How many different straight lines are determined by these points .
set Judging rewriting
#include<iostream> #include<set> #include<vector> #include<cmath> using
namespace std; typedef pair<int,int> PII; set<pair<PII, int>> s; // Weight removal after division
vector<PII> v; int gcd(int a, int b) // Maximum common divisor { return b ? gcd(b, a % b) :
a; } int main(){ for(int i = 0; i < 20; i++) for(int j = 0; j < 21; j++ )
v.push_back({i,j}); // Read in all points for(int i = 0; i < v.size(); i++) { for(int j = i +
1; j < v.size(); j++) { int x1 = v[i].first, y1 = v[i].second; int x2 =
v[j].first, y2 = v[j].second; int A = x2 - x1, B = y1 - y2, C = x1 * y2 - x2 *
y1; int d = gcd(gcd(A,B), C); s.insert({ { B / d, A / d }, C / d });
// Read in the reduced slope and constant set Automatic weight judgment } } cout << s.size(); return 0; }
sort double Writing method , Accuracy problem
#include <iostream> #include <cstring> #include <algorithm> #include <cmath>
using namespace std; const int N = 200000; int n; struct Line { double k, b;
bool operator< (const Line& t) const { if (k != t.k) return k < t.k; return b <
t.b; } }l[N]; int main() { for (int x1 = 0; x1 < 20; x1 ++ ) for (int y1 = 0;
y1 < 21; y1 ++ ) for (int x2 = 0; x2 < 20; x2 ++ ) for (int y2 = 0; y2 < 21; y2
++ ) if (x1 != x2) { double k = (double)(y2 - y1) / (x2 - x1); double b = y1 -
k * x1; l[n ++ ] = {k, b}; } sort(l, l + n); int res = 1; for (int i = 1; i <
n; i ++ ) if (fabs(l[i].k - l[i - 1].k) > 1e-8 || fabs(l[i].b - l[i - 1].b) >
1e-8) res ++ ; cout << res + 20 << endl; // Plus the slope is 0 Twenty vertical lines of return 0; }
<> test questions D Cargo placement
Xiaolan has a huge warehouse , Can put a lot of goods .
Now? , Xiao Lanyou n Boxes of goods shall be placed in the warehouse , Each box of goods is a regular cube .
Xiaolan stipulated the length , wide , Three mutually perpendicular directions , The sides of each case must be strictly parallel to the length , wide , high .
Xiaolan hopes that all the goods will eventually be placed into a big cube . That is, in the long , wide , Stacked separately in the high direction L,W,H Goods , satisfy n = L × W × H.
given n, How many schemes for stacking goods meet the requirements .
for example , When n = 4 Hour , Have the following 6 Schemes ：1×1×4,1×2×2,1×4×1,2×1×2,2×2×1,4×1×1.
Excuse me? , When n = 2021041820210418 （ Attention yes 16 Digit number ） Hour , How many in total
programme ?
Tips ： Computer programming is recommended to solve the problem .
The precondition is a, b, c Will be n to be divisible by , So it's possible to expose the approximate post violence ,（ Direct violence takes too long ...）
#include <iostream> #include <cstring> #include <algorithm> #include <vector>
using namespace std; typedef long long LL; int main() { LL n =
2021041820210418; vector<LL> d; // Divisor board for (LL i = 1; i * i <= n; i ++ ) if (n
% i == 0) { d.push_back(i); if (n / i != i) d.push_back(n / i); } int res = 0;
for (auto a: d) for (auto b: d) for (auto c: d) if (a * b * c == n) res ++ ;
cout << res << endl; return 0; }
<> test questions E route
Xiaolan is very happy after learning the shortest path , He defined a particular graph , Want to find the shortest path in the graph .
The picture of Xiaolan is shown by 2021 Composed of nodes , Serial number 1 to 2021.
For two different nodes a, b, If a and b The absolute value of the difference of is greater than 21, Then there is no edge connection between the two nodes ;
If a and b The absolute value of the difference of is less than or equal to 21, Then there is a line with a length of a and b The undirected edge of the least common multiple of .
for example ： node 1 And node 23 There is no edge connection between ; node 3 And node 24 There is an undirected edge between , Count Reg 24;
node 15 And node 25 There is an undirected edge between , Count Reg 75.
Please calculate , node 1 And node 2021 What is the shortest path length between .
Tips ： Computer programming is recommended to solve the problem .
Template dictation
#include <iostream> #include <cstring> #include <algorithm> #include <queue>
using namespace std; const int N = 2200, M = N * 50; int n; int h[N], e[M],
w[M], ne[M], idx; int q[N], dist[N]; bool st[N]; int gcd(int a, int b) //
Euclidean algorithm { return b ? gcd(b, a % b) : a; } void add(int a, int b, int c) //
Add an edge a->b, Edge weight is c { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int
spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1);
st[1] = true; while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for
(int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] +
w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } }
} return dist[n]; } int main() { n = 2021; memset(h, -1, sizeof h); for (int i
= 1; i <= n; i ++ ) for (int j = max(1, i - 21); j <= min(n, i + 21); j ++ ) {
int d = gcd(i, j); add(i, j, i * j / d); } printf("%d\n", spfa()); return 0; }
<> test questions F Time display
Xiaolan wants to cooperate with her friends to develop a time display website .
On the server , Friend has obtained the current time , Expressed as an integer .
Value is from 1970 year 1 month 1 day 00:00:00 Number of milliseconds elapsed to the current time .
Now? , Xiaolan wants to display this time on the client .
Little blue doesn't need to show year, month and day , Just display the hours, minutes and seconds , Milliseconds are not displayed , Just round it off .
Given a time expressed as an integer , Please output the hour, minute and second corresponding to this time .
thinking ： Just consider the time of day , Not related to calendar issues
#include <iostream> #include <cstring> #include <algorithm> using namespace
std; typedef long long LL; int main() { LL n; cin >> n; n /= 1000; n %= 86400;
int h = n / 3600; n %= 3600; int m = n / 60; int s = n % 60;
printf("%02d:%02d:%02d\n", h, m, s); return 0; }
<> test questions G Weight weighing
<> Title Description
You have a scale and N Weights , this N The weights of the weights are W1, W2, … , WN.
Please calculate how many different weights you can weigh ?
Note that the weights can be placed on both sides of the balance .
<> Input format
The first line of input contains an integer N.
The second line contains N Integers ：W1, W2, W3, … , WN.
about 50% Evaluation case for ,1 ≤ N ≤ 15.
For all profiling cases ,1 ≤ N ≤ 100,N The total weight of each weight does not exceed 100000.
<> Output format
Output an integer to represent the answer .
<> sample input
3 1 4 6
<> sample output
10
#include <iostream> #include <cstring> #include <algorithm> using namespace
std; const int N = 110, M = 200010, B = M / 2; int n, m; int w[N]; bool
f[N][M]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]), m += w[i]; f[0][B] = true; for (int i = 1; i <= n; i ++ )
for (int j = -m; j <= m; j ++ ) // Negative numbers are left , A positive number is the right { f[i][j + B] = f[i - 1][j +
B]; // Negative numbers are possible , So add an offset to all 2D if (j - w[i] >= -m) f[i][j + B] |= f[i - 1][j -
w[i] + B];// Equal or equal to if (j + w[i] <= m) f[i][j + B] |= f[i - 1][j + w[i] + B];
// with f[i][j + B] = f[i - 1][j + w[i] + B] || f[i][j + B]; } int res = 0; for (int
j = 1; j <= m; j ++ ) if (f[n][j + B]) res ++ ; printf("%d\n", res); return 0; }
<> test questions H Yanghui triangle
<> Title Description
The following figure is the famous Yanghui triangle ：
If we press from top to bottom , Arrange all numbers in a row from left to right , The following sequence can be obtained ：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
Given a positive integer N, Please output the first time in the sequence N Which number is it ?
<> Input format
Input contains T that 's ok , express T Group test data .T Not more than 10.
Enter an integer per line N,N Not more than 10^9.
<> Output format
For each set of test data, output a row to indicate the answer .
<> sample input
2 3 6
<> sample output
8 13
thinking ： See code
#include <iostream> #include <cstring> #include <algorithm> using namespace
std; typedef long long LL; int n; /* Find the first one , Yang Hui triangle is symmetrical, so it can't be on the right 1 --- C(0, 0) 1 1 2
--- C(2, 1) 1 3 1 4 6 --- C(4, 2) 1 5 10 1 6 15 20 --- C(6, 3) ....
So it can be concluded that enumerating diagonal rows to find values Listed as ： Second line 2 3 4 5 6 Because the sequence of numbers is ordered and monotonous, it can be solved by dichotomy */ LL C(int a, int b)
// Direct violence for combination number { LL res = 1; for (int i = a, j = 1; j <= b; i --, j ++ ) { res =
res * i / j; if (res > n) return res; } return res; } bool check(int k) // Binary evaluation
{ LL l = k * 2, r = max((LL)n, l); // Line 1 special circumstances , r Must compare l large while (l < r) { LL mid =
l + r >> 1; if (C(mid, k) >= n) r = mid; else l = mid + 1; } if (C(r, k) != n)
return false; // According to coordinates （r,k） Find the position cout << r * (r + 1) / 2 + k + 1 << endl; return
true; } int main() { cin >> n; // n maximum 1e9,C(34, 17) > 1e9, C(32, 16) <
1e9, So just before enumerating 16 A diagonal line is enough for (int k = 16; ; k -- ) if (check(k)) break; return 0; }
<> test questions I Bidirectional sort
<> Title Description
Given sequence (a[1], a[2], … , a[n]) = (1, 2, … , n), Namely a[i] = i.
Xiaolan will test this sequence m Operations , Every time it may be a[1], a[2], … a[qi] Descending sort , Or will a[qi], a[qi+1], … , a[n]
Ascending sort .
Request the sequence after the operation is completed .
<> Input format
The first line of input contains two integers n, m, Represents the length of the sequence and the number of operations, respectively .
next m Line describes the operation on the sequence , Of which No i Line contains two integers pi, qi Represents the operation type and parameters .
When pi = 0 Hour , Indicates that a[1], a[2], … a[qi] Descending sort ; When pi = 1 Hour , Indicates that a[qi], a[qi+1], … , a[n]
Ascending sort ascending sort .
about 30% Evaluation case for ,n,m ≤ 1000;
about 60% Evaluation case for ,n,m ≤ 5000;
For all profiling cases ,1 ≤ n,m ≤ 100000, 0 ≤ ai ≤ 1,1 ≤ bi ≤ n.
<> Output format
Output one line , contain n Integers , Adjacent integers are separated by a space , Represents the sequence after the operation is completed .
<> sample input
3 3 0 3 1 2 0 2
<> sample output
3 1 2
thinking ： Suppose this is our original sequence
Optimization I ： Because the initial sequence is ascending , So it is meaningless if the initial operation is a suffix operation , The sequence will not change , So let's start with the prefix operation , Red is the prefix sequence to be operated on
If there is a continuous prefix operation , We found that only the longest prefix operation is required , Because after the short prefix operation , Long or operation , Why not directly perform the longest prefix operation , The same is true for suffix operation , We put all the operation nodes on the stack , There are two member variables , Whether the current operation is a prefix operation or a suffix operation , The other is the boundary of operation
Optimization II ： If this situation occurs in the following figure
Blue is the original sequence , Red is the longest continuous prefix , Orange is the longest continuous suffix
From the figure below, we find that
* Original sequence AA Segment strictly greater than BB paragraph
* AA paragraph == A1A1 paragraph , BB paragraph == B1B1 paragraph
* therefore A1A1 Segment strictly greater than B1B1 paragraph
* A2A2 paragraph == A1A1 paragraph
* therefore A2A2 Segment strictly greater than CC paragraph , So suffix ascending operation （ orange ） Action only CC Segment
*
The same is true for prefix operations , Action only CC Segment
Optimization III ： When the following occurs
That is, after a prefix operation and a suffix operation , The next prefix operation is after the node of the previous prefix operation , At this time, we can delete the first two operations , Directly perform this prefix operation , Because the last suffix operation and prefix operation are included in this prefix operation , The first two operations are useless , So we just need to keep the current operation
in addition , We can find that in the process of our operations , The operating range is slowly becoming smaller , Every time , There is always a part of the sequence that does not require operation , We can also use a variable to decrementally fill the array
#include <iostream> #include <cstring> #include <algorithm> #define x first
#define y second using namespace std; typedef pair<int, int> PII; const int N =
100010; int n, m; PII stk[N]; int ans[N]; int main() { scanf("%d%d", &n, &m);
int top = 0; while (m -- ) { int p, q; scanf("%d%d", &p, &q); if (!p) { while
(top && stk[top].x == 0) q = max(q, stk[top -- ].y); while (top >= 2 && stk[top
- 1].y <= q) top -= 2; stk[ ++ top] = {0, q}; } else if (top) { while (top &&
stk[top].x == 1) q = min(q, stk[top -- ].y); while (top >= 2 && stk[top - 1].y
>= q) top -= 2; stk[ ++ top] = {1, q}; } } int k = n, l = 1, r = n; for (int i
= 1; i <= top; i ++ ) { if (stk[i].x == 0) while (r > stk[i].y && l <= r) ans[r
-- ] = k -- ; else while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ; if (l >
r) break; } if (top % 2) while (l <= r) ans[l ++ ] = k -- ; else while (l <= r)
ans[r -- ] = k -- ; for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0; }
<> test questions J Parenthesis sequence
<> Title Description
Given a sequence of parentheses , It is required to add as few parentheses as possible to make the sequence of parentheses legal .
When the addition is complete , Will produce different addition results , How many adding results are essentially different .
Two results are essentially different, which means that there is a certain position, and one result is a left parenthesis , The other is a closing parenthesis .
for example , For bracket sequences (((), Just add two parentheses to make it legal
There are several different addition results ：()()(),()(()),(())(),(()()) and ((())).
<> Input format
Input line contains a string s, Represents the given sequence of parentheses , There are only left and right parentheses in the sequence .
about 40% Evaluation case for ,|s| ≤ 200.
For all profiling cases ,1 ≤ |s| ≤ 5000.
<> Output format
Output an integer to represent the answer , The answer may be big , Please output the answer divided by 1000000007
<> sample input
((()
<> sample output
5
thinking ： Considering that we can only insert parentheses in the space , If we add a pair of left and right parentheses that are not in the same space , So they obviously don't interfere with each other ; If it is added in the same gap ,
Then their order of addition is unique , Only ）（, Because if it is （） If , Then our addition this time is invalid , Not enough to add the least parentheses to make the sequence match . From this ,
We only need to calculate the number of schemes with left parentheses , Multiply by the number of schemes with separate right parentheses to be the number of answers
#include <iostream> #include <cstring> #include <algorithm> using namespace
std; typedef long long LL; const int N = 5010, MOD = 1e9 + 7; int n; char
str[N]; LL f[N][N]; // front i Parentheses there are more left parentheses than right parentheses j Collection of LL work() { // initialization memset(f, 0, sizeof
f); f[0][0] = 1; for (int i = 1; i <= n; i ++ ) if (str[i] ==
'(')// If it is an open parenthesis, it is in the previous state j - 1 { for (int j = 1; j <= n; j ++ ) f[i][j] = f[i - 1][j
- 1]; } else { f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD; for (int j = 1; j
<= n; j ++ ) /* f[i][j] = f[i - 1][0] + f[i - 1][1] + ...... + f[i - 1][j]
f[i][j + 1] = f[i - 1][0] + f[i - 1][1] + ...... + f[i - 1][j] + f[i - 1][j +
1] So we can conclude that f[i][j] = f[i][j - 1] + f[i - 1][j - 1] */ f[i][j] = (f[i - 1][j +
1] + f[i][j - 1]) % MOD; } for (int i = 0; i <= n; i ++ ) if (f[n][i]) return
f[n][i]; return -1; } int main() { scanf("%s", str + 1); n = strlen(str + 1);
LL l = work(); // Because the state transition is indicated by the left parenthesis , The title is the right parenthesis, so just reverse the left and right parentheses and exchange them reverse(str + 1, str
+ n + 1); for (int i = 1; i <= n; i ++ ) if (str[i] == '(') str[i] = ')'; else
str[i] = '('; LL r = work(); printf("%lld\n", l * r % MOD); return 0; }
<> reference resources ：
acwing 《 Blue Bridge Cup C++AB Group coaching class 》
Technology