单调队列优化的多重背包 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m; void solve() { cin >> n >> m; vector<int> w(n + 1), v(n + 1), s(n + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i...

完全背包模板 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m; void solve() { cin >> n >> m; vector<int> w(n + 1), v(n + 1), dp(m + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; ...

01背包模板 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, m; void solve() { cin >> n >> m; vector<int> w(n + 1), v(n + 1), dp(m + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; ...

很讨厌的分类讨论，就是分别讨论杀死的两个怪是相邻还是不相邻，是第一个还是不是第一个 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n; void solve() { cin >> n; vector<int> num(n); for (int i = 0; i < n; i++) cin >> num[i]; int ans = 1e...

四张牌每次用一张考虑状压dp[1111][i] 代表人在第 i 位且四张牌都有的情况下的最优答案dp[1010][i] 代表人在第 i 位只有4，2号牌的情况下的最优答案不难发现在任意位置，能转移而来的情况只有最大 15 种，我们可以直接遍历所有情况，然后判断是否存在一个合法的历史情况，如果存在，那就转移这道题也是只转移合法情况的题，如果使用数组的话要初始化成-1来标记不合法情况，我这里使用map实现，只转移合法情况，就可以避免标记 #include <bits/stdc++.h> using namespace std; #define int long long const i...

观察数据范围很大只能考虑组合数了一个合法子序列其实就是分别对于每个字母，都只能出现偶数个的子序列，对应每个字母来说，其出现情况是独立的，我们可以单独计算所有字母子序列的个数，如果一个字母出现了 x 次，其合法子序列的个数就是 C(0,x)+C(2,x)+C(4,x)+C(6,x)…，我们可以直接模拟算出这些组合数，因为计算最多只会有200000次，然后把所有的情况乘起来，记得减一，因为所有字母都不存在的情况不计数 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5...

维护一个总和 sum ，如果 sum/n 向下取整大于等于 l 且 sum/n 向上取整小于等于 r ，那么代表一定有解，此时就看超出 l 和 r 的部分谁大了，答案就是大的那个，反之无解 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, l, r, a; void solve() { cin >> n >> l >> r; int sum = 0, p = 0, d ...

我们可以直接dfs这棵树，在回溯的时候判断，如果当前节点和其父亲是满足条件的且都是白色节点，那么一定可以将其染色，因为这时一定代表着当前节点 u 不存在儿子 v ，使得 u v 满足条件，不然 u 已经是红色了，这样贪心的染色一定可以染出最大答案 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, u, v, w[N], vis[N], ans = 0; vector<int> g[N]; void dfs(i...

我们假设 dp[i][j] 代表在当前位 i 之前，还有 j 个左括号的情况的数量，那么很明显，初始情况下 dp[0][0]=1 如果第 i 位是可以是一个左括号，那么代表对于所有的 dp[i-1][x] ，都可以让 dp[i][x+1] 增加其权值也就是 dp[i-1][x]，因为这个左括号会拼接在之前的所有情况下，使得这个新情况多了一个左括号 x+1如果第 i 位是可以是一个右括号，那么代表对于所有的 x 不等于0的情况 dp[i-1][x] ，都可以让 dp[i][x-1] 增加其权值也就是 dp[i-1][x]，因为这个右括号会和之前的一个左括号匹配，少了一个左括号 x-1然后我们发现...

每次操作只有三种可能将两个1变成两个0将两个1变成两个0将一个1一个0变成一个0一个1我们发现1和0的数量转换只能是2的倍数，所以如果1和0的数量都是奇数那就一定不可能，反之一定有解 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n; string s; void solve() { cin >> s; int n0 = count(s.begin(), s.end(), '0') % 2; ...

我们发现题目所描述的 a 数组就是一个set每次一定优先乘最大的那个数，所有可以用greater<int>来让set从大到小存储，然后直接遍历即可 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, x, y, a; set<int, greater<int>> st; void solve() { cin >> x >> y >> n; ...

每个连通块对答案的贡献是固定的，如果连通块内有 n 个点，那么答案就是 n*(n-1)/2 ，所以我们可以用并查集维护出所有的连通块，然后维护出初始的答案，然后枚举剩下的所有为 0 的点变成 1 以后的情况，他会连接所有的相邻的 1 的连通块 #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N = 1e5 + 5; int __t = 1, n, u, v, sum, m, f[N], w[N], vis[N]; string s;...

大水题，跑完dijk后就可以得知 1 的其他点的最短路，然后每次乘2即可，因为是来回 #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N = 1e5 + 5; int __t = 1; vector<pair<int, int>> a[N]; int dist[N]; void dijkstra(int s) { fill(dist, dist + N, INF); priority_queu...

而对于每个重量而言，能走的边是固定的，所以能不能到达 n 也是确定的，那么如果存在最终答案的重量 w ，所有大于等于 w 的重量一定也能到达 n ，而所有小于 w 的都不可能到达，所以我们可以二分然后判断一个重量能不能到达就直接跑dijk #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N = 2e5 + 5; int __t = 1, n; vector<pair<int, pair<int, int>&g...