hunxuewangzi

分类

题解(11)

/ 注册

全部文章（共11篇）

系数题解(lucas+思维)

题目链接题目思路这个题目的关键就是答案模3 要利用这个来突破令则因为显然只有那么就可以得证则那么使用lucas求解时间复杂度代码 #include<bits/stdc++.h> #define fi first #define se second #define...

2021-02-26

0 602

动态最小生成树题解(线段树+归并排序)

题目链接题目思路看到单点修改，区间查询其实很容易想到线段树但是这个线段树有点特殊线段树的每个节点代表这个区间的最小生成树的所有边，用vector存那么每个节点最多n-1条边你每次合并使用类似归并排序就是如果暴力合并就是那么使用归并排序总的时间复杂度就是代码 #include<...

2021-02-26

0 722

组合数问题题解(虚数)

题目链接题目大意计算题目思路如果是计算显然两式相加而下面就有点神奇要类比，想到虚数第一次真想不到而则则而最终代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; c...

2021-02-24

0 623

Spy Syndrome 2 题解(dp+hash)

题目链接题目思路这个题目算是一个经典的dp 设表示以i结尾的最后一个字符串的序列是 hash预处理然后计算答案直接回溯即可复杂度代码 #include<bits/stdc++.h> #define fi first #define se second #define debug...

2021-02-23

0 629

I 九峰与分割序列题解(线段树维护dp)

题目链接题目思路首先要想到一个dp模型为右端点为i前一个子区间小于等于k的最大贡献为右端点为i前一个子区间大于k的最大贡献那么这样利用前缀和可以写出一个的dp 暴力dp #include<bits/stdc++.h> #define fi first #define se se...

2021-02-21

0 661

Train Hard, Win Easy 题解(sort)

题目链接题目大意题目意思真的有点难懂总共有个人就是每个人都会与其余个人进行两两配对每个人都有自己的两个权值若配对则每个人的权值加而有个不能配对两两的关系求每个人最后的权值题目思路其实很简单就是sort一下然后不能配对的久直接减去即可代码 #include<bits/st...

2021-02-18

0 669

Subsequences (hard version) 题解(dp求不重复子序列)

题目链接题目大意给你一个长度为的字符串要你找出个不同的子序列，使得k个不同的子序列总价值最小是多少一个子序列的价值为删去的字符长度空串也为子序列题目思路其实不难就是要明白怎么设dp方程设为前i个字符构造长度为j的不同子序列长度显然就是选和不选第i个字符的问题但是会有重复假设...

2021-02-18

0 867

Dima and Salad 题解(01背包变形)

题目链接题目大意给你n个物品，每个物品有两个值一个为a，一个为b 要你拿任意的物品使得题目思路一个显然易见的思路设为是否有然后最后复杂度为显然不行所以考虑化简把这个问题转化为每个物品重量为价值为转化为变为01背包然后由于有负数，所以把背包的初始体积平移一下即可代码 #inc...

2021-02-09

0 681

济南 Tree Constructer 题解(二分图染色+构造)

题目大意给你一颗树(n<=100) 要你给点赋权值，如果x|y= 则代表x和y有边题目思路只要没有回路的图都可以看作是一个二分图把这个想成二分图染色想成白点和黑点（白点个数<黑点个数）白点的第59位为0，以及白点的id位为0，给每个白点赋值一个不同的id，其他位白点均为1 黑...

2021-01-31

0 642

魔改森林题解(dp+容斥+组合数学)

题目链接题目大意给你一个n*m的方格图，中间有k个障碍，要你求从左下角到右上角有多少种方案mod 998244353 题目思路这个题目真是很oi......首先直接如果方格数量很多，观察障碍物很少，则可以想到容斥的思维然后再用组合数学预处理一下一定要注意要预处理到2e5 wa了我一辈...

2021-01-27

0 615