2026HAUE新生周赛热身赛题解
2026热身赛 题解A - 博丽神社的赛钱箱题意给定 n 个正整数求它们的总和。解题思路这是一道最基础的求和题直接遍历累加即可。算法线性遍历累加求和复杂度时间复杂度O(n)空间复杂度O(1)代码voidsolve(){intn;cinn;intsum0;for(inti0;in;i){intx;cinx;sumx;}coutsumendl;}注意事项使用long long防止溢出n10^5, 每个数109总和可达1014B - 雾之湖的冰精题意给定 n 个正整数找出其中的最小值。解题思路遍历所有数维护当前最小值。算法线性遍历维护最小值复杂度时间复杂度O(n)空间复杂度O(1)代码voidsolve(){intn;cinn;intminnMAX;for(inti0;in;i){intx;cinx;minnmin(minn,x);}coutminnendl;}注意事项初始化最小值为一个很大的数如LLONG_MAXC - 命莲寺的钟声题意每a分钟敲一次钟每次敲b下。从第一声铃声到祭祀结束时间间隔为t分钟。求从第一声铃声到最后一个铃声响起这段时间内总共敲了多少下钟。输入三个正整数a、b、t1 ≤ a, b, t ≤ 1000。解题思路第一声铃声发生在时刻 0之后每隔a分钟再敲一次敲钟时刻为0, a, 2a, 3a, …祭祀在时刻t结束因此只计入时刻≤ t的敲钟最后一个敲钟时刻为⌊t/a⌋ · a敲钟场次数 ⌊t/a⌋ 1总敲钟下数 (⌊t/a⌋ 1) × b样例3 2 10敲钟时刻为 0, 3, 6, 9共 4 次每次敲 2 下答案为 8。算法公式计算复杂度时间复杂度O(1)空间复杂度O(1)代码voidsolve(){inta,b,t;cinabt;cout(t/a1)*bendl;}注意事项t / a是整数除法等价于向下取整⌊t/a⌋时刻 0 的第一声铃声要算上所以场次数是t/a 1而不是t/a若t是a的倍数时刻t的敲钟也算在内场次数含端点答案最大为(1000/1 1) × 1000 1001000普通int即可D - 香霖堂的货物题意给定 n 个字符串统计每个长度出现的次数按长度从小到大输出。解题思路使用 map 记录每个长度的出现次数map 会自动按 key长度排序算法计数 排序复杂度时间复杂度O(n log n)空间复杂度O(n)代码voidsolve(){intn;cinn;mapint,intmp;for(inti0;in;i){string s;cins;mp[s.size()];}for(auto[len,cnt]:mp){coutlen cntendl;}}注意事项使用 map 自动排序也可以用数组 sortE - 红魔馆的图书馆题意给定 n 个正整数按从小到大排序后输出。解题思路直接使用 STL 的 sort 函数。算法快速排序复杂度时间复杂度O(n log n)空间复杂度O(n)代码voidsolve(){intn;cinn;vectorinta(n);for(inti0;in;i){cina[i];}sort(all(a));for(inti0;in;i){couta[i] \n[in-1];}}注意事项输出格式数字之间用空格分隔F - 红魔乡的妖精题意给定一个正整数 n判断它是奇数还是偶数。解题思路判断 n % 2 的值。算法取模运算复杂度时间复杂度O(1)空间复杂度O(1)代码voidsolve(){intn;cinn;if(n%20){coutEvenendl;}else{coutOddendl;}}注意事项注意输出是 “Odd”/“Even”首字母大写G - 妖怪山的阶梯题意给定 n≤ 10^9求 12…n 的结果对 998244353 取模。解题思路等差数列求和公式S n*(n1)/2n ≤ 10^9n*(n1) 最大约 10^18在 long long 范围内先计算乘积再除以 2最后取模算法等差数列求和复杂度时间复杂度O(1)空间复杂度O(1)代码constintMOD998244353;voidsolve(){intn;cinn;cout(n1)*n/2%MODendl;}注意事项n*(n1) 不会溢出 long long可以直接计算H - 地灵殿的宝石题意给定 n 个正整数找出最大值和最小值输出它们的差值。解题思路遍历一次同时维护最大值和最小值。算法线性遍历复杂度时间复杂度O(n)空间复杂度O(1)代码voidsolve(){intn;cinn;intmaxx0,minnMAX;for(inti0;in;i){intx;cinx;maxxmax(maxx,x);minnmin(minn,x);}coutmaxx-minnendl;}注意事项n ≤ 100数据很小无需优化I - 辉针城的符卡题意给定一个字符串统计其中大写字母和小写字母的数量。解题思路遍历字符串使用isupper()判断字符类型。算法字符遍历复杂度时间复杂度O(|s|)空间复杂度O(1)代码voidsolve(){string s;cins;intupper0,lower0;for(charc:s){if(isupper(c))upper;elselower;}coutupper lowerendl;}注意事项字符串长度不超过 100无需优化J - 天界的空间题意给定一个正整数 n≤ 10^12判断它是否是质数。解题思路n 的范围是 10^12√n ≈ 10^6使用试除法复杂度 O(√n) 完全可以接受优化先排除 2 和 3 的倍数然后只检查 6k±1 形式的数算法试除法复杂度时间复杂度O(√n)空间复杂度O(1)代码boolisPrime(longlongn){if(n2)returnfalse;if(n2||n3)returntrue;if(n%20||n%30)returnfalse;for(longlongi5;i*in;i6){if(n%i0||n%(i2)0)returnfalse;}returntrue;}voidsolve(){longlongn;cinn;cout(isPrime(n)?Yes:No)endl;}注意事项√(10^12) 10^6试除法可以在 1 秒内完成只检查 6k±1 形式的数可以减少约 2/3 的检查次数约束#includebits/stdc.h#defineintlonglong#defineullunsignedlonglong#defineendl\n#defineMAXLLONG_MAX#definePIIpairint,int#definepbpush_back#defineebemplace_back#definefifirst#definesesecond#defineall(a)a.begin(),a.end()#definerall(a)a.rbegin(),a.rend()usingnamespacestd;signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int_1;//cin _;while(_--){solve();}return0;}