分类： Computer

源文件头部注释 列出：版权、作者、编写日期和描述。 每行不要超过80个字符的宽度。 示例： /************************************************* Copyright:Call_Me_Why Author:why Date:2010-08-25 Description:Something about C++ **************************************************/ 函数头部注释 列出：函数的目的/功能、输

题目链接

题目链接

题目链接 #include <cstdio> #include <cstring> #include <queue> #include <cmath> using namespace std; const int MAXN = 1e5 + 100; const int MAXM = MAXN << 2; struct node { int u, v, nxt; } edge[MAXM]; int head[MAXN]; int tot,

给出两个矩阵A和B。 A的长是N1，宽是M1；B的 长是N2，宽是M2。

该怎样去加速幂运算的过程呢？既然我们觉得将幂运算分为n步进行太慢，那我们就要想办法减少步骤，把其中的某一部分合成一步来进行。

struct prime_t { vector<bool> pri_flg; // 素数表 pri_flg[i] 表示 i 是否为素数 vector<lli> pri_tab; // 素数表 pri_tab[0~num] 保存着 0 ~ n 中的素数 prime_t(lli n) : pri_flg(n + 1, true) { // 重置素数表 假设都是素数 pri_flg[0] = pri_flg[1] = false; // 规定 0 和 1 不是素数 for (l

题目链接

最小点覆盖 同样的转化为图G=(V,E)，则问题转化为： 在图G中选取尽可能少的点，使得图中每一条边至少有一个端点被选中。 这个问题在二分图问题中被称为最小点覆盖问题。即用最少的点去覆盖所有的边。 结论：由König定理可知最小点覆盖的点数 = 二分图最大匹配 最大独立集 依旧转化为图G=(V,E)，则问题转化为： 在图G中选取尽可能多的点，使得任意两个点之间没有连边。 这个问题在二分图问题中被称为最大独立集问题。 结论：最大独立集的点数 = 总点数 – 二分图最大匹配 证明： 假设

题目链接：https://www.luogu.org/problem/T84891 题目 思路 如果零件A与零件B冲突，且零件A与零件C冲突，那么零件B与零件C也是冲突的。 也就是说在零件A、零件B、零件C中，我们只能选出其中一个零件。 而零件A 、零件B、零件C有一个共同的特征，那就是%K后为同一值。 所以只要把所有输入内容%K后塞入一个set，最后输出这个set的大小就可以了。 代码 #include <cstdio> #include <algorithm> #in

题目链接：https://www.luogu.org/problem/T84893 众所众知，二分用来查找单调序列中的内容，三分用来查找单峰序列中的内容。 题目 代码 #include <cstdio> #include <utility> #include <iostream> #include <vector> #include <cmath> using namespace std; const long long INF = 0

struct segment_tree_t { lli n; vector<lli> te; vector<lli> lz; segment_tree_t(lli n) : n(n), te(n << 2, 0), lz(n << 2, 0) { } lli ls(lli x) { return x << 1; } lli rs(lli x) { return x << 1 | 1; } void push_up(lli r

前缀和是用来快速实现区间加减的方法（O（N^2)–>O(N)），可分为单维和多维。其实现形式是通过数据离线将下面是两个单维前缀和的代码 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int a[1000016]; int b[1000016];

#include <cstdlib> //头文件 srand(2333); //设置种子 long long x = (1LL * rand() << 15) + rand(); //取longlong类型的随机数 随机数范围是0~32767

链接：https://ac.nowcoder.com/acm/contest/140/J?&headNav=www 题目描述 White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row belongs the a[i][j]-th type. 白兔有一个N*m的长方形农田，

题目链接：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，意义如“题目描述” 第二行n个数，描述数组。 第3-M+2行，共M行，每行

题目链接

树状数组 重点是在树状的数组 大家都知道二叉树吧 叶子结点代表 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]+

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

#include <cstdio> #include <string> #include <cstring> using namespace std; const int MAXN = 1e5 + 100; int main() { int temp; scanf("%d", &temp); getchar(); //如果在读入非字符串后要读入字符串，先吃回车 string str; str.resize(MAXN); //需要先开

题目传送门 大体题意 Alice 和 Bob 在玩一个游戏，Alice是先手，Bob是后手 给出一个数字序列，Alice和Bob每回合可以从中取出一个数 当序列变为不下降序列时，上一回合的玩家获胜 输入 第一行为 T[1<=T<=100] ，组数。 每组第一行为 N[2<=N<=15] ，序列长度。 后面是一个长度为 N 的序列 A ，其中 [1<=Ai<=N]。 样例 2 3 1 3 2 5 5 3 2 1 4 输出 对应每组的答案，获胜玩家。 样例 Ali

模板题：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&

题目链接：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

Dijkstra [ CF 20C – 模板 ] \Omicron(V \log V + E) struct disn_t { lli v; lli w; disn_t() { } disn_t(lli iv, lli iw) : v(iv), w(iw) { } friend bool operator <(const disn_t& a, const disn_t& b) { return a.w > b.w; } }; lli dis[maxn];

前言 乍一看搜索跟这个一样都可以找出一个点到另一个点的最短距离，但是有些问题两者都可以解决，而另一些搜索就不能解决了，搜索有确定的方向一步一步走，而最短路是告诉你某两个点直接可以直接走，没有确定的方向。最短路问题，通俗的说就是就是给你n个点，m条边，然后找出某两个点之间的最短距离。解决最短路常用的有三种算法Floyd、Dijkstra、SPFA。三种方法各有优劣 Floyd算法是多源最短路算法，复杂度最高（n^3），通常用在点比较少的起点不固定的问题中。能解决负边（负权）但不能解决负环。 Dij

定义 连通图：任意两个顶点vi与vj都有路径相通。 强连通图：任意两个顶点vi与vj都有路径相通。 连通图：图的边具有一定的意义，每一条变都有对应着一个权。 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点。 最小生成树：建立生成树且所花费的权最少。 PS：如果生成树中再添加一条边，则必定成环。 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。 贪心算法： 每一步都要最好的，权重最小的边。 需要的约束： 智能用图里有的边。 智能正好用掉|v|-1条

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

基本解法 \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][

可以将有序数列中的查找操作的时间复杂度优化到log N级别 数列为T获取查找部分的开头下标[start]和结束下标[end]以及要查找的数[x] 计算中间平分点下标[mid],即start和end的平均数

基础解法[O(N^2)] T为输入的序列,F为以第i个数结尾的最长上升子序列长度 可得到F[i]等于F[0 …… i – 1]中满足T[i] > T[0 …… i – 1]的数 例如序列T = {1, 5, 6, 4, 2, 9} 对应的F = {1, 2, 3, 2, 2, 4} F序列中最大的数即为最长上升子序列

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

题目描述 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入输出格式 输入格式 第一行有22个整数T(1 \le T \le 100

用于快速查找某个点在哪个集合中，常用于有关图的题中，可查看洛谷 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

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变量。

序列式容器 向量[vector] 列表[list] 双端队列[deque] 适配器容器 栈[stack] 队列[queue] 优先队列[priority_queue] 关联式容器 集合[set] 多重集合[multiset] 映射[map] 多重映射[multimap] 完整XLSX文件传送门

BFS – 广度优先遍历 一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。形象一点如下： 总的来说，就是先遍历离根节点近的，一层一层的。 程序思路 函数传入需要遍历的树/图的根节点，然后将根节点放入队列，开始循环操作，只要队不是空的，就取队首并且将队首元素所连接的点放入队中。 要注意的是，图中可能出现环，可能会陷入死循环，所以要定义一个数组记录节点是否被访问过。 实现方法 – 存储方式为点对点 广度优先遍历，参数v是开始遍历的点