- 博客(64)
- 收藏
- 关注
RSS订阅原创 博客搬家
csdn博客是我大一的时候写题解用的第一个博客，大二的时候就和队友一样，自己在腾讯云上买了自己的服务器，搭建了自己的博客。如今ACM已经退役，从大一省赛Cu，大二省赛Ag，大三省赛Au，大三区域赛Cu，包括能够参加国赛的总决赛，自己当时定的目标，如今也已经实现。尤其是第十届省赛距离Au只差那么一点点，悔恨了一年，而在上一周，也弥补了这个遗憾。这个博客，也不会再更了，或许以后会回来看看。新博客地址：...
2018-06-03 18:01:50
343
原创 河南省第十一届ACM大学生程序设计竞赛总结
河南省第十届ACM大学生程序设计竞赛总结27号中午的时候到的信阳师范学院，下午3点半热身，热身赛是三道题，其中三道题中两道题是省赛的原题，一道是序号互换，一道是Metric Matrice，还有一道是贪心的水题。省赛的原题，我们去年省赛的时候刷过，所以分工的时候，我写那个贪心的水题，吴杨写Metric Matrice，吴荣写序号互换。而我第一次写的时候不有考虑到数据的范围，结果错了一次，纠正了...
2018-05-28 16:22:55
1403
原创 河南省第十届ACM大学生程序设计竞赛总结
题目：6道水题+一道题目略难读懂但写起来很水+一道oi原题&&理论上是防AK题+一道不是防AK的题。 组队大致策略:我+吴荣写代码，吴杨读题+出思路。 比赛过程：起手是A题，就是给你一篇文章，让你统计文章中出现次数最多的前十个单词，以及其出现的次数，水题，我写了一发，Yes。之后荣神又切了一道水题，第三道水题我写了一发。紧接着荣神又A一道，之后是一道DP，我大致想了一下，应该是区间DP，想了下，
2017-05-09 21:56:53
1083
1
原创 3.25天梯赛总结
题目不难，但是只得了178分，差点垫底。 比赛原本是1点开始的，结果服务器崩了，延迟到2点开始，刚好利用这个空挡，敲敲头文件，又敲了遍spfa练练键盘熟练感，原本还想比赛的时候说不定比赛的时候还能用到呢。 刚开始想先写一道L2的题，抢个一血，但是题目还没看懂，一血就被抢了，就赶紧开写L1的题。L1有两道题刚开始蜜汁wa，浪费了我好多时间debug，一到是L1-5. A除以B。题目有这么一句话：输
2017-03-26 11:49:55
684
原创 POJ3252 Round Numbers
题目链接：http://poj.org/problem?id=3252 题意：假设将一个数字转换为二进制，其中二进制中的0的个数大于等于二进制中1的个数，那么这个数字称为Round Numbers。问[l,r]（1<=l<=r<=2e9）内存在多少个Round Numbers。 想法：很简答的数位DP，开一个dp[i][one][zero]，i表示第i位，one表示最高位到此位1的个数，zero
2017-02-27 10:52:46
470
原创 HDU - 3709 Balanced Number 数位DP
题目链接：https://cn.vjudge.net/contest/70324#problem/F 题意：在一个数字中，假设以其中一位为对称中心，两边的每位分别乘以它到对称中心的距离，如果两边的和相等的话，就称为Balanced Number。如：4139以3为对称中心的话，左边是4*2+1*1=9，右边是9*1=9。即为Balanced Number。 想法：依然是数位DP，遍历一个数字的每
2017-02-27 10:44:34
673
原创 CodeForces - 55D Beautiful numbers 数位DP
题意：如果一个数字能被自己所有位上数字整除，则称这个数字为Beautiful numbers，现在问[l,r](1 ≤ l≤ r ≤ 9 *10^18)内存在多少个Beautiful numbers。 想法：依然是数位DP，对于每一位数字如果他们的最小公倍数(lcm)能够整除这个数字，那么这个数字肯定就是Beautiful numbers。可以计算出1到9的最小公倍数是2520。可以开一个三维dp
2017-02-27 10:32:03
532
原创 HDU4507 吉哥系列故事――恨7不成妻 数位DP
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4507 题意：求[L,R](1 <= L <= R <= 10^18)区间内和7无关的数字的平方和。 如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关—— 1、整数中某一位是7； 2、整数的每一位加起来的和是7的整数倍； 3、这个整数是7的整数倍； 想法：如果不是求平
2017-02-27 10:18:33
872
原创 HDU4352 XHXJ's LIS 数位DP+状态压缩
题意：假设把一个数字当成字符串，将它的最长单调递增子序列长度称为power值，求[L,R]区间内power值等于k（1<=K<=10）的值有多少个。 想法：很明显是数位DP，只是单调递增子序列状态压缩稍微麻烦点，单调递增子序列的nlogn解法是另开一个dp数组，在dp数组中将最长的单调递增序列存进去，并不断更新，在更新过程中dp数组始终是单调递增（不是非单调递减）的，所以我们可以将整个序列用二进制
2017-02-26 23:38:10
523
原创 hdu3567 Eight II 康拓展开+打表+路径回溯+映射
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3567 题意：给你一个八数码的起始和终止状态，让你打印路径，要求字典序最小，长度最短，保证输入数据必有解。思路：2000ms 200组数据，平均10ms一组数据。用A*的话，可能会tle，而且还不能保证字典序最小。所以直接打表，考虑到起点，终点不定，所以需要映射，比如我把起点564178X23映射成1
2017-01-15 15:23:30
1172
原创 hdu1401 Solitaire双向bfs
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1401 题意：给你一个8*8的棋盘以及棋盘上有四个棋子，再给你四个棋子的位置，问你之前的四个棋子八步之内能不能走到后面的棋子的位置，一步指的是单个棋子上下左右移动到相邻的空的位置，或者若上下左右有棋子，跳过相邻的棋子到此方向的下一格（如果此处没有棋子）。 四个棋子，四个位置，可以开一个8维数组来标记这
2017-01-15 13:47:02
488
原创 HDU1560 DNA sequence 迭代深搜IDA*
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1560 题意是给你一些DNA串，要你输出一串字符串使得它能包含所有的DNA串的序列，要求其字典序最小，长度最短。 代码：#include<cstdio>#include<cstring>#include<string>#include<queue>#include<cmath>#includ
2017-01-14 19:08:06
706
原创 hdu2234无题I 迭代深搜IDA*
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2234 题目意思是一个4*4矩阵里面有4个1，4个2，4个3，4个4，每一步可以将矩阵的某一行向左移一步或向右移一步，或者将矩阵的某一列向上或向下移一步，问能是否在5步内使矩阵的每一行或者每一列都一样，如果在5步内的话，输出确定的最小步数，大于5步输出-1。 依然是迭代深搜，同时A*剪枝，考虑移动一行
2017-01-14 19:01:05
677
原创 hdu1667The Rotation Game 迭代深搜IDA*
题目链接：http://acm.hdu.edu.cn/data/images/1667-1.jpg 题目是这个棋盘里面摆放着8个1，8个2和8个3，每一步你可以沿着A、B、 C、D、E、F、G、H任意一个方向移动该字母所指的长块。移出边界的小块会从 另一端移进来。如最左边的棋盘经过操作A，就会变成中间的棋盘布局， 再进行操作C，就会变成右边的棋盘布局。 要使的最中间的8个格子的数字
2017-01-14 17:43:54
629
原创 hdu1043 Eight 康拓展开+bfs打表
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043 经典的八数码，一般做法直接bfs，肯定tle。应该用A*剪枝或者打表，我用的是打表，打表更快点。 我的思路是以最终状态为起点进行bfs，同时开个结构体数组来记忆bfs过程中的状态（方向，这个八数码状态的上个状态的结构体数组下标），最终可以回溯打印路径。 同时给定一种状态要能找到他对应的结构体
2017-01-14 17:14:44
734
原创 hdu5093 Battle ships 二分图匹配
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5093 题目是给你一个n*m的图，图中有三种字符，*表示海洋，#表示冰山，o表示浮冰。浮冰和冰山不能放战舰，每一行一列只能放一艘战舰，除非两个战舰中间有冰山，问最多能放多少艘战舰？ 这题和放炮台那个题类似（炮台：http://acm.hdu.edu.cn/showproblem.php?pid=104
2016-12-08 20:26:21
488
原创 hdu2647 Reward 拓扑排序
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2647 题意是给n个人，m个x,y（x的钱要比y的钱多），每个人最少888，问最少要多少钱？ 自己写老是想着dfs，结果dfs搜的头都晕了，还是不对。 应该是分层次的排，先排888，然后889，890。。。 先遍历找到所有入度为零且未标记的点，然后将这些点所连接的点的存一下，等遍历完，再将这些存的点的
2016-12-05 17:18:13
464
原创 哈理工团队赛 D pairs
D Pairs Description Given N integers, count the number of pairs of integers whose sum is less than K. And we have M queries. Input The first behavior is an integer T (1 < = T < = 10), on behalf of
2016-12-05 14:47:55
483
原创 浙江理工大学新生赛 B巴比伦花园 rmq+二分
题目：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4239 起初觉得是线段树，但是不知道如何建树才能查询到题目要求的答案。后来看了题解，才知道是rmq&&二分来写，不过在这之前要先来预处理一下，提前知道每个点最能够到达的最远距离，然后rmq存一下区间内点能到达的最远距离，然后在查询的时候，二分查询(l,r)区间能够到达的超过或等于r的第
2016-11-30 20:21:03
859
原创 刷题常犯错误
整理下自己常犯错误，以后做题写完后，先匹配一下这些错误（虽然这些里面不乏脑残错误，但是有时候就是这样神奇的出错）。常犯错误： 0.杜绝改了一项bug，就提交（每次提交前应让队友输入几组数据测试），每wa一次，应来一名队友协助debug（组队赛）。[0] 1）.数组开小（re||tle||wa，线段树maxn未<<2，切记计算好数组大小，数组下标运算过程中很有可能会爆数组，血的教训）。 [1]
2016-11-29 20:29:14
966
原创 poj1523 最小割+并查集
题目链接：http://poj.org/problem?id=1523 题意是给你一些点，每两个点连成一条边，问图中有几个割点，同时如果去除割点后，图中有多少个能够互相联通的集合，比较坑的是点不是按顺序给的，即可能不是从1开始。 求割点直接套割点模板，去除割点后，还有多少能够互相联通的点的集合，可以求出割点后，对割点dfs，凡是两个不含割点的点，并到一个集合中，最后看有多少个集合即可。 代码：
2016-11-24 18:12:50
497
原创 poj 1144求图的割点
题目：http://poj.org/problem?id=1144 题目看了好久没看懂，猜样例也没才出来，后来看别人博客对题目的解释才看懂题意。意思是给你一个n，表示有1～n这些点，然后后面有不超过n行数据，每一行开始一个m，后面几个还有若干个数字表示和m这个点有一条边，若开始的数字m为0，则说明这组数据结束，最后问图中割点数量。 直接啊哈算法模板：#include<stdio.h>#incl
2016-11-23 10:29:30
498
原创 Codeforces Round 380 C. Road to Cinema
很简单的二分题，可惜写代码太慢，bug还老是挑不出来，比赛也没写出来，还是手速慢，脑子转的慢。。。 题目：http://codeforces.com/contest/738/problem/C 题意是给你数字n，k，s，t，表示你有n辆车，要行驶s的路程在时间t内到达一个电影院，其中路程中有k个加油站，可以给车加油，且加油不费时间。开车有两种开法，一是正常速度，1km/**2**h，1km浪费1
2016-11-21 15:51:50
722
原创 hdu2586How far away 最近公共祖先Lca tarjan算法
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586 第一次用targan算法，留个模板。#include<stdio.h>#include<string.h>#define spot 40010#define edge 80010#define query 410struct stu{ int to,value,next;}
2016-11-17 19:58:44
782
原创 nyoj1068 ST 线段树
题目链接 线段树查询区间和以及区间奇数个数。 区间和很好求，很快就写好了，区间奇数个数写起来麻烦一点，除了查询的时候需要lazy操作，更新的时候也需要lazy操作。 直接上代码：#include<stdio.h>#include<string.h>#define ll long long#define maxn 10010struct stu{ ll l,r,mid,lazy
2016-11-05 19:18:28
427
原创 hdu3549 Flow Problem 网络最大流的三种写法（Ek，Dinic(邻接矩阵，邻接表)，Isap）
初学网络流，用的是小白书上面的EK算法模板，自己看别人的博客理解了一发，在这里存个模板。hdu3549 Flow Problem （网络最大流EK算法）#include<stdio.h>#include<string.h>#include<algorithm>#include<queue>using namespace std;#define maxn 20#define inf 0x3
2016-11-02 12:43:08
998
原创 南阳理工学院软件、计科16级新生联合月赛（10月）
//如果发现错误，请联系QQ：528859519。 A：矩阵相乘。 签到题，题目很容易理解，多组数据，两个n*n的矩阵的相乘，相乘的定义是：a[i][j]*b[i][j]=c[i][j]。 即两层for循环遍历i,j,使得c[i][j]=a[i][j]*b[i][j]，不过需要留意一下，输出矩阵的每一个数字后面都有空格。#include<stdio.h>int a[11][11],b[11]
2016-10-30 14:24:33
2754
1
原创 nyoj221 nyoj756 重建二叉树
nyoj221题目链接 已知二叉树前序中序遍历求二叉树后序遍历：已知二叉树前序中序遍历可重建二叉树，进而遍历后序。#include<stdio.h>#include<string.h>#include<stdlib.h>struct node{ char value; struct node*l,*r;};node *rebuildtree(char *preord
2016-09-18 16:36:05
438
原创 zzuli1917 rmq+二分
之前做过类似的，一眼就看出来rmq+二分，可惜代码能力太菜了，写了快两个小时才写出来。 思想：肯定是一层for()循环遍历每一个下标，对于每个下标i向左查找到第一个比自身值小的右边那个下标left，同时向右查找到第一个比自身值小的左边那个下标right。比如然后(right-i+1)(i-left+1)*a[i]，即为所求值。比如1 5 4 6 2对应4这个数，其下标为3，那么左边第一个比自身值小
2016-08-17 18:00:26
673
转载 hduoj 分类
1001 整数求和 水题 1002 C语言实验题——两个数比较 水题 1003 1、2、3、4、5… 简单题 1004 渊子赛马 排序+贪心的方法归并 1005 Hero In Maze 广度搜索 1006 Redraiment猜想 数论：容斥定理 1007 童年生活二三事 递推题 1008 University 简单hash 1009 目标柏林 简单模拟题 1010 Rails
2016-08-08 17:55:05
3049
原创 nyoj 760 See LCS again 最长公共子序列
正常dp的最长公共子序列时间复杂度为n*m； 优化后的为nlogn~n*m*log(nm),不是太稳定，不过做这道题时还是可以A的，毕竟数字不是字母，相同的还是很少的; 思路： 如: 5 7 1 2 6 5 4 1 3 2 4 6 6 5 先查找第一个子串在第二个中出现的下标如1（1），2（3） ，6（6，5），5（7），4（4）；（注意：下标逆序排列） 然后构成一个新的子串1，3，
2016-08-01 10:15:59
458
原创 poj 2965 The Pilots Brothers' refrigerator bfs+状态压缩+路径回溯
此题易超时，因为16个开关，每个开关有两种状态，可以将’-‘看成0，’+’看成1，从第一排第一个到第四排最后一个，每一种状态都可以用一个数字来代替，所以一共是(1<<16)-1种状态，即65535种，bfs还是可以的。在广搜过程中，因为每一个开关扳动的过程其对应的一行及一列都会发生变化，可以将其状态对应的值分别和这些状态对应的数字进行^处理，为了防止TLE，可以提前打个表，这样异或一下就可以了，不用
2016-07-29 10:56:07
511
原创 2016 hdu多校联赛1004 GCD rmq+二分
题意：最多给10W数据，然后最多有10W次询问，每次提问一个区间，问此区间的最大公约数是多少，同时和此区间的最大公约数相同的区间还有多少个？ 10W次询问区间的gcd，并同时询问和这个gcd相等的区间还有多少个，第一问很容易解决，用rmq||线段树，第二问想了好久也没想出来不TLE的办法。后来问了学长，才知道应该用二分来解决。 对于多次询问，肯定要做预处理，尽量做到询问时O（1）的复杂度，rmq
2016-07-21 08:23:38
829
原创 第九届河南省赛 C nyoj1274 信道安全
1W个点，5W条遍，邻接表+Bellman-Ford的队列优化。仿效啊哈算法P174,175，Bellman-Ford的队列优化. 信道安全 时间限制：1000 ms | 内存限制：65535 KB 难度：2 描述 Alpha 机构有自己的一套网络系统进行信息传送。情报员 A 位于节点 1，他准备将一份情报 发送给位于节点 n 的情报部门。可是由于最近国际纷争，战事不断，很多信道都有可
2016-07-15 16:23:16
1223
原创 第九届河南省赛 A nyoj1272 表达式求值
每年河南省省赛基本上都有表达式求值这类题，对于还没开数据结构这门课的偶来说简单一点的还好，复杂点的就跪了，-_-||| 之前写过计算器，省赛的时候还带了计算器的模板，结果本来想到最后来写，结果最后没时间了。 和计算器类似，不过是多了一个Smax，我的想法是可以将Smax的小括号改成中括号，同时符号里面增加一个’,’，这样区分开来，同样是计算器的写法，中括号的优先级和小括号的优先级一样，逗号的优先
2016-06-26 18:21:17
627
原创 第九届河南省省赛E题 nyoj 1276 机器设备
这道题我的做法和nyoj的20题吝啬的国度有点类似，深搜从(0,0)开始搜直到搜到指定的齿轮位置结束，怎么搜呢？开一个二维vector，首先把所有的齿轮的遍历一遍，搜他们周围和他相切的齿轮，并用vector存起来，这样已知一个齿轮，便可以知道他周围和他相切的所有齿轮，接下来就是从起点(0,0)开始深搜，直到搜到末位置的那个齿轮。 至于轮速，题中给的公式不靠谱，轮速应该是=(0,0)处齿轮的半径*1
2016-06-11 19:00:51
910
原创 nyoj 61 传纸条（一） nyoj 712探寻宝藏 双线dp
之前自己看到这道题一直想的是按照题意那样先从左上角到到右下角遍历一遍，再从右下角到左上角遍历一遍，可是怎么不走重复的路就不知道怎么解决了。 原来可以开一个四维的数组，来记录对应的状态。可以假设有两个纸条同时从左上角朝右下角走，假设起初第一个纸条朝向起点的右方，第二个纸条朝向起点的下方，假设第一个纸条的位置已知，则第二个纸条肯定始终在第一个纸条的下面的排，因为同时开始传，所以若已知第二个纸条在哪儿一
2016-06-07 18:45:51
960
原创 nyoj 737 石子合并（一） 区间dp
区间dp，因为只能相邻的相加，所以牵扯到区间dp，即若要求一个大的区间的最优解，先求小区间的最优解然后小区间慢慢的推出大区间的最优解。 比如样例： 5 1 2 3 4 5 要求1~5这个区间，用dp[1][5]来形容1~5的最优值，那么dp[1][5]肯定为dp[1][1]+dp[2][5], dp[1][2]+dp[3][5], dp[1][3]+dp[4][5] ,d[1][4]+
2016-05-26 20:12:29
1474
原创 nyoj 762第k个互质数 poj 2773Happy 2006
nyoj和poj题意一样，就是查找第k个互质数， nyoj应该用容斥原理+二分查找，这道题在poj很容易AC，本来poj时间限制就长，而且后台水，比如我自己写的代码在poj32ms，在nyoj就一直TLE。 容易想到的方法就是二分查找数字，然后判断这个数字和n有多少个互质数，至于怎么判断，可以用容斥原理。（之前自己用的是递归，看了 http://blog.csdn.net/lyhvoyage
2016-05-26 10:30:55
1079
原创 南京理工校赛 C count_prime
上次的广工业刚刚出过容斥的题，然而当初那道题问学长，学长说不会，自己看别人博客，博客里说了下是容斥原理，剩下的只有代码，看到别人写得那么长的代码（其实也不算长，只是没用头文件10+行，看着就头疼，唉~~）自己看时连容斥原理都没搞懂，更别提看代码了，总觉得很难。结果这次比赛又遇到了，懵逼~ 刚好今天没比赛，顺手补补题，把容斥原理搞懂了，刚把广工的容斥搞懂，又把这道题给AC了， 唉~
2016-05-25 12:37:24
567
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人