怎样建淘宝客网站,网站建设所有软件清单,网站优化公司哪个好,国外免费服务器提供点评#xff1a; 题目总体来说偏向于中下难度 1.字符串前缀 题目描述#xff1a; 现在有两个字符串S和T#xff0c;你需要对S进行若干次操作#xff0c;使得S是T的一个前缀#xff08;空串也是一个前缀#xff09;。每次操作可以修改S的一个字符#xff0c;或者删除一个… 点评 题目总体来说偏向于中下难度 1.字符串前缀 题目描述 现在有两个字符串S和T你需要对S进行若干次操作使得S是T的一个前缀空串也是一个前缀。每次操作可以修改S的一个字符或者删除一个S末尾的字符。小团需要写一段程序输出最少需要操作的次数。 输入描述 第一行一个正整数C表示数据组数 对于每一组数据输入两行仅包含小写字母的字符串S和T。 1≤|S|,|T|≤5X10^4 , 1≤C≤10 输出描述 对于每一组数据输出一个整数表示最少需要操作的次数。 样例输入 2
aba
abb
abcd
efg样例输出 1
4 解题代码
初始化两个整数变量res和posres用来表示不同字符的数量pos用来追踪当前字符的索引。计算两个字符串的长度分别存储在maxx和minn中其中maxx表示较长字符串的长度minn表示较短字符串的长度。计算两个字符串长度的差值并将结果存储在res中。这个差值表示需要添加或删除的字符数量以使两个字符串的长度相等。从字符串末尾开始向前遍历即从minn - 1的位置开始。对于每个位置比较S和T中的字符如果它们不相等增加res的值表示需要修改的字符数量。在每次迭代后将pos减1以继续比较下一个字符。最后打印res即需要进行的总操作次数。
#include bits/stdc.h
using namespace std;
int main() {int C;cin C;while (C--) {string S, T;cin S T;int res 0, pos 0;int maxx max(T.size(), S.size()), minn min(T.size(), S.size());res maxx - minn;pos minn - 1;while (pos0) {if (S[pos] ! T[pos])res;pos--;}cout res \n;}
} 2.小美分糖 题目描述 某一天小美从商店买了两种糖果分别买了a个和b个要分给班上n个小朋友。为了不浪费每块糖果都得恰好分到一个小朋友。另外两种糖果一起吃的话味道其实并不好所以每一个小朋友都只能得到其中一种糖果。小美希望分得最少糖果的那个小朋友能得到尽量多的糖果。小美的任务是求得这个数量是多少。 输入描述 第一行一个正整数T表示有T组数据。 对于每一组数据输入一行n,a,b中间用空格隔开。 1≤a,b≤10000, 2≤n≤ab, 1≤T≤100 输出描述 对于每一组数据输出仅一行一个整数表示答案。 样例输入 2
5 2 3
4 7 10样例输出 1
3 解题代码
初始化两个整数变量l和r它们用于表示当前查找范围的左边界和右边界。初始时l为0r为a b。使用二分查找来寻找满足特定条件的最大值。在每次循环中计算中间值mid采用右中位数的方式(l r 1) 1以确保向上取整。这个中间值mid表示当前查找范围的中点。调用check(mid)函数来检查是否满足条件。check函数的目的是计算以mid为单位能够满足条件的次数。具体来说它计算a除以x的整数部分再加上b除以x的整数部分以表示在长度为x的单位中a和b分别包含多少个。如果check(mid)返回true表示以长度为mid的单位可以满足条件将l更新为mid即将查找范围右移。如果返回false表示以长度为mid的单位不能满足条件将r更新为mid - 1即将查找范围左移。继续二分查找直到l和r相等此时找到的最大mid值就是满足条件的最大单位长度。最后输出r的值它表示满足条件的最大单位长度。
#include bits/stdc.h
using namespace std;
int n, a, b, mid;
int check(int x) {int cnt 0;cnt (a / x ) (b / x);return cnt n;
}
int main() {int t;cin t;while (t--) {cin n a b;int l 0, r a b;while (l r) {mid (l r 1) 1;if (check(mid))l mid;elser mid - 1;}cout r \n;}
} 3.交通规划 题目描述 A国有n个城市这n个城市排成一列依次编号为1,2,3,...,n。一开始这n座城市之间都没有任何交通路线于是政府打算修建一些铁路来进行交通规划。接下来T天每一天会进行如下操作的其中一种- “L x”表示编号为 x 的城市与其左边的城市之间修建一条铁路。如果 x 左边没有城市或者已经修建了铁路则无视该操作- “R x”表示编号为 x 的城市与其右边的城市之间修建一条铁路。如果 x 右边没有城市或者已经修建了铁路则无视该操作- “Q x”表示查询 x 往左边和往右边最远能到达的城市编号。你的任务是模拟以上操作并对于每一条“Q x”操作输出对应的答案。 输入描述 第一行输入两个正整数 n , T 接下来T行每行输入形如题面中的其中一种。 1≤n≤10000, 1≤T≤200 1≤x≤n 输出描述 对于每一个Q x”操作输出一行两个正整数分别表示 x 往左边和往右边最远能到达的城市编号中间用空格隔开。 样例输入 3 5
Q 2
L 2
Q 2
R 2
Q 2样例输出 2 2
1 2
1 3 解题思路并查集 首先定义一个常数N表示最大元素数量。声明一个整数数组p[N]用于表示每个元素的父节点。 实现find函数它是典型的并查集中的查找函数。给定一个元素xfind(x) 函数返回其所属集合的代表元素同时进行路径压缩即将查找路径上的所有节点的父节点设置为代表元素。 在main函数中首先从输入读取两个整数n和Tn表示元素的总数量T表示待执行的操作次数。 初始化并查集将每个元素的父节点初始化为自身即p[i] i表示每个元素都自成一个集合。 进入循环处理T次操作。每个操作由一个字符串op和一个整数x表示。 如果操作op是 L则表示要将元素x与其左侧的元素合并。这里首先通过find(x)找到x所属的集合代表元素然后判断如果x的左侧元素与x不在同一个集合并且x不小于1将x所属集合的代表元素设置为x左侧元素所属集合的代表元素。 如果操作op是 R则表示要将元素x与其右侧的元素合并。类似地首先通过find(x)找到x所属的集合代表元素然后判断如果x的右侧元素与x不在同一个集合并且x不大于n-1将x所属集合的代表元素设置为x右侧元素所属集合的代表元素。 如果操作op是其他字符这个操作是查询操作。首先初始化两个整数l和r用于找到x所属集合的所有元素的范围。通过二分查找首先向左找到l1即从x开始往左一直到x所属集合的边界。然后向右找到r即从x开始往右一直到x所属集合的边界。输出l1和r表示这个集合的范围。
#include bits/stdc.h
using namespace std;
const int N 1e6 10;
int p[N];int find(int x) {if (p[x] ! x)p[x] find(p[x]);return p[x];
}int main() {int n, T;cin n T;for (int i 1; i n; i) {p[i] i;}while (T--) {string op;int x;cin op x;if (op L ) {if (find(x) ! find(x - 1) x 1)p[find(x)] find(x - 1);} else if (op R) {if (find(x) ! find(x 1) x n - 1) {p[find(x)] find(x 1);}} else {int l 0, r x;while (l r) {int mid l r 1;if (find(x) find(mid)) {r mid;} elsel mid 1;}int l1 l;l x, r n;while (l r) {int mid (l r 1) 1;if (find(x) find(mid)) {l mid;} elser mid - 1;}cout l1 r \n;}}
} 4.小美玩套娃 题目描述 小美最近喜欢上了玩套娃。具体的小美有 n 个套娃第 i 个套娃的大小为 ai内部空间为 bi(bi≤ai)。对于两个套娃x,y x能放入y中当且仅当ax≤by 且放入后会占据 y 大小为 ax 的内部空间即 y 的内部空间剩下 by-ax每个套娃只能放在另外的一个套娃内每个套娃内部也只能放一个套娃当然内部放的这个套娃可以内部还有套娃。显然套娃是套的越多越好于是小美给每个套娃定义了一个价值 ci如果套完之后套娃 i 还剩 k 的内部空间小美需要付出ci*k 的花费总花费为所有套娃的花费之和现在小美想知道最小的花费为多少。 输入描述 第一行一个正整数 n 表示套娃的个数 接下来三行每行 n 个整数分别为 a1,a2,...an b1,b2,...bn c1,c2,...,cn 1≤n,ai,bi,ci,≤100000bi≤ai 输出描述 输出一个整数表示最小的花费 样例输入 3
5 4 3
4 2 2
3 2 1样例输出 6 解题思路贪心 创建三个vectora、b、c用于存储n个元素的数据。通过循环分别读取a、b、c数组的值。 创建两个二维vector t0 和 t1每个元素是一个包含四个整数的向量用于存储a、b、c以及元素的索引。这两个向量是用来排序的备份。 对t0 和 t1 分别进行排序 t0 根据a的值由小到大排序。t1 根据c的值由小到大排序。 初始化一个变量 ri表示可用于装载元素的空间初始值为n-1。 初始化一个变量 res 用于记录最终的结果初始值为0。 开始一个逆序的循环从n-1到0 在每一次循环中首先用二分查找找到能够容纳当前元素的位置。这里通过比较 t1[i] 中的 b 值和 t0[mid] 中的 a 值来查找。如果找到了一个合适的位置 r更新 ri 为 r-1。注意代码中存在一些处理以避免重复使用相同的元素t0[r][3] t1[i][3]以及如果 t1[i][1] 小于 t0[r][0] 则退出循环。 最后遍历 t1 数组计算每个元素的价值c * 剩余的容纳空间并将结果累加到 res 中。 输出 res即为最终的答案。
#include bits/stdc.h
using namespace std;
const int N 1e6 10;
//int a[N], b[N], c[N];int main() {int n;cin n;vectorint a(n);vectorint b(n);vectorint c(n);for (int i 0; i n; i) {cin a[i];}for (int i 0; i n; i) {cin b[i];}for (int i 0; i n; i) {cin c[i];}vectorvectorint t0(n);vectorvectorint t1(n);for (int i 0; i n; i) {t0[i] {a[i], b[i], c[i], i};t1[i] {a[i], b[i], c[i], i};}//按照a由小到大sort(t0.begin(), t0.end(), [](const vectorint x, const vectorint y) {return x[0] y[0];});//按照c又小到大sort(t1.begin(), t1.end(), [](const vectorint x, const vectorint y) {return x[2] y[2];});int ri n - 1;long long res 0;for (int i n - 1; i 0; i--) {//按照c价值由大到小和容纳空间然后二分查找到符合的个头塞入int l 0;int r ri;while (l r) {int mid (l r 1 ) 1;if (t1[i][1] t0[mid][0]) {l mid;} elser mid - 1;}if (t0[r][3] t1[i][3])r--;if ( t1[i][1] t0[r][0] )break;t1[i][1] - t0[r][0];ri r - 1;}for (int i 0; i n; i) {res (long long)(t1[i][2] * t1[i][1]);}cout res \n;
}
