虽然吧_但是

分类

数据结构(1) 数论(2) 题解(22)

/ 注册

全部文章（共25篇）

每日一题 [JSOI2007]建筑抢修

这题的思路和https://ac.nowcoder.com/acm/problem/50439 类似在我们看来，每一段都存在一个截至区域，首先肯定是要把截至区域按从小到大的顺序排列，这样之前的选择会为后面的选择腾出更多的时间，这个贪心就是可行的。既然所选需要最多，有些我选择过后，如果当前总和小于截至...

2020-05-27

1 671

吐泡泡

写过括号匹配这种题就很容易想到用栈来解决此类问题首先要理解栈是什么，它是一种线性表你可以将它理解为一个容器但他只能从栈顶出，栈顶入，后进先出实际定义（来自百度百科）：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈...

2020-05-23

6 954

Subsequence

题目大意：给定一个长度为n的序列，找出一个最短的子序列使其之和大于等于s我也就来摸摸鱼，尺取+前缀和弄一个双指针分别对前缀进行处理sum[i]代表前i项之和要求i-j的子序列只需要sum[j]-sum[i-1]即可接下来只要运用尺取法在保证当前子序列之和大于等于s的情况下移动左指针一旦小于移动...

2020-05-22

9 764

[HNOI2003]激光炸弹

题解写重了参考https://blog.nowcoder.net/n/62b1d5cfab0647cbae38a868fdd0e713本题图片说明按上图设置M[i][j]记录以（1，1）为左上角端点以(i,j)为右下角端点的矩形大矩形=红色矩形+青色矩形-黑色重叠矩形+（i，j）点的数值不难发现...

2020-05-21

0 652

切长条

由于存在区间包含的关系，被包含的小区间满足时大区间也一定满足。把所有区间按照右端点从大到小排序。如果右端点相等，按照左端点从大到小排不妨想想，取哪个点由于右端点是从小到大，可以取最上面那个区间的右端点1.如果后面区间的左端点小于该区间，那么就是包含，就一定取得到2.如果后面区间的左端点大于该区间，依...

2020-05-21

1 703

Selfish Grazing

这么经典的题目没人写题解（我来水一波）题目大意：牧场有N头牛，每头牛都有它喜欢的放牧区间[si,Ei]大多数人都知道母牛很自私。没有牛愿意与其他人共享任何放牧区域。因此，如果Si> = Ej或Ei <= Sj，则两只母牛i和j只能同时放牧。FJ希望知道给定的一组奶牛可以同时放牧的最大...

2020-05-21

3 826

校门外的树

这数据O(n^2) 模拟，我不想tle看区间，区间覆盖的贪心，多想想，人总是贪心的思路：不妨把左端点从小到大排序，此时就是把覆盖的区间进行合并比如合并过后区间是[l1,r2]但要注意像下面这种情况第一个区间包含第二个区间此时我们就无需改变右指针所以right=max(a[i].r,ri...

2020-05-21

8 752

铺地毯

铺矩形地毯既然前一张会被后一张所覆盖那么不如直接按照反方向的顺序直接找到最后一张地毯（一年前的代码，缩进比较尴尬） #include <iostream> using namespace std; int a[100000][4]; int main(){ int n; cin>...

2020-05-21

1 716

纪念品分组

很明显就是一道关于背包的贪心问题那么根据贪心策略固定容量的背包，装多样物品，使得背包数最小首先把大的装入背包，如果能匹配到一个最小的，他们的和小于容量就是优解因为之前的最小的，会为后面稍大的提供空间，否则剩余的会超出容量达不到最优（我记得紫书上有讲） #include <bits/stdc...

2020-05-21

1 815

每日一题 [CQOI2009]中位数图

题目描述给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元>素从小到大排列后，位于中间的数。输入描述: 第一行为两个正整数n和b ，第二行为1~n 的排列。对于 30% 的数据中，满足 n≤100；对于 60% 的数据中，满足 n≤100...

2020-05-21

1 687