第十三届蓝桥杯国赛C++B组（个人题解）
好难啊呜呜呜呜呜，填空题第一个就懵了真要命。这是个人题解（就是说不一定对，大家看个乐子就行，后续把题补了再改）
试题 B: 钟表
【问题描述】
在 12 小时制的钟表中，有分针、时针、秒针来表示时间。记分针和时
针之间的夹角度数为 A（0 ≤ A ≤ 180）、分针和秒针之间的夹角度数为 B（0 ≤ B ≤ 180）。而恰好在 s 时 f 分 m 秒时，满足条件 A = 2B 且 0 ≤ s ≤ 6； 0 ≤ f < 60；0 ≤ m < 60，请问 s, f, m 分别是多少。
注意时针、分针、秒针都围绕中心匀速转动。
提交格式为三个由一个空格隔开的整数，分别表示 s, f, m。如 3 11 58表示
3 点 11 分 58 秒
问题解析
本人答案是：4 48 0.
我是这么想的，常见的那种时钟，分针和秒针走了，时针也是会跟着走的，比如有的人可能想着是6 0 15这样，但是秒针走了时针和分针其实也在走，严格来说此时分针和秒针并不是90度，分针和时针也不是180度，所以我认为是不行的。
我们知道秒针走一圈（360度）是60秒，即秒针一秒钟可以走6度；分针60分钟走一圈，即10秒钟走1度；时针12小时走一圈，即120秒走一度。根据范围我们知道我们可以枚举的最大时间是6小时59分59秒，即25199秒，我们只要从0枚举到25199，通过秒数算出分针、时针和秒针走过的角度，相减后得到角A和角B，再判断是否满足A=2*B即可。算出来后发现有两个结果：0 0 0和4 48 0，0 0 0被官方发公告ban了，所以我写的是4 48 0.
代码
#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
typedef long long ll;
int main()
{
for (int i = 0; i < 25199; i++)
{
double m = (double)1 / 10.0 * i;
double h = (double)1 / 120.0 * i;
double s = (double)6 / 1.0 * i;
while (m > 360)m -= 360;
while (s > 360)s -= 360;
double A, B;
if (m < h)
{
A = h - m;
}
else A = m - h;
if (m < s)
{
B = s - m;
}
else B = m - s;
if (A == 2 * B)
{
cout << i / 3600 << " " << i / 60 % 60 << " " << i % 60 << endl;
}
}
return 0;
}
试题 C: 卡牌
【问题描述】
这天，小明在整理他的卡牌。
他一共有 n 种卡牌，第 i 种卡牌上印有正整数数 i(i ∈ [1, n])，且第 i 种卡牌现有 ai 张。而如果有 n 张卡牌，其中每种卡牌各一张，那么这 n 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 m 张空白牌，他可以在上面写上数i，将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 i种牌最多手写 bi 张。
请问小明最多能凑出多少套牌？
【输入格式】
输入共 3 行，第一行为两个正整数 n, m。
第二行为 n 个正整数 a1, a2, …, an。
第三行为 n 个正整数 b1, b2, …, bn。
【输出格式】
一行，一个整数表示答案。
【样例输入】
4 5
1 2 3 4
5 5 5 5
【样例输出】
3
【评测用例规模与约定】
对于 30% 的数据，保证 n ≤ 2000 ；
对于 100% 的数据，保证 n ≤ 2 × 10^5; ai, bi ≤ n; m ≤ n
问题解析
比较明显的二分答案，二分枚举一下可能组成的套数mid就行。然后看枚举卡牌能否组出这mid套牌：
遍历a数组，如果ai大于等于mid，说明这个牌的数量够组出mid牌，然后我们看下一张牌（组出mid套牌需要每张牌都至少有mid张）。如果牌数不够，就看我们能不能够通过m张空白卡片填补这差距，如果不行，说明我们的mid太大了，要小点。遍历完a后如果能组成mid套牌，我们就加大mid的值。
（下界是0，因为可能一套牌都组不出，然后懒得想上界了于是直接开了个1e18）
代码
#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
typedef long long ll;
ll n, m;
bool check(ll mid, vector<ll>& a, vector<ll>& b)
{
int ans = m;
for (int i = 0; i < n; i++)
{
if (a[i] < mid)
{
if (mid - a[i] > b[i] || mid - a[i] > ans)return false;
else ans -= mid - a[i];
}
}
return ans >= 0;
}
int main()
{
cin >> n >> m;
vector<ll>a(n), b(n);
for (int i = 0; i < n; i++)cin >> a[i];
for (int i = 0; i < n; i++)cin >> b[i];
ll l = 0, r = 1e18;
while (l < r)
{
ll mid = (l + r + 1) / 2;
if (check(mid, a, b))l = mid;
else r = mid - 1;
}
cout << l;
return 0;
}
试题 D: 最大数字
【问题描述】
给定一个正整数 N。你可以对 N 的任意一位数字执行任意次以下 2 种操作：
-
将该位数字加 1。如果该位数字已经是 9，加 1 之后变成 0。 -
将该位数字减 1。如果该位数字已经是 0，减 1 之后变成 9。
你现在总共可以执行 1 号操作不超过 A 次，2 号操作不超过 B 次。
请问你最大可以将 N 变成多少？
【输入格式】
第一行包含 3 个整数：N, A, B。
【输出格式】
一个整数代表答案。
【样例输入】
123 1 2
【样例输出】
933
【样例说明】
对百位数字执行 2 次 2 号操作，对十位数字执行 1 次 1 号操作。
【评测用例规模与约定】
对于 30% 的数据，1 ≤ N ≤ 100; 0 ≤ A, B ≤ 10
对于 100% 的数据，1 ≤ N ≤ 1017; 0 ≤ A, B ≤ 100
问题解析
其实直接贪心应该就行？我当时脑子有问题还写了个dfs。
先把数拆成一位一位的，然后存入数组中，从最高位开始操作，每一位我都计算要把这位变成通过+1变成9或者减1变成9需要多少步，如果不够+1变成9，那就能加多少加多少，如果不能-1变成9，那就不减了。当dfs到最后一位的时候，维护一下最大值。
代码
#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
typedef long long ll;
typedef pair<ll, ll>PII;
ll res = 0, a = 0, b = 0;
void dfs(vector<ll>v, ll x, ll y, ll pos)
{
if (pos == v.size())
{
ll ans = 0;
for (auto i : v)
{
ans *= 10;
ans += i;
}
res = max(res, ans);
return;
}
ll temp = v[pos];
if (x + 9 - v[pos] <= a)
{
v[pos] = 9;
dfs(v, x + 9 - temp, y, pos + 1);
v[pos] = temp;
}
else
{
v[pos] += a - x;
dfs(v, a, y, pos + 1);
v[pos] = temp;
}
if (v[pos] + y + 1 <= b)
{
v[pos] = 9;
dfs(v, x, y + temp + 1, pos + 1);
v[pos] = temp;
}
else dfs(v, x, y, pos + 1);
}
int main()
{
cin >> res >> a >> b;
vector<ll>v;
ll ans = res;
while (ans)
{
v.push_back(ans % 10);
ans /= 10;
}
reverse(v.begin(), v.end());
dfs(v, 0, 0, 0);
cout << res;
return 0;
}
试题 E: 出差
【问题描述】
A 国有 N 个城市，编号为 1 . . . N。小明是编号为 1 的城市中一家公司的员工，今天突然接到了上级通知需要去编号为 N 的城市出差。由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市 1 到达城市 N，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了 M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。（由于小明之前在城市 1，因此可以直接离开城市 1，不需要隔离）由于上级要求，小明希望能够尽快赶到城市 N，因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市 N。
【输入格式】
第 1 行：两个正整数 N, M，N 表示 A 国的城市数量，M 表示未关闭的路线数量
第 2 行：N 个正整数，第 i 个整数 C**i 表示到达编号为 i 的城市后需要隔离的时间
第 3 . . . M + 2 行：每行 3 个正整数，u, v, c，表示有一条城市 u 到城市 v 的双向路线仍然开通着，通过该路线的时间为 c
【输出格式】
第 1 行：1 个正整数，表示小明从城市 1 出发到达城市 N 的最短时间（到达城市 N，不需要计算城市 N 的隔离时间）
【样例输入】
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5
【样例输出】
13
【样例说明】
路线 1：1 -> 2 -> 4，时间为 4+7(隔离)+3=14
路线 2：1 -> 3 -> 4，时间为 5+3(隔离)+5=13
【评测用例规模与约定】
对于 100% 的数据，1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000, 1 ≤ C**i ≤ 200, 1 ≤ u, v ≤
N, 1 ≤ c ≤ 1000
问题解析
对于这题本人图论学的很屎（简单来说就是基础的最短路模板都不会），所以自己写了个dfs的解法。
我们把城市a到城市b的代价看为：a到b的线路+在b隔离的时间。用map和set存下一个城市到其它所有城市的路径，如果有相同的路径，我们取用时短的那个。然后以城市1为起点dfs一遍，同时记录下已经去过的城市（减枝），dfs过程中累加去到下一个城市的时间，当到达城市N时，我们维护一下到达N的时间，取最小值即可。
代码
#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
typedef long long ll;
ll res = 1e18, n, m, a, b, c;
ll f[1002][1002];
vector<ll>geli;
unordered_map<ll, set<ll>>mymap;
void dfs(ll x, ll ans, vector<ll>&cnt)
{
if (x == n)
{
res = min(res, ans - geli[x]);
return;
}
cnt[x] = 1;
for (auto i : mymap[x])
{
if (cnt[i] == 0)
{
dfs(i, ans + f[x][i] + geli[i], cnt);
}
}
cnt[x] = 0;
}
int main()
{
memset(f, 127, sizeof f);
cin >> n >> m;
geli.push_back(0);
for (int i = 0; i < n; i++)
{
cin >> a;
geli.push_back(a);
}
for (int i = 0; i < m; i++)
{
cin >> a >> b >> c;
f[a][b] = min(f[a][b], c);
f[b][a] = min(f[b][a], c);
mymap[a].insert(b);
mymap[b].insert(a);
}
vector<ll>cnt(1002);
dfs(1, 0, cnt);
cout << res;
return 0;
}
试题 F: 费用报销
【问题描述】
小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 K 天，且总金额不得超过实际差旅费用 M。比如财务要求 K = 7 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票据，1 月 1 日及之前和 1 月 15 日及之后的票据则可以提交。公司的同事们一起给小明凑了 N 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据，并使总金额尽可能接近 M。需要注意，由于这些票据都是同一年的，因此 12 月底的票据不会影响到 1月初票据的提交。这一年不是闰年。
【输入格式】
第 1 行：3 个整数，N, M, K
第 2 . . . N + 1 行：每行 3 个整数 mi, di, vi，第 i + 1 行表示第 i 张票据时间的月份 mi 和日期 di，vi 表示该票据的面值
【输出格式】
第 1 行：1 个整数，表示小明能够凑出的最大报销金额
【样例输入】
4 16 3
1 1 1
1 3 2
1 4 4
1 6 8
【样例输出】
10
【样例说明】
选择 1 月 3 日和 1 月 6 日的票据
【评测用例规模与约定】
对于 100% 的评测用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 50, 1 ≤ mi ≤12, 1 ≤ di ≤ 31, 1 ≤ vi ≤ 400
日期保证合法。
问题解析
用一个12*31的二维数组来存i月j日的发票v[i] [j]，如果当天有多张发票，我们当然选金额高的那个，另一个12 *31的二维数组f的意思是：f[i] [j]表示1月1日到i月j日能报销的最大金额。然后对于i月j天我们有两种选择，一是报销今天的发票，二是不报销今天的发票。
如果报销今天的发票，那f[i] [j]就等于1月1日到i月j日的k天前的能报销的最大金额+v[i] [j]。
如果不报销今天的发票，那f[i] [j]就等于1月1日到i月j日能报销的最大金额。
至于处理k天前的问题，我用双指针，快指针r从1月1日出发，l指针从1月1-k日出发，即l指针是r指针的第k天前，且l指针当天的发票是可以和r指针当天的发票一起报销的。这样如果报销r指针当天发票，那之前的金额就是1月1日到达l指针那一天为止的最大金额；不报销就是1月1日到r指针那一天为止的最大金额。双指针我用的pair形式，first表示月，second表示天，当天数大于当前月的天数时，我们就进入下一个月。
代码
#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
typedef long long ll;
typedef pair<ll, ll>PII;
ll f[13][32],v[13][32];
int main()
{
ll day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
ll n, m, k, res = 0;
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
{
ll a, b, c;
cin >> a >> b >> c;
v[a][b] = max(v[a][b], c);
}
PII l = { 1,1 - k }, r = { 1,1 };
while (r.first <= 12 && r.second <= 31)
{
ll res1 = 0, res0 = 0;
for (int i = 1; i <= r.first; i++)
{
for (int j = 1; j < r.second && j <= day[i]; j++)
{
res0 = max(res0, f[i][j]);
}
}
for (int i = 1; i <= l.first; i++)
{
for (int j = 1; j <= l.second && j <= day[i]; j++)
{
res1 = max(res1, f[i][j]);
}
}
f[r.first][r.second] = max(res1 + v[r.first][r.second], res0);
r.second++;
if (r.second > day[r.first])
{
r.first++;
r.second = 1;
}
l.second++;
if (l.second > day[l.first])
{
l.first++;
l.second = 1;
}
}
cout << f[12][31];
return 0;
}
试题 H: 机房
【问题描述】
这天，小明在机房学习。他发现机房里一共有 n 台电脑，编号为 1 到 n，电脑和电脑之间有网线连接，一共有 n ? 1 根网线将 n 台电脑连接起来使得任意两台电脑都直接或者间接地相连。小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 d 台电脑，那么任何经过这台电脑的信息都会延迟 d 单位时间 (发送方和接收方也会产生这样的延迟，当然如果发送方和接收方都是同一台电脑就只会产生一次延迟)。小明一共产生了 m 个疑问：如果电脑 ui 向电脑 vi 发送信息，那么信息从ui 传到 vi 的最短时间是多少？
【输入格式】
输入共 n + m 行，第一行为两个正整数 n, m。
后面 n ? 1 行，每行两个正整数 x, y 表示编号为 x 和 y 的两台电脑用网线直接相连。
后面 m 行，每行两个正整数 u**i, v**i 表示小明的第 i 个疑问。
【输出格式】
输出共 m 行，第 i 行一个正整数表示小明第 i 个疑问的答案。
【样例输入】
4 3
1 2
1 3
2 4
2 3
3 4
3 3
【样例输出】
5
6
1
【样例说明】
这四台电脑各自的延迟分别为 2, 2, 1, 1。
对于第一个询问，从 2 到 3 需要经过 2, 1, 3，所以时间和为 2 + 2 + 1 = 5。
对于第二个询问，从 3 到 4 需要经过 3, 1, 2, 4，所以时间和为 1+2+2+1 =6。
对于第三个询问，从 3 到 3 只会产生一次延迟，所以时间为 1。
【评测用例规模与约定】
对于 30% 的数据，保证 n, m ≤ 1000；
对于 100% 的数据，保证 n, m ≤ 100000 。
问题解析
时间不够，纯暴力写法只为骗分，方法和前面的出差问题差不多，也是先存下一个电脑到另一个电脑的全部路径，然后在dfs一个个算，从电脑a到电脑b的用时是a链接其它电脑的数量。注意一点就是如果自己给自己发消息也是要计算延时的。
代码
#include<iostream>
using namespace std;
#include<unordered_map>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
typedef long long ll;
ll n, m, a, b;
unordered_map<ll, set<ll>>mymap;
ll yanchi[100050];
unordered_map<ll, unordered_map<ll,ll>>cnt;
void dfs(ll x, ll ans, vector<ll>& st, ll& res)
{
if (x == b)
{
res = min(res, ans);
return;
}
st[x] = 1;
for (auto i : mymap[x])
{
if (st[i] == 0)
{
dfs(i, ans + yanchi[i], st, res);
}
}
st[x] = 0;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n - 1; i++)
{
cin >> a >> b;
mymap[a].insert(b);
mymap[b].insert(a);
}
for (int i = 1; i <= n; i++)
{
yanchi[i] = mymap[i].size();
}
vector<ll>st(100050);
while (m--)
{
ll res = 1e9;
cin >> a >> b;
if (a == b)
{
cout << yanchi[a] << endl;
}
else if (cnt[a][b] != 0)
{
cout << cnt[a][b] << endl;
}
else
{
dfs(a, yanchi[a], st, res);
cnt[a][b] = res;
cnt[b][a] = res;
cout << res << endl;
}
}
return 0;
}
|