Menu Sidebar
Menu

Archive: July 19, 2015

Codeforces Round #312 (Div. 2) B. Amr and The Large Array

原题:http://codeforces.com/problemset/problem/558/B 题目大意: 给一个数组, 找出其中的子数组,并且要求原数组中出现最多次数的数字在在子数组中.最多次数的数字可以不唯一. 所以答案也不一定唯一 分析: 暴啊暴啊…先按照频率排序,然后找同频率下所有的数字间隔在原数组中间隔最小的. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int nums[] = IOUtils.readIntArray(in, n); HashMap<Integer,Item> map = new HashMap<>(); // <num, item> for (int i = 0 ; i < nums.length; i++) { int x = nums[i]; if (!map.containsKey(x)) map.put(x,new Item(i,i,1)); else { Item […]

Ramsey Theorem 拉姆齐定理

– – 首先吐槽一下这个wiki的翻译, 看了一下是一个台湾人翻译的, 虽然语言很标准..但是读着不是很流畅. 我看Ramsey Number是看 Combinatorics Through Guided Discovery 的时候看到的. 里面第二章介绍Double Induction and Ramsey Number 说的非常详细, 而且很简洁. 这本书是免费的, 伯克利也在用, 强烈推荐. 下面介绍Ramsey Number: Ramsey Number可以从两个方面考虑: 一个是实际问题: 请多少的客人吃饭, 能正好让他们有至少m个互相认识或者n个都不认识. 这里有几点需要注意: 所求的值和条件都为至少 m和n是或者的关系 另一个描述是从图论出发: 一个无向完全图中,最少多少个顶点, 有m大小的Clique或者n大小Independent Set. Clique的定义是:一个顶点的集合,其中任意两点都有边. Independent Set的定义是: 一个顶点的集合, 其中任意两点都没有边. 通过定义, 我们可以很清楚的看出, Ramsey Number是对称的, 即: R(m.n) = R(n,m) 证明Ramsey Number是非常复杂的, 借用wiki上的话就是: 想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了 虽然证明一个不容易, 但是通过一个不等式,可以知道其大概的范围: 如果R(m-1,n)和R(m,n-1)不全是偶数: R(m, […]

[Amazon] Abstract Class 与 Anonymous Class

这是我面Amazon Intern的其中一个问题,  当时是解释什么是Abstract class, 我啪啦啪啦的说了一堆, 其中就说, 我们一般不实例化抽象类, 因为其中有抽象方法, 抽象方法会让实例变得毫无意义, 我的原话是meaningless, 这里的毫无意义是因为实例就是拿去直接用的, 然而其中如果有抽象方法, 说明这个实例是不完整的. 当时印度小哥立刻就问完, 你说抽象类能实例化么? 我说能的. 然后Amazon就那么离我而去了. Talk is cheap. Show me the code public abstract class Car { public int getAge(){ return 5; } public static void main(String[] args) { Car mycar = new Car(){}; System.out.println(mycar.getAge()); LinkedList list = new LinkedList(); } } Car是一个抽象类, […]

Codeforces Round #312 (Div. 2) A. Lala Land and Apple Trees

原题:http://codeforces.com/problemset/problem/558/A 题目大意: 坐标轴上, 每个坐标上有一颗苹果树, 坐标的值代表的值是苹果的数量, 人从0开始走, 可以往左,也可以往右, 当遇到一个苹果树时, 人必须往反向走, 问:最多拿多少个的苹果? 分析: 无非开始往左or往右, 两种情况, 当遇到另一边没有树的时候, 停止, 所以最多拿max([left+1,right],[right+1,left]).left,right 原点左右的树的数量. 建个Pair<Integer,Integer>, 前边是index, 后边是value, 然后sort下 加一下就出来了. public void solve(int testNumber, Scanner in, PrintWriter out) { int n = in.nextInt(); ArrayList<Pair<Integer,Integer>> pos = new ArrayList<Pair<Integer,Integer>>(); ArrayList<Pair<Integer,Integer>> neg = new ArrayList<Pair<Integer, Integer>>(); for (int i = 0; i < n; i++) […]

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

July 2015
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  
© 2025 书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.