博客首页 → ACM

最新文章列表

[SPFA]hdoj 3790：最短路径问题

大致题意：    给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。   大致思路：    最短路稍稍变形，加入一个val限制即可   #include<iostream> #include<cmath> #include<cstdio> #inc ...
最短路图论acmhdoj 3790bbezxcy 
暴风雪 评论(0) 有2426人浏览 2012-04-07 19:20

bbezxcy-ACM/ICPC模版(图论+字符串部分)

bbezxcy-ACM/ICPC模版已整理完成，下载后解压即可。求试用，求改错，求补充，求完善，各种求Orz…… 没有iteye账号的可以把这张图片另存为到电脑上，再把扩展名改为rar即可    
代码acmicpcbbezxcy模版 
暴风雪 评论(2) 有1819人浏览 2012-04-07 09:21

[无向图全局最小割]zoj 2753：Min Cut (Destroy Trade Net)

大致题意：    给出一个无向图，求移除权值最少的边使得这个图被分为两个连通块。   大致思路：     裸的StoerWagner模版题，在神牛的博客瞎逛的时候看到了，就刷掉吧……希望不要降RP     #include<iostream> #include<cstdio> #include<cstring> using namespace s ...
无向图全局最小割zoj 2753acm数据结构图论 
暴风雪 评论(0) 有1917人浏览 2012-04-02 17:11

[点双连通分量-奇环判定]poj 2942：Knights of the Round Table

大致题意：     给出一个无向图，求出这个图的补图G。求出在G中存在多少个点使得这些点不属于任何一个奇环中。   大致思路：    这道题从一开始就是个杯具！先是把题目想成边的双连通分量做，狂哇。后来用割点的模版照着网上的代码改造出一个点双连通分量的代码，依然哇！！原因是同一个点可能属于不同的点双连通分量！！   后来把搜索染色的过程加到Tarjan里面，还是哇！！检查出来原因是搜索u的时候 ...
点双连通分量poj 2942acm数据结构图论 
暴风雪 评论(0) 有2571人浏览 2012-03-30 22:14

[后缀数组]poj 3729：Facer’s string

大致题意：     给出两个字符串a,b和一个数字k，求出a中存在多少后缀，使得其和b中所有后缀的lcp的最大值等于k。   大致思路：    又弱智了的说，上来就用后缀数组+RMQ来爆，O(n^2)的效率果断TLE了，不要bs我……在网上看到的正解是先求出a中存在多少后缀，使得其和b的所有后缀的lcp最大值大于等于k，再求出a中存在多少后缀，使得其和b的所有后缀的lcp最大值大于等于k+1。 ...
后缀数组poj 3729Facer’s stringacm数据结构 
暴风雪 评论(0) 有1579人浏览 2012-03-28 17:11

[最长公共子串-后缀数组]hdoj 1403：Longest Common Substring

大致题意：    如题。   大致思路：    后缀数组+二分的简单应用，可以扩展到多串匹配中去   #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int nMax = 500000; int num[nMax]; i ...
最长公共子串后缀数组hdoj 1403acm数据结构 
暴风雪 评论(0) 有1257人浏览 2012-03-27 20:48

[后缀数组]hdoj 4080：Stammering Aliens

大致题意：     给出一个数字m和一个字符串str，求出str中至少出现m次的最长的子串长度，并且求出这些子串中最靠右的子串的位置。   大致思路：    先求出后缀数组，二分枚举这个长度mid，然后分析height数组的每个大于mid的区间。过程稍复杂，具体看我代码即可。   #include<iostream> #include<cstdio> #i ...
后缀数组hdoj 4080acm数据结构字符串 
暴风雪 评论(0) 有1028人浏览 2012-03-27 12:54

[后缀数组]hdoj 3518：Boring counting

大致题意：    给出一个字符串，求出所有不重叠出现次数大于等于两次的子串的数目。   大致思路：    后缀数组的好题，思想很妙也很难想到。大致过程就是先枚举子串的长度tmp，对于每一个height值大于等于tmp的区间内找到sa的最大值和最小值，看他们之间的距离是否小于tmp，是的话则ans++；   #include<iostream> #include<cs ...
后缀数组hdoj 3518Boring countingacm数据结构 
暴风雪 评论(0) 有1100人浏览 2012-03-26 17:07

【拓扑+DP】HDU 4109 Instrction Arrangement

KIDx的解题报告   题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4109 题意：输入点数n[编号0到n-1]和关系数，输入a，b，c，表示a操作做完后第c纳秒可以做b，问所有操作搞完至少花多长时间？   Sample Input 5 2 1 2 1 3 4 1  
ACMKIDxC++编程算法 
基德KID.1412 评论(0) 有1470人浏览 2012-03-25 23:34

HDU1000

HDU 1000 注意：1、不止有一组测试数据，所以用while   #include<stdio.h> int main(){ int a,b; while (scanf("%d %d",&a,&b)==2){ printf("%d\n",a+b); } ret ...
acmHDUACM 
麦蒂小东 评论(0) 有991人浏览 2012-03-24 02:03

[网络流]hdoj 3251：Being a Hero

大致题意：    给出一个由n个点，m条边组成的有向图，给出切掉每条边的花费。给出f个点和得到这个点的收益值。现在要割掉一些边是的1点和某些城市分开，同时你会得到相应的收益值。求总收益的最大值。   大致思路：     网络流经典构图……   #include<iostream> #include<cstring> #include<cstdio&g ...
网络流hdoj 3251acm数据结构图论 
暴风雪 评论(0) 有1135人浏览 2012-03-22 16:15

[模拟+并查集]poj 1164：The Castle

大致题意：    见http://www.nocow.cn/index.php/Translate:USACO/castle   大致思路：    苦逼模拟的并查集……usaco里面的还需要输出炸哪一堵墙……崩溃>_<   /* ID:123ldss2 PROG: castle LANG: C++ */ #include<iostre ...
并查集poj 1164acm数据结构算法 
暴风雪 评论(0) 有1125人浏览 2012-03-19 18:35

[最小割]hdoj 2435：There is a war

大致题意：    给出一个有向带权图，设1为源点，n为汇点。现在要在2~n-1的点中加上一条容量为无穷的边使得这个图的最小割最大。求加上这条边后最小割最大是多少。   大致思路：    先对原图求一遍最小割，割值为maxflow，在残余网络中分别找到两个点a,b，使得从1点到a的最大流值最大，为flowA，从b点到n点的最大流最大，为flowB。然后用maxflow+min(flowA,flow ...
最小割hdoj 2435acm数据结构图论 
暴风雪 评论(0) 有1092人浏览 2012-03-19 14:21

[后缀数组]ural 1590：Bacon’s Cipher

大致题意：     给出一个字符串，求这个字符串有多少个不同的子串。   大致思路：     用后缀数组对这个字符串的所有后缀进行排序，然后依次根据每个后缀和排在他后面的那个后缀讨论即可。   #include<iostream> #include<cstdio> #include<cstring> using namespace std; ...
后缀数组ural 1590acm数据结构字符串 
暴风雪 评论(0) 有1479人浏览 2012-03-18 17:32

[USACO] Chapter1-Getting started(入门)

Greedy Gift Givers (gift1)    /* ID:123ldss2 PROG: gift1 LANG: C++ */ #include<iostream> #include<cstring> #include<cstdio> #include<fstream> #include<cmath> ...
usacoacm数据结构 
暴风雪 评论(0) 有899人浏览 2012-03-15 10:18

[字符串最长回文子串]hdoj 3068：最长回文

大致题意：    给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度。大致思路：    这题用后缀数组超时了……囧rz。其实这里用的是manacher算法，效率为O(n)，比后缀数组的O(log n)要高。 算法详见http://blog.csdn.net/tanhaiyuan/article/details/7091019 #include<ios ...
hdoj 3068最长回文acm数据结构字符串 
暴风雪 评论(0) 有2334人浏览 2012-03-13 21:42

最近博客热门TAG

Java(141741) C(73643) C++(68602) SQL(64557) C#(59604) XML(59131) HTML(59042) JavaScript(54916) .net(54782) Web(54511) 工作(54116) Linux(50906) Oracle(49861) 应用服务器(43285) Spring(40811) 编程(39452) Windows(39380) JSP(37540) MySQL(37266) 数据结构(36420)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics