目录
- 试题 A. 日期统计
- 1.题目描述
- 2.解题思路
- 3.模板代码
- 试题 B.01 串的熵
- 1.题目描述
- 2.解题思路
- 3.模板代码
- 试题 C. 冶炼金属
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 D. 飞机降落
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 E. 接龙数列
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 F. 岛屿个数
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 G. 子串简写
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 H.整数删除
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 I. 景区旅游
- 1.题目描述
- 2. 解题思路
- 3.模板代码
- 试题 J. 砍树
- 1.题目描述
- 2. 解题思路
- 3. 模板代码
目前除 B、F题未补,其余题均已更完,经非官方数据测试均可AC。欢迎交流
试题 A. 日期统计
1.题目描述
小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的
范围之内。数组中的元素从左至右如下所示:
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列:
- 子序列的长度为 88 8;
- . 这个子序列可以按照下标顺序组成一个 yyyymmddyyyymmdd yyyymmdd 格式的日期,并且
要求这个日期是 20232023 2023 年中的某一天的日期,例如 20230902,2023122320230902,20231223 20230902,20231223。
yyyyyyyy yyyy 表示年份,mmmm mm 表示月份,dddd dd 表示天数,当月份或者天数的长度只
有一位时需要一个前导零补充。
- . 这个子序列可以按照下标顺序组成一个 yyyymmddyyyymmdd yyyymmdd 格式的日期,并且
请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。
对于相同的日期你只需要统计一次即可。
2.解题思路
考虑八层循环枚举一下,中间需要进行减枝加快搜索步骤,不建议写 dfs
,不然就像我一样在考场写烂,注意答案需要去重,答案为235
。
3.模板代码
暂更
试题 B.01 串的熵
1.题目描述
没学过数学,暂更
2.解题思路
3.模板代码
试题 C. 冶炼金属
1.题目描述
小蓝有一个神奇的炉子用于将普通金属 OOO 冶炼成为一种特殊金属 XXX。这个
炉子有一个称作转换率的属性 VVV, VVV 是一个正整数,这意味着消耗 VVV 个普通金
属 OOO 恰好可以冶炼出一个特殊金属 XXX,当普通金属 OOO 的数目不足 VVV 时,无法
继续冶炼。
现在给出了 NNN 条冶炼记录,每条记录中包含两个整数 AAA 和 BBB,这表示本次投入了 AAA 个普通金属 OOO,最终冶炼出了 BBB 个特殊金属 XXX。每条记录都是独立
的,这意味着上一次没消耗完的普通金属 OOO 不会累加到下一次的冶炼当中。
根据这 NNN 条冶炼记录,请你推测出转换率 VVV 的最小值和最大值分别可能是多少,题目保证评测数据不存在无解的情况。
2. 解题思路
如果看过样例的话,显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是 AC= B\frac{A}{C} = BCA=B。 AAA 是不变的,我们先考虑二分求最小的 CCC,因为需要保证所有式子的 BBB 都不变,如果 CCC 太小,显然会有某一组的 BBB 增大,所以需要保证每一组都符合a[i]/x <= b[i]
。反过来考虑求最大的 CCC, 如果 CCC 太大,显然会有某一组的 BBB 变小,需要保证每一组都符合 a[i]/x >= B
。
3.模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N], b[N];bool check(LL x) {for (int i = 1; i <= n; ++i) {if (a[i] / x > b[i]) return false;}return true;}bool check2(LL x) {for (int i = 1; i <= n; ++i) {if (a[i] / x < b[i]) return false;}return true;}void solve(){cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];LL l = 1, r = 1e9;while (l < r) {LL mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}int s = r;l = 1, r = 1e9;while (l < r) {LL mid = l + r + 1 >> 1;if (check2(mid)) l = mid;else r = mid - 1;}cout << s << " " << r << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}
试题 D. 飞机降落
1.题目描述
NNN 架飞机准备降落到某个只有一条跑道的机场。其中第 iii 架飞机在 T iTiTi 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D iDiDi 个单位时间,即它最早
可以于 T iTiTi 时刻开始降落,最晚可以于 T i + D iTi + DiTi+Di 时刻开始降落。降落过程需要 L iLiLi
个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不
能在前一架飞机完成降落前开始降落。
请你判断 NNN 架飞机是否可以全部安全降落。
2. 解题思路
看 NNN 最大为10
,T
最大也为10
,考虑全排列枚举所有的降落情况,只要有一种符合的情况即可,大概计算一下复杂度为 10 ! × 10 × 1010 ! \times10\times1010!×10×10 等于3e8
,理论可过 。
3.模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N], b[N], c[N];void solve(){cin >> n;for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];std::vector<int> d(n);auto check = [&]() {int v = 0;for (int i = 0; i < n; ++i) {int x = d[i];if (i == 0) {v = a[x] + c[x];} else {if (a[x] + b[x] < v) return false;v = max(v, a[x]) + c[x];}}return true;};iota(all(d), 0);bool f = false;do {if (check()) {f = true;break;}} while (next_permutation(all(d)));if (f) cout << "YES" << '\n';else cout << "NO" << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;}
试题 E. 接龙数列
1.题目描述
对于一个长度为 KKK 的整数数列: A1, A2, . . . , AK A_1, A_2, . . . , A_KA1,A2,…,AK,我们称之为接龙数列当且仅当 Ai A_iAi 的首位数字恰好等于 A i − 1 A_{i-1}Ai−1 的末位数字 ( 2 ≤ i ≤ K )(2 ≤ i ≤ K)(2≤i≤K)。
例如 12 , 23 , 35 , 56 , 61 , 1112, 23, 35, 56, 61, 1112,23,35,56,61,11 是接龙数列; 12 , 23 , 34 , 5612, 23, 34, 5612,23,34,56 不是接龙数列,因为 565656 的首位数字不等于 343434 的末位数字。所有长度为 111 的整数数列都是接龙数列。
现在给定一个长度为 NNN 的数列 A1, A2, . . . , AN A_1, A_2, . . . , A_NA1,A2,…,AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?
2. 解题思路
考场读完题的时候感觉有点奇怪,发现思路还是比较简单的。首先一个数我们只需要关注其首位数字和末位数字,定以 f [ i ]f[i]f[i] 为以数字 iii 结尾的最长接龙序列的长度, iii 的范围是 [ 0 , 9 ][0,9][0,9]。对于每个数字设其首位数字为 aaa ,末尾数字为 bbb,则有转移方程:
f[b]=max(f[b],f[a]+1)f[b]=max(f[b],f[a]+1) f[b]=max(f[b],f[a]+1)
最后在 f [ 0 ] 、 f [ 1 ] . . . f [ 9 ]f[0]、f[1]…f[9]f[0]、f[1]…f[9] 取一个最大值 a n sansans,答案则为 n − a n sn-ansn−ans。
3.模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N], b[N];int f[10];void solve(){cin >> n;for (int i = 1; i <= n; ++i) {int x;cin >> x;b[i] = x % 10;string s = to_string(x);a[i] = s[0] - '0';}for (int i = 1; i <= n; ++i) {f[b[i]] = max(f[b[i]], f[a[i]] + 1);}int ans = 0;for (int i = 0; i <= 9; ++i) ans = max(ans, f[i]);cout << n - ans << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}
试题 F. 岛屿个数
1.题目描述
暂更,感觉不好写
2. 解题思路
3.模板代码
试题 G. 子串简写
1.题目描述
程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如 i n t e r n a t i o n − a l i z a t i o ninternation-alizationinternation−alization 简写成 i 18 ni18ni18n, K u b e r n e t e sKubernetesKubernetes (注意连字符不是字符串的一部分)简写成 K 8 s , L a n q i a oK8s, LanqiaoK8s,Lanqiao 简写成 L 5 oL5oL5o等。
在本题中,我们规定长度大于等于 KKK 的字符串都可以采用这种简写方法(长度小于 KKK 的字符串不配使用这种简写)。
给定一个字符串 SSS 和两个字符 c 1c1c1 和 c 2c2c2,请你计算 SSS 有多少个以 c 1c1c1 开头 c 2c2c2 结尾的子串可以采用这种简写?
2. 解题思路
这道题放在 G
题感觉更奇怪了,一道前缀和模板题。假设下标为 iii 的字符为 c 1c1c1,那我们只需要统计在区间 [ i + k − 1 , n ][i+k-1,n][i+k−1,n]有多少个 c 2c2c2 即可,前缀和预处理一下 c 2c2c2 字符,直接累加答案即可,注意答案会爆int
,复杂度 O ( n )O(n)O(n)
3.模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 500010;int k;string s;char c1, c2;int a[N];void solve(){cin >> k >> s >> c1 >> c2;int n = s.size();s = '?' + s;for (int i = 1; i <= n; ++i) {a[i] = (s[i] == c2);a[i] += a[i - 1];}LL ans = 0;for (int i = 1; i + k - 2 < n; ++i) {if (s[i] == c1) ans += a[n] - a[i + k - 2];}cout << ans << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}
试题 H.整数删除
1.题目描述
给定一个长度为 NNN 的整数数列: A1, A2, . . . , AN A_1, A_2, . . . , A_NA1,A2,…,AN。你要重复以下操作 KKK 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
输出 KKK 次操作后的序列。
2. 解题思路
感觉是比较典的题目,用优先队列维护,存入值和下标,再用一个数组cnt
累计每个下标增加的和,当弹出最小的值下标为 i
时,如果此时cnt[i]
不等于0
,说明它实际的值需要加上cnt[i]
,我们将其增加后再放回优先对列,注意需要清空cnt[i]
。如果此时cnt[i]
等于0
,那我们就成功弹出当前最小元素,这时需要将其前一个元素和后一个元素值增加,我们需要模拟链表去记录每个元素的前后元素是谁,pre[i]
表示下标为i
的上一个元素是谁,ne[i]
表示下标为 i
的下一个元素是谁,直到堆的元素个数只剩n-k
时结束循环。不难想象,堆元素的出入次数是线性的。
3.模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 500010;int n, k;int pre[N], ne[N];LL cnt[N];void solve(){cin >> n >> k;priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>> >q;for (int i = 1; i <= n; ++i) {LL v;cin >> v;q.push({v, i});pre[i] = i - 1;ne[i] = i + 1;}int g = n - k;while (q.size() > g) {auto p = q.top(); q.pop();LL v = p.first, ix = p.second;if (cnt[ix]) {q.push({v + cnt[ix], ix});cnt[ix] = 0;} else {int l = pre[ix], r = ne[ix];cnt[l] += v;cnt[r] += v;ne[l] = r;pre[r] = l;}}std::vector<LL> a(n + 1);for (int i = 0; i < g; ++i) {auto p = q.top(); q.pop();a[p.second] = p.first + cnt[p.second];}for (int i = 1; i <= n; ++i) {if (a[i]) cout << a[i] << " ";}}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}
试题 I. 景区旅游
1.题目描述
某景区一共有 NNN 个景点,编号 111 到 NNN。景点之间共有 N − 1N − 1N−1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。
小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 KKK 个景点: A1, A2, . . . , AK A_1, A_2, . . . , A_KA1,A2,…,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1K − 1K−1 个景点。具体来说,如果小明选择跳过 Ai A_iAi,那么他会按顺序带游客游览 A1, A2, . . . , A i − 1, A i + 1, . . . , AK, ( 1 ≤ i ≤ K )A_1, A_2, . . . , A_{i−1}, A_{i+1}, . . . , A_K, (1 ≤ i ≤ K)A1,A2,…,Ai−1,Ai+1,…,AK,(1≤i≤K)。
请你对任意一个 A iAiAi,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?
2. 解题思路
L C ALCALCA 模板题(问题是比赛写不出板子呢),首先肯定需要考虑求树上任意两点的距离。设点 u , vu,vu,v 的最近公共祖先为 zzz,定义 f [ i ]f[i]f[i] 为点 iii 到根节点的距离,那么则有公式:
dist(u,v)=f[u]+f[v]−2∗f[z]dist(u,v)=f[u]+f[v]-2*f[z] dist(u,v)=f[u]+f[v]−2∗f[z]
先求出不跳过任何的点时需要走的距离为ans
以及任意相邻两个跳点的距离。假设我们跳过四个点分别为 a , b , c , da,b,c,da,b,c,d。当跳过的点为 aaa 时,我们只需要用ans
减去 aaa到 bbb的距离,当跳过的点为 ddd 时,我们只需要用ans
减去 ccc 到 ddd 的距离,这是首尾两个点的情况。
那么当跳过的点为中间点呢?比如我们跳过的是 bbb,那么则需要用ans
减去 aaa到 bbb以及 bbb到 ccc的距离,并且还需要加上 aaa到 ccc的距离,其余的中间点处理同理。
3.模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s)#define SZ(s) ((int)s.size())#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const intmod = 1000000007;const int N = 200010;int n, m;std::vector<pair<int, LL>> e[N];int depth[N], fa[N][32];LL f[N];int root;void bfs(int root){memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[root] = 1;queue<int> q;q.push(root);while (!q.empty()) {auto t = q.front();q.pop();for (auto [j, c] : e[t]) {if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q.push(j);fa[j][0] = t;for (int k = 1; k <= 20; k++) {fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}}void dfs(int u, int fa) {for (auto [v, c] : e[u]) {if (v == fa) continue;f[v] = f[u] + c;dfs(v, u);}}int lca(int a, int b) {if (depth[a] < depth[b]) swap(a, b);for (int k = 20; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b]) {a = fa[a][k];}}if (a == b) return a;for (int k = 20; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];}LL calc(int u, int v) {int z = lca(u, v);return f[u] + f[v] - 2 * f[z];}void solve(){cin >> n >> m;for (int i = 0; i < n - 1; ++i) {int u, v , c;cin >> u >> v >> c;e[u].push_back({v, c});e[v].push_back({u, c});}bfs(1);dfs(1, -1);std::vector<LL> g(m + 1);for (int i = 1; i <= m; ++i) cin >> g[i];LL ans = 0;for (int i = 1; i < m; ++i) {ans += calc(g[i], g[i + 1]);}for (int i = 1; i <= m; ++i) {if (i == 1) cout << ans - calc(g[i], g[i + 1]) << " ";else if (i == m) cout << ans - calc(g[i - 1], g[i]) << " ";else {LL res = ans - calc(g[i], g[i + 1]) - calc(g[i - 1], g[i]) + calc(g[i - 1], g[i + 1]);cout << res << " ";}}}signed main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}
试题 J. 砍树
1.题目描述
给定一棵由 nnn 个结点组成的树以及 mmm 个不重复的无序数对 ( a 1 , b 1 ) , ( a2, b2) , . . . , ( am, bm)(a1, b1), (a_2, b_2),. . . , (a_m, b_m)(a1,b1),(a2,b2),…,(am,bm),其中 a iaiai 互不相同, bi b_ibi 互不相同, ai, bj( 1 ≤ i , j ≤ m )a_i , b_j(1 ≤ i, j ≤ m)ai,bj(1≤i,j≤m)。
小明想知道是否能够选择一条树上的边砍断,使得对于每个 ( a i , b i )(ai , bi)(ai,bi) 满足 a iaiai和 b ibibi 不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 111 开始),否则输出 − 1-1−1。
2. 解题思路
又是 L C ALCALCA 模板题啊,但我之前没做过(反正也写不出 L C ALCALCA)。考虑一对无序数对的点 xxx 和 yyy ,如果我们砍掉某条边可以让这两个点不连通,那么这条边一定是从 xxx 到 yyy 路径上的一点,我们可以让从 xxx 到 yyy 路径的边权值都加1
。这个操作我们可以使用树上差分。 对于 mmm 个无序数对我们都如此操作,最后如果某条边的权值为 mmm 则说明它符合条件,我们选出符合条件编号最大的那条边就是答案,如果没有权值为 mmm 的边则说明无解。
3. 模板代码
#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n, m;std::vector<int> e[N];int depth[N], fa[N][32];int f[N];int root;int ans;map<PII, int> mp;void bfs(int root){ms(depth, 0x3f);depth[0] = 0, depth[root] = 1;queue<int> q;q.push(root);while (!q.empty()) {auto t = q.front();q.pop();for (int j : e[t]) {if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q.push(j);fa[j][0] = t;for (int k = 1; k <= 15; k++) {fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}}int lca(int a, int b) {if (depth[a] < depth[b]) swap(a, b);for (int k = 15; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b]) {a = fa[a][k];}}if (a == b) return a;for (int k = 15; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];}int dfs(int u, int fa) {int res = f[u];for (auto v : e[u]) {if (v == fa) continue;int g = dfs(v, u);if (g == m) {ans = max(ans, mp[ {v, u}]);}res += g;}return res;}void solve(){cin >> n >> m;for (int i = 0; i < n - 1; ++i) {int u, v;cin >> u >> v;mp[ {u, v}] = mp[ {v, u}] = i + 1;e[u].push_back(v);e[v].push_back(u);}bfs(1);for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;int z = lca(u, v);f[u]++;f[v]++;f[z] -= 2;}dfs(1, -1);cout << (ans == 0 ? -1 : ans) << '\n';}int main(){ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;}