【第16届蓝桥杯软件赛】CB组第一次省赛

个人主页：Guiat
归属专栏：算法竞赛

正文

总共10道题。

A. 移动距离（5分填空题）

【题目】移动距离

【分析】
考察数学。先往右走直线，再走圆弧，即最优解。

【答案】1576

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve()
{int x = 233, y = 666; double r = sqrt(x * x + y * y);double res = r * (1 + atan2(y, x));cout << fixed << setprecision(0)  << res << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

B. 客流量上限（5分填空题）

【题目】客流量上限

【分析】

【答案】781448427

【AC_Code1】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long; const int mod = 1e9 + 7;int FE(int m, int k, int p)
{ll t = m, res = 1;while (k){if (k & 1) res = res * t % p;k >>= 1; t = t * t % p;}return res;
}void solve()
{cout << FE(2, 1012, mod) << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

【AC_Code2】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int mod = 1e9 + 7;int pow(int m, int k, int p)
{int res = 1;while (k --) res = res * m % p;return res;
}void solve()
{cout << pow(2, 1012, mod) << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

C. 可分解的正整数

【题目】可分解的正整数

【分析】
考察模拟。根据题意，分析出除1以外的任何整数都可以分解。

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e5 + 10; int a[N], ans;void solve()
{int n; cin >> n;for (int i = 0; i < n; i ++) { cin >> a[i]; if (a[i] != 1) ans ++; }cout << ans << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

D. 产值调整

【题目】产值调整

【分析】
按题意暴力模拟会超时只有30分。“观察到”如果 A, B, C 三个数相同的话再处理还是不改变三个数大小，此时直接跳出循环来节省时间，可以拿到满分。

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve()
{int T; cin >> T;while (T --){int A, B, C, K; cin >> A >> B >> C >> K;while (K --){int a = A, b = B, c = C;A = (b + c) / 2; B = (a + c) / 2; C = (a + b) / 2;if (A == B && B == C) break;   // 拿满分关键 }cout << A << ' ' << B << ' ' << C << '\n';}
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

E. 画展布置

【题目】画展布置

【分析】

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const int N = 1e5 + 10; ll a[N], ans = LLONG_MAX;void solve()
{int n, m; cin >> n >> m;for (int i = 0; i < n; i ++) cin >> a[i], a[i] *= a[i];sort(a, a + n);for (int l = 0, r = m - 1; r < n; l ++, r ++) ans = min(a[r] - a[l], ans);cout << ans << '\n';  
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

F. 水质检测

【题目】水质检测

【分析】

【AC_Code】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve()
{string a, b; cin >> a >> b;int last = -1, state = -1, cnt = 0;for (int i = 0; i < a.length(); i ++){if (a[i] == '.' && b[i] == '.') continue;if (last != -1) cnt += i - last - 1;if (a[i] == '#' && b[i] == '#') state = 3;else if (a[i] == '#' && b[i] == '.'){if (state == 2) { cnt ++; state = 3; } else state = 1;}else if (a[i] == '.' && b[i] == '#'){if (state == 1) { cnt ++; state = 3; } else state = 2;}last = i;}cout << cnt << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

G. 生产车间

【题目】生产车间

【分析】

【AC_Code】

H. 装修报价

【题目】装修报价

【分析】

【AC_Code1】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const int mod = 1e9 + 7;int s, ans;ll FE(ll a, ll b, ll p)
{ll ans = 1; a %= p;while (b){if (b & 1) ans = (ans * a) % p;b >>= 1; a = (a * a) % p;}return ans % p;
}void solve()
{int n; cin >> n;for (int i = 1; i <= n; i ++){int a; cin >> a; s ^= a;if (i < n) { ans += 2 * s * FE(3ll, n - i - 1, mod) % mod; }else ans += s;ans %= mod;}cout << ans << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

【AC_Code2】

#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const int mod = 1e9 + 7; ll sum, ans;void solve()
{int n; cin >> n;for (int i = 1; i <= n; i ++){int a; cin >> a;ans = (ans * 3 - sum + (sum ^= a) + mod) % mod;}cout << ans << '\n';
}int main()
{IOS int _ = 1;   // cin >> _;while (_ --) solve();return 0;
}

结语
感谢您的阅读！期待您的一键三连！欢迎指正！