Coco_young
- 浏览: 120658 次
- 性别:
- 来自: 湖南长沙
-
最新评论
-
5474510：
哪有源码，哪有 文本？
通信——基于Xmpp协议实现的聊天室 -
Flywarrior：
很喜欢楼主的编程风格，学习了。
POJ_2337_欧拉回路+贪心 -
igdnss：
static List<Home> symbol= ...
我的多线程小游戏——坦克大战 -
yinger_fei：
赞一个！！
我的多线程小游戏——坦克大战 -
Coco_young：
25262875 写道您好楼主，我下来试了试，服务器启动不了。 ...
通信——实现多人聊天室
文章列表
题意：求矩形面积并
分析：本来是要学习扫描线的，不过还没看懂。。囧。。在看了黑书之后，发现这题数据规模如此小（100个矩形），于是YY出了一种方法：
1.首先把X，Y坐标都进行离散化。
2.离散化之后，将整个平面划分成很多面积不等的小矩形。
3.枚举每个大矩形，得到大矩形离散化后的左上角点和右下角点的位置。
4.把每个小矩形标记为c[i][j]表示第i行第j列个矩形是否已经被计算过，那么在大矩形中枚举其包含的所有小矩形，如果小矩形未被包含着总面积增加小矩形的面积，并标记该小矩形。
各种蛋疼：1.自己2B的把左移写成右移，结果数组开小了，检查了半天。。。
2.POJ上面 ...
- 2012-05-14 00:48
- 浏览 646
- 评论(0)
关键句：我还是弱爆了，又是这种感觉，无助的感觉。
其实这个结果也算是意料之中，毕竟我和队友还是没有一起做过一次Contest，各方面都很欠缺。
开始回顾历史：
A. 很水的一道题，直接模拟即可，当时很快就A了，貌似是全场第一个气球。。
B.一道dp题，把二维最长公共子序列上升到了三维，其实状态转移基本没变，于是也很快1Y了。
C.看了下，英文题，比较长，于是我先放了，让队友读。后来队友描述题意是，给定N个人，N个开关，初始时开关都是0，每个人能够改变一些开关的值（具体开关的编号由数据给出），问使得所有的开关都变成1的最少的人数组成的操作序列（1,2,3表示第一个人先 ...
- 2012-05-13 23:49
- 浏览 625
- 评论(0)
1266 - Points in Rectangle
PDF (English)
Statistics
Forum
Time Limit:2 second(s)
Memory Limit:32 MB
As the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-or ...
- 2012-05-11 12:48
- 浏览 647
- 评论(0)
1085 - All Possible Increasing Subsequences
PDF (English)
Statistics
Forum
Time Limit:3 second(s)
Memory Limit:64 MB
An increasing subsequence from a sequenceA1, A2... Anis defined byAi1, Ai2... Aik, where the following properties hold
1.i1< i2< i3< ... < ikand
2 ...
- 2012-05-11 11:50
- 浏览 904
- 评论(0)
最近一直搞专辑，所以没写啥解题报告，今天终于搞完了一个，小结一下下
题目来源，LightOJ，在Problem Category里的Graph Theory里的Articulation/Bridge/Biconnected
Component
1026 - Critical Links
裸题，找桥用tarjan算法即可解决
代码：
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using ...
- 2012-05-04 16:02
- 浏览 1860
- 评论(0)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024
题目大意：略
状态为：dp(i,j)，表示包含a[j]的前j个数划分成i段时的最大值。
基本的状态转移方程为：dp(i,j) = max{dp(i,j-1)+a[j],max{dp(i-1,k)}+a[j]}, 1<=i<=m, i<=j<=n, i-1<=k<j
如何理解上述状态转移方程：dp(i,j-1)+a[j],表示第i段包含住a[j],(a[j]不是第j段的开头),max{dp(i-1,k)}+a[j],表示第i段以a[j]为开头。
上述 ...
- 2012-04-17 01:05
- 浏览 525
- 评论(0)
题目来源：HNU
http://acm.hnu.cn/online/?action=problem&type=show&id=12301&courseid=214
题目大意：给定一个数字(0-9)序列，没有前导0，要求你求出所有这样的连续子序列，即该子序列为11的倍数（0不算），序列长度可以达到80000
分析：要求解的实际上是两个子问题，1.如何判断一个序列能整除11，2.如何求出所有的这种序列。很容易想到，枚举起点终点，然后做大数取模，如果能整除11，那么记录下来，这样做的复杂度能达到O(n^3)，显然会超时。那么，这里需要用到一个结论：在Radix进制下的数 ...
- 2012-04-16 01:01
- 浏览 634
- 评论(0)
什么是Catalan数
说到Catalan数，就不得不提及Catalan序列，Catalan序列是一个整数序列，其通项公式是我们从中取出的就叫做第n个Catalan数，前几个Catalan数是：1,
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, …咋看之下没什么特别的，但是Catalan数却是许多计数问题的最终形式。
Catalan数的一些性质
Catalan数的基本公式就是上个部分所列出的那样，但是却有一些变形和具体的性质：
1、
这 ...
- 2012-04-15 01:35
- 浏览 544
- 评论(0)
SPFA与堆优化的Dijkstra的速度之争不是一天两天了，SPFA用在分层图上会比较慢。SPFA是按照FIFO的原则更新距离的，没有考虑到距离标号的作用。实现中 SPFA 有两个非常著名的优化：SLF
和 LLL。 SLF：Small Label First 策略。
实现方法是，设队首元素为
，队列中要加入节点
- 2012-04-15 00:40
- 浏览 525
- 评论(0)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007
题目大意：在平面上有N个点，求出两点之间距离的最小值/2，就是结果.
算法详细介绍：http://blog.csdn.net/guyulongcs/article/details/6841550，这里讲得很清楚。
也就是一个很裸的算法题吧，要求用O(nlogn)的算法求出最近点对，翻了翻算法导论，看完了上面用分治法解答，自己实现的时候有几个点需要注意：
1.如果每次递归求解的时候，开出新的数组来保存，集合Sy的划分，那么一定会MLE，看了别人的代码后，发现可以用先分解，再归并，那么 ...
- 2012-04-13 20:03
- 浏览 812
- 评论(0)
题目链接：http://poj.org/problem?id=2761
题意：给定一个序列，有N个数，给定M个询问，询问的形式为 a b c ，询问区间[a,b]内第c小的数。
解题方法：一次性读入所有的询问，然后把询问进行排序，排序的顺序为终点小的在前，终点一样，起点大的在前，然后对排序后的每个询问进行处理，每次保证SBT中只有区间[a,b]的数（用插入和删除操作来保证），然后查询第K小。
总结：注意旋转操作调整size域的顺序。 不能搞反。
代码：
#include<iostream>
#include<cstdio>
#include<algori ...
- 2012-03-29 13:16
- 浏览 649
- 评论(0)
题目还是牛耳杯程序设计大赛的D题，之前已经描述过，就不在赘述了。
之前用AVL实现的，这里附上一个用SBT实现的版本，对比发现SBT实现更为简单，而且时空消耗略少。
搓长丑的SBT代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<memory.h>
#include<ctime>
using namespace std;
const int MAXN = 100010;
struct KEY
{
int wgt;
int n ...
- 2012-03-27 20:11
- 浏览 617
- 评论(0)
题目描述：
BallsInTheBox
Timelimit:1sMemorylimit:32768kb
ProblemDescription
ThereareNboxesinStaginner’shouse,andwemarkthemby1,2,…,N.ThereareNi(1<=Ni<=10^4)ballsintheboxiinitially.NowStaginnerwilldosomeoperations,andhewillaskyousomesimplequestions.
Theoperationscontain:
1.Cij:take ...
- 2012-03-27 11:55
- 浏览 708
- 评论(0)
最短路径的算法及其应用：
算法有很多，包括上面没有讲到的和讲到的：
SSSP（单源最短路径）：1.标号法 2.Dijkstra(可以用heap优化) 3.Bellman_ford(可以检测负环) 4.SPFA(可以检测负环,还可以继续优化，不过还没学)
所有点对的最短路径：1.可以求N次SSSP 2.Floyd算法
该章提到的应用问题：
1. 求图的中心点：
中心点定义：找出一个顶点，使得其到所有其他的顶点的最短路径的最大值最小。
求法：求出所有顶点对的最短路径，求出每个顶点到其他所有顶点的最短路径的最大值，从中选出最小的那个，用Floyd算法求解，时间复杂度为 ...
- 2012-03-21 15:22
- 浏览 522
- 评论(0)
吴文虎图论中的一个求最短路的方法
只需要O(ElogE)的时间复杂度就可以求出单源结点的所有最短路径, 实现的时候使用优先队列来维护可选的弧集,代码如下:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 110;
struct gnode;
vector<gnode> g[MAXN];
int mark[MAXN],d[MAXN];
struct gnode
{
int v,val;
};
struct ...
- 2012-03-19 12:29
- 浏览 517
- 评论(0)