- 博客(31)
- 收藏
- 关注
原创 Poj 3468 A Simple Problem with Integers(树状数组&&线段树)
代码如下:#include#include#includeusing namespace std;typedef long long ll;const ll N = 100007;ll a[N], b[N], c[N];void add(ll s[], ll i, ll x, ll n){ while(i <= n) { s[i] += x;
2016-06-14 21:16:09 365
原创 Light OJ 1033 - Generating Palindromes
题目大意:给你一个字符串,问最少添加多少个字符,使原字符串变成回文串思路:回文串的性质是倒过来两者一样, 那么有这个性质可知, 设原始字符串为a,原始字符串颠倒过来的字符串为b, 那么求a和b的最长公共子序列, 字符串a的长度减去最长公共自序列的长度不就是最少添加的字符!代码如下:#include using namespace std;typedef long long
2016-06-13 21:30:00 439
原创 Light OJ 1047 Neighbor House
题目大意:给你nx3的矩阵, 每行选一个数, 相邻的行不能选同一列的数,问选取数的最小和是多少?定义dp[i][j]为第i行选取第j个数的最小和那么状态转移方程不就是dp[i][j] = min(dp[i][j], dp[i-1][k] + mp[i][j])代码如下:#include using namespace std;typedef long long ll;co
2016-06-13 20:37:42 338
原创 Light OJ 1013 Love Calculator
题目大意:给你两个字符串a, b,问存在多少个这样的字符串。这样的字符串是指字符串a和字符串b都是该字符串的子串, 且这样的字符串要求长度最小。输出这样的字符串的长度和存在多少个
2016-06-13 09:17:30 430
原创 LightOJ 1011 Marriage Ceremonies
题目大意:n对男女,现在要求将他们配对, 给你nxn的矩阵, 第i行第j列表示, 第i个男生和第j个女生配对的优先指数, 将n对男女全部配对的最大优先指数参考题解:http://blog.csdn.net/guard_mine/article/details/46386421定义dp[i][j] 表示第i个男生,状态为j时的最大值#include usin
2016-06-05 15:06:40 325
原创 匈牙利匹配 fzuoj 2232 炉石传说
Problem Description在简化版的炉石传说中:每个随从只有生命值和攻击力,并且在你的回合下,你的每只随从在本回合下只能选择一个敌方随从进行攻击。当两个随从a,b交战时,a的生命值将减去b的攻击力,b的生命值将减去a的攻击力,(两个伤害没有先后顺序,同时结算)。如果a或b的生命值不大于0,该随从将死亡。某一次对局中,GG学长和对手场面上均有n个随从,并且是GG学长的回合。由
2016-05-26 00:25:47 555
原创 python爬虫
经过一周的尝试,终于把一个能够一直爬取网页的爬虫写出来了。 写爬虫之前,要先确定爬虫的结构,在进行模块化的编写;一个简单爬虫需要什么? 需要把网页下载下来, 需要把网页中的数据解析出来, 需要把网页内部的链接加入到待爬取的队列中, 然后把数据储存下来!确定了需要的东西,我们就可以开始编写爬虫了;首先定义四个模块,DataStore由于我将url和data全部在数据库中
2016-05-20 11:24:59 410
原创 poj 3190 Stall Reservations
题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=39459
2016-04-26 09:12:07 324
原创 矩阵快速幂 - hduoj 5667 Sequence -nyoj 301 递推求值
nyoj: 301:给你一个递推公式:f(x)=a*f(x-2)+b*f(x-1)+c并给你f(1),f(2)的值,请求出f(n)的值,由于f(n)的值可能过大,求出f(n)对1000007取模后的值。输入数据有f(1),f(2),a,b,c,n求f(n)对1e9+7取余的值;由于n的范围很大,所以此时就需要把递推式变成矩阵的形式;所以直
2016-04-26 08:54:12 579
原创 素数筛选--总结
第一种:直接暴力,在这就不说了第二种:埃氏筛法(能处理1e6以下的数据)首先,将2到n范围内的所有整数写下来。其中最小的素数为2,将表中所有2的倍数都划去。表中剩余的最小数字是3,不能被更小的数整除,所以也是素数,将表中所有3的倍数也划去。。。 依此类推,如果表中剩余的最小数字为m时,m就是素数,再将m的所有倍数划去。代码如下:int prime[100007], s = 0;b
2016-03-26 12:06:34 955
原创 NOJ 1656 搬砖
问题描述开学了,万恶的大二学长们又要领着大一的鲜肉们一起敲代码搬砖了,这不,著名的杨神拿着n块砖头,当然他把这n块砖头的重量都告诉你了,让你搬走其中的2*k块,其中每次你只能拿2块,消耗的体力是这两块砖头重量之差的平方,比如一块砖重量为5,另一块是11,那么搬走这两块砖头消耗体力为(11- 5)^2 = 36,机智如你,你能算出如何搬2*k块,才能使你花费的体力最小呢?输入
2016-03-14 22:51:51 389
原创 算法分析——归并排序
算法分析:归并排序刚刚看了网易公开课上的算法导论的第一节,讲的是插入排序和归并排序。插入排序很简单双重循环,第一层循环i从1到n,第二层循环j从0到i,将元素插入的0到i已经排好序的序列中正确的位置,这就是插入排序。时间复杂度的最坏情况是1+2+3+4+···+n也就是n*(n+1)/2,最后时间复杂度就是n^2.归并排序感触颇深,想详细总结一下对于一个有n个元素的数组(1
2016-02-15 15:08:00 334
原创 python字符串函数
python大小写转换函数:1: capitalize() #字符串首字母大写,其余全部小写2: lower() #字符串全部小写3: upper() #字符串全部大写4: title() #字符串中每个单词首字母大写,其余小写5: def UpperFirstWord(str): return str[0].upper + str[1:] #
2016-01-15 11:27:04 350
原创 hdu 4325 Flowers
Problem DescriptionAs is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many fl
2015-11-14 19:21:26 410
原创 hdu 1541 Stars
Problem DescriptionAstronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars tha
2015-11-10 21:10:19 410
原创 HDU 5124 lines
Problem DescriptionJohn has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A. InputThe first
2015-11-07 20:20:40 424
原创 2015 CCPC D题
Pick The Sticks Time Limit: 15000/10000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)The story happened long long ago. One day, Cao Cao made a special order calle
2015-11-07 13:07:05 370
原创 2015 CCPC C题(超时代码)
The Battle of Chibi Time Limit: 6000/4000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)Cao Cao made up a big army and was going to invade the whole South China. Y
2015-11-07 12:55:27 609
原创 CCPC 2015 A题
Secrete Master Plan Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)Master Mind KongMing gave Fei Zhang a secrete master plan stashed in a pock
2015-11-07 12:46:25 364
原创 杭电 3792 Twin Prime Conjecture
最近在学树状数组,于是乎找了几个树状数组模板题练一下手;题意:给你数字n,找出从零到n中,有多少孪生素数;孪生素数是指两个连续的素数的差值为2;例如(3, 5),(5,7)等; Sample Input1520-2 Sample Output014刚开始看这道题的时候,第一反应直接暴力,方正数据范围也不是很大;
2015-11-02 22:41:26 428
转载 kmp算法 --转自matrix67
KMP算法详解 如果机房马上要关门了,或者你急着要和MM约会,请直接跳到第六个自然段。 我们这里说的KMP不是拿来放电影的(虽然我很喜欢这个软件),而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说,给你两个字符串,你需要回答,B串是否是A串的子串(A串是否包含B串)。比如,字符串A="I'm matrix67",字符串B="matrix",我们就说B是A的子串。你可
2015-11-01 15:24:22 375
原创 杭电 1166 敌兵布阵
Problem DescriptionC国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
2015-11-01 14:59:50 408
原创 HELLO,WORLD
不知不觉间已经大二了,仔细想想大一一年什么都没做,瞬间觉得可怕;该好好做一件事了。这个博客我会坚持更新,努力的完善自己来记录自己的大学经历;以此纪念我拥有的大学生活!
2015-10-31 18:29:24 299
原创 杭电 2059 龟兔赛跑
简单dp题解:http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=13573&messageid=1&deep=0以充电的地方做为dp的地方,将起点,终点充当做充电站,则下表分别为a[0],a[n+1];dp[i]表示从起点到达实际第i个充电站的最小消耗时间;内层让j从0遍历到i-1,每一个j表示最后一次充电到
2015-10-31 17:59:43 468
原创 杭电 5506 GT and set
题意:给出N个集合。每次你可以指定一个数,然后所有包含这个元素的集合可以被删掉。问你能否经过最多L轮操作使得所有集合都被删掉。Sample Input22 11 11 23 23 1 2 33 4 5 63 2 5 6 Sample OutputNOYES范围很小,直接暴力;# include # i
2015-10-31 17:58:06 334
原创 杭电1180 诡异的楼梯
BFS题目大意是说:给你一张地图,给你起点,终点,问你从起点走到终点的最少时间(一格是一时间单位),简单来说就是BFS 求最短路径问题;这个题需要注意的是:如果走到楼梯上,且当时楼梯是不可走状态,可以原地呆在那(当时没看见,WA五六遍,,,),等楼梯可走时再走;可以直接写BFS,也可以优先队列;#include#include#include#in
2015-10-31 17:55:47 412
原创 HDU 1698 线段树区间更新以及lazy思想
线段树是一种二叉搜索数,每一个节点都对应一定的区间,能够快速的对区间进行更新,时间复杂度比较小;常运用于线段树的一个算法是lazy思想,lazy思想是说若更新的区间已经完全包含区间s,将s区间标记,暂不向下更新,若下一次的更新或询问需要用的已经标记过的区间的子区间,再将标记过得区间进行向下更新,并且取消对区间s的标记,增加对区间两个左右子树的标记。若一直未询问到,则不向下更新。
2015-10-31 17:53:47 466
原创 杭电1176—免费馅饼题解
简单dp#include#include#includeint max1(int a, int b);int max2(int a,int b,int c);int op[100005][11],jk[100005][11];int main(){ int a,b,c,i,j,k,n,t; while(scanf("%d",&t),t!=0) {
2015-10-31 17:52:18 471
原创 杭电1159—Common Subsequence题解
求两个字符串的最长公共子序列#include#includeint maximum_length_common_subsequence(char *op,char *jk);int max(int a,int b);int main(){ char op[505],jk[505]; while(scanf("%s%s",op,jk)!=EOF) {
2015-10-31 17:50:05 499
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人