目录T1. 计算矩阵边缘元素之和思路分析T2. 最长最短单词思路分析T3. 啤酒厂选址思路分析T4. 统计误差范围内的数思路分析T5. 单词排序思路分析T1. 计算矩阵边缘元素之和题目链接SOJ D1254输入一个整数矩阵计算位于矩阵边缘的元素之和。所谓矩阵边缘的元素就是第一行和最后一行的元素以及第一列和最后一列的元素。时间限制1 s内存限制64 MB输入第一行分别为矩阵的行数m mm和列数n nnm 100 m 100m100n 100 n 100n100两者之间以一个空格分开。接下来输入的m mm行数据中每行包含n nn个整数整数之间以一个空格分开。输出输出对应矩阵的边缘元素和。样例输入3 3 3 4 1 3 7 1 2 0 1样例输出15思路分析此题考察嵌套循环属于入门题。根据题目描述我们应该定义一个二维数组进行存储与求解。事实上只需要判断当前输入的数据是否处于矩阵边缘即可无需二维数组详见参考代码。/* * Name: T1.cpp * Problem: 计算矩阵边缘元素之和 * Author: Teacher Gao. * DateTime: 2024/11/16 00:06 */#includeiostreamusingnamespacestd;intmain(){intm,n,x,sum0;cinmn;for(inti1;im;i){for(intj1;jn;j){cinx;if(i1||j1||im||jn){sumx;}}}coutsum;return0;}T2. 最长最短单词题目链接SOJ D1225输入1 11行句子不多于200 200200个单词每个单词长度不超过100 100100只包含字母、空格和逗号。单词由至少一个连续的字母构成空格和逗号都是单词间的间隔。试输出第1 11个最长的单词和第1 11个最短单词。时间限制1 s内存限制64 MB输入一行句子。输出两行输出第1 11行第一个最长的单词。第2 22行第一个最短的单词。样例输入I am studying Programming language C in Peking University样例输出Programming I提示如果所有单词长度相同那么第一个单词既是最长单词也是最短单词。思路分析此题考察字符串操作与打擂台思想难度入门。此题与 2022 年 3 月二级 T3 类似利用cin无法读取空格这个事实我们迅速解决不定项输入的问题。接下来只需要考虑当前字符串中是否存在逗号如果存在逗号就将单词进行分隔然后用每一个单词的长度参与两次打擂台即可。/* * Name: T2.cpp * Problem: 最长最短单词 * Author: Teacher Gao. * DateTime: 2024/11/15 22:56 */#includeiostream#includestringusingnamespacestd;intmain(){string s,Min(105,a),Max;while(cins){intps.find(,);while(p!-1){if(pMax.size()){Maxs.substr(0,p);}if(pMin.size()){Mins.substr(0,p);}s.erase(0,p1);ps.find(,);}if(s.size()Max.size()){Maxs;}if(s.size()Min.size()){Mins;}}coutMaxendlMin;return0;}T3. 啤酒厂选址题目链接SOJ P2855海上有一个岛在环海边上建有一条环岛高速公路沿着公路有n nn5 ≤ n ≤ 10000 5 \le n \le 100005≤n≤10000个居民点假设每个居民点有一个编号从0 00开始按顺时针依次从小到大即0 , 1 , . . . , n − 1 0,1,...,n-10,1,...,n−1编号。在岛上啤酒很受青睐。某啤酒企业计划在岛上投资建一个啤酒厂并根据啤酒需求每天向居住点送啤酒。已知两个相邻的居民点的距离以及每个居住点每天的啤酒需求量假设每个居住点每天不超过2000 20002000桶。假定每单位长度的路程送一桶啤酒需要的费用恒定为单位费用1 11。请问选择哪一个居民点建啤酒厂才能使每天送啤酒的费用最小空车不计费用。时间限制1 s内存限制64 MB输入第一行为居民点数目n nn。后面为n nn行每行为一个居民点的啤酒需求量以及按顺时针离下一个居民点的距离距离为不超过100 100100的正整数从编号为0 00的开始按递增顺次给出。注意后面第n nn行对应于居民点( n − 1 ) (n-1)(n−1)的啤酒需求量以及到编号为0 00的居民点距离。输出啤酒厂所在的居民点编号以及每天的运输费用其间以空格分隔数据保证答案唯一。样例输入6 500 10 300 30 350 25 400 60 700 28 200 35样例输出0 94100思路分析此题考察枚举法属于基础题。依次枚举啤酒厂的位置然后计算每个居住点的运输成本最后在所有运输成本中选取最小值即可。计算居住点的运输成本时应该选择两个运输方向中运输距离较短的一个。注意题目给出的距离是相邻两个居住点的距离因此计算运输距离时需要累加。该算法的时间复杂度为O ( n 2 ) O(n^2)O(n2)。/* * Name: T3_1.cpp * Problem: 啤酒厂选址 * Author: Teacher Gao. * DateTime: 2026/01/10 02:17 */#includeiostreamusingnamespacestd;intmain(){ios::sync_with_stdio(false),cin.tie(0);intn,a[10005]{0},d[10005]{0};intsumlen0;cinn;for(inti0;in;i){cina[i]d[i];// 计算环线总长度sumlend[i];}longlongans1LL60,ansid0;// 枚举啤酒厂的位置for(inti0;in;i){intindex,len0;longlongcnt0;// 依次计算每一个居住点的运输成本for(intji;jni;j){indexj;// 居住点编号修正if(jn)indexj-n;cntmin(len,sumlen-len)*a[index];// 计算下一个居住点的运输距离lend[index];}if(cntans){anscnt;ansidi;}}coutansid ansendl;return0;}注意到随着啤酒厂的位置向右移动啤酒厂左侧的居住点到啤酒厂的距离如果超过环线总长度的一半那么该居住点就应该从啤酒厂的右侧运输。换言之随着啤酒厂的位置向右移动最左侧居住点的编号和最右侧居住点的编号都会向右单向移动适用于尺取法。为了保持这种单向移动我们可以把输入数据连续存储两遍于是a [ n ] a[n]a[n]的下一个就是a [ 1 ] a[1]a[1]。这样一来居住点的编号就不再需要修正运输成本的计算就变成了求区间和的操作适用于前缀和。至此我们得到了一个O ( n ) O(n)O(n)时间复杂度的算法。首先假设居住点0 00在啤酒厂左侧居住点n − 1 n-1n−1在啤酒厂右侧于是我们可以找到这种情况下啤酒厂的位置p pp并且计算出对应的运输成本t o t tottot。记s 0 s0s0t n − 1 tn-1tn−1分别表示目前啤酒厂两侧距离啤酒厂最远的居住点编号接下来让啤酒厂向右移动一个位置然后检测s ss号居住点到新酒厂的距离是否超过了环线总长度的一半如果是的话就将该居住点移动到酒厂右侧即s 1 s1s1t 1 t1t1直到s ss号居住点到酒厂的距离不超过环线总长度的一半。在移动啤酒厂和居住点的过程中更新运输成本t o t tottot并求出每次更新之后t o t tottot的最小值即为答案具体来说原来啤酒厂右侧的居住点编号p ∼ t p\sim tp∼t运输成本降低从左侧移动到右侧的居住点的运输成本需要重新计算先减去移动之前的再加上移动之后的依然留在左侧的居住点的运输成本增加。/* * Name: T3_2.cpp * Problem: 啤酒厂选址 * Author: Teacher Gao. * DateTime: 2026/01/10 02:17 */#includeiostream#includecmathusingnamespacestd;intn,a[20005],d[20005];longlongsuma[20005],sumd[20005],DIS;intmain(){ios::sync_with_stdio(false),cin.tie(0);cinn;for(inti0;in;i){// 距离 d 的存储做了下标偏移目的是便于之后计算距离成本防止下标越界cina[i]d[i1];DISd[i1];a[in]a[i],d[in1]d[i1];}sumd[1]d[1];suma[0]a[0];for(inti2;inn;i){sumd[i]sumd[i-1]d[i];suma[i-1]suma[i-2]a[i-1];}// 寻找第一个建啤酒厂的位置longlongtot0,p0;while(sumd[p1](DIS1)/2)p;for(inti0;in;i){tota[i]*abs(sumd[p]-sumd[i]);}longlongansidp,anstot,s0,tn-1;for(inti1;in;i){// 枚举新啤酒厂的位置intnppi;// 新啤酒厂右边的居住点运输成本降低tot-d[np]*(suma[t]-suma[np-1]);// 把原啤酒厂左边的居住点中到新啤酒厂距离超过环长一半的居住点改为从右侧运输while(sumd[np]-sumd[s](DIS1)/2){// 减去原来的运输成本tot-a[s]*(sumd[np-1]-sumd[s]);s,t;// 计算新的运输成本tota[t]*(sumd[t]-sumd[np]);}// 剩下的依然留在左边的居住点运输成本增加totd[np]*(suma[np-1]-suma[s-1]);if(totans){anstot;ansidnp;}}coutansid%n ansendl;return0;}T4. 统计误差范围内的数题目链接SOJ D1199统计一个整数序列中与指定数字m mm误差范围小于等于x xx的数的个数。时间限制1 s内存限制64 MB输入输入包含三行第一行为n nn表示整数序列的长度n ≤ 100 n \le 100n≤100第二行为n nn个整数整数之间以一个空格分开第三行包含2 22个整数为指定的整数m mm误差范围x xx。输出输出为n nn个数中与指定数字m mm误差范围小于等于x xx的数的个数。样例输入5 1 2 3 4 5 3 1样例输出3提示样例中2 223 334 44都满足条件故答案为3 33。思路分析此题考察一维数组的查找与统计属于入门题。此题与 2021 年 12 月二级 T1 类似将给定数据存储在数组中之后依次遍历每一个元素检测其是否介于m − x ∼ m x m-x \sim mxm−x∼mx范围内若是则计数器变量累加1 11最后输出计数器变量的值即可。/* * Name: T4.cpp * Problem: 统计误差范围内的数 * Author: Teacher Gao. * DateTime: 2024/11/15 21:40 */#includeiostreamusingnamespacestd;intmain(){intn,a[105],m,x;cinn;for(inti1;in;i){cina[i];}cinmx;inttot0;for(inti1;in;i){if(m-xa[i]a[i]mx){tot;}}couttot;return0;}T5. 单词排序题目链接SOJ D1266输入一行单词序列相邻单词之间由1 11个或多个空格间隔请按照字典序输出这些单词要求重复的单词只输出一次。区分大小写。时间限制1 s内存限制64 MB输入一行单词序列长度小于10000 1000010000最少1 11个单词最多100 100100个单词每个单词长度不超过50 5050单词之间用至少1 11个空格间隔。数据不含除字母、空格外的其他字符。输出按字典序输出这些单词重复的单词只输出一次。样例输入She wants to go to Peking University to study Chinese样例输出Chinese Peking She University go study to wants思路分析此题考察字符串的查找与排序属于入门题。用string数组存储所有字符串之后分别用sort()函数和unique()函数即可达到按字典序排序并去重的效果。/* * Name: T5.cpp * Problem: 单词排序 * Author: Teacher Gao. * DateTime: 2024/11/16 00:41 */#includeiostream#includestring#includealgorithmusingnamespacestd;intmain(){intn0;string s[105];while(cins[n]);sort(s1,sn);intmunique(s1,sn)-(s1);for(inti1;im;i){couts[i]endl;}return0;}