目录1 题目描述1.1 输入描述1.2 输出描述1.3 示例12 题解 题目链接:https://ac.nowcoder.com/acm/contest/135/I?&headNav=acm 题目描述 Apojacsleam喜欢数组。 他现在有一个n个元素的数组a,而他要对a[L]-a[R]进行M次操作: 操作一:将a[L]-a[R]内的元素都加上P 操作二:将a[L]-a[R]内的元素都减去P 最后询问a[l]-a[r]内的元素之和 输入描述 输入共M+3行: 第一行两个数,n,M,意

Read More

树状数组 重点是在树状的数组 大家都知道二叉树吧 叶子结点代表 A 数组 A[1]~A[8] 现在变形一下 现在定义每一列的顶端结点C[]数组 如下图 C[i]代表 子树的叶子结点的权值之和// 这里以求和举例 如图可以知道 C[1]=A[1]; C[2]=A[1]+A[2]; C[3]=A[3]; C[4]=A[1]+A[2]+A[3]+A[4]; C[5]=A[5]; C[6]=A[5]+A[6]; C[7]=A[7]; C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+

Read More

在使用string类时,需要包含头文件 #include<string></string>。并且引入using std::string; using std::wstring;或using namespace std; 下面你就可以使用string/wstring了,它们两分别对应着char和wchar_t。 string和wstring的用法是一样的,以下只用string作介绍:

Read More

目录1 大体题意1.1 输入1.2 输出2 思路2.1 博弈部分2.2 判断函数2.3 DFS函数2.4 状态压缩部分3 完整代码 题目传送门 大体题意 Alice 和 Bob 在玩一个游戏,Alice是先手,Bob是后手 给出一个数字序列,Alice和Bob每回合可以从中取出一个数 当序列变为不下降序列时,上一回合的玩家获胜 输入 第一行为 T[1<=T<=100] ,组数。 每组第一行为 N[2<=N<=15] ,序列长度。 后面是一个长度为 N 的序列 A ,其中

Read More

模板题:https://nanti.jisuanke.com/t/38232 可以求出一个序列中是否存在某个子序列 基本思想 定义一个next数组,用来存储在第i位后面出现的序列中的某一个元素的出现位置。 例如字符串abcdefg[字符串下标从一开始] 可以得到next的内容为: next[0]['a'] = 1; next[1]['a'] = -1; next[2]['a'] = -1; …… next[0]['b&

Read More

题目链接:https://vjudge.net/problem/HDU-4027 主要题意:区间开方,区间求和 #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; const int N = 1e5 + 100; int n, m; int bl[N]; long long blo; long long sum

Read More

目录1 前言2 Floyd算法2.1 参数解释2.2 算法思想2.3 代码3 Dijkstra算法3.1 参数解释3.2 算法思想3.3 代码3.4 前向星版4 SPFA算法4.1 参数解释4.2 算法思想4.3 代码 前言 乍一看搜索跟这个一样都可以找出一个点到另一个点的最短距离,但是有些问题两者都可以解决,而另一些搜索就不能解决了,搜索有确定的方向一步一步走,而最短路是告诉你某两个点直接可以直接走,没有确定的方向。最短路问题,通俗的说就是就是给你n个点,m条边,然后找出某两个点之间的最短距离

Read More

目录1 定义2 Kruskal 算法2.1 伪代码2.2 完全代码3 Prim 算法3.1 伪代码3.2 完全代码 定义 连通图:任意两个顶点vi与vj都有路径相通。 强连通图:任意两个顶点vi与vj都有路径相通。 连通图:图的边具有一定的意义,每一条变都有对应着一个权。 生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点。 最小生成树:建立生成树且所花费的权最少。 PS:如果生成树中再添加一条边,则必定成环。 最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)

Read More

前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序, 并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

Read More

基本解法 \Omicron(N^2) 譬如给定 2 个序列: 1 2 3 4 5 3 2 1 4 5 试求出最长的公共子序列。 显然长度是 3 ,包含 3 4 5 三个元素(不唯一) 我们可以用 dp[i][j] 来表示第一个串的前 i 位,第二个串的前 j 位的 LCS 的长度, 那么很容易想到状态转移方程: 如果当前的 A1[i]A1[i]A1[i] 和 A2[j]A2[j]A2[j] 相同(即是有新的公共元素),那么 dp[i][j] = \max(dp[i][j], dp[i − 1][

Read More

1. 在关系数据库中,存放在数据库中的数据的逻辑结构以二维表为主。 2. ASCII 码的含义是美国信息交换标准代码。 3. 不存在一种算法,对任何一个程序及相应的输入数据,都可以判断是否会出现死循环,因而, 任何编译系统都不做死循环检验 。 4. ∧ = and丶∨ = or 丶 ¬ = 取反。

Read More

目录1 题目描述2 输入输出格式2.1 输入格式2.2 输出格式3 样例3.1 样例输入3.2 样例输出:4 题解 题目描述 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。

Read More

用于快速查找某个点在哪个集合中,常用于有关图的题中,可查看洛谷 P3367 题。 #include <cstdio> #define _for(i, n) for(int i = 0; i < n; i++) using namespace std; const int MAXN = 1e6 + 100; int m, n, o, x, y; int map[MAXN]; int find(int u) { if(map[u] != u) map[u] = find(map[u

Read More

struct nodef { string name; int score; bool operator <(const nodef &n) const { return this -> score < n.score; } }; 这几句表示建立了一个名为nodef的结构体,其成员变量有name和score,重载了运算符<,表示当一个nodef与nodef做<运算时,第二个nodef作为参数n传入,并且运算的返回值为bool型,比较依据是score变量。

Read More

目录1 序列式容器1.1 向量[vector]1.2 列表[list]1.3 双端队列[deque]2 适配器容器2.1 栈[stack]2.2 队列[queue]2.3 优先队列[priority_queue]3 关联式容器3.1 集合[set]3.2 多重集合[multiset]3.3 映射[map]3.4 多重映射[multimap] 序列式容器 向量[vector] 列表[list] 双端队列[deque] 适配器容器 栈[stack] 队列[queue] 优先队列[priority_q

Read More

目录1 BFS – 广度优先遍历1.1 程序思路1.2 实现方法 – 存储方式为点对点1.3 程序实例 – 存储方式为点对点2 DFS – 深度优先遍历2.1 实现方法 – 存储方式为点对点2.2 程序实例 – 存储方式为点对点 BFS – 广度优先遍历 一种利用队列实现的搜索算法。简单来说,其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。形象一点如下: 总的来说,就是先遍历离根节点近的,一层一层的。 程序

Read More

点对点 建立一个数组,用下标表示不同的点,用其内容表示这个点所连接的点。例如数组名为graph,然后可以用graph[0] = 1表示0点可以通向1点。 其中,如果一个点可以连向多个点,可以使用二维数组存储,例如graph[0][0] = 1和graph[0][1] = 2表示0点所连接的点有1点和2点。通常,这个二维数组的第二维不会被填满,所以,可以使用向量作为第二维,像下面一样: #include <vector> using namespace std; const int M

Read More

用于一些特殊的类进行遍历访问所用,类似于一个指针。 以下使用vector[向量]进行举例: 如何建立一个迭代器: list<int>::iterator it; 常用操作,迭代器进行遍历: for(it = l.begin(); it != l.end(); it++) 其中,l是一个list类型的变量,首先迭代器等于l的首地址然后自加到l的尾地址 PS:在大部分STL中, 尾地址是指向了一个空的元素,所以用!= 对迭代器进行访问: print(%d, *it); 这表示输出list

Read More