Mag1c0nch

分类

/ 注册

全部文章（共63篇）

题解 | #小美和大富翁#

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

2024-11-28

2 70

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

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

2024-11-28

2 39

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

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

2024-11-28

2 42

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

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

2024-11-28

2 44

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

我们假设 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 86

题解 | #小红的01串#

每次操作只有三种可能将两个1变成两个0将两个1变成两个0将一个1一个0变成一个0一个1我们发现1和0的数量转换只能是2的倍数，所以如果1和0的数量都是奇数那就一定不可能，反之一定有解 #include <bits/stdc++.h> using namespace std; #defin...

2024-11-28

1 47

题解 | #小欧的选数乘积#

我们发现题目所描述的 a 数组就是一个set每次一定优先乘最大的那个数，所有可以用greater<int>来让set从大到小存储，然后直接遍历即可 #include <bits/stdc++.h> using namespace std; #define int long l...

2024-11-28

1 48

题解 | #小欧皇#

每个连通块对答案的贡献是固定的，如果连通块内有 n 个点，那么答案就是 n*(n-1)/2 ，所以我们可以用并查集维护出所有的连通块，然后维护出初始的答案，然后枚举剩下的所有为 0 的点变成 1 以后的情况，他会连接所有的相邻的 1 的连通块 #include <bits/stdc++.h&g...

2024-11-28

1 47

题解 | #小红送外卖#

大水题，跑完dijk后就可以得知 1 的其他点的最短路，然后每次乘2即可，因为是来回 #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N...

2024-11-28

1 57

题解 | #游游出游#

而对于每个重量而言，能走的边是固定的，所以能不能到达 n 也是确定的，那么如果存在最终答案的重量 w ，所有大于等于 w 的重量一定也能到达 n ，而所有小于 w 的都不可能到达，所以我们可以二分然后判断一个重量能不能到达就直接跑dijk #include <bits/stdc++.h>...

2024-11-28

1 48