Coco_young
- 浏览: 120343 次
- 性别:
- 来自: 湖南长沙
-
最新评论
-
5474510：
哪有源码，哪有 文本？
通信——基于Xmpp协议实现的聊天室 -
Flywarrior：
很喜欢楼主的编程风格，学习了。
POJ_2337_欧拉回路+贪心 -
igdnss：
static List<Home> symbol= ...
我的多线程小游戏——坦克大战 -
yinger_fei：
赞一个！！
我的多线程小游戏——坦克大战 -
Coco_young：
25262875 写道您好楼主，我下来试了试，服务器启动不了。 ...
通信——实现多人聊天室
文章列表
1099 - Not the Best
PDF (English)
Statistics
Forum
Time Limit:2 second(s)
Memory Limit:32 MB
Robin has moved to a small village and sometimes enjoys returning to visit one of his best friends. He does not want to get to his old home too quickly, because he likes the scenery al ...
- 2012-05-25 01:37
- 浏览 607
- 评论(0)
这里的第K短路的定义是：
1.如果起点终点相同，那么0并不是最短路，而是要出去一圈回来之后才是最短路，那么第K短路也是一样。
2.每个顶点和每条边都可以使用多次。（可以存在环和来回走）
然后求K短路使用A*算法，其估价函数f(n) = g(n)+h(n)，h(n)是终点到结点n的最短路径，g(n)是起点到结点n的实际代价， 这样选择显然能满足A*估价函数的要求，g(n)>=g'(n)，
h(n)<=h'(n)。
h(n)可以对原图的逆图进行SPFA得出。
终止条件是，如果终点第K次出队的话，那么表明已经找到第K短路。
注意处理起点终点不连通的情况。
很裸的K短路题 ...
- 2012-05-25 01:32
- 浏览 1075
- 评论(0)
求最短路。。。 要多水就有多水，刷水的感觉很差，很少用SPFA，所以算是练习下SPFA把。。
传送门：http://lightoj.com/volume_showproblem.php?problem=1019
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 111;
i ...
- 2012-05-24 01:26
- 浏览 675
- 评论(0)
一.动态规划
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
推荐题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
简单http://acm.pku.edu.cn/JudgeOnline/problem?id=2288
中等，经典TSP问题http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
中等，状态压缩DPhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1112
中等
- 2012-05-24 01:01
- 浏览 653
- 评论(0)
传送门：http://lightoj.com/volume_showproblem.php?problem=1210
1210 - Efficient Traffic System
PDF (English)
Statistics
Forum
Time Limit:2 second(s)
Memory Limit:32 MB
I was given the task to make all the major two way roads in Bangladesh into one way roads. And I have done ...
- 2012-05-24 00:55
- 浏览 713
- 评论(0)
传送门：http://lightoj.com/volume_showproblem.php?problem=1034
1034 - Hit the Light Switches
PDF (English)
Statistics
Forum
Time Limit:2 second(s)
Memory Limit:32 MB
Ronju is a night-guard at the "Lavish office buildings Ltd." headquarters. The office has a large gras ...
- 2012-05-22 01:14
- 浏览 921
- 评论(0)
昨天熬夜做了人生的第二场SRM，还是有所收获的，总结总结。
250：
超级简单的题，读懂题意就基本上出来了。
500：
一道考异或操作的题，给定一个整数区间[L,R]，要求计算L XOR L+1 XOR L+2 XOR ...... XOR R 的值，L,R可以在1-4000000 ...
- 2012-05-20 12:39
- 浏览 714
- 评论(0)
转自：http://hi.baidu.com/acmjordan/blog/item/3fd0bcc9f7f4605c0fb345dd.html
供自己看以及训练：
路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
可以用Dijkstra解决问题的特征
负边权最短路径
Bellman-Ford
Bellman-Ford的Yen-氏优化
差分约束系统
Floyd
广义路径问题
传递闭包
极小极大距离/极大极小距离
Euler Path / Tour
圈套圈算法
混合图的Euler Path / Tour
Ham ...
- 2012-05-19 23:22
- 浏览 578
- 评论(0)
题目链接：http://lightoj.com/volume_showproblem.php?problem=1183
1183 - Computing Fast Average
PDF (English)
Statistics
Forum
Time Limit:2 second(s)
Memory Limit:64 MB
Given an array of integers (0indexed), you have to perform two types of queries in the array.
1.1 i j v- ch ...
- 2012-05-18 09:21
- 浏览 738
- 评论(0)
传送门：http://lightoj.com/volume_showproblem.php?problem=1120
1120 - Rectangle Union
PDF (English)
Statistics
Forum
Time Limit:2 second(s)
Memory Limit:64 MB
Given some axis parallel rectangles, you have to find the union of their area. For example, see the shaded regions in ...
- 2012-05-18 01:52
- 浏览 798
- 评论(0)
传送门：http://lightoj.com/volume_showproblem.php?problem=1207
题意：区间染色，询问区间中不同颜色的总数，这题实际上是POJ 上 Mayor poster 的削弱版，不需要离散化（那题的离散化要特殊处理），直接建树+成段更新+query即可。（需要简单哈希一下）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 100010;
int t,n,has ...
- 2012-05-18 01:25
- 浏览 660
- 评论(0)
题意：给定N个海报，海报中间被挖掉了一个矩形的孔，所有的海报贴在(0,0)-(50000,50000)的矩形区域里，求海报覆盖的面积。
思路：把1个海报分成四个小矩形，求矩形面积并。（很裸）
各种蛋疼：
1.建立段树一定要记得加判断，对于插入一个点的情况不予考虑（比如插入区间为0,0）或者在线段树里面加判断(l==r-1)return;（不加的话等着StackOverFlow吧）
2.不知为何，这个题一定要unsigned int才能过。。（long long __int64）都不可以，我蛋碎了。
代码：
#include<iostream>
# ...
- 2012-05-17 12:21
- 浏览 718
- 评论(0)
昨天晚上和瑞瑞约好一起做CF，然后在23:30的时候兴冲冲的开始搞起，打开A题，读完了以后发现很水，于是马上开始敲。敲完一交----judgement fail 我擦，什么情况，什么情况，一看status发现CF又崩溃了。。。。蛋碎。
后来CF发了个通知说是不算Rating了，然后所有的提交重新开始judge，于是我又看了下B题，B题也很水，于是又敲了一下下。交上去了inqueue。。。。
最后看了C题，发现C题其实也很水，一个递归就完了。。（不过晚上真是木有精神啊，搞了半天还没写出来，然后CF就结束了，不能交题了，今天中午回来交，各种悲剧啊尼玛，在DFS的时候写出了各种BUG）
...
- 2012-05-17 11:39
- 浏览 399
- 评论(0)
题意：求矩形周长并。
总结：这道题也算是很经典的一道扫描线题吧，就是陈宏论文上面提到的那道IOI的试题，也算试了一下用扫描线法求矩形的周长并.
注意点：1.几个必须要的域，cnt-区间被线段覆盖的次数，sum-测度，seq-连续段数，lbd-是否包含区间的左边界，rbd-是否包含区间的右边界，其中lbd,rbd是为了求得seq的。
2.理解线段插入删除的思想。//为什么在这里不需要把信息传给子节点，这里需要进一步理解。
3.理解如果更新上述的几个域.
4.如何根据测度信息和连续段数信息计算答案。//需要进一步理解
各种蛋疼：1.注意求X方向的周长与求Y方向的周 ...
- 2012-05-16 00:18
- 浏览 851
- 评论(0)
题意：求矩形面积并
前天直接用“矩形切割”（我也不知道我那方法是不是矩形切割，姑且打上引号吧），过掉了这个题，那个猥琐的算法达到了O(n^3)，如果题目数据很大的话，还是不行的，所以这两天还是继续学习扫描线，发现网上的很多文章讲的都不算很清楚，于是翻除了1999年陈宏的论文，开始研究，最终总算搞定了扫描线这个玩意儿。
注意点：要理解论文中提到的测度（即线段并的长度）和连续段的含义（求矩形周长并需要用到），这两点很关键，然后建树的时候用段树比较好一点，用点树我还没想到这么处理，建段树的话，数组稍微开大点（最好是5倍左右），否则会悲剧的。。
各种蛋疼：最后忘记去掉freopen.. ...
- 2012-05-15 14:38
- 浏览 518
- 评论(0)