三金老师

分类

题解(25)

/ 注册

全部文章（共25篇）

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

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

每日一题思维前缀和

2020-04-20

0 524

【每日一题】华华给月月准备礼物（二分答案）

Solution二分答案模板题。先给出俺的万能二分模板： (ans为答案且注意初始化为0，其他只要改一下check函数就可以用于其他题) ll l=1,r=max,ans=0; while(l<=r){ ll mid=l+r>>1; if(check(mid)) a...

每日一题二分答案

2020-04-16

0 652

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

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

牛客算法周周练1

A.Solution因为是非递减数列，所以只移动k位是最佳的，那么对于原数列的美丽值来说移动k位所造成的变化是增加了而减少了，所以遍历大于k的部分， =，那遍历取max即可。Code #include<bits/stdc++.h> #define ll long long #defin...

2020-04-08

1 674

【每日一题】树 (dp)

Solution因为是树，所以保证任意两点都可以到达，所以可以选择从一个叶子节点作为出发点思考，表示这个叶子节点所在包含了 i 个节点的子图染了 j 种颜色的方案。考虑当前取的颜色是否和前次取的颜色一样，就是两种决策：若取的颜色相同则：若取的是新的颜色,则有种新颜色可以选择，则： ...

每日一题 DP

2020-04-06

4 1475

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

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

每日一题思维优先队列

2020-04-02

1 668

【每日一题】数学考试 (前缀和+dp)

Solution鬼鬼，鬼知道我这道题做了多少次，一直卡在83，今天才发现ans的初始值没处理好，一开始ans初始化为0一直过不去，这么多天终于过了。取区间里两段长度为k的子区间使和最大，肯定是dp。设pre[i]前i个数的长度为k的区间的最大和，那么只要遍历的时候再加上i-k的另一段k区间就可以了。...

每日一题 DP 前缀和

2020-04-02

0 684