阿日哥的向量空间

在做算法题时，我们常常需要用到一个能够表示“无穷大”的值INF，最容易想到的，我们可以把INF设为0x7fffffff，因为这是32位int的最大值。如果这个无穷大只用于一般的比较（比如求最小值时min变量的初值），那么0x7fffffff确实是一个完美的选择。但是更多情况下，0x7fffffff并不是一个最好的选择，比如在Dijkstra算法中，我们使用松弛操作： if (dist[u] + weight[u][v] < dist[v]) dist[v] = dist[u] + weight[u][v]; 如果u和v之间没有边，那么weight[u]=INF，如果此时将INF取作0x7fffffff，那么dist[u] + weight[u][v]就会向上溢出而变成负数，我们的松弛操作便出错了！ 准确来说，0x7fffffff在作为32位整数的情况下不能满足无穷大加无穷大依然是无穷大这个条件，一旦溢出就变成了一个很小的负数。 可以考虑这样一个取值INF=0x3f3f3f3f，0x3f3f3f3f的十进制是1061109567，是109级别的（和0x7fffffff一个数 ...

原题链接：https://www.acwing.com/problem/content/803/ 思路： 采用lowbit()函数 采用位运算 #include <iostream>int bitCount(unsigned int n) { n = ((n & 0xAAAAAAAA) >> 1) + (n & ~0xAAAAAAAA); n = ((n & 0xCCCCCCCC) >> 2) + (n & ~0xCCCCCCCC); n = ((n & 0xF0F0F0F0) >> 4) + (n & ~0xF0F0F0F0); n = ((n & 0xFF00FF00) >> 8) + (n & ~0xFF00FF00); n = ((n & 0xFFFF0000) >> 16) + (n & ~0xFFFF0000); return n;}int count(int n) { int ...

原题链接：https://www.acwing.com/activity/content/problem/content/2981/ 思路：基础的双指针算法。 #include <iostream>#define N 100005int a[N], b[N];int n, m;int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < m; ++i) scanf("%d", &b[i]); int i = 0, j = 0; while (j < m && i < n) { if (a[i] == b[j]) i++; j++; } printf("%s", (i == n ? "Yes" : "No")); return 0;}

原题链接：https://www.acwing.com/problem/content/submission/code_detail/22373905/ 两种思路： ，因此可以采用二分查找的思路，时间复杂度。 由于所给数组已经有序，可以采用矩阵搜索的思路。等价于在一个矩阵中寻找目标值，其中满足沿轴方向和轴方向都是递增的。这种方法时间复杂度为。 #include <iostream>#include <algorithm>int n, m, x; int bin_search(int b[], int left, int right, int target) { int i = left, j = right, mid; while (i < j) { mid = (i + j) >> 1; if (b[mid] > target) j = mid; else if (b[mid] < target) i = mid + 1; else return mid; ...

原题链接：https://www.acwing.com/problem/content/description/801/ 思路： 用一个pos[]数组来存储某个数上次出现的位置 双指针i和j，表示当前最长不重复区间[i,j)。每当将要把nums[j]纳入区间时，考察nums[j]上次出现的位置。 若在i的左侧，则可以直接把nums[j]纳入最长不重复区间。 否则，将i移动到nums[j]上次出现位置的右侧。 #include <iostream>#include <cstring>#define N 100005int nums[N];// 记录一个数上次出现的位置int pos[N];int n;// 区间[i, j)，j表示下一个将要纳入区间的数的下标int longest_repeat() { int i = 0, j = 1, max = 0; while (j <= n) { if (j - i > max) max = j -i; if (j == n) break; if ...

原题链接：https://www.acwing.com/problem/content/800/ 参考之前的构造一维矩阵的思路（差分是前缀和的逆运算），假设数组是的前缀和矩阵，有以下等式成立： 将除了矩阵以外的所有项移到左边，就可以得到根据前缀和矩阵求出差分矩阵的等式： 构造出差分矩阵后，就可以根据一维差分的思想，来修改二维差分矩阵了。这个过程本质上用的也还是容斥原理。 #include<iostream>#define N 1005int a[N][N];int b[N][N];int n, m, q;// 构建二维差分矩阵，本质是前缀和的逆运算void build() { // a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i-1][j-1] // b[i-1][j-1] = a[i][j] - a[i][j-1] - a[i-1][j] + a[i-1][j-1] for (int i = 1; i <= n; i++) { for (int j = 1; j <= ...

原题链接：https://www.acwing.com/problem/content/description/799/ 所谓的差分，是对于一个数组，定义一个数组，使得是的前缀和数组。即： 为了满足这个条件，我们可以构造这样一个数组： 所以差分又是前缀和的逆运算。通过差分数组，我们可以方便地为中的任意一段区间加上或者减去一个数，其时间复杂度为。 #include <iostream>#define N 100005int a[N], b[N];int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 构造差分数组 // b[0] = a[1] // b[1] + b[0] = a[2] // b[2] + b[1] + b[0] = a[3]; // ... // b[i] = a[i+1] - a[i], b[0] ...

原题链接：https://www.acwing.com/activity/content/problem/content/830/ 与前缀和大致相似，我们定义子矩阵数组preSum[]中，表示所有位于左下角的元素之和。如表示原数组中坐标和的元素和。 sub_matrix 于是，可以得出以下等式： 因此，代码如下： #include <iostream>#define N 1005#define M 1005#define Q 200005int preSum[N][M];int nums[N][M];int ans[Q];int n, m, q;void build() { preSum[0][0] = 0; for (int i = 1; i < n; ++i) preSum[i][0] = 0; for (int i = 1; i < m; ++i) preSum[0][i] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++ ...

原题链接：https://www.acwing.com/problem/content/797/ 简单题，只需注意区间的定义，是左闭右开的即可。 #include <iostream>#define N 100005int preSum[N]; // 前缀和数组int ans[N];int main() { int n, m; preSum[0] = 0; scanf("%d %d", &n, &m); int tmp; // 构造前缀和数组 // preSum[i]表示[0, i)的和。如preSum[1]表示[0, 1)的和，即presum[1] = nums[0]。 for (int i = 0; i < n; ++i) { scanf("%d", &tmp); preSum[i + 1] += preSum[i] + tmp; } int l, r; // 查询[l-1, r)的和，等于[0, r) - [0, l-1)。 for (int ...

原题链接：https://www.acwing.com/problem/content/796/ 模拟手工除法，从高位往低位依次除。也正因为从高位往低位除，因此最后去除前导0的时候要首先将结果向量reverse一次。 #include <iostream>#include <algorithm>using namespace std;vector<int> div(vector<int>& A, int B, int& r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ) { r = r * 10 + A[i]; C.push_back(r / B); r %= B; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_ ...