Mag1c0nch

分类

/ 注册

全部文章（共48篇）

题解 | #【模板】区间dp#

区间dp模板 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 705; int __t = 1, n, a[N], sum[N], dp[N][N]; void solve...

2024-11-30

1 40

题解 | #【模板】多重背包#

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

2024-11-30

2 34

题解 | #【模板】完全背包#

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

2024-11-30

1 32

题解 | #【模板】01背包#

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 >...

2024-11-30

1 34

题解 | #小红的小踏前斩#

很讨厌的分类讨论，就是分别讨论杀死的两个怪是相邻还是不相邻，是第一个还是不是第一个 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1...

2024-11-29

4 56

题解 | #小美和大富翁#

四张牌每次用一张考虑状压dp[1111][i] 代表人在第 i 位且四张牌都有的情况下的最优答案dp[1010][i] 代表人在第 i 位只有4，2号牌的情况下的最优答案不难发现在任意位置，能转移而来的情况只有最大 15 种，我们可以直接遍历所有情况，然后判断是否存在一个合法的历史情况，如果存在，那...

2024-11-28

1 39

题解 | #小红的好子序列#

观察数据范围很大只能考虑组合数了一个合法子序列其实就是分别对于每个字母，都只能出现偶数个的子序列，对应每个字母来说，其出现情况是独立的，我们可以单独计算所有字母子序列的个数，如果一个字母出现了 x 次，其合法子序列的个数就是 C(0,x)+C(2,x)+C(4,x)+C(6,x)…，我们可以直接模拟...

2024-11-28

2 32

题解 | #游游的元素修改#

维护一个总和 sum ，如果 sum/n 向下取整大于等于 l 且 sum/n 向上取整小于等于 r ，那么代表一定有解，此时就看超出 l 和 r 的部分谁大了，答案就是大的那个，反之无解 #include <bits/stdc++.h> using namespace std; #de...

2024-11-28

2 33

题解 | #小美的树上染色#

我们可以直接dfs这棵树，在回溯的时候判断，如果当前节点和其父亲是满足条件的且都是白色节点，那么一定可以将其染色，因为这时一定代表着当前节点 u 不存在儿子 v ，使得 u v 满足条件，不然 u 已经是红色了，这样贪心的染色一定可以染出最大答案 #include <bits/stdc++.h...

2024-11-28

2 31

题解 | #合法的括号序列#

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

2024-11-28

3 57