第十六届蓝桥杯软件赛省赛C++ B组 题解。
A. 移动距离
首先不难发现一个简单的达到目的地的方案。
然后只需证明这个最简单的方案也是最优的就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
double x = 233, y = 666;
double l = sqrt(x * x + y * y);
cout << fixed << setprecision(0);
cout << l + l * atan2(y, x) << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
B. 客流量上限
$$
A_i\ne 2025 (i\le 2024)\leftarrow A_i^2\le i^2+2025
$$
于是 $A_{2025}=2025$.
$$
A_i\ne 2024 (i\le 2023)\leftarrow A_i^2\le i^2+2025
$$
于是 $A_{2024}=2024$.
….
重复此过程，右侧能推得左侧的条件是：
$$
(t+1)^2>t^2+2025\rightarrow t> 1012
$$
所以 $A_i=i\ (i\ge 1013)$。
接下来，令 $A_j=2025$，推得 $A_i\times2025\le A_i\times2025+2025$，即 $A_i\le i+1\ (i\le 1012)$。
最后证明 $A_i=i\ (i\ge 1013)$，$A_i\le i+1\ (i\le 1012)$ 也是满足题设的充分条件即可。
分为三种情况讨论：
- $i,j\le 1012$，$A_iA_j\le(i+1)(j+1)=ij+i+j+1\le ij+2025$，满足。
- $i\le1012,j\ge1013$，$A_iA_j\le(i+1)j\le ij+j\le ij+2025$，满足。
- $i,j\ge 1013$，$A_iA_j\le ij\le ij+2025$，满足。
所以:
$A_1$ 可取 1，2
$A_2$ 可取 1，2，3
$A_3$ 可取 1，2，3，4
…
$A_{1012}$ 可取 1，2，3，4，…，1013
每个数都有两种选择（在前面的数选完的基础上）。
所以答案为 $2^{1012} (mod\ 1e9+7)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod = 1e9 + 7;
int qmi(int a, int k, int p){
int res = 1;
while(k){
if(k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
void solve(){
cout << qmi(2, 1012, mod) << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
C. 可分解的正整数
类似一个构造题，可以发现，任何大于 1 的数 $n$ 都可以被表示为 ：
$$
-(n-1),-(n-2),…,n-2,n-1,n
$$
且序列长度至少有 3，只有 1 无法被三个连续递增的整数表示。
输出非 1 的个数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n; cin >> n;
int res = 0;
while(n--){
int x; cin >> x;
res += x != 1;
}
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
D. 产值调整
第一眼看似乎没有很好的优化方法，但细看发现，三个数的差值基本在以一个 $\log$ 的速度收敛，所以直接模拟该过程，知道三个数相等为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int a, b, c, k; cin >> a >> b >> c >> k;
for(int i = 0; i < k; i++){
int u = b + c >> 1;
int v = a + c >> 1;
int w = a + b >> 1;
a = u, b = v, c = w;
if(a == b && b == c) break;
}
cout << a << ' ' << b << ' ' << c << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while(t--) solve();
return 0;
}
|
E. 画展布置
显然排序后取连续的一段可以让答案最优，找出最优的一段即可。
（排序后，求和的结果可以将绝对值打开，最后就是 $B_M^2-B_1^2$ 即可）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n, m; cin >> n >> m;
vector<int> a(n);
for(auto &i : a) cin >> i;
sort(a.begin(), a.end());
int res = 1e18;
for(int i = 0; i + m - 1 < n; i++){
res = min(res, a[i + m - 1] * a[i + m - 1] - a[i] * a[i]);
}
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
F. 水质检测
先想出最优的方案，然后模拟你想出来的方案即可。
写了一个小状压，将每一列压成一个状态，从第一次找到 # 开始，准备填充。
进入准备填充状态后，每次遇到新的 #，找一个最优的填充方案，然后将 last 状态更新即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
string a, b; cin >> a >> b;
int n = a.size();
vector<int> dp(n);
for(int i = 0; i < n; i++){
dp[i] = (a[i] == '#') + (b[i] == '#') * 2;
}
int fd = 0, last = 0, pos = 0, res = 0;
for(int i = 0; i < n; i++){
if(!dp[i]) continue;
if(!fd){
fd = 1;
last = dp[i];
}
else{
if(last & dp[i]){
res += i - pos - 1;
last = dp[i];
}
else{
res += i - pos;
last = 3;
}
}
pos = i;
}
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
G. 生产车间
实质是，每次用子节点可达的数去更新父节点可达的数。
每次更新是一个卷积的过程，子节点可达 $a_i$，父节点可达 $b_i$，那么更新后所有可达的值为 $a_i+b_j$ 的所有组合。（所以有大佬用 fft 实现可以达到 $O(n\log n)$）
当然，我们用一个 bitset 优化基本时间就够了。更新过程用移位加速，更新完保留低 w[u] 位的值。
最后看根节点的最大可达值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n; cin >> n;
vector<int> w(n);
for(auto &i : w) cin >> i;
vector<vector<int>> adj(n);
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
u--, v--;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
vector<bitset<1001>> dp(n);
function<void(int, int)> dfs = [&](int u, int fa){
dp[u][0] = 1;
if(u && adj[u].size() == 1){
dp[u][w[u]] = 1;
return;
}
bitset<1001> tmp;
tmp[0] = 1;
for(auto &v : adj[u]){
if(v == fa) continue;
dfs(v, u);
for(int i = 0; i < 1001; i++){
if(dp[u][i]){
tmp |= dp[v] << i;
}
}
swap(dp[u], tmp);
}
dp[u] <<= (1000 - w[u]);
dp[u] >>= (1000 - w[u]);
};
dfs(0, -1);
int res = 0;
for(int i = w[0]; i >= 0; i--){
if(dp[0][i]){
res = i;
break;
}
}
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
H. 装修报价
观察这么一个随意的式子：
$$
a+b\oplus c-d+e
$$
我们很容易找出其对偶（我们暂且这么称呼）：
$$
a-b\oplus c+d-e
$$
此两者的和为 $2a$，不妨记每一个的贡献为 $a$ 好了。
不难发现所有的式子都可以如此配对，有的贡献为 $a$，有的贡献为 $a\oplus b$，…
动手模拟一下就可以看出，这些贡献都是这个序列的异或前缀，我们只需计算出每个异或前缀出现的次数就好了。
对于贡献为 $a$ 的，紧跟其后的符号有 + - 两个选择，其余符号任意，因此出现$2\times 3^{n-2}$ 次，对于贡献为 $a\oplus b$ 的，类似分析下去 …
需要注意全体序列异或的出现次数需要特判一下，为 1。
整理一下，答案应该为：
$$
\sum_{i=0}^{n-2} \oplus_{k=0}^{i} a_i\times 2\times 3^{n-2-i} + \oplus_{k=0}^{n-1} a_i
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod = 1e9 + 7;
void solve(){
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
vector<int> p3(n, 1);
for(int i = 1; i < n; i++) p3[i] = p3[i - 1] * 3 % mod;
int pre = 0;
int res = 0;
for(int i = 0; i < n - 1; i++){
pre ^= a[i];
res += pre * 2 * p3[n - 2 - i];
res %= mod;
}
pre ^= a[n - 1];
res = (res + pre) % mod;
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|