算法解决最短路 注意要对取模 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef long double LD; typedef pair<LL, int> PII; const int N = 1e5 + 10, MOD = 998244353; const LL INF = 1e18; void solve() { int n, p, x, q, y; cin >> n >> p...

背包问题变形 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef long double LD; typedef pair<int, int> PII; const int N = 1e5 + 10, MOD = 998244353; const LL INF = 1e18; struct F { int a, b, c, d, e; }; void solve() { int n, m; cin >...

第一篇题解的C++实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef long double LD; typedef pair<int, int> PII; const int N = 1e5 + 10, MOD = 998244353; const LL INF = 1e18; void solve() { string a, b; vector<int> v1, v2; cin &gt...

孩子们别写 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef long double LD; typedef pair<int, int> PII; const int N = 60, MOD = 998244353; const int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0}; const LL INF = 1e18; int n, m, h; string...

分析 非常有教育意义的状态压缩问题 注意到每个位置的状态有三个, 可以对应 并且发现行的数量非常少只有, 因此可以考虑三进制状态压缩 定义状态表示前列并且第列的状态是的最小代价, 状态转移递推即可  三进制状态的每一位获取方法是, 下一位获取方法是   首先预处理合法状态 初始化第一列状态 当前列的最小代价从前一列转移过来  代码实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int...

区间标准解法 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 510, MOD = 998244353; const LL INF = 1e18; int n; string s; LL a[N]; void solve() { cin >> n >> s; s = ' ' + s; for (int i = 1...

没想到竟然过了 代码实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1e4 + 10, MOD = 998244353; const LL INF = 1e18; int n, m; LL v[N], w[N]; void solve() { cin >> n >> m; for (int i = 1; i...

分析 非常好的模拟 + 位运算题目 因为棋盘最大是, 如果用二进制表示状态的话最多种状态 因此用二进制表示每个位置是否是雷, 对于初始状态已经有数字的部分自然不是雷 答案应该是初始状态的子集并且每个位置的数字和周围雷的排布情况应该是一样的 因此可以写一个函数判断当前状态是否是合法的, 具体实现看代码 实现代码 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; con...

分析  定义, 的倍数的位置个数 假设分配给的倍数位置是, 那么分配给非的倍数的位置就是 那么得到等式  得到 那么答案等于  个位置里面选择个位置是的倍数的位置 里面还剩下个的倍数, 因为位置不是的倍数, 但是是的倍数, 因此整体也是的倍数 个位置任意排列 个位置任意排列   代码实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = ...

分析 非常好的构造题  这是题目的核心要求 可以做如下考虑  如果当前是, 那么直接按照顺序输出, 构成排列 如果当前是, 找到下一个的位置, 并且交换  为什么这么操作? 假设当前位置是是, 下一个位置是, 对于前交换不会影响是否构成排列, 但是交换后因为引入了, 不构成排列了 代码实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N =...

分析 定义状态表示表示从到最后一行能得到的最大价值 为什么这么定义? 因为方便对题目的条件进行判断 从起点到最后一行向右移动了, 向左移动了, 设 那么最终到达最后一行的位置是 也就是, 因此有约束条件 因此只需要初始化最后一行的状态就能计算约束条件, 不需要额外判断  for (int i = 1; i <= 2 * n - 1; ++i) { if (abs(i - n) > k) f[n][i] = -INF; }  代码实现 算法时间复杂度 #include <bits/stdc++.h> #define x first #define y second usi...

分析 因为是单行道, 不发生碰撞的条件是并且 那么只需要将车按照位置排序, 然后计算最长不下降子序列即可 因为, 需要贪心 + 二分优化计算 代码实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1e5 + 10, MOD = 998244353; int n; struct F { int x, v; bool operator&...

思路 发现只需要将所有的空段找出来, 分别计算贡献 假设对于当前空段, 长度是, 可以填的数字数量是 假设对于数字填了个, 数字填了个... 那么有  发现每个, 将其转化, 得到新的  这样就可以利用隔板法计算组合数, 要求将球的数量分为堆, 放置个隔板 方案数是 计算组合数可以用乘法逆元优化 实现代码 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const...

分析 注意到, 如果每个字符串都生成并且计算逆序对 暴力的算法时间复杂度是无法通过 必须要递推观察性质 定义为中逆序对的数量, 表示中的数量, 表示中的数量 由下面转移过来      代码实现 #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1e5 + 10, MOD = 1e9 + 7; LL f[N], z[N], o[N]; vo...