三金老师
三金老师
全部文章
分类
题解(25)
归档
标签
去牛客网
登录
/
注册
**者的茶会
很懒
全部文章
(共23篇)
【每日一题】 图的遍历 (dfs / 染色+判奇环)
Solution题意:无向图有n个点,从点1开始遍历,每次走两步,遍历整个图。问最少加几条边,可以完整的遍历整个图。 思路:首先可以想到的是如果图不连通,那么答案至少需要 (联通块的数目-1) 来把各个联通块连起来。而走两步的话,不难联想到奇偶形,考虑奇环的话两步可以到达环内任意一点,所以只要连通后...
dfs
联通块
每日一题
2020-05-21
0
909
【每日一题】 过河 (dp / 数据压缩)
Solution题意:题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。范围:st 属于[1,10], 石头数量<=100, L<=1e9思路:很明显的dp题,dp[i]维护到达 i 点的最少步数: 但是要考虑到木板的...
每日一题
DP
2020-05-13
0
817
【每日一题】「火」皇家烈焰 (dp / 递推)
Solution题意: 0:这个格子没有烈焰,且其左右两个格子均没有烈焰 1:这个格子没有烈焰,且其左右两个格子中只有一个烈焰 2:这个格子没有烈焰,且其左右两个格子中均有烈焰 *:这个格子有烈焰 ?:未告诉你本格情况 求满足条件的方案数。 思路: 考虑用 表示第 i 个字符 是/不是 火焰 以...
每日一题
DP
2020-05-10
0
666
【每日一题】合并回文子串 (dp / 字符串 回文)
Solution安利一下我的线性dp博客:https://blog.csdn.net/JiangHxin/article/details/105184169一般情况下,动态规划的解题步骤是:第一步:根据原问题和子问题来确定状态(dp数组表示什么东西)第二步:根据状态确定状态转移方程(怎样求解dp数组...
回文
每日一题
字符串
DP
2020-05-05
1
832
【每日一题】换个角度思考 (树状数组+离线 / 区间问题)
Solution题意:给出一个数列,针对每个L,R,X 的区间求 [ L, R ] 中小于等于 x 的个数。 区间 个数 很容易想到树状数组来维护考虑 离线处理问题pair 存储数列的元素内容和索引 然后按照从小到大排序然后再对 存储询问的结构体 按 x 的值 从小到大排序 以上的前戏做完,就可以计...
树状数组
每日一题
前缀和
区间问题
2020-04-30
0
720
【每日一题】美味菜肴 (dp / 01背包)
Solution题意:给出m道菜,有a,b,c属性,美味值是a-b*c,求T时间能制作出菜肴的最大价值和。 规定条件范围内的最大价值和/方案数,妥妥背包~跟国王游戏很像,每道菜的价值跟选取的顺序有关,所以要预处理出每道菜的顺序。考虑任意两道菜x和y的价值: x煮完后再煮y : y煮完后...
每日一题
背包
DP
2020-04-28
0
836
【每日一题】Removal (dp+思维 / 子序列 计数)
Solution题意:给出n个元素,每个元素不大于k,求 删除m个元素后的子序列个数。 子序列问题,通常可以联想到dp来做,考虑 维护 前 i 个元素删除 j 个元素的方案数,考虑第 i 个元素删或者不删,即有: 但是这样计算的话肯定会有重复的方案,拿样例2来说:4 2 21 2 1 2删除第一...
每日一题
思维
DP
2020-04-24
0
664
【每日一题】边的染色(dfs+思维 / 联通块+xor)
Solution题意:给定一个无向图,有一些边已经染色,求让你染色剩下的边使得每个环的异或和都为0的方案数。 好难想!好难想!好难想!重要的事情要说三遍! 1.思维点:题解很巧妙,把对边染色转移到对点染色,取边为两个端点的xor,这样的话每个环的异或和肯定为0,因为每个点都xor了两次~ 2.答案的...
dfs
联通块
每日一题
思维
2020-04-24
0
729
【每日一题】子序列(枚举/ 树状数组优化)
Solution题意:求满足条件的子序列个数之和。 条件: 朴素做法1: 时间复杂度: 直接暴力枚举即可,关注点在于如何判断 直接计算可能会出现 100^100 这样是无法操作的考虑取对数,有 剩下的以 dp[i]维护 以i为结尾满足条件的子序列方案枚举更新即可 树状数组优化做法2: 时间复...
树状数组
每日一题
暴力
2020-04-23
0
571
【每日一题】K-th Number(二分 / 区间问题)
Solution题意:B的元素取 对于A的每个长度大于k的子区间取第k大元素,求B的第m大元素。 知识点:二分 首先由于数据过大,枚举区间肯定不行,在题解中有一句话非常好:考虑把求值变成验证。求第m大元素,即判断第k大元素比m大的区间数是否>=m。想到二分,但是不会计算区间数就很尴尬,还是很佩...
每日一题
二分答案
思维
区间问题
2020-04-22
1
834
首页
上一页
1
2
3
下一页
末页