- 博客(54)
- 收藏
- 关注
RSS订阅
原创 HDU4302_zkw线段树
这题好像被hdu加强数据了，网上的一些线段树代码已经WA了，贴一个已经AC的327ms //MJRT#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//////////////////////#include<iostream>#include<algorithm>#include<string>#i
2016-01-26 16:49:20
499
原创 ZOJ 1654_Place the Robots(建立二分图)
二分图概念及其相关算法：http://www.renfei.org/blog/bipartite-matching.html本题难在如何建立二分图，详情看注释：//MJRT#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//////////////////////#include<iostream>#in
2015-10-31 18:50:41
469
原创 uva11212_Editing a Book(A*算法)
这题学到了很多啊，也碰到一些原来没有遇见过的情况。题解： A*算法，移动一块最多可以导致3个后缀改变，如果改变都是我们所期望的，那么我们可以认为最少进行h/3次搜索就可以搜到了，如果 当前搜索步数+最少修改步数 > 最大步数，就不可能完成了，剪枝即可。 这题有意思的一点是h（），求相邻逆序数函数，我刚开始的时候是这样写的：int h()//计算相邻逆序数对的个数{ int cnt = 0
2015-09-17 00:19:01
460
转载 欢迎使用CSDN-markdown编辑器
欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
2015-09-08 15:56:20
369
原创 uva1584_水题（环状串的处理）
我的方法是：用指针不断从头部向尾部转移值； 大白代码仓库中方法：利用模运算；My Code：#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//////////////////////#include<iostream>#include<algorithm>#include<string>#inclu
2015-08-20 20:12:47
1549
原创 uva401_水题（映射）
原来一直都是一个一个switch来着，这回方便了。。。#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//////////////////////#include<iostream>#include<algorithm>#include<string>#include <iterator>#incl
2015-08-20 18:12:03
444
原创 uva140_dfs（回溯）最优性剪枝
题解： 1.原书中已经说明，如果两个节点的带宽 >= 最小带宽，无论如何也不可能比原解更优，应该剪掉。2.注意此题读入的时候一定要按 字典序 存储，这样计算出的最小值才是符合要求的3.注意strtok的用法#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>//////////////////////#inc
2015-08-20 08:53:17
1026
原创 uva10976_整数拆分（优化至3ms）
PS：刘汝佳代码仓库中这题的代码逗了，我交上去居然RE了。。。。（逃题解： 原书的意思是找出最大值于最小值枚举就好了，然而仔细观察的话就会发现，第一组分母较小的数的分母为k+1,而其他组数据这个数都 不是 素数，最后数据分母必为2*k，那么我们只要在非素数中查找符合条件的值即可。PS：我又写了一份暴力的，果断T了。。。。。。#include<cstdio>#include<cstdlib
2015-08-17 20:13:18
1024
原创 uva725_一道水题（优化到了29ms）
可以用 n * fghij 去枚举 abcde 判重即可由于fghij 可能自身重复较多，可以先判掉，节省时间；如果不写成函数的形式还能更快一些，因为第二次判段中x，已经判断过了。书中的做法是把两个数字化成字符串去，排序后判断用时 123ms#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>///////
2015-08-17 17:50:43
698
原创 C++ STL：：bitset
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-08-13 21:35:07
423
原创 G++/C++ 手动扩栈
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-08-13 21:05:00
863
原创 CodeForces 510B 无向图找环的两种方法（搜索与并查集）
题目连接：http://codeforces.com/problemset/problem/510/B解法：dfs 每次把父节点的值记录并传递下去，判断一下新达到节点： （1）没有走过 → 继续搜索； （2）走过&&不是父节点（对于本题步数也要>=4） → 找到环；并查集 每个节点映射成 i*m+j从起点开始分别把它下面与于右面的节点加进来，如果发现有节点已经在集
2015-08-13 20:58:14
1074
原创 hdu4430_Yukari's Birthday(数学放缩+二分)
本题根据蛋糕中心放不放蜡烛可以转化为 k1+k2+……+kr=n或n−1 k^ 1 + k^2 + ……+k^r = n 或 n-1 已知：等比数列求和公式n=k(kr−1)k−1n = \dfrac{k(k^r-1)}{k-1}我们知道18 ≤ n ≤ 1012 由此可以求出来r最大是
2015-08-06 15:41:58
706
原创 hdu1166_敌兵布阵(线段树入门)
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-31 20:02:12
373
原创 hdu5328_Problem Killer(简单dp)
今天才知道长度为1或2的数组，既符合等差数列又符合等比数列。。。。dp【0】的初值赋为1，之后其他项赋为2，直接扫一遍，找出最大值就好了还学到了一点：判断等比数列的时候用双精度（double）除法去做，避免数据太大的时候int爆了，这里WA了好久。。。（逃#include<sstream>#include<string>#include<iostream>#include<algorithm
2015-07-30 19:57:14
595
原创 hdu5327_Olympiad(数组前缀和)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5327题解：1.判重 （利用set或压成2进制） 2.前缀和，结果为 sum[b] - sum[a-1]#include<sstream>#include<string>#include<iostream>#include<algorithm>#include<cstdio
2015-07-30 17:55:13
1240
2
原创 hdu4800_Josephina and RPG（二维状态dp）
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-29 21:47:47
461
原创 zoj3728_Collision(简单计算几何)
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-29 21:39:49
610
原创 zoj3726_2013长沙区域赛（二分查找+预处理）
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-29 19:30:33
736
原创 hdu5326_（优美的并查集解法）2015 Multi-University Training Contest 3（1011）
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-28 19:27:03
706
原创 hdu4771_2013亚洲区域赛杭州站（状态压缩bfs）
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-28 14:35:13
616
原创 uva1600_巡逻的机器人（状态bfs）
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-26 16:18:46
583
原创 uva439_骑士的移动
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-26 14:37:18
610
原创 uva536_树的重建（由先序，中序历遍推出后续历遍）
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.
2015-07-25 14:45:56
798
原创 uva712_S树
题解： 把查询的值看成二进制，转换成十进制之后去叶子里面找对应的值输出即可#include<cstdio>#include<cstring>#include<iostream>const int N = 100009;int change(char * s);//pow调用库中的也可，由于可能存在的精度问题，重写了一下int pow(int x, int y);void rev(char
2015-07-24 21:19:37
698
原创 uva673_平衡的括号（网上写的好麻烦。。）
这就是个水题，本质上就是判断括号顺序，只要考虑下列几种错误的情况：1.）（ 或】【 2.（【） 或【（】 3.（（（） 或 【】】】】或（）））或【【【【【】简单来说，保持个数平衡，括号对称，没有夹杂的就好了#include<cstdio>#include<iostream>#include<cstring>int main(){ int n; scanf("%d",&n
2015-07-24 20:38:21
834
原创 uva1572——自组（World Final 2013，图论模型）
这题值得学习的几点： 1.输入匹配的代码十分优美！ 2.把A+,A-映射成2n,2n+1做，然后通过（2n）^1 = 2n+1 , （2n+1）^1 = 2n 来反转，不得不说十分精妙！题解：由于正方形是无限的，把要去连接编号与被链接的正方形上的其他可扩展编号看成节点，被链接的正方形看成边，寻找次有向图的环。 题目中的例子： A- |->->->->->->->->->->A+|->->-
2015-07-23 20:10:37
2666
2
原创 uva10562——看图写树（树的先序遍历！）
妈蛋，这题坑了我2个多小时。。终于过了。。 做的时候主要在这几个WA点卡住了： 1.读取行数的时候忘记减去“#”的行数了 2.没有考虑到空树的情况 3.递归的时候没有判断右边界值‘\0’ 4.被样例误导了，以为节点只能是字母。。。。。。一个发现： 用 isspace() 或者 isalpha() 比手动判断要快！ 本题解法： 在读取到节点的时候，如果发现下面有字符‘|’，把此节点当作根
2015-07-23 16:52:22
704
原创 uva122_二叉树的层次历遍
大白2，P150页#include<cstdio>#include<iostream>#include<cstring>#include<vector>#include<queue>const int N = 100009;struct Node{ bool have_value; int v; Node *left,*right; Node(): ha
2015-07-20 17:02:51
787
原创 hiho一下 第五十一周(有向图欧拉路径)51
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt267 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.c
2015-06-23 12:59:25
822
原创 hiho一下 第五十周（欧拉路径）50
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt267 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击：http://blog.c
2015-06-14 18:42:41
659
转载 STL中的排序算法一览
STL中有多种排序算法，各有各的适用范围，下面听我一一道来：I、完全排序 sort() 首先要隆重推出的当然是最最常用的sort了，sort有两种形式，第一种形式有两个迭代器参数，构成一个前开后闭的区间，按照元素的 less 关系排序；第二种形式多加一个指定排序准则的谓词。sort基本是最通用的排序函数，它使用快速排序算法，并且在递归过程中，当元素数目小于一个阈值（一般是16，我的试验是24）
2015-06-07 18:33:25
1495
原创 hiho一下 第四十九周（欧拉路的判定）49
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt267 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 转载请注明：http://blog.csdn.net
2015-06-06 22:09:32
496
转载 hdu,poj 分类
hdu,poj 分类POJ:按照ac的代码长度分类（主要参考最短代码和自己写的代码） 短代码：0.01K–0.50K；中短代码：0.51K–1.00K；中等代码量：1.01K–2.00K；长代码：2.01K以上。短：1147、1163、1922、2211、2215、2229、2232、2234、2242、2245、2262、2301、2309、2313、2334、2346、2348、2350、23
2015-06-05 19:15:28
1021
原创 hiho一下 第四十八周（拓扑排序的应用）48
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt267 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 转载请注明：http://blog.csdn.net
2015-06-04 17:22:15
437
原创 hiho一下 第四十七周（拓扑排序）47
/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt267 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 转载请注明：http://blog.csdn.net
2015-06-04 17:18:44
364
原创 2015百度之星资格赛1004_放盘子
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1004仔细看给的提示和样例，如果小度能把第一个放进去，那么他必然赢，因为偶数边正多边形都是对称的，如果只能放进去一个也是小度赢，所以说。。。。#include<iostream>#include<algorithm>#include<mat
2015-05-25 15:21:47
481
原创 2015百度之星资格赛1001_大搬家
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1001这题主要是找规律，组合数学和递推式。举个例子啊，987654321→912345678 我们从最小的单位——一个数开始考虑它的所有情况，共有两种： 1.不换位置 （4→4） 2.与其他数的位置对换（7→2,2→7）我们记共有i个数
2015-05-25 13:14:35
535
原创 2015百度之星资格赛1002_列变位法解密
题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1002这题好麻烦啊，wa了好几次，开始的时候以为思路错了，换用一维数组存储矩阵去做，结果超时了，后来一想是忽略了正常的没有空的情况 ⊙▂⊙ ，加上之后就AC了。。。#include<stdio.h>#include<string.h>#
2015-05-25 11:21:34
658
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人