# [Individual problem solutions for the 13th Blue Bridge Cup Provincial Competition in 2022]

Hits: 0

### A: Nine to [Decimal] (5 points)

Topic description:
Nine positive integers (2022) 9 (2022)_9 (2022)9​Convert to decimal equal to what?

AC code

```#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace  std ;
int  main ()
{
// IOS;
int k = 9 ;            // base
string num = "2022" ; // number
int ans = 0 ;
ll temp = 1;
int len = num.size();
for (int i = len - 1; i >= 0; --i)
{
ans += temp * (num[i] - '0');
temp *= k;
}
cout << ans;
return 0;
}```

### B: Shunja Date (5 points)

Title description:
Xiao Ming likes Shunzi very much. A straight refers to three consecutive numbers: 123, 456, etc. A straight date refers to a date in which any consecutive three-digit number is a straight in the `yyyymmdd`notation of a date. For example `20220123`is a straight date, because it appears a straight: 123; while `20221023`is not a straight date, it does not have a straight. Xiao Ming wants to know how many Shunzi dates there are in the entire 2022
year.

I
don’t know if a 0 starts with a straight, but if it counts, it’s 14, not a 4.

### C: Statistics for brushing questions (10 points)

Topic description:
Xiao Ming decided to work hard to prepare for [the Blue Bridge Cup] competition from next Monday. He plans to do it every day from Monday to Friday a a aQuestions to do every day on Saturday and Sunday b b bRoad topic. Please help Xiao Ming to calculate, according to the plan, he will achieve the number of questions to be greater than or equal to in the next few days. n n nquestion?

Input format:
input a line containing three integers a , b a, b a,b and n n n.

Output format:
output an integer representing the number of days.

Input sample:

10 20 99

Sample output:

8

Evaluation Case Size and Convention
For 50% of evaluation cases, 1 ≤ a , b , n ≤ 1 0 6 1 ≤ a, b, n ≤ 10^6 1≤a,b,n≤106
For 100% of the evaluation cases, 1 ≤ a , b , n ≤ 1 0 18 1 ≤ a, b, n ≤ 10^{18} 1≤a,b,n≤1018

ideas
_

AC code

```#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;

int main()
{
IOS;
ll a, b, n;
cin >> a >> b >> n;
ll ans = n / (5 * a + 2 * b) * 7;
ll t = ans / 7 * (5 * a + 2 * b);
for (int i = 1; i <= 7; i++)
{
if (t >= n)
break;
if (i < 6)
t += a, ans++;
else
t += b, ans++;
}
cout << ans << endl;

return 0;
}```

### D: pruning shrubs (10 points)

Topic description:
Alice is going to finish a job pruning a bush.
There are N shrubs neatly lined up from left to right. Alice prunes a shrub every evening so that the height of the shrub becomes 0 cm. Alice’s order of pruning shrubs is to start with the leftmost shrub and prune one shrub to the right each day. When the rightmost shrub has been trimmed, she will turn around and start trimming the shrub to the left the next day. Turn direction again until the leftmost shrub has been trimmed. And so on and so forth.
The bush will grow 1 cm taller from morning to evening and not the rest of the time. On the morning of the first day, the height of all shrubs was 0 cm. Alice wants to know how tall each bush can grow.

Input format:
a positive integer N N N , the meaning is as described in the title.

Output format:
output N N N lines, each line is an integer, the th line represents the ith i i How tall can i trees grow.

Input sample:

3

Sample output:

4
2
4

Measurement case size and conventions N ≤ 10 N ≤ 10
for 30% of the dataN≤1 0 .
For 100% of the data, 1 < N ≤ 10000 1 < N ≤ 10000 1<N≤10000.

ideas
_

AC code

```#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;

int main()
{
IOS;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cout << 2 * max(n - i, i - 1) << endl;
return 0;
}```

### E: X-base subtraction (15 points)

Topic description: The
hexadecimal defines the number of digits in the digits.
X X X base is a very magical base, because the base of each digit is not fixed! Say something like
X X X base number, the lowest digit is binary, the second digit is decimal, and the third digit is octal, then
X X X base number 321 321 3 2 1 converts to decimal as 65 65 65 . _
Now there are two X X Integer A A in base XA and B B B , but the base of each digit is still uncertain
, only A A A and B are the same base rule, and each digit is up to N N N base, the minimum is binary
. Please calculate A − B A − B What is the smallest possible result of A − B.
Note that you need to guarantee A A A and B B B at X X It is legal in X base, that is, the number on each digit
should be smaller than its base.

Input format:
the first line is a positive integer N N N , the meaning is as described in the title.
The second line is a positive integer M a M_a Ma​, which means X X X number A A A ‘s digits.
The third row M a M_a Ma​space-separated integers representing X X X number A A A
Representation of the numbers on each digit in decimal inorder from high to low
The fourth line is a positive integer M b M_b Mb​, which means X X X- ary number B B The number of digits of B.
Fifth row M b M_b Mb​space-separated integers representing X X X- ary number B B BRepresentation
of the numbers on each digit in decimal inorder from high to low
Note that all numbers in the input are in decimal.

Output format:
output an integer in one line, representing X X X- ary number A − B A − B The smallest possible value of the result of A − B is converted to decimal
and modulo 1000000007 1000000007 1 0 0 0 0 0 0 0 0 7 results.

Input sample:

11
3
10 4 0
3
1 2 0

Sample output:

94

Measurement case size and conventions
For 30% of the data, N ≤ 10 ; Ma , M b ≤ 8 N ≤ 10 ; Ma, Mb ≤ 8 N≤10;Ma,Mb≤8. For
100% data, 2 ≤ N ≤ 1000; 1 ≤ Ma, M b ≤ 100000; A ≥ B 2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B 2≤N≤1000;1≤Ma,Mb≤100000;A≥B.

### F: Statistics Submatrix (15 points)

Topic description:
Given an N × M N × M N×Matrix A of M , please count how many sub-matrices (minimum 1 × 1 1 × 1 1×1 , maximum
N × M N × M N×M ) satisfies that the sum of all numbers in the submatrix does not exceed the given integer K K K?

Input format:
The first line contains three integers N , M and K N, M and K N,M and K. After
N N N lines each containing M M M integers representing the matrix A A A

Output format:
An integer representing the answer.

Input sample:

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

Sample output:

19

Measurement case size and conventions
For 30% of the data, N , M ≤ 20 N, M ≤ 20 N,M≤20. For
70% of the data, N , M ≤ 100 N, M ≤ 100 N,M≤1 0 0 .
For 100% of the data, 1 ≤ N , M ≤ 500 ; 0 ≤ A i j ≤ 1000 ; 1 ≤ K ≤ 250000000 1 ≤ N, M ≤ 500; 0 ≤ A_{ij} ≤ 1000; 1 ≤ K ≤ 250000000 1≤N,M≤500;0≤Aij​≤1000;1≤K≤250000000.

Ideas
First create a two-dimensional prefix and array.
First enumerate two vertical straight lines, which are the left and right sides of the matrix, and then scan with two pointers from top to bottom to turn a two-dimensional problem into a one-dimensional problem. That is, given a one-dimensional array, find a continuous interval and the number of intervals less than or equal to k

AC code

```#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 510;
int a[N][N], b[N][N];
int main()
{
IOS;
int n, m, k;
ll ans = 0;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
}
}
for ( int l = 1 ; l <= m; l++) // enumerate the left side of the matrix
{
for ( int r = l; r <= m; r++) // enumerate the right side of the matrix
{
for ( int i = 1 , j = 1 ; i <= n; i++) //With left and right boundaries, scan from top to bottom
{
while (j <= i && (b[i][r] - b[i][l - 1] - b[j - 1][r] + b[j - 1][l - 1]) > k)
j++;
if (j <= i) //It is possible that the smallest matrix is ​​not satisfied, then j>i
ans += (i - j + 1 );
}
}
}
cout << ans << endl;
return 0;
}```

### G: Block Drawing (20 points)

Description of the title:
Xiao Ming has recently become obsessed with building block painting. There are two types of building blocks, namely II and II .Type I (size 2 unit area) and L L L -shaped (3 unit areas in size)
At the same time, Xiaoming has an area of ​​2 × N 2 × N 2×N canvas, canvas consists of 2 x N 1 x 1 2 x N 1 x 1 2×N 1 _×1 area composition. Xiao Ming needs to use the above two kinds of building blocks to fill the canvas. He wants to know how many different ways are there in total? The blocks can be rotated arbitrarily, and the orientation of the canvas is fixed.

Input format:
input an integer N N N , representing the canvas size.

Output format:
Output an integer representing the answer. Since the answer can be large, output its pair 1000000007 1000000007 1 0 0 0 0 0 0 0 0 7 Modulo value

Input sample:

3

Sample output:

5

Test case size and conventions
For all test cases, 1 ≤ N ≤ 10000000 1 ≤ N ≤ 10000000 1≤N≤10000000.

Ideas:
Linear DP.

AC code

```#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const int N = 1e7 + 10;
const int mod = 1e9 + 7;

ll dp[N][ 4 ];
// 1 fill in the top 2 fill in the bottom 3 all fill

int main()
{
int n;
cin >> n;
dp = 1;
for (int i = 1; i <= n; i++)
{
dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
dp[i][ 3 ] = ((dp[i - 1 ][ 3 ] + dp[i - 1 ][ 1 ]) % mod + (dp[i - 1 ][ 2 ] + dp[i - 2 ] [ 3 ]) % mod) % mod; //The sum will exceed int without separate summation, and LL cannot be used for 1e7
}

cout << dp[n] % mod;
}```

### I: Li Bai Dajiu Enhanced Edition (25 points)

Topic description:
It is said that the great poet Li Bai was a great drinker all his life. Fortunately he never drives.
One day, he came out of the house with a jug with 2 buckets of wine in it. As he walked, he sang:
Walking on the street with nothing to do, carrying a pot to make wine. Every store doubles, and every flower drinks a bucket. Walking on the street with nothing to do, carrying a pot to make wine. Every store doubles, and every flower drinks a bucket. Walking on the street with nothing to do , carrying a pot to make wine . Every store doubles , and every flower drinks a bucket .
Along the way, he encountered a total of shop N N N times, encounter flower M M M times. Knowing that the last time he met was Hua,
he just finished drinking.
Could you please calculate the order in which Li Bai encounters shops and flowers along the way, how many different possibilities are there?
Note: It is legal to meet the shop when there is no wine in the pot (0 buckets), and there is still no wine after doubling it; but it
is illegal to meet the flower when there is no wine.

Input format:
The first line contains two integers N N N and M M M.

Output format:
Output an integer representing the answer. Since the answer can be large, output the result modulo 1000000007.

Input sample:

5 10

Sample output:

14

Measurement case size and conventions
For 40% of measurement cases: 1 ≤ N , M ≤ 10 1 ≤ N, M ≤ 10 1≤N,M≤1 0 .
For 100% evaluation cases: 1 ≤ N , M ≤ 100 1 ≤ N, M ≤ 100 1≤N,M≤100。

Idea
At a glance dp, the dp scheme is

If the last step is to go to the store, then j should be greater than 0, because there is at least the last step to the store, and the same is true for flowers,
if the last step is to go to the store, then the wine in the previous step should be k / 2, which is why we The k should be divisible by 2.
If the last move is to flower, then the wine in hand in the previous move should be k + 1.
When printing the answer, it is not printing dp[n][m], because it is impossible to distinguish whether it is the flower or the store at the end,
so push forward one step. If the flower is at the end, then the last step after drinking should be dp[n – 1][m].

AC code

```#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
const  int mod = 1e9 + 7 ;
const  int N = 110 ;
int dp[N][N][N]; //The three dimensions are shop, flower, wine
int  main ()
{
IOS;
int n, m;
cin >> n >> m;
dp[ 0 ][ 0 ][ 2 ] = 1 ; //initial state
for ( int i = 0 ; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k <= m; k++)
{

if (i && k % 2 == 0)
dp[i][j][k] += dp[i - 1 ][j][k / 2 ] % mod; // encounter shop
if (j)
dp[i][j][k] += dp[i][j - 1 ][k + 1 ] % mod; // encounter flower
}
}
}
cout << dp[n][m - 1 ][ 1 ] << endl ; //The last one encountered must be a flower
return  0 ;
}```