网站源码网址修改,网站建设与管理自考,合肥网站推广优化公司,进口食品销售销售在那个网站做目录试题 A. 日期统计1.题目描述2.解题思路3.模板代码试题 B.01 串的熵1.题目描述2.解题思路3.模板代码试题 C. 冶炼金属1.题目描述2. 解题思路3.模板代码试题 D. 飞机降落1.题目描述2. 解题思路3.模板代码试题 E. 接龙数列1.题目描述2. 解题思路3.模板代码试题 F. 岛屿个数1.题…
目录试题 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. 模板代码部分题暂更补代码欢迎评论区交流 试题 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 现在他想要从这个数组中寻找一些满足以下条件的子序列 子序列的长度为 888 . 这个子序列可以按照下标顺序组成一个 yyyymmddyyyymmddyyyymmdd 格式的日期并且 要求这个日期是 202320232023 年中的某一天的日期例如 202309022023122320230902202312232023090220231223。 yyyyyyyyyyyy 表示年份mmmmmm 表示月份dddddd 表示天数当月份或者天数的长度只 有一位时需要一个前导零补充。 请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。 对于相同的日期你只需要统计一次即可。
2.解题思路 考虑八层循环枚举一下中间需要进行减枝加快搜索步骤不建议写 dfs不然就像我一样在考场写烂注意答案需要去重答案为235。
3.模板代码 暂更
试题 B.01 串的熵
1.题目描述 没学过数学暂更
2.解题思路
3.模板代码
试题 C. 冶炼金属
1.题目描述 小蓝有一个神奇的炉子用于将普通金属 OOO 冶炼成为一种特殊金属 XXX。这个 炉子有一个称作转换率的属性 VVVVVV 是一个正整数这意味着消耗 VVV 个普通金 属 OOO 恰好可以冶炼出一个特殊金属 XXX当普通金属 OOO 的数目不足 VVV 时无法 继续冶炼。 现在给出了 NNN 条冶炼记录每条记录中包含两个整数 AAA 和 BBB这表示本次投入了 AAA 个普通金属 OOO最终冶炼出了 BBB 个特殊金属 XXX。每条记录都是独立 的这意味着上一次没消耗完的普通金属 OOO 不会累加到下一次的冶炼当中。 根据这 NNN 条冶炼记录请你推测出转换率 VVV 的最小值和最大值分别可能是多少题目保证评测数据不存在无解的情况。
2. 解题思路 如果看过样例的话显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是 ACB\frac{A}{C} BCAB。AAA 是不变的我们先考虑二分求最小的 CCC因为需要保证所有式子的 BBB 都不变如果 CCC 太小显然会有某一组的 BBB 增大所以需要保证每一组都符合a[i]/x b[i]。反过来考虑求最大的 CCC, 如果 CCC 太大显然会有某一组的 BBB 变小需要保证每一组都符合 a[i]/x B。
3.模板代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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 架飞机在 TiTiTi 时刻到达机场上空到达时它的剩余油料还可以继续盘旋 DiDiDi 个单位时间即它最早 可以于 TiTiTi 时刻开始降落最晚可以于 TiDiTi DiTiDi 时刻开始降落。降落过程需要 LiLiLi 个单位时间。 一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不 能在前一架飞机完成降落前开始降落。 请你判断 NNN 架飞机是否可以全部安全降落。
2. 解题思路 看 NNN 最大为10写了个全排列T组数据复杂度还是炸了暂更吧 。
3.模板代码
试题 E. 接龙数列
1.题目描述 对于一个长度为 KKK 的整数数列A1,A2,...,AKA_1, A_2, . . . , A_KA1,A2,...,AK我们称之为接龙数列当且仅当 AiA_iAi 的首位数字恰好等于 Ai−1A_{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,...,ANA_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] 取一个最大值 ansansans答案则为 n−ansn-ansn−ans。
3.模板代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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.题目描述 程序猿圈子里正在流行一种很新的简写方法对于一个字符串只保留首尾字符将首尾字符之间的所有字符用这部分的长度代替。例如 internation−alizationinternation-alizationinternation−alization 简写成 i18ni18ni18nKubernetesKubernetesKubernetes 注意连字符不是字符串的一部分简写成 K8s,LanqiaoK8s, LanqiaoK8s,Lanqiao 简写成 L5oL5oL5o等。 在本题中我们规定长度大于等于 KKK 的字符串都可以采用这种简写方法长度小于 KKK 的字符串不配使用这种简写。 给定一个字符串 SSS 和两个字符 c1c1c1 和 c2c2c2请你计算 SSS 有多少个以 c1c1c1 开头 c2c2c2 结尾的子串可以采用这种简写
2. 解题思路 这道题放在 G 题感觉更奇怪了一道前缀和模板题。假设下标为 iii 的字符为 c1c1c1那我们只需要统计在区间 [ik−1,n][ik-1,n][ik−1,n]有多少个 c2c2c2 即可前缀和预处理一下 c2c2c2 字符直接累加答案即可注意答案会爆int复杂度 O(n)O(n)O(n)
3.模板代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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,...,ANA_1, A_2, . . . , A_NA1,A2,...,AN。你要重复以下操作 KKK 次 每次选择数列中最小的整数如果最小值不止一个选择最靠前的将其删除。并把与它相邻的整数加上被删除的数值。 输出 KKK 次操作后的序列。
2. 解题思路 感觉是比较典的题目但是这题好像卡常我的代码在非官方数据TLE了大半。用优先队列维护存入值和下标再用一个数组cnt累计每个下标增加的和当弹出最小的值下标为 i 时如果此时cnt[i]不等于0说明它实际的值需要加上cnt[i]我们将其增加后再放回优先对列注意需要清空cnt[i]。如果此时cnt[i]等于0那我们就成功弹出当前最小元素这时需要将其前一个元素和后一个元素值增加我们需要模拟链表去记录每个元素的前后元素是谁pre[i]表示下标为i的上一个元素是谁ne[i]表示下标为 i 的下一个元素是谁直到堆的元素个数只剩n-k时结束循环。 评论区来个小伙伴帮忙优化下或者来个其他做法
3.模板代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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_queuepairLL, int, vectorpairLL, int, greaterpairLL, 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::vectorLL 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,...,AKA_1, A_2, . . . , A_KA1,A2,...,AK。今天由于时间原因小明决定跳过其中一个景点只带游客按顺序游览其中 K−1K − 1K−1 个景点。具体来说如果小明选择跳过 AiA_iAi那么他会按顺序带游客游览 A1,A2,...,Ai−1,Ai1,...,AK,(1≤i≤K)A_1, A_2, . . . , A_{i−1}, A_{i1}, . . . , A_K, (1 ≤ i ≤ K)A1,A2,...,Ai−1,Ai1,...,AK,(1≤i≤K)。 请你对任意一个 AiAiAi计算如果跳过这个景点小明需要花费多少时间在景点之间的摆渡车上
2. 解题思路 LCALCALCA 模板题问题是比赛写不出板子呢首先肯定需要考虑求树上任意两点的距离。设点 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.模板代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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::vectorPII 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;queueint 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 15; 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 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];
}
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::vectorLL g(m 1), w(m 1);for (int i 1; i m; i) cin g[i];LL ans 0;for (int i 1; i m; i) {int u g[i], v g[i 1];int z lca(u, v);w[i] f[u] f[v] - 2 * f[z];ans w[i];}for (int i 1; i m; i) {if (i 1) cout ans - w[1] ;else if (i m) cout ans - w[m - 1] ;else {LL res ans - w[i] - w[i - 1];int u g[i - 1], v g[i 1];int z lca(u, v);res f[u] f[v] - 2 * f[z];cout res ;}}
}
int 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 个不重复的无序数对 (a1,b1),(a2,b2),...,(am,bm)(a1, b1), (a_2, b_2),. . . , (a_m, b_m)(a1,b1),(a2,b2),...,(am,bm)其中 aiaiai 互不相同bib_ibi 互不相同ai,bj(1≤i,j≤m)a_i , b_j(1 ≤ i, j ≤ m)ai,bj(1≤i,j≤m)。 小明想知道是否能够选择一条树上的边砍断使得对于每个 (ai,bi)(ai , bi)(ai,bi) 满足 aiaiai和 bibibi 不连通如果可以则输出应该断掉的边的编号编号按输入顺序从 111 开始否则输出 −1-1−1。
2. 解题思路 又是 LCALCALCA 模板题啊但我之前没做过反正也写不出 LCALCALCA。考虑一对无序数对的点 xxx 和 yyy 如果我们砍掉某条边可以让这两个点不连通那么这条边一定是从 xxx 到 yyy 路径上的一点我们可以让从 xxx 到 yyy 路径的边权值都加1。这个操作我们可以使用树上差分。 对于 mmm 个无序数对我们都如此操作最后如果某条边的权值为 mmm 则说明它符合条件我们选出符合条件编号最大的那条边就是答案如果没有权值为 mmm 的边则说明无解。
3. 模板代码
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, 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::vectorint e[N];
int depth[N], fa[N][32];
int f[N];
int root;
int ans;
mapPII, int mp;
void bfs(int root)
{ms(depth, 0x3f);depth[0] 0, depth[root] 1;queueint 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;
}
