HBUACM

小A买了一个新的存钱罐，他很开心。从他买存钱罐的第 1 天起， 他每天都会往存钱罐里存钱， 第 1 天存 1 元， 第 2 天存 2 元…以此类推， 第 i 天存 i 元， 小A想要知道他最早哪一天能存到 N 元以上， 你能帮他算一算吗。 前3个测试点满足 1≤N≤105 后2个测试点满足 1≤N≤109 所有测试点中 T 满足 1≤T≤105 输入格式：总共有 T 次询问, Ni表示存钱罐中存到Ni元需要多少天 12345678TN1N2N3...Ni...NT 输出格式：输出T个数， 表示最早存到 Ni元以上的天数 输入样例：123212100128 输出样例：125447 对于第一个询问的解释 : 第 1 天存钱罐有 1 元 第 2 天存钱罐有 3 元 第 3 天存钱罐有 6 元 第 4 天存钱罐有 10 元 第 5 天存钱罐有 15 元, 大于 12 元, 因此答案是第 5 天 思路等差数列an=n，询问该等差数列前n项和，n为几时大于给定的Ni 可直接暴力循环计算，会超时 利用等差数列求和公式，Sn=(n*(a1+an))/2 代码12345678910111213 ...

给定一个长度为 n 的整数序列 a1 , a2 , … , an。我们称一个二元组(i,j)是完美配对的，当且仅当 i<j 并且 ai−aj=j−i.求完美配对的二元组数目. 对于前 3 个测试点 1≤n≤103 对于后两个测试点 1≤n≤105 所有的测试点都满足 1≤ai≤105 输入格式：12na1 a2 ... an 输出格式：输出完美配对的二元组数目 输入样例：1253 2 5 2 6 输出样例：仅有一对二元组（1, 2）满足条件， 因为 3 - 2 = 2 - 1. 11 思路暴力循环会超时 只要两个元素满足ai−aj=j−i，即ai+i=aj+j，元素数+索引数相等即可配对 开数组标记每个元素的元素数+索引数的和，扫描给定数组，每扫描一个数，寻找前面已扫描过的满足ai+i=aj+j的数量即可 代码123456789101112131415161718192021#include <iostream>using namespace std;const int N = 1e6 + 5;int arr[N], num[N];int main()  ...

给定某个正整数 N，求其素因子分解结果，即给出其因式分解表达式 N=p1K1⋅p2K2⋯pm 输入格式：输入long int范围内的正整数 N。 输出格式：按给定格式输出N的素因式分解表达式，即 N=p1^k1*p2^k2*…*pm^km，其中pi为素因子并要求由小到大输出，指数ki为pi的个数；当ki为1即因子pi只有一个时不输出ki。 输入样例：11323 输出样例：11323=3^3*7^2 思路数学模拟题。具体看代码，或者讲解视频 代码123456789101112131415161718192021222324#include<stdio.h>int main() { long long n; scanf("%lld", &n); int first = 0; printf("%lld=", n); for(int i = 2; i <= n / i; i++) { if(n % i == 0) { int num = 0; ...

给定一个包含 N 个正整数的集合，请你将它划分为两个集合 A1 和 A2，其中 A1 包含 n1 个元素，A2 包含 n2 个元素。集合中可以包含相同元素。用 S1 表示集合 A1 内所有元素之和，S2 表示集合 A2 内所有元素之和。请你妥善划分，使得∣n1−n2∣ 尽可能小，并在此基础上∣S1−S2∣ 尽可能大。 2≤N≤105, 保证集合中各元素以及所有元素之和小于 231。 输入格式：第一行包含整数 N。 第二行包含 N 个正整数。 输出格式：在一行中输出 ∣n1−n2∣ 和 ∣S1−S2∣，两数之间空格隔开。 输入样例1：121023 8 10 99 46 2333 46 1 666 555 输出样例1：10 3611 输入样例2：1213110 79 218 69 3721 100 29 135 2 6 13 5188 85 输出样例2：11 9359 思路将一个集合划分为S1和S2两个集合，首先使两集合元素总数的差尽可能小，在此基础上使两集合元素和的差尽可能小 两集合元素总数的差尽可能小，即尽可能趋于0。 原集合的元素总数为偶数，则可S1和S2各分配一半元素； ...

本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串，各单词之间用空格分隔，空格数可以是多个。 输入格式：输入给出一行字符。 输出格式：在一行中输出单词个数。 输入样例：1Let's go to room 209. 输出样例：15 鸣谢用户 张麦麦 补充数据！ 思路getline输入字符串，扫描字符串 遇到字母时，若这个字母的前一个字符不是空格，则是一个新单词 代码123456789101112131415161718192021#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { string str; getline(cin, str); char ch = ' '; //当前位置的前一个字符 int ret = 0; for(int i=0;i<(int)str.size();i++) { char it=st ...

本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据由（a0a1⋯an−1）变换为（am⋯an−1a0a1⋯am−1）（最前面的m个数循环移至最后面的m个位置）。如果还需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？ 输入格式：输入第1行给出正整数n（≤100）和整数m（≥0）；第2行给出n个整数，其间以空格分隔。 输出格式：在一行中输出循环左移m位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。 输入样例：128 31 2 3 4 5 6 7 8 输出样例：14 5 6 7 8 1 2 3 思路将数组左移m位，相当于（假设一个数组的索引为1n）：先输出(m+1)n，再输出1~m 注意，m可能大于等于n，等于n时，相当于没有变化；大于n时，需要m=m%n 正常法：扫描数组，让m索引后的数，a[i-1]=a[i]，左移 混水摸鱼法：不听题目的话，就单独开个数组，先存储进(m+1)n，然后存储进1m。输出这个单独开的数组。 代码混水摸鱼 12345678 ...

给定一个长度为 n 的整数序列 a1 , a2 , … , an。我们称一个二元组(i,j)是完美配对的，当且仅当 i<j 并且 ai−aj<j−i.求完美配对的二元组数目. 对于前 3 个测试点 1≤n≤103 对于后两个测试点 1≤n≤105 所有的测试点都满足 1≤ai≤105 输入格式：12na1 a2 ... an 输出格式：输出完美配对的二元组数目 输入样例：1253 2 5 2 6 输出样例：仅有一对二元组（1, 2）满足条件， 因为 3 - 2 = 2 - 1. 11 思路暴力循环会超时，弄懂完美配对1再看本题 需要树状数组，没有学习过数据结构的话，本题可不了解，等知识积累到一定程度后，再学习树状数组是什么 只要两个元素满足ai−aj<j−i，即ai+i<aj+j 扫描给定数组，每扫描一个数ai，寻找前面已扫描过的满足ai+i<aj+j的数的数量，相当于寻找标记的aj+j为0到aj+j为(ai+i-1)的所有元素数 不再和完美配对1那样取num[arr[i] + i-1]值，而是取num[0]~num[arr[i] + i-1]的所有 ...

2021河北大学暑期程序设计训练每日知识分享-day01 每日分享——复杂度分析在刷算法题时，经常遇到超时或者内存超限的提示，这与算法本身的时间复杂度和空间复杂度有关，其中时间复杂度是评判程序运行效率的重要指标，也是我们重点关注的部分。那么如何进行复杂度分析呢？1.复杂度分析： 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。因此从执行时间和占用空间两个维度来评估数据结构和算法的性能。 复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有（大 O 复杂度表示法）：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。 2.复杂度分析法则 单段代码看高频：比如循环。 多段代码取最大（加法法则）：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。 嵌套代码求乘积（乘法法则）：比如递归、多重循环等 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。 3.常用的复杂度级别 ...

天梯赛考前冲刺例题分享0、感觉感觉排序输出、字符串处理、数学题这样的题变化很大，使用的方法因题而定，很少固定的套路。这里只写了写那些可以靠固定套路（不怎么需要思考，基本围绕某一个算法）的题，感觉是一类题 1、模拟静态链表链表元素分类 Sharing 2、具体的排序方法快速排序 插入与归并 Insertion or Heap Sort 3、二叉树的遍历建立树的遍历 Tree Traversals Again 4、BST建立Build A Binary Search Tree Counting Nodes in a BST 5、树的深搜一般都是搜索结点的信息 Deepest Root Path of Equal Weight 6、AVL和R-BAVL和R-B似乎不是考点，但听说L2和甲级出题大纲一样，甲级都有AVL和R-B了（不过只涉及了基本的了解，而且会在题目中给出定义） Root of AVL Tree Is It A Red-Black Tree 7、图的最短路径只是突然想起来，万一考负权边，就要Bellman-Ford了。不过以前从未考过 8、是否完全二叉树的判断Complete ...

本题目要求通过读入无向网的边的信息（省略了各顶点的信息，仅用顶点编号来表示），构造图，并利用Dijkstra算法，求出指定源点到其它各点的最短路径。 输入样例:第一行，两个整数，顶点数vN和边数eN。 以后若干行，是相关边的信息，无向图的边是对称的，只输入一半的边（小编号到大编号的，间以空格），最后两行各一个整数，前一个指定源点，后一个指定的查询的终到点。 （注意，示例中34条边，只输入了17条边的信息） 123456789101112131415161718192010 340 1 20 3 51 2 51 3 22 4 82 5 43 5 43 6 24 7 54 5 25 6 35 7 95 8 76 8 77 8 37 9 48 9 808 输出样例:在一行中输出从源点到指定终点的短路径及代价，注意：所有符号均为西文符号。 10-->1-->3-->6-->8:13 思路： 单源最短路径算法，注意源点和终点相同的情况，需要特判输出 代码：12345678910111213141516171819202122232425262728293031323 ...