ThinkofBlank

题解

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

/ 注册

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

[JSOI2007]建筑抢修题解

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

题解数据结构

2020-05-25

0 587

小AA的数列题解

又是求异或和的和的常见套路——按位计算，即计算二进制中每一位的贡献。需要注意的是，题目要求的不仅要区间长度在[L,R],而且区间长度必须是偶数（因为这个debug了好久qwq）我们先来简化下题目。我们假设只考虑一个二进制位x，并且区间长度也可以为奇数，那么这个怎么做呢？很简单，我们为了方便处...

数论题解

2020-05-22

1 1094

[SCOI2010]传送带题解

直接复制以前写的代码，还带注释，真棒！咳咳。这道题，我们算从A到D点的最短距离，那么明显的，我们考虑三分。我们先三分出从A点到AB中的某个点X，作为出发点，然后，再三分出从X到CD的某个点Y，再从Y直接到D，这样，我们就可以求出最小的值了。我们来看看，我们这样三分是否完备。我们走的最短路线...

题解

2020-05-22

7 1411

[CQOI2009]中位数图题解

Ps:数据范围: 一道比较套路的题了因为对于一个数a[i],我们其实只需要知道它与b的大小关系就行了，并不需要知道其准确的值，所以，我们可以将每个点变为它对它所在的所有区间的中，这个数添加进区间后，会对b到中位数的位置的变化的贡献是多少：如果a[i]>b,那么，它会使得b的位置向左移一位，...

题解

2020-05-21

0 696

图的遍历题解

呜呜来晚了。。。题目大意：你只能两步两步的走,问你最少添加多少条边才可以使得你能遍历完整个图题解: 我们每次只能两步两步地走，那么如果，我们走一条边再回去，这是毫无意义的。如果，我们一个图中没有无向边环，（也即是图的形状类似于树），那么，很明显的，一个点到另外一个点走的步数的奇偶性就确定了，...

题解

2020-05-20

0 712

栈和排序题解

一个简单的贪心做法（已通过@7QQQQQQQ大佬的hack数据）我们设maxe[i]表示i-n的元素的最大值。那么，我们假设，当前栈顶的元素比maxe[i+1]大（最近入栈的是第i个元素），那么，不难发现，如果我们当前元素不出栈的话，之后如果有元素入栈，那么最后出栈的字典序一定会小于当前元素出栈...

题解

2020-05-19

18 1770

牛客算法周周练7 部分题解

还是来写点有意思的题目的题解吧/x C.Rabbit的工作(1) 这题很明显是个dp题，因为n很小，我们直接乱搞就行了，不用考虑优化什么的。。。我们设dp[i][j]表示前i天，我们一共工作了j天所耗费的最小疲惫度那么对于第i天来说，我们有如下情况：如果第i天为0，直接从i-1那里将值继承过来...

题解

2020-05-19

2 972

表达式计算4 题解

嗯。。。表达式计算的又一道类模板做这类题，其实就相当于在搞一个大模拟的题目。我们需要注意的是：因为有多余的括号出现，所以我们最好在一开始把多余的括号去掉，防止中途计算出现问题。其次，就是需要注意计算的顺序，对于此题，我们应该先算括号，再算乘方，然后按出现顺序算乘除，最后再按出现顺序算加减。我...

题解研究

2020-05-19

2 769

逆序数题解

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

题解数据结构

2020-05-19

2 907

华华教月月做数学题解

题目大意：给你三个数A,B,P,求快速幂模板题/xk 但是，我们注意到，P的值很大，可以达到,所以，我们不能直接打快速幂，我们需要搞个龟速乘进去。代码： #include<bits/stdc++.h> using namespace std; inline unsigned lon...

优化题解

2020-05-19

3 1042