Two matrices A and B are given. The length of A is N1 and the width is M1; the length of B is N2 and the width is M2.
Catalog: C++
How to speed up the process of exponentiation? Since we feel that dividing the power operation into n steps is too slow, we must find a way to reduce the steps and combine some parts into one step.
struct prime_t { vector pri_flg; // Prime number table pri_flg[i] indicates whether i is a prime number vector pri_tab; // The prime number table pri_tab[0~num] stores the prime numbers from 0 ~ n prime_t(lli n): pri_flg(n + 1, true) { // Reset the prime number table assuming that they are all prime numbers pri_flg[0] = pri_flg[1] = false; // Specifies that 0 and 1 are not prime numbers for (l
Question link
Minimum point coverage is also transformed into graph G = (V, E), then the problem is transformed into: Select as few points as possible in graph G so that at least one endpoint of each edge in the graph is selected. This problem is called the minimum point covering problem in bipartite graph problems. That is, use the fewest points to cover all edges. Conclusion: According to König’s theorem, it can be known that the number of points covered by the minimum point = the maximum matching maximum independent set of the bipartite graph is still transformed into the graph G = (V, E), then the problem is transformed into: Select as many points as possible in the graph G so that any two There are no edges between the points. This problem is called the maximum independent set problem in bipartite graph problems. Conclusion: The number of points in the maximum independent set = the total number of points – the maximum matching of the bipartite graph. Proof: Assumption
Question link: https://www.luogu.org/problem/T84891 Question idea: If part A conflicts with part B, and part A conflicts with part C, then part B and part C also conflict. That is to say, among part A, part B, and part C, we can only select one part. Part A, Part B, and Part C have a common feature, that is, the same value after %K. So just put all the input content into a set after %K, and finally output the size of the set. code#include #include #in
Question link: https://www.luogu.org/problem/T84893 As we all know, bisection is used to find content in monotonic sequences, and three-section is used to find content in unimodal sequences. Question code#include #include #include #include #include using namespace std; const long long INF = 0
struct segment_tree_t { lli n; vector te; vector 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
Prefix sum is a method used to quickly implement interval addition and subtraction (O(N^2)–>O(N)), which can be divided into single-dimensional and multi-dimensional. The implementation form is to use the data offline to #include the code below which is the sum of two single-dimensional prefixes. #include #include #include #include using namespace std; int a[1000016]; int b[1000016];
#include //Header file srand(2333); //Set the seed long long x = (1LL * rand() << 15) + rand(); //Get a longlong type random number. The random number range is 0~32767
Link: https://ac.nowcoder.com/acm/contest/140/J?&headNav=www Title Description 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. White Rabbit has an N*m rectangular farmland,
Question link: https://ac.nowcoder.com/acm/contest/135/I?&headNav=acm Question description Apojacsleam likes arrays. He now has an array a with n elements, and he wants to perform M operations on a[L]-a[R]: Operation 3: Add P operation to all elements in a[L]-a[R] 3: Subtract P from all the elements in a[L]-a[R] and finally ask for the sum of the elements in a[l]-a[r]. Enter the description and input a total of M+2 lines: Two numbers in the first line , n, M, meaning like "problem description" The second line of n numbers describes the array. Line XNUMX-M+XNUMX, total M lines, each line
Question link
The focus of tree-like arrays is on tree-like arrays. We all know binary trees, right? The leaf nodes represent A. Arrays A[1]~A[8]. Now transform it. Now define the top node C[] of each column. The array is as shown below C[i ] represents the sum of the weights of the leaf nodes of the subtree // Here we take the sum as an example, as shown in the figure, we can know that 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]+
When using the string class, you need to include the header file #include . And introduce using std::string; using std::wstring; or using namespace std; Now you can use string/wstring, which correspond to char and wchar_t respectively. The usage of string and wstring are the same. In the following, only string is used for introduction:
#include #include #include using namespace std; const int MAXN = 1e5 + 100; int main() { int temp; scanf("%d", &temp); getchar(); //If you want to read a string after reading a non-string, Enter first string str; str.resize(MAXN); //Need to open first
The general meaning of the question portal is that Alice and Bob are playing a game. Alice is the first mover and Bob is the second mover. A sequence of numbers is given. Alice and Bob can take out a number from it each round. When the sequence becomes a non-decreasing sequence, the previous round The first line of the player's winning input is T[1<=T<=100], the number of groups. The first line of each group is N[2<=N<=15], the sequence length. Followed by a sequence A of length N, where [1<=Ai<=N]. Example 2 3 1 3 2 5 5 3 2 1 4 Output the answer corresponding to each group and the winning player. SampleAli
Template question: https://nanti.jisuanke.com/t/38232 You can find out whether there is a certain subsequence in a sequence. The basic idea is to define a next array to store an element in the sequence that appears after the i-th position. location of occurrence. For example, the string abcdefg[string subscript starts from one] can get the content of next: next[0]['a'] = 1; next[1]['a'] = -1; next[2][ 'a'] = -1; …… next[0]['b&
Question link: https://vjudge.net/problem/HDU-4027 Main question meaning: interval square root, interval summation #include #include #include #include using namespace std; const int N = 1e5 + 100; int n, m; int bl[N]; long long blo; long long sum
Dijkstra [CF 20C – Template] \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 aw > bw; } }; lli dis[maxn];
Preface At first glance, it seems that search can find the shortest distance from one point to another like this one. However, some problems can be solved by both, while other searches cannot. Search has a certain direction to go step by step, and The shortest path tells you that you can walk directly from two points without a definite direction. The shortest path problem, in layman's terms, is to give you n points and m edges, and then find the shortest distance between two points. There are three algorithms commonly used to solve the shortest path: Floyd, Dijkstra, and SPFA. Each of the three methods has its own advantages and disadvantages. Floyd's algorithm is a multi-source shortest path algorithm with the highest complexity (n^3). It is usually used in problems with relatively few points and unfixed starting points. It can solve negative edges (negative weights) but cannot solve negative loops. Dij
Define a connected graph: any two vertices vi and vj are connected by a path. Strongly connected graph: any two vertices vi and vj are connected by paths. Connected graph: The edges of the graph have a certain meaning, and each change has a corresponding weight. Spanning tree: The spanning tree of a connected graph refers to a connected subgraph, which contains all n vertices in the graph. Minimum spanning tree: Establish a spanning tree with the least amount of weight. PS: If another edge is added to the spanning tree, it will definitely form a loop. The minimum spanning tree can be found using Kruskal's algorithm or Prim's algorithm. Greedy Algorithm: Each step requires the best edge with the smallest weight. Required constraints: Smart use of edges in the graph. Intelligence uses up exactly |v|-1 items
Forward star is a special edge set array. We sort each edge in the edge set array according to the starting point from small to large. If the starting points are the same, sort them according to the end point from small to large, and record the edges starting from a certain point. The starting position and storage length of all edges in the array, then the forward star is constructed.
Basic solution\Omicron(N^2) For example, given 2 sequences: 1 2 3 4 5 3 2 1 4 5, try to find the longest common subsequence. Obviously the length is 3 and contains three elements 3 4 5 (not unique). We can use dp[i][j] to represent the length of the LCS of the first i digits of the first string and the first j digits of the second string. Then it is easy to think of the state transition equation: If the current A1[i]A1[i]A1[i] and A2[j]A2[j]A2[j] are the same (that is, there are new common elements), then dp[ i][j] = \max(dp[i][j], dp[i − 1][
The time complexity of the search operation in the ordered sequence can be optimized to log N level array. Obtain the starting subscript [start] and the ending subscript [end] of the search part for T and the number to be searched [x]. Calculate the intermediate bisection point Subscript [mid], which is the average of start and end
Basic solution [O(N^2)] T is the input sequence, and F is the length of the longest ascending subsequence ending with the i-th number. It can be obtained that F[i] is equal to F[0...i – 1], which satisfies T. [i] > T[0…i – 1] For example, the sequence T = {1, 5, 6, 4, 2, 9} corresponds to F = {1, 2, 3, 2, 2, 4} F The largest number in the sequence is the longest ascending subsequence
1. In a relational database, the logical structure of the data stored in the database is mainly two-dimensional tables. 2. The meaning of ASCII code is American Standard Code for Information Interchange. 3. There is no algorithm that can determine whether an infinite loop will occur for any program and corresponding input data. Therefore, any compilation system does not perform infinite loop testing. 4. ∧ = and丶∨ = or 丶¬ = negation.
Title description: Chenchen is a talented child. His dream is to become the greatest doctor in the world. To this end, he wanted to become a disciple of the most prestigious doctor nearby. In order to judge his qualifications, the doctor gave him a difficult problem. The doctor took him to a cave full of medicinal herbs and said to him: "My child, there are some different herbs in this cave. It takes some time to collect each one, and each one has its own value. I will give You have a period of time, during which time you can collect some herbs. If you are a smart child, you should be able to maximize the total value of the herbs you collect." If you are Chenchen, you can complete this task ? Input and output format The first line of the input format contains 22 integers T (1 \le T \le 100
It is used to quickly find which set a certain point is in. It is often used in questions about graphs. You can check Luogu P3367 question. #include #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; } }; These sentences indicate that a structure named nodef is created, and its member variables are: Name and score are overloaded with the operator <, which means that when a nodef and nodef are used for < operation, the second nodef is passed in as parameter n, and the return value of the operation is bool type, and the comparison basis is the score variable.
BFS – 广度优先遍历 一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。形象一点如下： 总的来说，就是先遍历离根节点近的，一层一层的。 程序思路 函数传入需要遍历的树/图的根节点，然后将根节点放入队列，开始循环操作，只要队不是空的，就取队首并且将队首元素所连接的点放入队中。 要注意的是，图中可能出现环，可能会陷入死循环，所以要定义一个数组记录节点是否被访问过。 实现方法 – 存储方式为点对点 广度优先遍历，参数v是开始遍历的点
Create an array point-to-point, using subscripts to represent different points, and using its content to represent the points connected to this point. For example, if the array is named graph, then graph[0] = 1 can be used to indicate that point 0 can lead to point 1. Among them, if a point can be connected to multiple points, it can be stored in a two-dimensional array. For example, graph[0][0] = 1 and graph[0][1] = 2 means that the point connected to point 0 has 1 point and 2:XNUMX. Normally, the second dimension of this two-dimensional array will not be filled, so you can use a vector as the second dimension, like this: #include using namespace std; const int M
Used for traversal access by some special classes, similar to a pointer. The following uses vector[vector] as an example: How to create an iterator: list ::iterator it; Commonly used operations, iterator traversal: for(it = l.begin(); it != l.end(); it++) Among them, l is a list type variable, first the iterator is equal to l The first address is then added to the tail address of l PS: In most STL, the tail address points to an empty element, so use! = Access the iterator: print(%d, *it); This means outputting the list
Here, post your notes about C++ to share with everyone.