ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

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

背包题解

注意，答案直接向下取整！！！被这个玩意儿坑了，好惨啊。。。关于这道题，我们先来看看m是奇数怎么做。很明显，我们可以考虑枚举中位数，然后判断其是否可行即可。这样，我们先对所有物品按价值从小到大排序。那么，如果一个物品可以作为中位数，当前仅当存在一种方案，从这个物品的左边选个物品，再从它右边选个...

题解数据结构

2020-06-10

6 1072

[JSOI2007]建筑抢修题解

带后悔的贪心首先，我们设一场电影的持续时间时间为,结束时间为假设，我们决定好了要看哪些电影且其中一种合法的看电影顺序为那么，我们来贪心的化下式子：假设，我们调换了看第i部和第i+1部电影的顺序后，使得当前的顺序不合法了，(前i-1部用的总时长为S)那么有：当前方案：因为调换后不合法，...

题解数据结构

2020-05-25

0 587

逆序数题解

逆序对模板题/x(怎么又是模板题啊) 题目大意：给你一个长度为n的序列，求逆序对数直接上归并排序。。。才怪。。。作为一个热衷于权值线段树的菜鸡，当然直接上权值线段树辣！只需要实现insert()添加一个数和find()查询值的范围属于查询区间的数字的个数这两个基本函数就行。代码: #in...

题解数据结构

2020-05-19

2 907

tokitsukaze and Soldier 题解

来补题辣~ 这题很简单，我们来判断下一个选择的序列是否合法的充要条件是什么：合法是要满足对于所有的选择进去的i，都要满足s[i]>=总人数等价于min(s[i])>=总人数所以，我们可以直接枚举这个min(s[i])，然后问题就转化成了，在一定范围内，选s[i]-1个人的最大战力，...

排序题解数据结构

2020-05-04

1 594

滑动窗口题解

模板题留名/x 这题就是一个单调队列模板题（真模板题，被各个大佬用于单调队列的讲解）由于不想水题解，就在这里讲讲单调队列吧。。。我们用此题来讲解。假设我们现在在求窗口中的最小值，那么，如果满足存在两个位置:i,j在同一个窗口(i<j)，如果a[i]>=a[j]，那么，一定有答案不可...

题解数据结构

2020-05-02

1 804

换个角度思考题解

看样子，应该有比较好的做法，不过，这道题，肯定要上主席树辣！！如果打算用主席树做这道题的话，这道题就是一个主席树的纯板子问题了。。。相当于查询区间l-r中1-x的数字的个数代码： #include<bits/stdc++.h> using namespace std; const ...

题解主席树数据结构

2020-04-29

0 652

K-th Number 题解

Update:添加了一种常数小的做法一.闲话看了下大佬们的题解，然后。。。二分+尺取？？？我：。。。二.题解题目简意: 数组b的元素是，数组a中所有区间长度大于等于k的区间的第k大数(有点绕？) 求数组b中第m大的数要做这题，首先我们需要明白一个简单的性质，对于一个序列，我们如果添加进一...

优化题解数据结构

2020-04-21

10 1363

JOISC 2019 Day1 A 考试题解

题目简意有n个同学，每个同学有a,b,c三个数(c=a+b) 现在，有m次询问，每次给你三个数A,B,C问你满足a>=A,b>=B,c>=C的同学的人数一道明显的三维偏序问题，只是空间把主席树卡了（别问我为什么知道qwq）所以，这里我们就要打空间复杂度更小的cdq分治我们先...

优化题解数据结构

2020-04-19

0 818

牛客练习赛61 F苹果树题解

一.闲话学了淀粉质有一年多了，期间基本没用过，又因为当时是直接背的代码，导致打比赛的时候对这道题根本无从下手，甚至都没想到是淀粉质qwq 然后，今天去学了一下淀粉质，发现原理和实现特别简单，快速码了个模板后，又去顺带学了下点分树，就来搞这道题了。。。二.题解这道题，我们看数据范围，发现成熟度的...

优化题解数据结构

2020-04-17

0 729

Running Median 题解

一.题目大意给你P组数据，先输出数据编号和(n+1)/2,再依次输出所有前i(i为奇数)个数的中位数，每10个数换一行二.题解求中位数，作为一枚偏爱权值线段树的菜鸡，于是，我直接码了一棵权值线段树，对于每个有询问的i，我们直接查询kth((i+1)/2)即可。不...

题解数据结构

2020-04-13

0 518