☻ 课前练习 一. 素数 问题：如何判断一个数字是不是质数？ 质数定义：只有1和它本身2个因数的数，最小的质数(素数)是2。 方法1：统计因数个数 方法2：试除法， 2到n-1之间不存在第3个因数 实例1:A325.打印质数表 A. 非函数版 B. 函数版 实例2:A491.质因数 二. 最大公约数 实例: A7821.最大公约数 方法1: 枚举 方法2：辗转相除法(欧几里得) 三. 最小公倍数 实例：A30161.【循环】 最小公倍数

过不了关的。

⚑ 常见数学函数以及头文件 ⚑ 练习实例代码 实例1：最大值与最小值的和 实例2：打印分数 输出低于平均分的分数。 实例3：最大值最小值之间的数字个数 找到第一次出现的最大值or最小值，然后输出他两之间的数字个数。 实例4：数字统计 输出三行，第一行是在[x，y]区间内数字的个数， 第二行是区间内的数字， 第三行是不在区间内的数字。 实例5：找数字 输出数组中数字k出现的次数， 如果没有，则输出-1。

好难

第一题题解 A33695.换行 > 解题思路 > 第一题比较简单，单纯的考察C++的基础知识转义字符的使用，注意一下换行符的使用即可。 第二题题解 A33696.求和 > 解题思路 > 第二题主要考察了一下时间复杂度的计算，如果简单的使用forforfor循环，nnn的范围是1≤n≤21474836471≤n≤21474836471≤n≤2147483647，时间复杂度是O(n)O(n)O(n)，会超时，所以需要使用数学方法，高斯求和(等差求和公式)，时间复杂度是O(1)O(1)O(1)。 第三题题解 A33697.权重 > 解题思路： > 本题的重点还是考察了数据范围，把数据开成long long，基本上就没啥问题了。 > 首先读取字符串，统计一下每个字符出现的次数，然后给的公式计算权重进行累加即可。 第四题题解 A33698.最大公约数 1. 计算因子个数： * 定义函数 countFactors，用于计算一个整数的因子个数。通过从 1 到该整数的平方根进行遍历，因为如果 i 是 num 的因子，那么 num / i 也是 num 的因子（除了 i 和 num / i 相等的情况，此时只算一个）。 * 对于每个能整除 num 的 i，先将因子个数加 2（表示 i 和 num / i 两个因子），如果 i 和 num / i 相等，就需要把多算的一次减掉，从而准确得到 num 的因子个数。 2. 处理输入并计算因子个数序列： * 在 main 函数中，先读取输入的 n（整数个数）和 m（目标累加和）。 * 然后通过循环依次读取 n 个整数，对于每个读取到的整数 tmp，调用 countFactors 函数计算其因子个数，并将结果添加到向量 v 中，这样就得到了所有整数的因子个数构成的向量。 3. 排序与累加查找： * 使用 sort 函数对向量 v 中的因子个数进行排序，排序方式是从大到小（通过 greater<int> 指定）。 * 接着通过循环依次累加排序后的因子个数，用变量 sum 记录累加和。在每次累加后，判断 sum 是否大于等于 m，如果满足这个条件，就输出当前的累加次数 i + 1（因为索引是从 0 开始的，所以要加 1 才是从 1 开始计数的正确索引），然后程序结束。 复杂度分析 1. 时间复杂度： * 计算因子个数部分：对于每个整数计算因子个数时，需要从 1 到该整数的平方根进行遍历，假设输入的整数最大值为 N，那么计算一个整数因子个数的时间复杂度大约为 O(N)O(\sqrt{N})O(N )。总共要计算 n 个整数的因子个数，所以这部分的时间复杂度大约为 O(nN)O(n\sqrt{N})O(nN )。 * 排序部分：使用 sort 函数对向量 v 进行排序，一般 sort 函数的时间复杂度为 O(nlogn)O(nlogn)O(nlogn)，这里 n 是向量 v 的长度，也就是输入的整数个数。 * 累加查找部分：通过循环依次累加向量 v 中的元素，时间复杂度为 O(n)O(n)O(n)。 * 综合起来，整个程序的时间复杂度大约为 O(nN+nlogn+n)O(n\sqrt{N} + nlogn + n)O(nN +nlogn+n)，简化后约为 O(nN+nlogn)O(n\sqrt{N} + nlogn)O(nN +nlogn)。 2. 空间复杂度： * 主要的空间消耗在于存储每个整数的因子个数的向量 v，向量 v 的长度最大为 n，所以空间复杂度为 O(n)O(n)O(n)。 第五题题解 A33699.美丽数组 1. 判断回文 2. 判断奇数项之和与偶数项之和是否相等 时间复杂度分析 * 对于每个测试用例： * 判断回文数组的操作：在 isPalindrome 函数中，需要遍历数组的前半部分元素，时间复杂度为 O(n)O(n)O(n)，其中 n 为数组的长度。 * 判断奇数项之和与偶数项之和是否相等的操作：在 isSumEqual 个函数中，需要遍历数组的每一个元素，时间复杂度也为 O(n)O(n)O(n)。 * 总共存在 T 个测试用例，所以整个程序的时间复杂度为 O(Tn)O(Tn)O(Tn)。 空间复杂度分析 * 主要的空间消耗在于存储数组元素的数组 a，其大小为 100005，但实际上对于每个测试用例，只使用了其中的 n 个位置来存储数组元素。所以空间复杂度为 O(n)O(n)O(n)，这里的 n 是指每个测试用例中数组的长度。 第六题题解 A33700.字典序问题 1. 整体思路 * 我们要想办法构造出一个可能的字典序最大的字符串。考虑到数字越大在字典序中越靠后，所以要尽量让高位数字尽可能大。 * 因为 n 的取值范围可能很大（从代码中看，是用字符串来接收 n 的，这也暗示了 n 可能是非常大的数），所以我们通过对 n 的字符串表示进行分析和操作来找到答案。 2. 具体步骤 * 首先，判断 n 是否全部由数字 9 组成。如果是，那字典序最大的字符串就是 n 本身啦，不过代码里没有显式地处理这种全 9 的情况，我们先接着往下看一般情况的处理。 * 然后，我们先构造一个临时字符串 tmp，它的长度是 n 的长度减1，并且每个字符都是 9。为什么要这样做呢？因为我们要让高位尽可能大，所以先假设高位都是 9，然后再根据实际情况进行调整。假设现在有一个5位数，那么9999算是最大的数字，除非这个5位数是9999?,所以需要对最后一位数字进行判断。 * 最后，我们再看 n 的最后一位数字。如果 n 的最后一位不是 0，并且 n 的前 len - 1 位（也就是去掉最后一位的部分）组成的字符串大于等于我们刚才构造的 tmp，那就把 n 的最后一位数字加到 tmp 后面。这样得到的 tmp 就是我们要找的字典序最大的字符串啦。

bushini 你敢嘛~~~~

A30779求助！！！！

为了提高它们的体能，牛们开始学习体操！ 农民约翰指派他最喜欢的牛贝西来训练其他N头牛，并在它们学习各种体操技巧时评估它们的进步。 在每个练习环节中（1 ≤ K ≤ 10），贝西根据表现对N头牛进行排名（1 ≤ N ≤ 20）。之后，她对这些排名的一致性感到好奇。如果一对不同的牛中的一头在所有练习中都表现得比另一头好，那么这对牛就是一致对。 帮助贝西计算一致对的总数。 输入格式 输入文件的第一行包含两个正整数K和N。 接下来的K行每行包含整数1…N，表示牛的排名（牛用数字1…N标识）。如果A出现在其中一行的B之前，那意味着牛A的表现比牛B好。 输出格式 输出一行，表示一致对的数量。

这题是错题，那为什么还要加在ACGO

在一个U盘里写一个程序，插入时自动运行，这样不就好了吗？

T1 根据题意要计算出数组共有几个不重复的元素 用set秒了 C++ STL set容器完全攻略（超级详细） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 走路 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3 T3根据T4的提示就是个思维题↓ 。。。。好吧(づ′▽`)づ 首先题目要求 > 求min（ |d1-d2|, |d1-d3|, |d2-d3| ）的最大值 那么要让三个数的两两之间的差的最小值 最大 就是要让d1, d2, d3之间差越大 稍微举例一下就能发现规律 以下举例用 1 代表工作日，用 x 代表休息日 天数 分配 答案 10 11x1x1111x 1 11 111x1x1111x 1 12 111x1x11111x 2 13 111x1x111111x 2 14 1111x1x111111x 2 15 1111x1x1111111x 3 看出规律了吗？ 把一个工作日夹在剩下两个休息日中间 所以d2 = 1 整个月剩下的天数就是 n - 1（最后一天休息日）- 3 （一个工作日夹在剩下两个休息日中间） 剩下的天数分成 d1, d3 可以想到，当 2d1 = d3 的时候 |d1-d2| 和 |d2-d3| 是最大的 所以d1,d3 分别是 剩余天数（n-4）的 1/3 和 2/3 以及，如果n-4除不尽三就把d1加一 * 以下超短题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T4 求质数个数，用埃筛 埃氏筛法详解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T5 > 「好串」：如果这两个字符串中每个字符出现的次数相同（顺序不需要相同）则被称作为一对好串 把字符数组排序，然后逐个比较就行 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T6 Good Luck! ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > * 求赞！

波克布林=哥布林

这会的的欢乐赛有点离谱， 简直是·水题啊 第one道： 其实这道题很简单，用set或map都行（包括去重） 第tow道： 第一眼看到这题，我竟然第一下想到了“dfs” 啊啊啊啊啊啊啊啊啊啊啊啊 精神状态良好） 第three道： 这道题其实是一道思维题 我想了半天，最终推出来时“n/3−2n/3-2n/3−2”（so 我还想怎么能在欢乐赛出这种题呢？？？ 第four道： 这道题本来想用埃式筛的，结果一看数据，普通晒垡完全够。 第five道： 没啥可讲的，sort即可 第six道： 不想讲

根据邮件的重量和计算鸭是否选择加急计算邮费。

There is something wrong with the CF, please try again later

第一次过普及+

吾不知

循环的嵌套

#include<iostream> using namespace std; int main(){ char a; cin >> a; if (a=='a')cout<<"A"; else if (a == 'b') cout << "B"; else if (a == 'c') cout << "C"; else if (a == 'd') cout << "D"; else if (a == 'e') cout << "E"; else if (a == 'f') cout << "F"; else if (a == 'g') cout << "G"; else if (a == 'h') cout << "H"; else if (a == 'i') cout << "I"; else if (a == 'j') cout << "J"; else if (a == 'k') cout << "K"; else if (a == 'l') cout << "L"; else if (a == 'n') cout << "N"; else if (a == 'm') cout << "M"; else if (a == 'o') cout << "O"; else if (a == 'p') cout << "P"; else if (a == 'q') cout << "Q"; else if (a == 'r') cout << "R"; else if (a == 's') cout << "S"; else if (a == 't') cout << "T"; else if (a == 'u') cout << "U"; else if (a == 'v') cout << "V"; else if (a == 'w') cout << "W"; else if (a == 'x') cout << "X"; else if (a == 'y') cout << "Y"; else if (a == 'z') cout << "Z"; else if (a == 'A') cout << "a"; else if (a == 'B') cout << "b"; else if (a == 'C') cout << "c"; else if (a == 'D') cout << "d"; else if (a == 'E') cout << "e"; else if (a == 'F') cout << "f"; else if (a == 'G') cout << "g"; else if (a == 'H') cout << "h"; else if (a == 'I') cout << "i"; else if (a == 'J') cout << "j"; else if (a == 'K') cout << "k"; else if (a == 'L') cout << "l"; else if (a == 'N') cout << "n"; else if (a == 'M') cout << "m"; else if (a == 'O') cout << "o"; else if (a == 'T') cout << "t"; else if (a == 'U') cout << "u"; else if (a == 'V') cout << "v"; else if (a == 'W') cout << "w"; else if (a == 'X') cout << "x"; else if (a == 'Y') cout << "y"; else if (a == 'Z') cout << "z"; return 0; }