111qqz的小窝

老年咸鱼冲锋!

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

题目链接 题意: 在一个二维平面上,有n个加热设备,每个加热设备加热一个圆形,加热设备需要信号源才可以工作,信号源在原点上,但是高度不确定。假设

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

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. 思路:找规律。。。

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. 好像阿里一面的时候问过。。。 思路:肯定

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

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

leetcode 74. Search a 2D Matrix

题目链接 题意:给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。 思路:单调。。显然二分。。。唯一的技巧是从右上角

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

题目链接 题意:求一个BST中某两个节点LCA…. 思路:卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法

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

题目链接 d:题意:一棵树,给出边权和点权,定义点v控制点u,当且仅当u是v的子树中的点,并且dis(u,v)<=a[u],其中dis(

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

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

poj 3579 Median (尺取法+二分)

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

poj 2456 Aggressive cows (二分)

题目链接 题意:给出n个x轴上的坐标点,选取其中c个,问c个之中任意两个点的最小距离最大是多少。 思路:二分距离check合法性。 大水题。。。因

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

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

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

cf689C 题意:给出一个m。。问恰好使得不超过某个n的a*b^3(a,b是正整数)的方案数为m的n是多少。。。 思路:暴力+二分。。。 /* *********************************************** Author :111qqz Created Time :2

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必

poj 2452 Sticks Problem (rmq+二分,需要返回最值位置)

poj2452题目链接 题意:给你一组数a[n],求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路:大概能想到是rmq,然后想出了一个错

BZOJ 1650: [Usaco2006 Dec]River Hopscotch 跳石子 (二分)

1650: [Usaco2006 Dec]River Hopscotch 跳石子 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss] Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from

BZOJ 1639: [Usaco2007 Mar]Monthly Expense 月度开支 (二分)

1639: [Usaco2007 Mar]Monthly Expense 月度开支 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 767 Solved: 381 [Submit][Status][Discuss] Description Farmer John是一个令人惊讶的会计学天才,他已经明白了他可能会花光他的钱,这些钱本来是要维持农场每个

codeforces 617 C. Tourist's Notes (二分)

题目链接 题意:有n天的旅行,但是只剩下了m天的旅行记录,记录格式为d[i],h[d[i]],表示第i个记录是第d[i]天的,高度为h[d[i

codeforces #339 div2 D

http://codeforces.com/contest/613/problem/B 题意:有n个技能,初始每个技能的level为a[i],每个技能最大level为A(不妨称为满级技能),设满级技能个数为maxnum,最小的