三金老师

题解

/ 注册

全部文章 / 题解（共9篇）

【每日一题】Removal (dp+思维 / 子序列计数)

Solution题意：给出n个元素，每个元素不大于k，求删除m个元素后的子序列个数。子序列问题，通常可以联想到dp来做，考虑维护前 i 个元素删除 j 个元素的方案数，考虑第 i 个元素删或者不删，即有：但是这样计算的话肯定会有重复的方案，拿样例2来说：4 2 21 2 1 2删除第一...

每日一题思维 DP

2020-04-24

0 681

【每日一题】边的染色（dfs+思维 / 联通块+xor）

Solution题意：给定一个无向图，有一些边已经染色，求让你染色剩下的边使得每个环的异或和都为0的方案数。好难想!好难想!好难想!重要的事情要说三遍! 1.思维点：题解很巧妙，把对边染色转移到对点染色，取边为两个端点的xor，这样的话每个环的异或和肯定为0，因为每个点都xor了两次~ 2.答案的...

dfs 联通块每日一题思维

2020-04-24

0 738

【每日一题】K-th Number（二分 / 区间问题）

Solution题意：B的元素取对于A的每个长度大于k的子区间取第k大元素，求B的第m大元素。知识点：二分首先由于数据过大，枚举区间肯定不行，在题解中有一句话非常好：考虑把求值变成验证。求第m大元素，即判断第k大元素比m大的区间数是否>=m。想到二分，但是不会计算区间数就很尴尬，还是很佩...

每日一题二分答案思维区间问题

2020-04-22

1 830

【每日一题】糖糖别胡说，我真的不是签到题目（思维+枚举+前缀和）

Solution 知识点：枚举/暴力+前缀和+思维因为只要在队列后面出现能力值大于自己的能力值且与自己不是同一个阵营的自己就会去世，加上前 i-1 秒发功增加的能力值不会影响第 i 秒，所以可以考虑一下倒着遍历 n 秒，边枚举边更新最后面的最大值，这样的话复杂度最坏情况是，考虑用前缀和优化把能力值...

每日一题思维前缀和

2020-04-20

0 524

【每日一题】逆序对（思维）

Solution取任意两点，一者为0，一者为1，其他任意排列，则：由于取模，所以有两种选择：1.逆元2.预处理由于组合数比较小，所以选择了预处理。Code #include<bits/stdc++.h> #define mp make_pair #define pb push_back...

每日一题思维

2020-04-16

0 536

【每日一题】Treepath(树形dp)

Solution记得寒假牛客有道题就是这道题的扩展，好像是求路径数目+博弈论。表示以 i 为根的子树到 i 的距离为偶数/奇数的数目。那么在dfs过程中，以 u 为根且子结点为 v 对答案的贡献是: (子结点与父节点距离相差1，所以应操作不同奇偶性)当然遍历完也需要把 v 的路径数合并到 u里...

每日一题树形DP 思维

2020-04-15

0 736

【每日一题】Xorto (前缀和优化枚举)

Solution前缀和优化，用维护的区间异或和，那么的区间异或和即。那么遍历 i ，枚举 i 作为右端点统计区间异或和，再枚举 i+1 为左端点统计答案。关键点在于左边区间统计，右边区间更新而不统计，保证区间不重叠。 Code #include<bits/stdc++.h> #defin...

每日一题思维前缀和

2020-04-15

0 567

【每日一题】黑白树（思维+dfs）

Solutionemm昨天看了但是没有写出来，因为不会处理回溯过程中的更有利涂黑的情况。题解很巧妙，没想到可以用另外一个数组d来记录可以最多涂黑到哪个点，当数组d为0时就代表需要多操作一次，而这个更新操作次数正是这道题的灵魂所在。简单来说就是：更新回溯过程中最远可到达的距离更新回溯过程中...

dfs 每日一题思维

2020-04-08

0 614

【每日一题】tokitsukaze and Soldier (优先队列+思维)

Solution很奇妙的思路，看了第一篇题解才懂，先用结构体存每个士兵，然后按团数排序，再用优先队列存战力，用一个遍历cnt由n遍历到0，保证遍历保证每种可能都枚举到。注意在枚举时，如果队列里的元素超过当前限制，出队并减去这个元素对sum的贡献。 Code #include<bits/stdc...

每日一题思维优先队列

2020-04-02

1 668