从蓉的博客

原题链接 重要的是思路，实现起来非常简单… 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;int n, res;int main() { priority_queue<int, vector<int>, greater<int>> p; scanf("%d", &n); while(n--) { int a; scanf("%d", &a); p.push(a); } while(p.size() > 1) { int a = p.top(); p.pop(); int b = p.top(); p.pop(); res += (a + b); p.push(a+b); ...

原题链接 解题思路 将所有区间按左端点从小到大排序 从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间，然后将start更新为右端点的最大值。 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>using namespace std;const int N = 100001;int n, s, t, res;vector<pair<int,int>> v;#define MIN_INF -2e9int main() { scanf("%d%d%d", &s, &t, &n); int r = MIN_INF, l = MIN_INF; for(int i = 0; i < n; ++i) { int a, b; scanf("%d%d", &a, ...

原题链接 思路描述将所有区间根据区间的右端点进行排序，首先，记录最开始右端点的区间值，遍历后面的区间。如果后面区间的左端点大于等于该值，那么说明可以使用一个点来表示。如果无法表示，那么就说明需要增加一个点来使其再区间的内部。 算法证明设该算法得到的点数为res，正确答案为ans，下面证明$res == ans$。 证明$res \geq ans$ 由于该算法肯定是正确的，而ans又是最小值，因此该不等式肯定成立。 证明$res\leq ans$ ​ 在上述算法中，每次新记录一个右端点值的所有区间，实际上就是没有任意交集的区间，它们的个数正好是res。根据题目要求的描述，如果有res个没有交集的区间，那么至少就有res个点，因此有$res\leq ans$ 代码实现1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;vector<pair<int,int>> v;int n, res, r;int main() &# ...

原题链接 12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;const int R = 301, C = 301;int r, c, res;int m[R][C], step[R][C];int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int search(int x, int y) { if(step[x][y] != -1) return step[x][y]; step[x][y] = 1; for(int i = 0; i < 4; ++i) { int xx = x + dx[i], yy = y + dy[i]; if(xx >= 1 && xx <= r && yy >= ...

原题链接 对于每一个节点来说，只有两种情况，就是出席此次宴会和不出席此次宴会，因此储存节点状态可以使用u[N][2]来实现。这样，对于每个节点来说，两种情况分别如下： 若该节点选择不参加宴会，那么他的所有子节点可以参加也可以不参加，因此有$u[root][0]=\sum \max{u[s_i][0],u[s_i][1]}$ 若该节点参加宴会，那么他所有的子节点必须不参加，因此有$u[root][1]=\sum u[s_i][0]+happy[root]$ 实现代码如下： 123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;const int N = 6001;int happy[N], u[N][2];int h[N], idx, ne[N], e[N];int n;bool has_father[N];void add(int k, int l) { ...

题目链接 状态表示：f[i][j]i为储存的状态，j为当前从0=>j最后经过的一个点的值，f[i][j]的值为经过的路径总长度。 那么对于$k\in [1…n]$，有$$f[i,j]=\min{f[i-1<<k, j-{k}]+distance(k\rightarrow j)}$$ 1234567891011121314151617181920212223242526#include <bits/stdc++.h>using namespace std;const int N = 20, M = 1 << N;int f[M][N];int m[N][N];int n;int main() { scanf("%d", &n); int _m = 1 << n; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", &m[i][ ...

区间dp经典题 题目描述 AC代码： 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;const int N = 1e9+7;// f[i,j]表示为数字j，用小于等于i的数字的划分方法数// 那么有递推表达式： f[i,j] = f[i-1,j] + f[i-1,j-i] + f[i-1,j-2i]+f[i-1,j-3i]+...// f[i,j-i] = f[i-1,j-i]+f[i-1,j-2i]+f[i-1,j-3i]+f[i-1,j-4i]+...// f[i,j] = f[i-1,j] + f[i,j-i]long long int f[1001][1001];int n;int main() { scanf("%d", &n); for (int i = 0; i <= n; i ++) { f ...

原题链接 题目描述给定$n$个长度不超过10的字符串以及$m$次询问，每次询问会给定一个操作次数上限。求每次询问小于等于操作次数上限，能够让给定的字符串变为询问字符串的个数。 一次操作意味着修改一个字符，删除一个字符，以及加入一个字符。 直接暴力求解即可，时间复杂度为$O(mnL^2)$。 题解： 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>using namespace std;int n, m, limit;const int N = 1010;char s[N][13];char tmp[13];int f[N][N];int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%s", &s[i][1]); while(m--) { scanf(&q ...

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有： 删除–将字符串A中的某个字符删除。 插入–在字符串A的某个位置插入某个字符。 替换–将字符串A中的某个字符替换为另一个字符。 现在请你求出，将A变为B至少需要进行多少次操作。 考虑这个问题时，我们可以想此问题：当字符串A中的第$i$个字符和字符串B的第$j$个字符对应时，执行的操作是多少呢？这样就需要一个二维数组去保存之前的所有状态。并且状态转移方程也很好想到： 当A[i]=B[j]时，f[i][j]=f[i-1][j-1]。 当A[i]!=B[j]时，综合考虑三种操作：f[i][j]=min(f[i-1][j],f[i-1][j-1],f[i][j-1])+1 分别对应删除、替换和插入操作。 具体实现代码如下： 12345678910111213141516171819202122#include <bits/stdc++.h>using namespace std;char s1[1001], s2[1001];int n, m;int f[1001][1001];int main() { ...

题目链接 由于求的是某个区间，而且是矩形区间的和，所以想到用二维前缀数组求解。 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;int n, L, r, t;int m[601][601];int a[601][601];int main() { scanf("%d%d%d%d", &n, &L, &r, &t); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) scanf("%d", &m[i][j]); } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { a[ ...