# 第十三届蓝桥杯省赛C++ B组题解

## 试题 A: 九进制转十进制

#### 解题思路

(

2022

)

9

(2022)_9

(2022)9 转化成10进制.

2

9

0

+

2

9

1

+

0

9

2

+

2

9

3

2 * 9^0 + 2 * 9^1 + 0 * 9^2 + 2 * 9^3

290+291+092+293 填空.

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
int main()
{
int x = 2022;
int res = 0, base = 1;
do {
res += x % 10 * base;
x /= 10;
base *= 9;
} while (x);

printf("%dn", res);

/** 或者直接计算
int qaq = 2 + 2 * 9 + 2 * 9 * 9 * 9;
cout << qaq << endl;
*/
return 0;
}


## 试题 B: 顺子日期

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

string fact(int x) {
string s;
do {
s += '0' + x % 10;
x /= 10;
} while (x);

reverse(s.begin(), s.end());
if (s.size() == 1) s = "0" + s;

return s;
}

bool judge(const string& s) {
int len = 0, last = -2;
for (int i = 0; i < s.size(); ++i) {
int op = s[i] - '0';
op == last + 1 ? ++len : len = 1;

last = op;

if (len == 3) return 1;
}
return 0;
}
int main()
{
int res = 0;
rep(m, 12) {
rep(d, month[m]) {
string s = "2022" + fact(m) + fact(d);

if (judge(s)) res++, printf("%sn", s.c_str());
}
}

cout << res << endl;

return 0;
}


## 试题 C: 刷题统计

#### 解题思路

n

u

m

=

n

w

e

e

k

num = lfloor frac{n}{week} rfloor

num=weekn来计算出答案包含

n

u

m

num

num整周.然后再暴力最后一周的情况即可.

9

1

0

18

9 * 10^{18}

91018, 因此

w

e

e

k

week

week并不会导致溢出.

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
int main()
{
ll a, b, n; cin >> a >> b >> n;

ll week = 5 * a + 2 * b;

ll res = n / week * 7;
n %= week;

rep(i, 5) if (n > 0) n -= a, res++;
rep(i, 2) if (n > 0) n -= b, res++;

cout << res << endl;

return 0;
}


## 试题 D: 修剪灌木

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10;
int a[N];
int main()
{
int n; cin >> n;

if (n == 1) {
printf("%dn", 1);
return 0;
}

rep(i, (n + 1) / 2) {
int l = i, r = n - i + 1;
a[l] = a[r] = (n - i) * 2;
}

rep(i, n) printf("%dn", a[i]);

return 0;
}


## 试题 E: X 进制减法

#### 解题思路

321

321

321放入数组

a

[

]

a[]

a[], 有

a

[

0

]

=

3

,

a

[

1

]

=

2

,

a

[

2

]

=

1

a[0] = 3, a[1] = 2, a[2] = 1

a[0]=3,a[1]=2,a[2]=1 .

a

[

1

]

=

2

a[1] = 2

a[1]=2这一位为

10

10

10进制, 其高位有

a

[

0

]

=

3

a[0] = 3

a[0]=3, 说明如果不产生进位, 那么有

a

[

1

]

=

2

10

+

3

=

23

a[1] = 2 * 10 + 3 = 23

a[1]=210+3=23.

a

[

2

]

=

1

a[2] = 1

a[2]=1, 其高位

a

[

1

]

=

23

a[1] = 23

a[1]=23(我们刚计算的), 如果不进位, 则

a

[

0

]

=

23

2

+

1

=

65

a[0] = 23 * 2 + 1 = 65

a[0]=232+1=65

A

B

A ge B

AB, 且问最小的

A

B

A - B

AB.

A

,

B

A, B

A,B两个数右对齐后, 从右往左数第

i

i

i位的最小进制为:

m

a

x

(

{

A

o

p

i

+

1

,

B

o

p

i

+

1

,

2

}

)

max({ Aop_i + 1, Bop_i + 1, 2 })

max({Aopi+1,Bopi+1,2}), 其中

A

o

p

i

,

B

o

p

i

Aop_i, Bop_i

Aopi,Bopi为这位上,

A

,

B

A, B

A,B的数字.

A: 3 2 1
B:   4 0
M: 4 5 2 // 最小进制位


#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10, mod = 1000000007;
int a[N], b[N];
int main()
{
int n; cin >> n;
int la; cin >> la;
rep(i, la) scanf("%d", &a[i]);

int lb; cin >> lb;
rep(i, lb) scanf("%d", &b[i]);

int suma = 0, sumb = 0;
rep(i, la - lb) {
// 之前的和是suma, 这位进制至少是max(ai + 1, 2)
int low = max(a[i] + 1, 2);
suma = (1ll * suma * low + a[i]) % mod;
}

int py = la - lb; //偏移量
rep(i, lb) {
int opa = a[i + py], opb = b[i];
int low = max(opa, opb) + 1;
low = max(2, low);

suma = (1ll * suma * low + opa) % mod;
sumb = (1ll * sumb * low + opb) % mod;
}

int res = (suma - sumb + mod) % mod;
cout << res << endl;

return 0;
}


## 试题 F: 统计子矩阵

#### 解题思路

##### 赛场思路

O

(

n

4

)

O(n^4)

O(n4)的做法也不过分吧?

(

x

1

,

y

1

)

(x_1, y_1)

(x1,y1), 右下角

(

x

2

,

y

2

)

(x_2, y_2)

(x2,y2), 那么我们可以枚举

x

1

,

y

1

,

x

2

x_1, y_1, x_2

x1,y1,x2, 然后

y

2

y_2

y2是具有单调性的, 因此优化后复杂度为:

O

(

n

3

l

o

g

n

)

O(n^3logn)

O(n3logn). 虽然有些爆炸, 但是骗分足够了.

O

(

n

3

)

O(n^3)

O(n3)

#### 参考代码

/* 做法一: 复杂度O(n^3logn) */
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 5E2 + 10;
int a[N][N], s[N][N];

int calc(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
int main()
{
int n, m, k; cin >> n >> m >> k;

rep(i, n) rep(j, m) {
scanf("%d", &a[i][j]);
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}

ll res = 0;
rep(x1, n) rep(y1, m) {
for (int x2 = x1; x2 <= n; ++x2) {
if (calc(x1, y1, x2, y1) > k) break;

int l = y1, r = m;
while (l < r) {
int mid = l + r + 1 >> 1;
if (calc(x1, y1, x2, mid) <= k) l = mid;
else r = mid - 1;
}

res += (r - y1 + 1);

}
}

cout << res << endl;

return 0;
}

/* 做法2: 复杂度O(n^3) */
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 5E2 + 10;
int a[N][N], s[N][N];

int calc(int cur, int L, int R) { return s[cur][R] - s[cur][L - 1]; }
int main()
{
int n, m, k; cin >> n >> m >> k;
rep(i, n) rep(j, m) {
scanf("%d", &a[i][j]);
s[i][j] = s[i][j - 1] + a[i][j];
}

int res = 0;
rep(L, m) for (int R = L; R <= m; ++R) {
int top = 0, down = 0;
for (int l = 1, r = 0; l <= n; ++l) {
while (r + 1 <= n and down + calc(r + 1, L, R) - top <= k) {
down += calc(++r, L, R);
}

if (down - top <= k) {
res += r - l + 1;
}

top += calc(l, L, R);
}
}

cout << res << endl;

return 0;
}


## 试题 G: 积木画

#### 解题思路

2

2

2 * 2

22的格子即可完成不同种排列组合, L型则需要

3

2

3 * 2

32.

i

i

i列时, 比

i

1

i - 1

i1列多出了一列, 这一列我们只能竖着放I.

i

2

i - 2

i2列多出了两列, 这两列我们只能横着放I, 否则会与

i

1

i - 1

i1列的情况重复.

i

3

i - 3

i3列多出了三列, 此时我们只能放L型, 否则同样会和前面冲突, 而对于

3

2

3 * 2

32的格子, 有两种放L型积木的方式, 因此要

×

2

times 2

×2.

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E7 + 10, mod = 1000000007;
int a[N]; // 当然你可以选择不开数组.
int main()
{
int n; cin >> n;

a[1] = 1, a[2] = 2, a[3] = 5;

for (int i = 4; i <= n; ++i) {
a[i] = a[i - 1]; // 加一列在后面
a[i] = (a[i] + a[i - 2]) % mod;
a[i] = (0ll + a[i] + a[i - 3] * 2) % mod;
}

cout << a[n] << endl;

return 0;
}


## 试题 H: 扫雷

O

(

n

r

2

l

o

g

n

)

O(nr^2logn)

O(nr2logn)

l

o

g

log

log但是写起来太复杂了.

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

struct node {
int x, y, r;
node(int a, int b, int c) {
x = a, y = b, r = c;
}
};

map<PII, PII> mp; // { x, y } { r, num }

double getdis(const pair<int, int>& a, const pair<int, int>& b) {
int x1 = a.first, y1 = a.second;
int x2 = b.first, y2 = b.second;
ll x = (x1 - x2), y = (y1 - y2);
return sqrt(x * x + y * y);
}

int main()
{
int n, m; cin >> n >> m;
rep(i, n) {
int x, y, r; scanf("%d %d %d", &x, &y, &r);

PII p = make_pair(x, y);
if (!mp.count(p)) mp[p] = make_pair(r, 1);
else {
PII op = mp[p];
mp[p] = make_pair(max(op.first, r), op.second + 1);
}
}

queue<node> q;
rep(i, m) {
int x, y, r; scanf("%d %d %d", &x, &y, &r);
q.push(node(x, y, r));

int res = 0;
while (!q.empty()) {
node op = q.front(); q.pop();
x = op.x, y = op.y, r = op.r;
PII p = make_pair(x, y);

for (int px = x - r; px <= x + r; ++px) {
for (int py = y - r; py <= y + r; ++py) {
PII pp = make_pair(px, py);

if (getdis(p, pp) > r) continue;

if (!mp.count(pp)) continue;
PII now = mp[pp];
mp.erase(pp);

q.push(node(pp.first, pp.second, now.first));
res += now.second;
}
}
}
printf("%dn", res);
}

return 0;
}


## 试题 I: 李白打酒加强版

#### 参考代码

/* 暴力做法, 40%没问题 */
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int mod = 1000000007;
int main()
{
int n, m; cin >> n >> m;
const int B = n + m;
const int TOP = 1 << B;

int res = 0;
for (int i = 0; i < TOP; ++i) {
if (i % 2 == 1 or bitset<32>(i).count() != n) continue;

ll now = 2;
for (int j = B - 1; j >= 0; --j) {
if (i >> j & 1) now *= 2;
else now--;
}

if (!now) res++;
}

cout << res << endl;

return 0;
}

/* DP 100% O(n^3) 代码注释为比赛时的注释, 未修改 */
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E2 + 10, mod = 1000000007;
int dp[N * 2][N][N]; // 前i步中, 还有k个花 有j口酒的情况
int n, m;
int fact() {
int all = n + m;

dp[0][2][m] = 1;
rep(i, all) { // 枚举总步数
for (int j = 0; j <= m; ++j) { // 枚举当前步数下, 还有多少口酒
for (int k = j; k <= m; ++k) { // 枚举后续还能遇到多少个花
dp[i][j][k] = 0;

dp[i][j][k] = dp[i - 1][j + 1][k + 1];
if (j % 2 == 0) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j / 2][k]) % mod;
}
}
}

return dp[all - 1][1][1];
}
int main()
{
cin >> n >> m;

int res = fact();
cout << res << endl;

return 0;
}


## 试题 J: 砍竹子

#### 参考代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 2E5 + 10;
ll a[N];
struct node {
ll val;
int l, r;

node(ll a, int b, int c) {
val = a;
l = b, r = c;
}

bool operator<(const node& t) const {
return val < t.val;
}
};

ll fact(ll x) {
x = x / 2;
return sqrt(x + 1);
}

int main()
{
int n; cin >> n;
rep(i, n) scanf("%lld", &a[i]);

set<ll> st[2];

ll res = 0;
rep(i, n) {
int id = i & 1, anid = id ^ 1;
st[id].clear();

while (a[i] != 1) {
st[id].insert(a[i]);

if (!st[anid].count(a[i])) res++;

a[i] = fact(a[i]);
}
}

cout << res << endl;

return 0;
}



THE END