不知名啤酒人

题解

/ 注册

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

【每日一题】图的遍历 (dfs / 染色+判奇环)

Solution题意:无向图有n个点，从点1开始遍历，每次走两步，遍历整个图。问最少加几条边，可以完整的遍历整个图。思路：首先可以想到的是如果图不连通，那么答案至少需要 (联通块的数目-1) 来把各个联通块连起来。而走两步的话，不难联想到奇偶形，考虑奇环的话两步可以到达环内任意一点，所以只要连通后...

dfs 联通块每日一题

2020-05-21

0 720

【每日一题】过河 (dp / 数据压缩)

Solution题意:题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。范围：st 属于[1,10], 石头数量<=100, L<=1e9思路：很明显的dp题，dp[i]维护到达 i 点的最少步数：但是要考虑到木板的...

每日一题 DP

2020-05-13

0 667

【每日一题】「火」皇家烈焰 (dp / 递推)

Solution题意: 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈焰？：未告诉你本格情况求满足条件的方案数。思路：考虑用表示第 i 个字符是/不是火焰以...

每日一题 DP

2020-05-10

0 506

【每日一题】合并回文子串 (dp / 字符串回文)

Solution安利一下我的线性dp博客：https://blog.csdn.net/JiangHxin/article/details/105184169一般情况下，动态规划的解题步骤是：第一步：根据原问题和子问题来确定状态（dp数组表示什么东西）第二步：根据状态确定状态转移方程（怎样求解dp数组...

回文每日一题字符串 DP

2020-05-05

1 651

【每日一题】换个角度思考 (树状数组+离线 / 区间问题)

Solution题意：给出一个数列，针对每个L,R,X 的区间求 [ L, R ] 中小于等于 x 的个数。区间个数很容易想到树状数组来维护考虑离线处理问题pair 存储数列的元素内容和索引然后按照从小到大排序然后再对存储询问的结构体按 x 的值从小到大排序以上的前戏做完，就可以计...

树状数组每日一题前缀和区间问题

2020-04-30

0 590

【每日一题】美味菜肴 (dp / 01背包)

Solution题意：给出m道菜，有a,b,c属性，美味值是a-b*c,求T时间能制作出菜肴的最大价值和。规定条件范围内的最大价值和/方案数，妥妥背包~跟国王游戏很像，每道菜的价值跟选取的顺序有关，所以要预处理出每道菜的顺序。考虑任意两道菜x和y的价值： x煮完后再煮y : y煮完后...

每日一题背包 DP

2020-04-28

0 713

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

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

每日一题思维 DP

2020-04-24

0 537

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

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

dfs 联通块每日一题思维

2020-04-24

0 566

【每日一题】子序列（枚举/ 树状数组优化）

Solution题意：求满足条件的子序列个数之和。条件：朴素做法1：时间复杂度: 直接暴力枚举即可，关注点在于如何判断直接计算可能会出现 100^100 这样是无法操作的考虑取对数，有剩下的以 dp[i]维护以i为结尾满足条件的子序列方案枚举更新即可树状数组优化做法2：时间复...

树状数组每日一题暴力

2020-04-23

0 441

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

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

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

2020-04-22

1 627