2023 HBU 天梯赛第一次测试 题目集

目录

1 建校日期

2 发射小球

3 背上书包去旅行

4 吉利的数字

5 向前走

6 热水器

7 走方格

8 朋友圈

9 交保护费

10 走方格

11 和与积

12 缩短字符串

13 买木棒

---

1 建校日期

在2022 ICPC沈阳站上，东北大学命题组给参赛的选手们出了一道签到题，这道题目让选手们输出东北大学的建校日期，这当时可难倒了大家。

在此，Rain Sure同学想让大家输出河北大学的建校日期。

输入格式

无输入

输出格式

输出河北大学的建校日期，格式为xxxx-xx-xx，例如今天是2023-02-23。

2023-03-04

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main(){cout << "1921-10-18";return 0;
}

2 发射小球

Rain Sure正在玩一个小游戏。

这个小游戏是一个在二维平面上的小游戏，二维平面上有一个小球，你可以把X坐标轴看作一面无限长的墙，当小球撞击到X平面后，小球会发生反弹，并且入射角等于出射角。

Rain Sure所控制的小球目前位于坐标(Sx,Sy)上，当他朝某一个点发射小球时，小球会沿直线朝那个点移动过去。

Rain Sure希望它可以让小球经过(Gx,Gy)这个点。请你告诉他，他应该向X坐标轴上的哪一个点发射呢？

输入格式

一行四个整数，分别代表Sx,Sy,Gx,Gy

−10e6≤Sx,Sy≤10e6

0<Sy,Gy≤10e6

Sx不等于Gx

输出格式

令(x,0)为Rain Sure同学应该发射的点，请你输出x。

当你的答案和正确结果之间的误差小于等于10−6时认为正确。

测试样例一

1 1 7 2

3.0000000000

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{double sx, sy, gx, gy;double k = 0;scanf("%lf%lf%lf%lf", &sx, &sy, &gx, &gy);gy = -gy;printf("%.10lf", sx - (double)(sx-gx)/(sy-gy)*sy);return 0;
}

3 背上书包去旅行

Rain Sure同学想要在本科毕业后就去旅行。

假设他想要去旅行的城市都分布在一个三维空间中，一共有n个城市，标号分别为1 ~ n。第i座城市的坐标为(Xi,Yi,Zi)。

从城市i（坐标为(a,b,c)）去城市j（坐标为(p,q,r)）所需要花费的代价为：∣p−a∣+∣q−b∣+max(0,r−c)。

请你求出Rain Sure从1号城市出发，在去过所有城市后至少一次后再返回1号城市所需要的最小代价。

输入格式

第一行一个正整数，代表n。

后面n行，每行三个数(xi,yi,zi)，代表城市i的坐标。

2≤n≤17

−106≤Xi,Yi,Zi≤106

保证没有两座城市在同一位置。

所有输入均为整数。

输出格式

输出Rain Sure需要花费的最小代价。

测试样例一

2
0 0 0
1 2 3

9

测试样例二

3
0 0 0
1 1 1
-1 -1 -1

10

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20,M = 1 << N, mod = 1e9 + 7;
int n, m;
int w[N][N];
int f[M][N];
struct NODE {int a, b, c;
}node[N];int main()
{cin >> n;int i = 0;for (; i < n; i++)cin >> node[i].a >> node[i].b >> node[i].c;node[i].a = node[0].a, node[i].b = node[0].b, node[i].c = node[0].c;n++;for (i = 0; i < n; i++) {for (int j = 0; j < n; j++) {w[i][j] = abs(node[j].a - node[i].a) + abs(node[j].b - node[i].b) + max(0, node[j].c - node[i].c);}}memset(f, 0x3f, sizeof(f));f[1][0] = 1;for (i = 1; i < (1 << n); i++) {for (int j = 0; j < n; j++) {if (i >> j & 1) {for (int k = 0; k < n; k++) {if (i >> k & 1) {f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);}}}}}cout << f[(1 << n) - 1][n - 1] - 1;return 0;
}

4 吉利的数字

Rain Sure同学喜欢吉利的数字。

给定一个数字字符串，其中只包含1到9的字符。

Rain Sure同学想考考你，能不能把这个字符串通过任意的重新排列，使其变为数字8的倍数。

如果可以，输出Yes，否则输出No。

输入格式

输入一个只包含数字1 ~ 9的字符串。

1≤∣S∣≤2×105

输出格式

输出Yes或者No

测试样例一

1234

Yes

测试样例二

13333

No

测试样例三

8

Yes

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2e5 + 10;
int st[11];
char s[N];
int main()
{cin >> s;if (strlen(s) == 1) {if ((s[0] - '0') % 8 == 0)cout << "Yes";else cout << "No";return 0;}if (strlen(s) == 2) {int t = 0, x = 0;t += s[0] - '0';t *= 10;t += s[1] - '0';x += s[1] - '0';x *= 10;x += s[0] - '0';if (t % 8 == 0 || x % 8 == 0)cout << "Yes";else cout << "No";return 0;}for (int i = 0; i < strlen(s); i++) {int x = s[i] - '0';st[x]++;}for (int i = 1; i < 10; i++)for (int j = 1; j < 10; j++)for (int k = 1; k < 10; k++) {int t = 0;bool fg1 = false, fg2 = false, fg3 = false;if (st[i]) {t += i;st[i]--;fg1 = true;}else continue;if (st[j]) {t *= 10;t += j;st[j]--;fg2 = true;}else{ st[i]++;continue;}if (st[k]) {t *= 10;t += k;st[k]--;fg3 = true;}else{ st[i]++;st[j]++;continue;}if (fg1)st[i]++;if (fg2)st[j]++;if (fg3)st[k]++;if (t && t % 8 == 0) {cout << "Yes";return 0;}}cout << "No";return 0;
}

5 向前走

给定一个长度为n的数组a，a1,a2,⋯,an。

Rain Sure同学现在站在一个坐标轴上，位于0点，他会按顺序进行如下操作：

• 向正方向移动a1的距离。
• 向正方向移动a1的距离，再向正方向移动a2的距离。
• 向正方向移动a1的距离，再向正方向移动a2的距离，再向正方向移动a3的距离。

⋮

• 向正方向移动a1的距离，再向正方向移动a2的距离，再向正方向移动a3的距离，⋯，再向正方向移动an的距离。

请你求出Rain Sure同学在移动过程中到达的最大的坐标是多少。

输入格式

第一行一个正整数n，如题中描述。

第二行n个整数，代表数组a。

1≤n≤200000

−108≤ai≤108

输出格式

请输出Rain Sure能到达的最大的坐标值。

测试样例一

3
2 -1 -2

5

测试样例二

5
-2 1 3 -1 -1

2

测试样例三

5
-1000 -1000 -1000 -1000 -1000

0

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n,w;
LL s[N],t[N];int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&s[i]);s[i]+=s[i-1];t[i] = max(s[i],t[i-1]);//cout<<t[i]<<endl;}LL res=0;for(int i=1;i<=n;i++){res=max(res,s[i-1]+t[i]);s[i]+=s[i-1];}cout<<res;return 0;
}

6 热水器

C1教学楼的5楼有一个热水器，学生们可以在课间来这里接热水喝。

这个热水器可以在每分钟提供W升的热水。

现在有n名同学来这里打水，第i名同学打算在Si ~ Ti(不包括第Ti分钟)的时间内接热水，每分钟接走Pi的热水。热水器并不会储存热水，也就是说每分钟只有W升的热水，可以多名同学在同一分钟同时接水。

现在请你判断这个热水器能不能满足所有同学的打水的需求呢？

输入格式

第一行两个正整数，分别代表n和W.

后面n行，每行三个整数，分别为Si,Ti,Pi。

1≤n≤2×105

0≤Si≤Ti≤2×105

1≤Wi,Pi≤109

所有输入均为整数

输出格式

如果可以满足所有同学的打水的需求，输出Yes，否则输出No。

测试样例一

4 10
1 3 5
2 4 4
3 10 6
2 4 1

No

测试样例二

4 10
1 3 5
2 4 4
3 10 6
2 3 1

Yes

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
LL n,w;
LL s[N];int main()
{scanf("%lld%lld",&n,&w);int l,r,c,maxn=0;for(int i=0;i<n;i++){scanf("%d%d%d",&l,&r,&c);s[l]+=c,s[r]-=c;maxn=max(maxn,r+1);}bool fg = true;for(int i=0;i<=maxn+1;i++){if(i!=0)s[i]+=s[i-1];if(s[i]>w){fg=false;break;}}if(fg)printf("Yes");else printf("No");return 0;
}

7 走方格

给定一个n行m列的网格S，每个格子都是小正方形。其中有的小方格上面有障碍物，有的是空白。

其中，如果Si,j是#，代表该位置放有一个障碍物；如果Si,j是.，代表该位置是空白。

Rain Sure同学站在(1,1)位置，每次他可以向右或者向下或者沿对角线向右下走任意数量的格子，但是不可以走到障碍物上！

请你求出Rain Sure同学从(1,1)走到(n,m)一共有多少种方案，请输出答案对1e9+7取模的结果。

输入格式

第一行包括两个正整数，分别为n和m。

后面n行，每行一个长度为m的字符串，代表网格。

2≤n,m≤2000

Si,j是#或者.

S1,1和Sn,m一定是.

输出格式

输出答案对1e9+7取模的结果

测试样例一

3 3
...
.#.
...

10

测试样例二

4 4
...#
....
..#.
....

84

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010, mod = 1e9 + 7;
int n, m;
char ch[N][N];
LL f[N][N];
LL s1[N][N],s2[N][N],s3[N][N];int main()
{scanf("%d%d", &n, &m);getchar();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++)scanf("%c", &ch[i][j]);getchar();}f[1][1] = 1,s1[1][1]= s2[1][1] = s3[1][1] =1;for(int i=1;i<=n;i++)for (int j = 1; j <= m; j++) {if (ch[i][j] == '#') { continue; }f[i][j] += ((s1[i - 1][j] + s2[i][j - 1])%mod + s3[i - 1][j - 1])%mod;s1[i][j] = (f[i][j] + s1[i - 1][j])%mod;s2[i][j] = (f[i][j] + s2[i][j - 1]) % mod;s3[i][j] = (f[i][j] + s3[i - 1][j - 1]) % mod;}cout << f[n][m];return 0;
}

8 朋友圈

有n名学生在一个学校里，其中第i名学生是Ci班的。

他们将在学校认识新的朋友，现在给定q次查询，每次查询是下面两种查询中的一种：

1 a b :a同学和b同学交朋友，并且a同学的朋友圈和b同学的朋友圈会合并为一个大朋友圈。

2 x y : 要求你回答出，学生x的朋友圈中有多少名同学是来自班级y的。

输入格式

第一行两个正整数，分别代表n和q。

第二行有n个正整数，代表n名同学来自哪个班。

后面q行，每行代表一个查询，格式如题中描述

1≤n≤2×105

1≤q≤2×105

1≤Ci,a,b,x,y≤n

在查询1 a b中，保证a=b

输出格式

对于每个2 x y输出答案。

测试样例一

5 5
1 2 3 2 1
1 1 2
1 2 5
2 1 1
1 3 4
2 3 4

2
0

测试样例二

5 4
2 2 2 2 2
1 1 2
1 1 3
1 2 3
2 2 2

3

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, q, x;
int a, b, c;
int p[N];
map<int, int> res[N];
int siz[N];
int find(int x) {if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> q;for (int i = 1; i <= n; i++) {siz[i] = 1;scanf("%d", &x);res[i][x]++;p[i] = i;}while (q--) {scanf("%d%d%d" ,&c, &a, &b);if (c == 1) {a = find(a), b = find(b);if (a != b) {if (siz[a] > siz[b]) {p[b] = a;siz[a] += siz[b];for (auto it : res[b]) {res[a][it.first] += it.second;}}else {p[a] = b;siz[b] += siz[a];for (auto it : res[a]) {res[b][it.first] += it.second;}}}}else {a = find(a);printf("%d\n", res[a][b]);}}return 0;
}

9 交保护费

RainSure同学对数字非常敏感，他有m个不喜欢的数字，分别是D1,D2,⋯,Dm

RainSure同学需要定期向HBU里的黑社会老大Arbalest提交保护费，并且每次不得少于n元，否则下场就会很惨。。。

同时，RainSure同学希望他提交的保护费在十进制表示中不能出现他不喜欢的数字。

请你告诉他，他每次最少需要交多少钱，保护费要求是一个正整数，因为Arbalest不喜欢小数点。

输入格式

第一行包含两个正整数分别为n和m。

第二行m个数字，表示RainSure同学不喜欢的数字。

1≤n<10000

1≤m<10

0≤D1<D2<D3,⋯,Dm≤9

{D1,D2,⋯,Dm}=1,2,3,4,5,6,7,8,9

输出格式

输出一个正整数，代表每次最少需要提交的保护费。

测试样例一

1000 8
1 3 4 5 6 7 8 9

2000

样例说明，首先，RainSure至少需要提交1000元的保护费，并且十进制表示下只能包括0和2。大于等于1000的最小的只包括0和2的数字就是2000。所以，答案为2000.

测试样例二

9999 1
0

9999

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int w, n;
int a[20];
int main()
{cin >> w >> n;memset(a, 0, sizeof(a));for (int i = 0; i < n; i++) {int x;cin >> x;if(x>=0&&x<10)a[x] = 1;}for (int i = w; i <= 100000; i++) {int j = i;bool fg = true;while (j != 0) {int x = j % 10;j /= 10;if (a[x] == 1) {fg = false;break;}}if (fg) {cout << i;return 0;}}return 0;
}

10 走方格

有一个n行m列的网格，你每一次只能向右或者向下走，直到走到右下角的格子。

现在，在网格的左下角有一个a行b列的小网格被障碍物挡住了，你不可以经过这些区域。

请你求出在不经过障碍物区域的情况下，从左上角(1, 1)走到右下角(n, m)一共有多少种方案。

方案数可能很大，请输出答案对1e9+7取模的结果。

输入格式

一行包括四个正整数，分别代表n,m,a,b。

1≤n,m≤105

1≤a<n

1≤b<m

输出格式

输出方案数对1e9+7取模的结果。

测试样例一

2 3 1 1

2

说明：两种方案：右右下、右下右。

测试样例二

10 7 3 4

3570

测试样例三

100000 100000 99999 99999

1

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, m, a, b;int fact[N], infact[N];
int qmi(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}LL com(int n, int m) {return ((LL)fact[n] * infact[m] % mod * infact[n - m]) % mod;
}int main()
{scanf("%d%d%d%d", &n, &m, &a, &b);fact[0] = infact[0] = 1;for (int i = 1; i < N; i++){fact[i] = (LL)fact[i - 1] * i % mod;infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;}LL res = 0;for (int i = 0; i < n - a; i++) {LL t = ((LL)com(b + i - 1, b - 1) * com(n + m - b - i - 2, n - i - 1))%mod;res = (res + t)%mod;}cout << res;return 0;
}

11 和与积

给定两个正整数S和P。请你回答是否存在一对正整数(n,m)满足条件：n+m=S并且n×m=P。

如果存在，输出Yes；否则，输出No.

输入格式

一行内两个正整数，分别代表S和P。

1≤S,P≤1012

输出格式

如果存在，输出Yes；否则，输出No。

测试样例一

3 2

Yes

测试样例二

1000000000000 1

No

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL S, P;
int main()
{cin >> S >> P;LL j = 0;for (LL i = 1; i <= P/i; i++) {j = S - i;if ((LL)i * j == P) {cout << "Yes";return 0;}}cout << "No";return 0;
}

12 缩短字符串

给定一个长度为n的只包含小写字母的字符串。HBU的算竞大哥Arbalest想让Rain Sure把这个字符串变的尽可能短，并且要求他只能进行如下操作任意次：

如果字符串中存在子串fox，可以将其删去，然后将左右两个字符串再拼在一起。

Rain Sure表示完全不会，请你帮帮他！

输出能够得到的最短长度。

输入格式

第一行一个正整数n，代表字符串长度。

第二行一个长度为n的，只包含小写字母的字符串。

1≤n≤2×105

输出格式

一个整数，代表可能的最短长度。

测试样例一

6
icefox

3

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 1e9 + 7;
string s;
char st[N];
int top,n;
int main()
{cin >> n;cin >> s;for (int i = 0; i < n; i++) {if (top >= 1) {if (st[top - 1] == 'f' && st[top] == 'o' && s[i] == 'x') {top -= 2;continue;}}if (top >= 0 && i < n - 1) {if (st[top] == 'f' && s[i] == 'o' && s[i + 1] == 'x') {top--, i++;continue;}}st[++top] = s[i];}cout << top;return 0;
}

13 买木棒

Rain Sure同学想去商店买木棒，他需要长度1 ~ n的木棒各一个。商店现在有长度为1 ~ n+1的木棒各一个，且售价均为1元。

Rain Sure买下一个木棒后，可以回家将它分成任意多段，比如一根长度为L的木棒，如果将其分成k段，长度分别为L1,L2,⋯,Lk，需要满足L1+L2+⋯+Lk=L。

Rain Sure想要花尽可能少的钱得到长度为1 ~ n的木棒各一个，请你帮他算出他最少需要花多少钱。

输入格式

输入一个正整数，代表n。

1≤n≤1018

输出格式

输出最少需要花费多少钱。

测试样例一

4

3

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL S, P;
int main()
{cin >> S;P = S;S++;int i = 1;while (S >= i) {S -= i;i++;}cout << P - i + 2;return 0;
}