- 博客(360)
- 资源 (3)
- 收藏
- 关注
RSS订阅
转载 POJ题目分类
转自：Kuangbin的博客初期:一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,
2015-01-14 15:24:08
829
原创 线段树题目总结
一、单点更新 1.hdu1166 敌兵布阵：有N个兵营，每个兵营都给出了人数ai（下标从1开始），有四种命令，（1）”Addij"，表示第i个营地增加j人。（2）“Sub i j”，表示第i个营地减少j人。（3）“Query ij"，查询第i个营地到第j个营地的总人数。（4）”End“，表示命令结束。解题报告Here。 2.hdu1754 I Hate It：给
2014-10-05 08:13:49
2769
1
原创 线段树之入门篇
线段树(interval tree) 是把区间逐次二分得到的一树状结构，它反映了包括归并排序在内的很多分治算法的问题求解方式。 上图是一棵典型的线段树，它对区间[1,10]进行分割，直到单个点。这棵树的特点是：1. 每一层都是区间[a, b]的一个划分，记 L = b - a2. 一共有log2L层3. 给定一个点p，从根到叶子p上的所有区间都包含点p，且其他区间都不包
2014-10-02 07:42:29
2360
原创 通过金矿模型介绍动态规划（讲得真心不错～～～）
通过金矿模型讲动态规划----第一节----初识动态规划-------- 经典的01背包问题是这样的： 有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？[对于每个物品不可以取多次，最多只能取一次，之所以叫
2014-07-24 09:40:11
1482
原创 Windows7和linux双系统安全删除linux
1.下载MbrFix，解压，将MbrFix.exe拷到C:\Windows\System32下2.在开始》所有程序》附件》中，找到 命令提示符，右键，通过管理员权限（直接打开，权限不够，无法修复mbr）打开3.在命令提示符中输入MbrFix /drive 0 fixmbr /yes4.重启电脑，直接进到windows5.找到linux系统所在的磁盘，
2016-02-25 21:40:28
627
原创 2014ACM/ICPC亚洲区广州站 && HDU Song Jiang's rank list （排序）
Song Jiang's rank listTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 805 Accepted Submission(s): 410Problem Description《Shui Hu Zh
2015-10-04 16:01:17
607
原创 弱校联萌十一大决战之强力热身 J. Right turn （模拟）
J. Right turnTime Limit: 1000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: MainSubmit Statusfrog is trapped in a maze. The maze is infinitely large and divided into gri
2015-10-03 17:39:04
1135
原创 弱校联萌十一大决战之强力热身 E. Rectangle （规律）
E. RectangleTime Limit: 1000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: MainSubmit Statusfrog has a piece of paper divided into n rows and m columns. Today, she would
2015-10-03 15:38:30
1158
原创 弱校联萌十一大决战之强力热身 C. Censor （KMP + stack）
C. CensorTime Limit: 2000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: MainSubmit Statusfrog is now a editor to censor so-called sensitive words (敏感词).She has a lon
2015-10-03 13:19:37
1259
原创 弱校联萌十一大决战之强力热身 B. Carries （二分）
B. CarriesTime Limit: 1000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: MainSubmit Statusfrog has n integers a1,a2,…,an, and she wants to add them pairwise.Unfortun
2015-10-02 18:18:13
1220
原创 弱校联萌十一大决战之强力热身 A. Easy Math （水）
A. Easy MathTime Limit: 2000msMemory Limit: 65536KB 64-bit integer IO format: %lld Java class name: MainSubmit StatusGiven n integers a1,a2,…,an, check if the sum of their square root √a1+√a2+⋯+
2015-10-02 17:28:04
771
原创 2013 ACM-ICPC吉林通化全国邀请赛 && HDU 4493 Tutor （水）
TutorTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 3411 Accepted Submission(s): 910Problem DescriptionLilin was a student of Tonghu
2015-10-02 16:45:28
838
原创 2013 ACM-ICPC吉林通化全国邀请赛 && HDU 4499 Cannon （搜索）
AC代码：#include using namespace std;int n, m, q;int g[10][10];int ans;void dfs(int x, int y, int cnt){ if(x >= n){ //搜索结束 ans = max(ans, cnt); return ; } if(y >=
2015-10-02 15:33:57
617
原创 UVA 10891 Game of Sum （博弈论 + 区间dp）
Game of SumTime Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %lluSubmit StatusDescriptionThis is a two player game. Initially there are n integer numbers in an array and pl
2015-10-02 14:27:39
528
原创 2013 ACM-ICPC吉林通化全国邀请赛 && HDU 4597 Play Game （博弈 + 区间dp）
Play GameTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1185 Accepted Submission(s): 685Problem DescriptionAlice and Bob are playing
2015-10-02 12:59:18
860
1
原创 2013 ACM-ICPC吉林通化全国邀请赛 && HDU 4496 D-City （并查集）
题目链接：D-City解析：一般的思路应该是先将任意两点之间不在询问中的各边连起来，然后再按照倒序将询问的边一个一个加入并查集，同时记录联通块数即可。但是，这样试了一下，老是MLE和TLE，这题能卡住这种常规的做法。因为题意没这么复杂。。。仔细读题才发现：最后会将所有的边都删去，也就是说，最后一定是n个联通块，而且所有边都删除之后，则倒着操作的起始并查集里没有有一条边。然后就可以向
2015-10-01 16:42:40
765
转载 19个必须知道的Visual Studio快捷键
英文原文：19 Must-Know Visual Studio Keyboard Shortcuts 本文将为大家列出在 Visual Studio 中常用的快捷键，正确熟练地使用快捷键，将大大提高你的编程工作效率。 项目相关的快捷键 Ctrl + Shift + B = 生成项目 Ctrl + Alt + L = 显示 Solution Explore
2015-09-27 23:21:27
422
原创 HDU 2102 A计划 （BFS + 预处理）
题目链接：A计划解析：三维的搜索，但是只有两层。先将地图预处理：两层对应位置都是‘#’的和一层是‘#’一层是‘*'的，两层都处理成’*‘。再bfs即可。AC代码：#include #include #include #include #include using namespace std;char mz[2][12][12];bool
2015-09-11 07:29:37
473
原创 HDU 2181 哈密顿绕行世界问题 （DFS）
题目链接：哈密顿绕行世界问题解析：将每个点的相邻三个点按字典序存放，直接dfs即可。AC代码：#include using namespace std;int city[30][5];int vis[30];int pre[30];int m;int cnt;void print_ans(int cur){ if(cur !=
2015-09-09 19:51:45
541
原创 HDU 3567 Eight II （A*）
题目链接：Eight II解析：还是八数码问题，当然还是Ａ*了，只不过这次要加上预处理才行。先枚举出‘Ｘ’的位置，然后用前驱表保存所有情况然后直接回溯就行了，不用再搜了。ＡＣ代码：#include #include #include #include #include #include #include using namespac
2015-09-08 15:32:13
1293
3
原创 HDU 1043 && POJ 1077 Eight （Ａ*）
题目链接：HDU 1043 POJ 1077解析：Ａ*算法搜索中选择路径的条件：f = g + hg：搜索深度h：当前状态所有格点与目标状态对应格点曼哈顿距离。（曼哈顿距离：横纵坐标差值的绝对值之和）中间还有一个剪枝：只有起始状态和目标状态的奇偶性相同时，才有解，否则，直接输出无解。ＡＣ代码：#inc
2015-09-07 13:08:18
585
原创 hihoCoder挑战赛14-1224
题目链接：赛车解析：用down[]数组记录每个节点能向下走得最大深度，然后再枚举两个不在同一集合内的两点连接（若在同一集合，则会成环）。AC代码：#include #include #include #include using namespace std;int first[100005], nxt[100005], to[100005], e;
2015-08-31 19:17:01
675
原创 hihoCoder挑战赛14-1223
题目链接：不等式解析：直接枚举C的位置，然后判断所有C中所满足的最大个数。注意C没有讲是整数，所以枚举要+0.5实话说，我也不懂为什么枚举实数要这样枚举。。。AC代码：#include #include #include #include using namespace std;struct Node{ string p; d
2015-08-31 16:18:28
847
原创 ubuntu14.04下的chromium安装flash插件
在尝试很多网上的方法，大多数是拷贝 libflashplayer.so，尝试之后，时而有用，时而又不行了。最后还是从大牛处找到了命令。打开terminal:sudo apt-get install pepperflashplugin-nonfreesudo update-pepperflashplugin-nonfree --install成功解决～
2015-08-28 14:03:01
573
原创 FZU 2150 Fire Game （DFS + BFS）
题目链接：Fire Game题意：一块n*m的矩形中，‘#’代表是草，‘.'代表空地，空地点不着火。两个人同时开始点火，问最短多少时间能把所有草地点着，不能输出’-1‘。解析：先用dfs预判断草地的连通块数，超过2则无法全部点燃任选两个草地作起点，两者看作是一个整体，用bfs搜到起点到所有草地的最短时间，然后保留其中最长的时间在所有的最长时间中，选择最短的，即为所求。
2015-08-26 17:03:18
783
原创 POJ 3087 Shuffle'm Up （DFS）
题目链接：Shuffle'm Up题意：有a和b两个长度为n的字符序列，现定义操作：将a、b的字符交叉合并到一个序列c，再将c最上面的n个归为a，最下面n个归为b给出a，b和目标序列c，问最少多少次操作a、b转化为c解析：将a、b放入哈希表，然后模拟操作过程直接dfs即可。AC代码：#include #include #include
2015-08-25 21:36:58
718
原创 POJ 3126 Prime Path （BFS）
题目链接：Prime Path解析：两个长度为4的数字s和e，操作定义为：每步只能改变一位数字，并且改变后的数字必须为素数。问s最少经历多少次操作能变成e。先预处理筛出10000以内的素数每次操作可以对4个数字中的一个操作对于每个数字有10种可能性AC代码：#include #include #include #include #in
2015-08-25 09:55:49
577
原创 POJ 3414 Pots （DFS || BFS）
题目链接：Pots解析：给定两个水瓶的大小a和b，以及目标c，输出最短操作使某一水瓶中剩下c容量的水。操作包括倒空、倒满、两瓶互相倒。解法一：DFS枚举每次可行的方案，并对枚举的上限做了限制，即如果当前的枚举次数已经大于目前最小次数解就剪枝。AC代码：#include #include #include using namespace std;
2015-08-24 13:00:18
673
原创 HDU 1495 非常可乐 （DFS）
题目链接：非常可乐解析：一个瓶子，容量为s，两个杯子，容量分别为n和m，问最少多少次倾倒才能将一瓶可乐均分为两份。直接模拟每次的倾倒，然后递归求解。可以加个预判的条件，要是s是奇数的时候，无论如何也是分不均的。AC代码：#include #include #include using namespace std;int s, n, m, ans
2015-08-23 20:22:48
952
原创 HDU 1241 Oil Deposits （DFS）
题目链接：Oil Deposits解析：问有多少个“@”块，其中每个块内的各个“@”至少通过八个方向之一相邻。直接从“@”的地方开始向相邻八个方向搜索，每搜到一个格子，就将它替换成“.”，一次搜索就会搜索完一个块，记录搜索的次数为答案。AC代码：#include #include #include using namespace std;char
2015-08-23 17:33:18
515
原创 HDU 2612 Find a way （BFS）
题目链接：Find a way解析：使用两次bfs从“Y”和“M”的位置分别使用bfs搜出各自到所有“@”点的最短时间在遍历所有“@”点，求出最小的最短时间。AC代码：#include #include #include using namespace std;char mz[205][205];int vis[205][205],
2015-08-23 13:36:11
571
原创 UVA 11624 Fire! （BFS）
题目链接：Fire!解析：先用bfs处理出Fire到每个格子的最短时间。然后再使用bfs求出最短时间。注意：判断能否扩展的时候，要满足在格子着火之前才可以扩展。AC代码：#include #include #include #include using namespace std;const int maxn = 1000 + 5;char
2015-08-22 18:08:22
549
原创 POJ 3279 Fliptile
题目链接：Fliptile解析：先确定第一行的翻转方式，然后再判断是否存在解以及解的最小步数是多少。然后将第一行的所有翻转方式枚举一遍即可求出最优解。枚举的时候可以用整数表示集合。AC代码：#include #include #include #include using namespace std;const int dx[5] =
2015-08-21 13:29:34
585
原创 POJ 1426 Find The Multiple （DFS / BFS）
题目链接：Find The Multiple解析：直接从前往后搜，设当前数为k用long long保存,则下一个数不是k*10就是k*10+1AC代码：#include #include #include #include using namespace std;long long n;int DEEP;bool flag;void dfs(
2015-08-19 20:29:06
569
原创 POJ 2251 Dungeon Master （BFS）
题目链接：Dungeon Master解析：三维BFS模板题。6个方向开始想的太复杂了，水了好久，其实只要老老实照二维的套就完了。AC代码：#include #include #include #include #include using namespace std;int L, R, C;string m[32][32];bool
2015-08-19 19:31:31
493
原创 POJ 1321 棋盘问题 （DFS）
题目链接：棋盘问题解析：dfs暴力从上到下、从左到右搜索。AC代码：//代码1#include #include #include using namespace std;int n, k, ans;char maze[10][10];bool vis[10][10];void dfs(int x, int y, int step){
2015-08-19 15:14:18
651
原创 POJ 3278 Catch That Cow （BFS）
题目链接：Catch That Cow解析：两个数n和k，三种操作：+1、-1、*2，问n最少经过多少次操作能和k相等。最简单的bfs模板了，注意+1的条件：x+1 -1的条件：x-1 >= 0*2的条件：x AC代码：#include #include #include #include #include using name
2015-08-19 11:52:07
578
原创 ZOJ 3494 BCD Code （AC自动机 + 数位DP）
题目链接：BCD Code解析：n个病毒串，问给定区间上有多少个转换成BCD码后不包含病毒串的数。非常神奇的题目。。经典的 AC自动机 + 数位DP 的题目。首先使用AC自动机，得到bcd[i][j]表示状态i,加了数字j以后到达的状态，为-1表示不能转移然后就是数位DP了注意记录为0的状态AC代码：#include #include
2015-08-18 13:35:32
1151
原创 HDU 3247 Resource Archiver （AC自动机 + BFS + 状态压缩DP）
题目链接：Resource Archiver解析：n个正常的串，m个病毒串，问包含所有正常串（可重叠）且不包含任何病毒串的字符串的最小长度为多少。AC自动机 + bfs + 状态压缩DP用最短路预处理出状态的转移。可以优化很多AC代码：#include #include #include #include #include using name
2015-08-18 11:39:04
711
编译原理课程设计之编译器（完整代码 + 测试样例）
2015-07-29
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人