- 2022-04-02 16:16
*views 6*- Algorithm
- Blue Bridge Cup

<> 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

- Java296 blogs
- Python265 blogs
- Vue125 blogs
- C Language122 blogs
- Algorithm108 blogs
- MySQL96 blogs
- Flow Chart83 blogs
- JavaScript79 blogs
- More...

©2020-2022 ioDraw All rights reserved