xindoo的博客XINDOO

xindoo is
always here
未分类

python 的几种数据类型

xindoo阅读(4483)评论(0)赞(0)

列表  列表是 Python  的主力数据类型。当提到 “ 列表 ” 时,您脑海中可 能会闪现“ 必须进一步声明大小的数组,只能包含同一类对象 “  等想法。千万别这么想。列表比那要酷得...

未分类

poj 1990 MooFest 树状数组

xindoo阅读(4554)评论(0)赞(0)

题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?       显然总共有n...

操作系统

从windows平台转战ubuntu

xindoo阅读(4571)评论(0)赞(0)

      说到ubuntu,可能很多人会有些陌生,但对于有些人很熟悉。ubuntu是linux里面最为流行的一版,以下来自百度百科。             Ubuntu(乌班图)是基于De...

未分类

布隆过滤器

xindoo阅读(4429)评论(0)赞(0)

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一...

未分类

light oj 1159 - Batman LCS

xindoo阅读(4551)评论(0)赞(0)

学过简单动态规划的人应该对最长公共子序列的问题很熟悉了,这道题只不过多加了一条字符串变成三条了,还记得,只要把状态变成三维的即可。 //http://lightoj.com/volume_showprob...

未分类

hdoj 3732 Ahui Writes Word (多重背包)

xindoo阅读(4474)评论(0)赞(0)

      之前在做背包的题目时看到了这道题,一看,大喜,这不是裸裸的01背包吗!!  然后华丽丽的超时,相信很多人也和我一样没有考虑到数据量的大小。       时隔多日,回过头...

poj 2823 Sliding Window-XINDOO
未分类

poj 2823 Sliding Window

xindoo阅读(4430)评论(0)赞(0)

      在这里先说一道微软的面试题目———《队列中的最大值》       让你设计一个队列,是其求里面最大值的时间复杂度尽可能的低,但这个队列除了最大值外,就是一个普通的队列,该怎么进出还是怎么进出,...

未分类

POJ 3264 RMQ

xindoo阅读(4455)评论(0)赞(0)

题意就是让你求区间最大和最小值的差值。 这题可以用线段树,也可以用Tarjan 的Sparse Table算法(参考刘汝佳训练指南197),这里我用了ST算法,还有要说明的是题目描述的数据范围是不准确的如...

未分类

poj 1068 模拟

xindoo阅读(4504)评论(0)赞(0)

题目链接     大概题意就是告诉你有个n个小括号,每一个“)”左边有多少个“(”都告诉你了,然后让你求出每一对括号之间有多少对括号(包含自己本身)。 思路:        我先计...

未分类

codeforces 327 B. Hungry Sequence

xindoo阅读(4536)评论(0)赞(0)

题目链接    题目就是让你输出n个数的序列,要保证该序列是递增的,并且第i个数的前面不能保护它的约数,我直接先对前100000的素数打表,然后输出前n个,so easy。 //cf 191 ...

未分类

codeforces 327 A Ciel and Dancing

xindoo阅读(4492)评论(0)赞(0)

题目链接     给你一串只有0和1的数字,然后对某一区间的数翻转1次(0变1 1变0),只翻转一次而且不能不翻转,然后让你计算最多可能出现多少个1。     这里要注意很多细节 比如全为1,...

未分类

codeforces 322 B Ciel and Flowers

xindoo阅读(4571)评论(0)赞(0)

题目链接 有红绿蓝三种颜色的画,每种拿三朵可以组成一束花,或者各拿一朵组成花束,告诉你每种花的数目,求出可能组成最多的花束。 如果你的代码过不了,考虑一下 8 8 9这种组合。  因为数据量很大,我的思想就是局部和总体采用不同的策略。 #i...

codeforces 322 A Ciel and Dancing-XINDOO
未分类

codeforces 322 A Ciel and Dancing

xindoo阅读(4735)评论(0)赞(0)

题目链接 题意:       有n个男孩和m个女孩,他们要结对跳舞,每对要有一个女孩和一个男孩,而且其中一个要求之前没有和其他人结对,求出最大可以结多少对。 如图,一条...

未分类

hdoj 2089 不要62

xindoo阅读(4480)评论(0)赞(0)

这题数据量相对比较小,可以暴力打表解决。不过我这里用数位dp  刚开始学数位dp,参考了别人的代码。 //2013-06-27-15.30 #include <stdio.h> #includ...

未分类

poj 1164 放苹果

xindoo阅读(4641)评论(0)赞(0)

http://poj.org/problem?id=1664          这题可以用递归的方式做,想给第一个盘子里放上苹果从(0到m),然后给第二个放上,为了保证每次产生的放法是不同的,第二个里面放...

未分类

寻找最大的K个数

xindoo阅读(4409)评论(0)赞(0)

给你n个数,让你找出其中最大的K个数。 解法1: 很多人上来就对其进行排序,选用不同的排序方法有不同的时间复杂度,这里我们假设使用了最快的快排,...

未分类

省赛总结

xindoo阅读(4502)评论(0)赞(0)

         虽然结果比我们预期的好一些,拿了银牌(本来感觉只能拿铜牌),但感觉还是很弱。 我们只A了三个最水的题目。         开始确实有些失策,晨晨看了第一题(给出等边三角形的两个点,计算第...

未分类

codeforces 285C - Building Permutation

xindoo阅读(4434)评论(0)赞(0)

题目链接 题目大意是有一个含n个数的数组,你可以通过+1或者-1的操作使得其中的数是1--n中的数,且没有重复的数。 既然是这样的题意,那么我就应该把原数组中的数尽量往他最接近1--n中的位置...

未分类

codeforces 299 A. Ksusha and Array

xindoo阅读(4541)评论(0)赞(0)

题目链接 题目就是让你找出一个数组中可以将这个数组中所有数整除的数,很明显,如果存在,这个数肯定是最小的一个。 //cf 299A //2013-06-05-20.51 #include &l...

未分类

codeforces 304 B. Calendar

xindoo阅读(4432)评论(0)赞(0)

题目链接 就是给你两个日期,让你求两个日期之间差多少天。 我先算出两个日期分别是公元多少天,然后相减得到结果。 //cf 304B //2013-06-05-18.38 #incl...

未分类

codeforces 304A. Pythagorean Theorem II

xindoo阅读(4581)评论(0)赞(0)

题目链接 给你一个n,计算出1 ≤ a ≤ b ≤ c ≤ n.使得由abc构成的三角形满足勾股定理,c为斜边。 没有简单的方法,直接爆力,但是要注意,有些abc满足勾股定理的表达式,但不一定...

未分类

codeforces 289 B. Polo the Penguin and Matrix

xindoo阅读(4547)评论(0)赞(0)

题目链接 题目意思是在n*m的矩阵中,你可以对矩阵中的每个数加或者减d,求最少的操作次数,使得矩阵中所有的元素相同。 虽然在condeforces中被分到了dp一类,但完全可以通过排序,暴力的...

未分类

hdoj 4572 Bottles Arrangement

xindoo阅读(4448)评论(0)赞(0)

题目链接 虽然不知道怎么做,但是AC还是没有问题的。 大概就是循环n次,从m加到m-n/2 除了最后一个数,每个都加两次。 #include <stdio.h&g...

poj 1159 Palindrome(最长公共子串)-XINDOO
未分类

poj 1159 Palindrome(最长公共子串)

xindoo阅读(4581)评论(0)赞(0)

大概题意就是求最少添加多少个字符可以把长度为N的字符串编程回文串。 则需要最少需要补充的字母数 = 原序列S的长度 —  S和S'的最长公共子串长度 S'为原串的逆串。 关于求最长...

未分类

codeforces 302 B. Eugeny and Play List

xindoo阅读(4428)评论(0)赞(0)

题目链接 有n首歌,编号从1到n,每首歌播放时间为t,播放次数为c,n首歌按次序播放,有m个询问,输出第v分钟正在播放的歌曲编号。 很简单的二分查找,直接贴代码。 //2013-0...

未分类

uva 10340 all in all

xindoo阅读(4540)评论(0)赞(0)

题目链接 输入两个字符串s和t,判断是否可以从t中删除0个或多个字符(其他字符顺序不变),得到字符串是。 代码: //2013-05-22-07.47 #include...

未分类

UVA live 2678 - Subsequence

xindoo阅读(4499)评论(0)赞(0)

题目链接 题意:     有n个正整数组成的序列,给定一个整数s,求长度最短的连续序列,使他们的和大于或等于s。     关于这个题目,有多种的解法,如果枚举起点和终点,时间复杂度为...

未分类

hdoj 4288coder & cf 85d Sum of Medians

xindoo阅读(4459)评论(0)赞(0)

题目链接    这两个题目是一样的,大概题意是有3个操作 add x, 在集合中加入x, del x 是删除x, sum 是求出由小到大排序后所有下标mod5等于3的数的和。    这个在hd...

ACM

light oj 1258 - Making Huge Palindromes(KMP)

xindoo阅读(4434)评论(0)赞(0)

题目链接 题意:      给你一个字符串,在字符串尾部加上一些字符,使这个字符串变成一个回文串(正反读都一样的字符串),求该回文串的最小长度。 思路:      在l...

未分类

light oj 1005 - Rooks(组合数学)

xindoo阅读(4477)评论(0)赞(0)

题目链接 题意:在一个n*n的棋盘上放m个车,使得各个车之间不相互攻击。有多少种放法? 组合数学解法    现在n行中选出m行,C(n,m),再在n列中选出m列随便放A...

未分类

求最大连续子段和 的 dp算法

xindoo阅读(4483)评论(0)赞(0)

问题描述:      有n个数(以下都视为整数,浮点的也一样),每个数有正有负,现在要在n个数中选取相邻的一段,使其和最大,输出最大的和。 问题分析: &#...

未分类

HDOJ搜索题辑录I(总计100题)

xindoo阅读(4448)评论(0)赞(0)

DFS(Depth First Search ) 一般是不用hash的,所以很多时候称之为”暴力”,也就是穷举所有情况,一般看几个我们OJ的dfs的版本的题目就可以模仿着做了,因为牵涉到递归,初学者学的时候...

ACM

hdoj 1907

xindoo阅读(4546)评论(0)赞(0)

题目链接 这是一道博弈的题,准确说是尼姆博弈,只要判断各项的异或值即可。 代码 #include <stdio.h> const int maxn = 5000; in...

hdoj 1520 Anniversary party(树形dp)-XINDOO
ACM

hdoj 1520 Anniversary party(树形dp)

xindoo阅读(4426)评论(0)赞(0)

题目链接    按照等级我们可以建一颗树,如图       我们可以把一个节点当做一个人,每个节点都有一个权重。按照题目意思,如果我们取了某个节点,那么他的父节点和子节点都是不能取...

ACM

poj 并查集小结

xindoo阅读(4485)评论(0)赞(0)

并查集小结 并查集大体分为三个:普通的并查集,带种类的并查集,扩展的并查集(主要是必须指定合并时的父子关系,或者统计一些数据,比如此集合内的元素数目。) &...

未分类

hdoj 3466 Proud Merchants(01背包)

xindoo阅读(4445)评论(0)赞(0)

题目链接      这并不是一题裸的01背包,它在简单到01背包上还加了一个限制条件Q,如果没有Q,这完全是一题裸01背包。      对于这个题目,我们只要加上排序对某些物品进行优先处理就好...

未分类

hdoj 2191 背包

xindoo阅读(4481)评论(0)赞(0)

题目链接      虽然每件物品的数目并不是1,可能有多个,但我们完全可以把这个题目转化成01背包来解决。 可以把多件相同的物品合并成一件,马上就变01背包了。 #include <st...

未分类

loj 1224 - DNA Prefix

xindoo阅读(4526)评论(0)赞(0)

题目链接 题目描述很简单  有n和DNA序列,求出他们中公共前缀长度和有相同公共前缀DNA序列乘积的最大值。 If we take the subset {ACGT} then the res...

动态规划详解-XINDOO
未分类

动态规划详解

xindoo阅读(5135)评论(0)赞(0)

<span style="font-family: Tahoma; background-color: rgb(255, 255, 255);">      其实根本就谈不上详解,应该说只是随便谈谈,真正...

未分类

poj 1088 记忆化搜索||动态规划

xindoo阅读(4422)评论(0)赞(0)

   poj 1088        记忆化搜索也也是采用递归深搜的对数据进行搜索,但不同于直接深搜的方式,记忆化搜索是在每次搜索时将得到的结果保存下来,避免了重复计算,这就是所谓的记忆化。记忆...

归并树&划分树详解-XINDOO
ACM

归并树&划分树详解

xindoo阅读(4424)评论(0)赞(0)

先放一张图片 对4 5 2 8 7 6 1 3 分别建划分树和归并树 划分树如下图 红色的点是此节点中被划分到左子树的点。       我们一般用一个结构体...

未分类

Codeforces Round #178 (Div. 2)

xindoo阅读(4392)评论(0)赞(0)

A. Shaass and Oskols 题意:在n条电线上有不同数量的鸟, Shaass开了m枪,每一枪打的是第xi条电线上的第yi只鸟,然后被打中的这只鸟左边的飞到第i-1条电线上,右边的飞到i+1条...

ACM

POJ 1195 Mobile phones (二维树状树组)

xindoo阅读(4418)评论(0)赞(0)

       由于英语极差,看了半天也没看懂题目,最后参考了其他人的题解才搞懂题目,我就直接把题意贴过来了        题意:这道题目只是题意自己就去理解了半天,大概题意如下:给出i一个n*...

未分类

计算机科学中的树

xindoo阅读(4656)评论(0)赞(0)

二叉树 ▪ 二叉树 ▪ 二叉查找树 ▪ 笛卡尔树 ▪ Top tree ▪ T树 自平衡二叉查找树 ▪ AA树 ▪ AVL树 ▪ 红黑树 ▪ 伸展树 ▪ 树堆 ▪ 节点大...

ACM

hdoj 1166 敌兵布阵

xindoo阅读(4420)评论(0)赞(0)

    暴力超时,这道题可以用线段树做,因为更新的是单个节点,我们也可以用数组数组来做,我将两种方法的代码都给出     数组数组最适宜的用途就是区间求和和点的更新,但树状数组并不适用于区间的更新问题,也...

xindoo

联系我联系我们