- 博客(74)
- 收藏
- 关注
RSS订阅原创 Codeforces Round #316 (Div. 2) E. Pig and Palindromes
E. Pig and Palindromes题目大意给定一个N*M(N,M <= 500)的字符矩阵，从(1,1)走到(N,M)，每次只能向右和向下走，那么有多少种走法可以组成一个回文串。题目分析想要形成回文串，显然，从起点出发经过的字符要与从终点出发经过的字符相同。 所以相当于一个点从(1, 1)开始向右或向下走，另一个点从(n, m)开始向左或向上走，并且每次双方走的字符必须相同。 这样就可
2015-08-14 20:54:59
734
原创 Codeforces Round #316 (Div. 2) D. Tree Requests
D. Tree Requests题目大意一棵树上的包含N个节点 (N <= 500000) 每个节点包含一个小写字母，每次询问包含u, h，询问u节点所在的子树中所有深度为h的节点是否等够组成一个回文串（顺序可以随意排列）。题目分析能够组成回文串的充要条件是最多有一个字母其出现次数为奇数。 关键是如何统计字母的出现次数。 首先记录每个的节点DFS的首次经过的时间in[]和结束经过的时间out[]
2015-08-14 20:54:02
415
原创 HDU5294——Tricks Device（最短路 + 最大流）
第一次做最大流的题目… 这题就是堆模板#include <iostream>#include <algorithm>#include <cmath>#include <cstring>#include <cstdio>#include <cstdlib>#include <vector>#include <queue>using namespace std;typedef long
2015-07-21 19:29:51
1023
原创 LCA模板——倍增法
POJ1330#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <vector>using namespace std;typedef long long LL;const int MOD = 1e9
2015-06-11 13:03:50
665
原创 HDU5258(百度之星复赛1001)——数长方形(暴力)
题目描述小度熊喜欢玩木棒。一天他在玩木棒的时候，发现一些木棒会形成长方形。小度熊可能是处女座吧，他只会将木棒横竖摆放，这样会形成很多长方形。现在给你一些横竖摆放的木棒，请你帮小度熊数一数形成了多少个长方形。 为了简化题目，一个木棒的端点不会在另一个木棒上，也就是说，木棒的端点不会在长方形上。 第一行一个整数T，表示T组数据，不超过100组。 每组数据中，第一行是n，代表有多少个木棒，n不会超过
2015-06-09 16:16:47
724
原创 HDU5259(百度之星复赛1002)——弹吉他(DP)
题目连接题目分析这是一道比较典型的DP题目，但是题目的状态数量比较多，转移数量也比较多，所以枚举起来会比较麻烦，所以可以用一个技巧就是可以预处理出所有的序列然后用序列枚举状态转移，这样会使代码简洁很多。#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#incl
2015-06-09 16:08:25
755
原创 HDU2196——Computer(树形DP，经典)
题目连接题目解析经典的树形DP题。 题意是求树中每个点到所有叶子节点的距离的最大值是多少。 由于对于一个节点来说，可能得到的距离最大的值的路径来自他的子树，或者从他的父节点过来，所以用两次DFS。 第一次DFS求出所有节点在他的子树范围内到叶子节点距离的最大值和第二大的值，第二次DFS更新从父节点过来的情况就可以了。 因为如果只存最大值的话，判断一个点的从父节点过来的最大值，那么如果他的父节
2015-06-09 16:03:49
537
原创 ACdream1072——Kill The Monster
题目地址#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <vector>using namespace std;typedef long long LL;const int MOD = 1e9 + 7
2015-05-13 15:07:03
599
原创 hiho一下 第十五周——最近公共祖先·二(Trajan,离线LCA)
题目连接http://hihocoder.com/problemset/problem/1067题目大意就是一棵树求任意两个节点的最近公共祖先。算法描述在题目的提示里面有比较详细的解释。这里就不多说了。这种算法的时间复杂度是O(n+q)。 在算法的实现上也有一些技巧，在参考了一些代码后写了一个比较精简的Trajan_LAC算法。#include <bits/stdc++.h>using name
2015-03-09 13:21:24
977
1
原创 hiho一下第一周——最长回文子串
题目连接http://hihocoder.com/problemset/problem/1032题目分析类似于KMP的思想，利用已经匹配的信息计算未匹配的信息。 基本原理就是：我们将f[i]定义为以i为中心的最长回文串长度。那么如果有f[5]=7,f[4]=3, 那么我们可以得到f[6] >=3.以此来减少比较次数。当然还有一些细节要处理。比如回文串长度的奇偶性。代码这个是我自己写的版本，不是很精
2015-03-07 13:26:07
707
原创 HDU4638——Group（树状数组+离线操作）
题目链接题目大意n个数的序列，m次询问。 求一段区间连续数字的段数 。 (1 3 5 4 2) 询问[2,4]区间则3,5,4为连续序列输出 1 。解题思路我觉得这是一道不错的题目。 定义线段是求的连续序列。 首先将所有的询问离线，按照Li递增排序。 我们可以用一个结构维护Li为起点加入所有点后的各区间线段数，对于每个以Li为起点的询问进行处理。 当然这样不够，我们还要消除Li之前加入的
2015-02-16 20:03:59
856
原创 HDU4770 —— Lights Against Dudely （状态压缩，暴力枚举）
#include <iostream>#include <algorithm>#include <cmath>#include <cstring>#include <cstdio>#include <cstdlib>#include <vector>using namespace std;typedef long long LL;const int INF = 0x7fffffff;
2015-02-14 17:32:44
616
原创 HDU4782——Beautiful Soup（模拟）
题目大意题目给你一些没有经过排版的HTML代码，让你按照一定的格式排版好，去掉多余空格，保持规则的缩进。题目分析注意的地方就是’ ’ 和 ‘’ 可能在同一行。 其实题目本身并没有多少技巧，就是锻炼基本的代码功底。刚开始写的时候，写了一坨稀烂的代码，结果出错之后的Debug变得非常困难。所以看似这种随意的代码风格能节省时间，其实维护的成本要高得多得多。后来又重新敲了一遍，发现其实在你有了一个全局的
2015-02-13 14:21:43
690
原创 CF507E——Breaking Good(BFS,DP)
507EBreaking Gooddfs and similar, graphs, shortest paths x328题意：给你一些道路，道路长度都为1，道路有两个状态可用和不可用。 寻找一条1到N的最短路，使得该最短路上的道路全部可用，其他道路全部不可用，要求改变状态的道路数量尽量小。分析：1-N的最短路的长度一定
2015-01-24 16:23:38
879
原创 CF505C——Mr. Kitayuta, the Treasure Hunter(DP)
CMr. Kitayuta, the Treasure Hunterstandard input/output1 s, 256 MB x170比赛的时候没有做出来。。。首先这个题目很自然的一种状态表示方法就是 记录当前位置pos和最后一次跳跃距离len , 结果保存为dp[pos][len]，但是这两个数的范围都是300
2015-01-19 19:27:41
1199
原创 CF496D——Tennis Game(高效，模拟)
Tennis Game#include #include #include #include #include #include #include #include #include #define INF 0x7fffffffusing namespace std;const int MOD = 1e9 + 7;const int N = 1e5 + 10;
2015-01-17 19:00:25
521
原创 POJ1469——COURSES(二分图最大匹配模板)
题目#include #include #include #include #include #include #include #include #include #define INF 0x7fffffffusing namespace std;const int MOD = 1e9 + 7;const int N = 100 + 10;const int M
2015-01-17 18:54:05
566
原创 UVA 10817——Headmaster's Headache(DP)
Problem D: Headmaster's HeadacheTime limit: 2 secondsThe headmaster of Spring Field School is considering employing some new teachers for certain subjects. There are a number o
2015-01-03 18:26:27
376
原创 HDU3847——Trash Removal（凸包，枚举）
Trash RemovalTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 848 Accepted Submission(s): 272Special JudgeProblem DescriptionA
2014-12-09 16:01:44
813
原创 POJ1113——Wall(凸包)
WallTime Limit: 1000MS Memory Limit: 10000KTotal Submissions: 30395 Accepted: 10224DescriptionOnce upon a time there was a greedy King who ordered his chief Arc
2014-12-09 15:06:33
435
原创 POJ2381——TOYS(暴力，叉积)
TOYSTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 10850 Accepted: 5208DescriptionCalculate the number of toys that land in each bin of a partitioned
2014-12-09 14:23:35
552
原创 Codeforces Round #277 (Div. 2)
Problems#Name ACalculating Functionstandard input/output1 s, 256 MB x4080BOR in Matrixstandard input/output1 s, 256
2014-11-18 18:42:55
445
原创 Uva10125/POJ2549——Sumsets(中途相遇法,hash)
A. SumsetsTime Limit: 3000msMemory Limit: 131072KB64-bit integer IO format: %lld Java class name: MainSubmit Status[PDF Link]Problem C - SumsetsGiven S, a set of
2014-11-10 19:31:36
530
原创 hiho一下 第十一周——树中的最长路
时间限制:10000ms单点时限:1000ms内存限制:256MB描述上回说到，小Ho得到了一棵二叉树玩具，这个玩具是由小球和木棍连接起来的，而在拆拼它的过程中，小Ho发现他不仅仅可以拼凑成一棵二叉树！还可以拼凑成一棵多叉树——好吧，其实就是更为平常的树而已。但是不管怎么说，小Ho喜爱的玩具又升级换代了，于是他更加爱不释手（其实说起来小球和木棍有什么好玩
2014-11-02 20:49:41
697
原创 POJ3368——Frequent values(RMQ)
Frequent valuesTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 13535 Accepted: 4981DescriptionYou are given a sequence of n integers a1 , a2 , ... , a
2014-10-26 19:14:47
449
原创 CPC3——H.喵喵的最长序列(RMQ|单调队列)
H.喵喵的最长序列Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 3 Solved: 2[Submit][Status][Web Board]Description喵喵刚做完LCS,LIS,LCIS啥的，突然想到一个非常Naive的问题。给你一个序列a，求一个序列的最长连续子串a[i]~a[j]使得m
2014-10-26 18:50:02
488
原创 HDU5071——Chat(模拟)
ChatTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 670 Accepted Submission(s): 158Problem DescriptionAs everyone knows, DR
2014-10-24 18:57:03
637
原创 ZOJ3829——Known Notation（贪心，模拟）
Known NotationTime Limit: 2 Seconds Memory Limit: 65536 KBDo you know reverse Polish notation (RPN)? It is a known notation in the area of mathematics and computer science. It is also k
2014-10-12 21:07:18
630
3
原创 HDU2517——How many ways??（矩阵快速幂）
How many ways??Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1565 Accepted Submission(s): 548Problem Description春天到了, HDU校园
2014-10-01 11:04:24
435
转载 STL 算法集合
C++ 算法(STL) 非修改性序列操作（12个）循环for_each()对序列中的每个元素执行某操作查找find()在序列中找出某个值的第一次出现的位置find_if()在序列中找出符合某谓词的第一个元素find_end()
2014-09-17 14:18:29
512
原创 ZOJ3641——Information Sharing（基础并查集）
DescriptionThere is going to be a test in the kindergarten. Since the kids would cry if they get a low score in the test, the teacher has already told every kid some information about the test in
2014-09-07 11:55:44
467
原创 ZOJ3635——Cinema in Akiba（树状数组+二分）
DescriptionCinema in Akiba (CIA) is a small but very popular cinema in Akihabara. Every night the cinema is full of people. The layout of CIA is very interesting, as there is only one row so tha
2014-09-07 11:52:54
484
原创 UVA11795——Mega Mans Missions（集合DP,状态压缩）
BMega Mans MissionsInputStandard InputOutputStandard Output Mega Man is off to save the world again. His objective is to kill the Robots created by
2014-09-04 16:16:04
534
原创 CF463C——Gargari and Bishops(模拟)
C. Gargari and Bishopstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputGargari is jealous that his friend C
2014-09-01 19:01:08
534
原创 UVA11552——Fewest Flops（DP）
FEWEST FLOPSA common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of times the character occurs followed by the charac
2014-08-27 15:09:48
443
原创 CF#262(div2) C——Present（二分）
C. Presenttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLittle beaver is a beginner programmer, so infor
2014-08-21 03:00:10
679
5
原创 HDU1074——Doing Homework（状态压缩DP）
Doing HomeworkTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5238 Accepted Submission(s): 2190Problem DescriptionIgnatius ha
2014-08-20 23:08:20
450
原创 CF417D——Cunning Gena(状态压缩DP)
#include #include #include #include #include #include using namespace std;typedef long long LL;const LL INF = 41e18;struct node{ int x,k,s;}f[105];LL dp[ (1<<20)+10 ];int cmp(node
2014-08-20 16:38:17
844
原创 HDU4961——Boring Sum(数论)
Boring SumTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 215 Accepted Submission(s): 103Problem DescriptionNumber theory
2014-08-19 21:12:14
319
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人