[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks
传送门:
1019:直线染色,离散化后直接做
1028:经典问题,先按x坐标第一关键字,y坐标第二关键字排序,然后线段树/树状数组/平衡树都行
1037:优先队列维护靠前的空间,单调队列维护删除
1067:改造版Trie+DFS
1090:经典逆序对问题,树状数组/线段树/归并排序
1097:离散化后暴力
1100:惟一的玄机就是stable_sort
1126:固定的一个序列里面RMQ,S-T/优先队列/线段树……
1147:开1000个线段树硬搞,n^2logn,空间卡的很紧
1220:貌似简单的问题,1000个栈,操作100000次就是push和pop,
很容易想到的裸做法是:int data[100000] 表示每个数据,int fa[100000]表示每点在栈里的父亲,int top[1000]表示1000个栈顶坐标
但是内存卡的很死很死,开200000个int是超的……
鉴于fa里的数据大小<=100000<17Bit,int的前15个Bit实际上浪费了,压缩一下,将100000个int压成了100000*17/32=52000个大概,过了
1306:求序列中位数,但是不给你存下所有数的空间,用一个大小为N/2+1的堆搞定……
1316:BST里插入删除Rank
1350:纯水
1414:用set和lower_bound水……
1439:初始一个集合1000000000个数,10000个操作:删除和查询第k大,由于操作不多,反其道而行之,用BST存储删除的值,查询第k大时应用二分+BST的rank
1470:三维树状数组
1471:树上两点间距离,DFS+LCA
1494:没读懂,上网查的,原来是判断一个序列能否由一个栈以及12345.....n的序列生成……直接搞
1521:Joesph问题,可线段树解决(忘了数学方法了)
1523:K-逆序对问题,按照他的定义,重复使用经典逆序对算法就行
1542:先把字符串排序,然后对一个前缀,用二分定区间,然后在区间里面线段树,线段树里存10个最大频率,我优化到了0.3S左右……求更快
1613:给你一个序列以及若干查询,问某数是否在区间【L,R】间出现过
STL的应用:map<int,set<int> >,对每个数维护一个出现集合,然后对每个查找,如果该数不在Map里,肯定没有,如果在的话,在set里进行lower_bound,查找出现集合和区间【L,R】有没有交
想法其实没错,但是TLE了,后观察到这东西本来插入时是1~N走的,本来就有单调性,不用Set,用vector就行,改后AC
1628:30000*30000的地图里,分布着60000个黑点,求空白线段数量,vector+二分,注意题意:答案为1*L和L*1(L>=2)的块数+1*1的块数
1650:按照题意用set、map之类的模拟水过
1654:给一个字符串,每次都消掉两个相邻且相同的字母,求最后得到的串,其实就是括号匹配,一个栈搞定
1671:给出一个图,给出一系列边,按顺序拆掉,问每拆掉一个边后图里有几个联通块
逆向思考,用并查集维护,把没拆的边先加入图里,然后倒着来,一一加上边,维护联通块个数
posted on 2010-10-02 00:03 sweetsc 阅读(358) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: