111qqz的小窝

老年咸鱼冲锋!

uvalive 7675 | 2016 北京 regional onsite H – A New Ground Heating Device (二分+多个圆面积并)

题目链接

题意:

在一个二维平面上,有n个加热设备,每个加热设备加热一个圆形,加热设备需要信号源才可以工作,信号源在原点上,但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足,至少有k个加热设备加热的面积大于s,问信号源的最高高度是多少。

思路:

训练的时候一眼二分,但是求圆并的时候gg了。。毫无思路。

搞定了多个圆面积并。。这题就很easy了。。

需要注意,每次二分的时候,记得初始化圆的d…

 

leetcode162. Find Peak Element (O(lgn)复杂度寻找峰值)

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:Your solution should be in logarithmic complexity.

思路:

为什么能lgn。。。

首先要想明白,这样的峰值是一定存在的(因为最左最右已经负无穷了。

如果中间元素的值,比它右边相邻元素的小,说明什么呢?

说明右边区间一定存在峰值。

为什么?

现在a[mid]<a[mid+1]

如果a[mid+1]>a[mid+2],那么 a[mid+1]就是峰值

如果a[mid+1]<=a[mid+2],那么可以继续缩小区间,到[mid+2,n-1]

由于a[n]为负无穷,因此至少会出现一个 a[x]>a[x+1]的情况,此时a[x]就是峰值。

想清楚了这点就好办了。二分就好。

 

leetcode 33. Search in Rotated Sorted Array (无重复数的旋转数组找定值)

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

思路:找规律。。。二分。。。

观察发现。。。a[mid]<a[r]的时候,后半段有序;

a[mid]>a[r]的时候,前半段有序。。

然后根据有序区间的端点值,确定tar是在该有序区间,还是在另一半区间。

 

 

leetcode 34. Search for a Range (二分,找到一段值为tar的区间)

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

 

思路:二分。。。

我好像根本不会二分啊???

二分查找

 

 

 

leetcode 81. Search in Rotated Sorted Array II (有重复元素的旋转数组找给定值)

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

好像阿里一面的时候问过。。。

思路:肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。

总的思路是。。。当发现重复元素。。并且该重复元素不是target的时候。。。缩小范围。。。

 

求旋转数组最小值(二分)

题意:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

思路:二分。。。注意有重复元素。。。

 

leetcode 74. Search a 2D Matrix

题目链接

题意:给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。

思路:单调。。显然二分。。。唯一的技巧是从右上角开始搜。

 

 

leetcode 235. Lowest Common Ancestor of a Binary Search Tree(求一个BST中某两个节点LCA)

题目链接

题意:求一个BST中某两个节点LCA….

思路:卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

两个节点的LCA的值一定在这两个节点之间。

可以根据这个条件做二分。。。

这道题的收获是。。。不要被已知的东西限制住思路。。。tarjan或者RMQ+DFS显然也能做。。。但是那样的相当于没有用到BST的条件。。。

 

codeforces 381 div 2 D. Alyona and a tree(二分+前缀和)

题目链接

d:题意:一棵树,给出边权和点权,定义点v控制点u,当且仅当u是v的子树中的点,并且dis(u,v)<=a[u],其中dis(u,v)为点u到点v路径上的边权和,a[u]为点u的点权,现在问对于每个节点v,其能控制的点有多少个。

思路:先写了个rmq+dfs的lca。。。那么任意两个点的距离都可以O(1)得到了。然后不会了233333.

upd:和lca没有什么关系,因为一个点能控制另一个点这两个点一定在一条通向根的链上,因此距离直接减一下就好了。

机智的做法:dfs的时候维护一个栈,对于栈中序列,后面一半是对当前点有贡献的。问题时求对于每个v统计其能控制多少个u,现在我们固定u,考虑能控制他的v。这些v在树上的形态时一条链 ,借助第二类前缀和的思想,对于u标记+1,对于u往上的离根最近的且能统治u的v上面的一个标记-1,然后dfs后序遍历(也就是链的起点时距离根远的那一边),距离处理的时候,只需要在递归之后更新ans就好了。

栈里面维护,到哪个节点,从根下来,边权和最大,找边权和>=当前边权和-a[u]的地方。

启示:由于两个存在统治关系的点在一条链上,边权都为正,边权和具有单调性,单调的东西,容易想到二分处理。

codeforces #609 F. Frogs and mosquitoes (线段树+二分)

题目链接

题意:n只青蛙,第i只位于x[i],舌头长度为t[i]。m只蚊子,第i只蚊子所在位置为p[i],蚊子的大小为b[i]。

蚊子按照出现顺序输入。

一只青蛙能吃到蚊子当且仅当蚊子和青蛙在同一个位置,或者蚊子在青蛙右边并且与青蛙的距离小于等于该青蛙舌头的长度。

当多只青蛙可以吃到同一只蚊子的时候,最左边的那只青蛙来吃。

当一只青蛙吃掉一只蚊子以后,青蛙的舌头增加蚊子的大小。

当一只青蛙吃掉一只蚊子后,因为舌头边长而又能吃到其他蚊子的时候,这只青蛙会继续吃,只到当前没有蚊子可以被任何一只青蛙吃到,在这个过程之后才会飞来下一只蚊子。

 

思路:问题的关键在于,对于某只蚊子,我们如何找到能吃到该蚊子的青蛙中最左边的那只。

可以抽象成寻找区间[1,r]中,最左边的那个>=x的元素。

联想到一个类似的问题:对于区间[1,n],找到最左边的>=x的元素。做法是线段树维护最大值,只需要每次先query左子树,就可以保证找到额是最左边的。

但是如果是区间[1,r]呢。。。

我们发现。。。区间[1..k] (k<=r)的最大值是随着k的增大而不减的。。。。(最大值。。。肯定不减呀)

也就是说是单调的。。。因此我们可以考虑二分。。。这很重要。。。

寻找区间[1,r]中第一个大于等于x的元素,利用单调性来二分做是一个很经典的做法,复杂度(lgn)^2,注意体会。

 

因此具体做法是:

建树,存的是区间中x[i]+t[i]的最大值。

对于每一只飞来的蚊子,寻找能吃到它的最左边的青蛙的编号(具体做法是,先找到最后一个位置小于等于蚊子位置的青蛙的下标,作为青蛙的下标的上界,然后二分,每次query区间最大值,不断缩小区间。)

当蚊子被吃的时候记录答案,更新青蛙的各种信息(线段树要update)

并且由于青蛙的舌头变长了,可能吃到之前没有青蛙能吃到的蚊子,因此要把之前的没有能被青蛙吃到的蚊子存进一个multiset(因为蚊子可能落在同一个位置) 然后让当前的青蛙尽可能吃这些没有被吃到的蚊子,同时更新青蛙的各种信息,并在multiset中删除这只蚊子/

没被吃的时候就扔进multiset里。

需要注意multiset erase的时候要erase一个迭代器。。。不然会把所有相同的都删掉。。。

 

 

poj 3579 Median (尺取法+二分)

题意:给出n个数,两两做差的绝对值,共有m=n*(n-1)/2个,问其中的中位数是多少。特别地,当m为偶数的时候,中位数为第m/2个。

思路:二分中位数。

一开始还觉得由于中位数在整数意义上不连续不能二分。。。。

但是最后结果不可能是那样的答案啊。。。

check的条件是,以k为中位数的时候,绝对值小于k的数要小于(m+1)/2个(也就是中位数所在的位置)

check的时候尺取即可。

复杂度 排序O(nlgn) + 二分(lgn)*尺取O(n) ,整体O(nlgn)

 

 

poj 2456 Aggressive cows (二分)

题目链接

题意:给出n个x轴上的坐标点,选取其中c个,问c个之中任意两个点的最小距离最大是多少。

思路:二分距离check合法性。

大水题。。。因为想把三分艹掉。。。三分的题又多和二分挂在一起。。。顺便就写了。。。。

 

seerc 2014 Circle of digits (二分+后缀数组)

题目链接

题意:把一个长度为n的只由数字构成的串分成k个不为空的字串,使得最大的串最小(大小是说串所对应的十进制数的大小)

思路:由于长度为x的串肯定大于长度为x-1的串,因此很容易想到,我们要尽可能使得k组串的长度尽可能平均(避免出现某一个串的长度非常大的情况)

我们可以知道,最大值的串的长度一定为 LEN=(n+k-1)/k;

而每一组的长度,只可能是LEN或者LEN-1。

然后build_sa

注意循环串的几个地方记得%n

接下来二分sa数组的下标。

二分check的时候,先枚举断点,断环为链。

由于每部分最长的长度为LEN,所以0..LEN-1中一定存在一个断点。

然后贪心,尽可能取LEN

根据rk值来决定某一段的长度是LEN还是LEN-1(如果rk值比当前的大,那么就只能取LEN-1,否则取LEN)

如果此时k段的长度之和超过了n,说明此时的最大值还可能更小。

于是继续二分区间的前一半。

 

 

whust 2016 warm up G ||codeforces 689C. Mike and Chocolate Thieves

cf689C

 

题意:给出一个m。。问恰好使得不超过某个n的a*b^3(a,b是正整数)的方案数为m的n是多少。。。

思路:暴力+二分。。。

 

 

 

BZOJ 1614: [Usaco2007 Jan]Telephone Lines架设电话线 (二分+spfa)

1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1325  Solved: 570
[Submit][Status][Discuss]

Description

Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务。于是,FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线,其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i,它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i,B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络,整个农场的电话线全都连到了编号为N的电话线杆上。也就是说,FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。 经过谈判,电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线,FJ需要为它们付的费用,等于其中最长的电话线的长度(每根电话线仅连结一对电话线杆)。如果需要连结的电话线杆不超过 K对,那么FJ的总支出为0。 请你计算一下,FJ最少需要在电话线上花多少钱。

Input

* 第1行: 3个用空格隔开的整数:N,P,以及K

* 第2..P+1行: 第i+1行为3个用空格隔开的整数:A_i,B_i,L_i

Output

* 第1行: 输出1个整数,为FJ在这项工程上的最小支出。如果任务不可能完成, 输出-1

Sample Input

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输入说明:

一共有5根废弃的电话线杆。电话线杆1不能直接与电话线杆4、5相连。电话
线杆5不能直接与电话线杆1、3相连。其余所有电话线杆间均可拉电话线。电信
公司可以免费为FJ连结一对电话线杆。

Sample Output

4

输出说明:

FJ选择如下的连结方案:1->3;3->2;2->5,这3对电话线杆间需要的
电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线,于是,
他所需要购买的电话线的最大长度为4。

HINT

 

思路:一开始把电话线条数和长度分别作为第一第二关键字,然后spfa.然后记录路径,找k个最大的以后的中最长的电话线就是答案。发现样例就是反例。。智力-2.

正确的做法是二分电话线的最大长度,大于最大长度的电话线交给电信公司取搞,看交给电信公司搞的电话线数目是否小于等于k.

二分的功夫还是不到家呀。。想不到。。
不过这道题和那个中国印度被喜马拉雅山脉阻隔,二分+bfs判断连通性的题目有点类似呢。