呱呱咕

题解

/ 注册

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

Minimizing maximizer(线段树优化dp 好题）

题意：N个排序器，每个可以把第l个数到第r个数这个区间里面的数从小到大排序，这些排序器按顺序运行，最后一个排序器运行完第n个数为第n小（最大数）。这些排序器去掉若干个也可以完成任务，问最少要留下几个，才能使留下的排序器依次运行使得对于任何输入最后一个排序器输出的最后一个数字为最大数。（题意看的一个犇...

线段树

2020-10-05

1 563

背包优先队列+二分

题意：找出m个不超过V的最大权值的中位数；题解：中位数的找法要区别奇偶，奇数直接就是中间，偶数就是中间两边数相加>>1,首先我们要知道如何处理这个问题，先找M>>1,就是先找中位数左右两边的数字，由于我们要找最大的权值，所以我们按照权值升序，在排大小，那么我们是不是就要尽量使...

2020-06-30

0 541

失衡天平 DP

一看题意首先想了求最值，那么就是二分但是操作过程中是很灵活的，然后果断pass掉，然后DP，很明确题目就是三种情况，要么放左边，要么不放，要么放右边，反正最后取得的武器必然左右两边差值不过M，那么就要想DP方程式，DP[i][j]=代表前i个物品左右最多相差j的质量，我们可以很容易想到要是本次不放...

2020-06-29

0 464

小A与小B 搜索

题意：就是一个人走八个方向，每次走一步，一个人走四个方向，每次走2步，问最少基几步两个人相遇。题解：首先我们要考虑好走两步的如何走，我们不能简单的把他弄成每一次直接就走2步，比如，...#D，这样子的话如果你走2步他直接就跳过障碍物了，但是实际上是走不通的，我们就可以把他处理一下，把两部变成走两次不...

搜索小A与小B

2020-06-12

0 457

最大子矩阵DP

题意：就是选出K个ab的子矩阵（a<n,b<m），不能选选过的点，然后问你这个K个子矩阵MAX;题解：首先这题一定要看范围，M=2，那么矩阵就是最大就是N2，我们是不是可以直接枚举暴力来做。（我们每一列求一个前缀和，第一列sum1,第二列sum2）首先.我们讨论M=1，是不是矩阵就是...

2020-06-10

0 470

扑克牌题解二分答案

题意就是给你N+1个种类的牌然后N+1个牌是万能牌，这N+1种牌每个牌都有Ci个，然后问你这N+1个牌能够组成牌数为N，而且每个N张牌里面没有重复的牌，问你一共可以组成多少种。题解：这题慕然一看感觉就是贪心，但是我们贪心做的话比如 1 2 3 （万能牌）10，答案很明显就是3，是不是可以贪心就是...

2020-06-10

0 483

德玛西亚万岁状压DP

题目范围非常小，一眼看就觉得要不是搜索要不是DP,但是是题意弄明白后就发现如果搜索的话很是麻烦，我们不能很顺利的去选择方案，然后就转换位dp，关键dp如何写，我们仔细看样列，是不是写的非常好，一行一行的就像是一个二进制串，那么是不是就可以想到状压，状压与二进制关联，然后我们就应该去判断条件，如何去写...

2020-06-09

0 526

旅游题解树形dp

首先题意说的很清楚，必须从一开始，然后去找最长的旅游天数，那么我们可以看出是在一颗树上面操作的，那么就是树形dp来解决，我们可以定义dp[i][1/0],什么意思呢，就是第i个地方我是选择住宿还是不住宿（1/0）的最长停留时间，那么我们如果到了以X为根的节点，如果要住那就是dp[x][1]=dp[y...

2020-06-09

0 542

Contest题解逆序对

这题很厉害我读了很久才真正的搞懂题意，答案+1的情况是任意一组a，b队必须三次比赛中a任何一次至少排名大于b一次和bd大于a一次，这样两个才算一次，那么是不是我们就可以把a第一次排序然后后面的就是查找第二次的逆序对啦，但是有三次比赛，我们是不是需要选择任意两次那就是C（n,2),对吧，组...

Contest

2020-06-08

0 520

管道取珠题解DP

直接入手似乎有些困难，不妨将原问题作一点转化：输出第i种特定序列的方案数a[i]即为二元组(X, Y)（其中X, Y分别代表一种输出第i种序列的方式，且X与Y相互独立）的组数。设X所对应的方案为(ix, jx)（从上管道取出了ix个，从下管道取出了jx个），Y所对应的方案为（iy, jy)（含义类似...

2020-06-05

0 549