ThinkofBlank

分类

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

/ 注册

TA的专栏 8篇文章 0人订阅

ThinkofBlank’s

8篇文章 1242人学习

全部文章（共105篇）

2020年牛客算法入门课练习赛1 题解

这次比赛真的。。。槽点满满啊。。。A,C,D,E都有问题。。。（害我罚时高到飞起） A.第k小数读完题，我：这nlogn直接艹，问题不大！然后。。。段错误*n 我:??? 然后，天真的以为sort出锅了，码了个基排。。。然后。。。段错误*n 我:??? 之后，自暴自弃，数组开个1e7，于是...

题解

2020-05-25

3 1107

[JSOI2007]建筑抢修题解

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

题解数据结构

2020-05-25

0 596

小AA的数列题解

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

数论题解

2020-05-22

1 1104

[SCOI2010]传送带题解

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

题解

2020-05-22

7 1432

[CQOI2009]中位数图题解

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

题解

2020-05-21

0 708

基于字典树实现的O(n)排序来自专栏

我们用字典树，从高位到低位进行排序，使用中有类似于基排的思路。残留问题在于，空间方面，需要我们使用vector或类似的动态扩充的来做。不过，不想去想了，先给个代码： #include<bits/stdc++.h> using namespace std; const int N=1e5...

研究

2020-05-20

1 706

图的遍历题解

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

题解

2020-05-20

0 715

栈和排序题解

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

题解

2020-05-19

24 1778

关于无向图缩点

把之前的补过来/xk 最近,做了好多图论,其中大部分都跟tarjan有关,而又有好多无向图。。。orz 我们都知道,tarjan会把能互达的若干点合并为一个点,然而,在无向图中,所有点都可互达(图联通),故,整个图就会缩成一个点...然鹅,我们把图画出来,又是另外的样子...明明就只有一个环,却把所...

理解图论研究

2020-05-19

0 1632

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

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

题解

2020-05-19

2 980