郑轻校赛的抢钱题，第6题到第7题的坎，或者做另外一个弱不会的网络流 比赛的时候知道是线段树，但是没有完全理解线段树lazy标记是干啥，所以呢，写了一个每次都传递到底的线段树，实质上比暴力还慢 线段树：为了查询和插入删除操作更加均衡的数据结构，时间都是O(logn) 网上有很多学习链接，其实质是一个节点代表一个区间的值，通常的用法是数组的第一个值a[1]表示整个区间的状态，然后依次二分，根据题意定义节点状态 如n=10个节点的线段树 a[1]：负责1-10区间 a[2]：负责1-5区间 a[3]：负责6-10区间 a[4]：负责1-3区间 a[5]：负责4-5区间 a...

最近补题补得有点惨，发现所谓的会写的题以前看过题解的题只要是自己做的话，永远都做不对 所以每次做完一道错题写完一道AC的代码之后都得水一发博客，下次也能记得在哪 分组背包第一题：分组背包 题意：有n门课程m天，矩阵a[i][j]为在第i门课程上花费j天能够获得的价值。现在m天求最大可以收获的价值 本质上是01背包：哪些选择哪些不选 可是细节上有不同：选择的课程中哪些科目花费多少天，这些都是需要制定的 定义二维：dp【i】【j】为在前i门课程中，花费一共j天的最大价值，那么需要由前i-1天的值推出，所以需要知道第i门课程花费了多少天（不得超过最价值的天数，同理可以不要第i门课...

如果在赛场上告诉我，这道题就是暴力的记忆化搜索，我肯定就搞了 如果在赛场上告诉我，线段树lazy标记是可以过的，我肯定现场就学了就过了 哎，还是实力不够，校赛给我了一发补题的机会也挺好的 题意：n*m的矩阵，每个点上有权值，一个人从左上角到右下角遍历两次，若两条路径有重复点，则只计算一次，求最大的收益，n和m的最大范围100 看到这种题，我知道是DP 正常情况的设置是：dp【i】【j】【k】【l】为第一个人走到了【i】【j】这个点，第二个走到【k】【l】，所能够得到的最大价值 但是范围在100，这样开数组是爆炸的，能不能少一维 注意到题意：只能从左上角走到右下角，意味...

http://www.pwnable.kr/play.php 以做题的方式来学习基本操作和命令，这个地方作为各个题的整体链接地址来慢慢补充，希望能够坚持下来，见证自己的成长与学习历程。 2016-04-22： [Toddler]-[fd] 2016-04-23： [Toddler]-[collision] 2016-05-04：第三题来得比较晚，因为学到了很多东西 [Toddler]-[bof] 2016-05-10：第四题一个大脑洞，给了个提示是reverse的任务，最常见的就是UPX之类的吧，在大神的指导下学了工具才学会的 [Toddler]-[flag] 2016...

第一个题呢，总是传说中的那么简单： ssh fd@pwnable.kr -p2222 password=guest 连接上去之后，使用ls：看到flag文件：cat flag：发现无法打开，肯定是有了设置不让打开的，注意到旁边有两个不一样的 一个是.c文件，一个是可执行文件，同名哦 打开fd.c源码和执行fd文件，很明显知道我们需要做到： 第一步：argc<2的绕过 第二步：read的理解与使用 第三步：strcmp函数为比较字符串函数，显然要让判断成立，需要有个LETMEWIN字符串 注意底下的printf哦：给了提示，需要学习Linux的文件输入输出 先说说应该怎么调试，很明显...

有了第一个就会有之后的很多很多个吧 ssh col@pwnable.kr -p2222 (pw:guest)之后，发现跟上一个题的套路差不太多 看到了三个文件col,col.c和flag，flag没法直接打开，需要去看程序 cat col.c查看源码：发现有一个套路差不多：argc<2的判断在第一题已经会了 另外，有了一个strlen的限制，长度必须是20位 想要拿到flag，就必须懂check_password这个函数 于是就拿着运行跑一次 ./col ABCDEFGHIJKLMNOPQRST 说好的是...

第一次这么专心的这么坚持的开始写这种模拟题，从昨晚的构造思路到300行代码，今天的重写，再到构造了一个特殊情况Hack了杭电的数据，简直完美简直Nice！ 题目链接：HDOJ4431 先说说题意：国粹！不按题目描述来解释了，按照麻将官方说法来解释 介绍牌型：4种类型 1万到9万：用1m到9m 1条到9条：用1s到9s 1筒到9筒：用1p到9p 花牌：东西南北中发白：用1c到7c 介绍胡牌方式： （1）七小对：一对牌就是两个一样的牌。手上13张牌+听的牌（题目中要求的），构成7个对子就可以胡牌。注意这儿有个Hack点！（杭电没有这种数据）7对牌不一定不同哦！比如4个...

线段树怎么学？刷题！（每个专题都是这种方法咯） 为什么要用线段树？因为暴力会超时：n最大是1e5，从后往前枚举的话，需要枚举当前这个点是不是被之后的所有点覆盖过，如果覆盖过就不是当前颜色；否则，ans++ 这种方法是肯定超时的 为什么要用lazy标记？因为很有可能出现第2次涂色2-8区间，第3、4、5、6、7、……一直涂色2-8区间的，那么只需要改那个标记就好，什么时候需要改子区间了，再把lazy标记下放就好，跟这个题是一样的套路：lazy标记 为什么要用离散化？因为数据太大，而且大得没有意义！一方面数值太大容易超时，另一方面，所需要的答案是多少根线段，与线段的长度并没有关...

原来看到过字符串hash 这次碰到了一个数值型hash就在比赛的时候放弃了，果然还是太弱，需要多学习 暴力的话，n平方的算法，而且需要顺时针和逆时针判断12次，肯定TLE 暴力不行才会需要想别的方法： 对所有的值进行HASH是分了对值进行分类，分类最正常也是最一般的想法就是%一个质数 质数选择很重要：几万左右的比较好 如果在一组的话，那么就使用暴力匹配，顺时针和逆时针判断12次，如果至少有1次匹配成功就说明正确 否则，当所有数据读完之后都没有，那就是没有结果 #include<map> #include<set> #include<m...

这个题也是一开始的思路不对。链接：戳我刷题 题意：给定n+1个数，分成k+1个组，每个组中的数需要是连续的 要求各组数求和的最大值最小。 两个最值的理解，求最大是说，在某一种分组情况中，k+1个组中，每个组求和后的k+1个数取最大 求最小是说，在所有的k+1个组的方法分配中，各个最大数比较的最小的方案 由于n和k都比较小，n最大1000，k最大300，一看就是典型的dp【i】【j】的结构，数组也可以开，想得特别完美 dp【i】【j】定义为：前n个数，分成k组的最大数的最小值是多少 dp【n+1】【k+1】为最终答案 dp是状态定义，答案定义，边界值dp【0】【0】，...

由一道简单数学题引发的思考 所有的做法和注释和总结都在代码上了 这个题很有意思，不同的方法实现难度和AC时间也不一样的 int n; int bruteforce(){ //完全暴力的做法，从1开始作为起点，终点走到走不动为止 //依次枚举起点和中间值，计算答案 int i,j,count=0,sum; for(i=1;i<=n;i++){ sum=0; for(j=i;j<=n;j++){ sum+=j; if (sum==n) count++; else if (sum>n) break; } } return...

做过很多遍的二进制搜索，每次写就是对着代码敲一遍，然后下次写又不会 链接：http://poj.org/problem?id=3279 题意：n*m的矩阵，全是0和1构成的，当选择翻一个点的时候，周围的点会受到影响，问选择翻n*m矩阵中的哪些点，可以将所有点均翻过来？ 为什么要用搜索？因为n和m很小，最大是15 为什么要用二进制搜索？因为是枚举状态，而且是每行每列的状态 怎么样枚举最好？枚举第一行，然后依次遍历其他行，枚举第一行的复杂度是2的n次方，然后遍历全矩阵式n*m，整个复杂度相乘没有问题 怎么搜索呢？ 用一个整数表示1行的状态，比如255=11111111（2...

字符串的新姿势新技能解锁：HDOJ5672 给定一个串长不超过1e6的字符串，统计其中子串中不同字母个数不小于k的子串总数 遇到这种题，肯定只能用O（n）的算法扫描一遍：姿势要好才能AC 如果从0到m刚好包括k个字符，那么0到m+1也有，0到len-1也有，总数为len-1-m+1=len-m个值 如果第0个字符在1-m的区间中存在，那么1-m子串也是符合题意的，同理1到m+1也有，1到len-1也有，总数为len-m-1个值 如果第1个字符在2-m的区间中存在…… 所以，只需要一次扫描，并且判定端点的值是不是在之后的区间中存在即可 int main(){ //i...

刷题的时候，最怕的一种题：题意上明明是模拟，但是根据其数据量大小去看，模拟完肯定TLE 这个题，给了一种解决方法：对所谓的模拟进行记录而不是动作，最终根据记录情况输出，而不是变换完毕之后输出 看完代码发现很简单，但是想写出这种思路转换的代码很难 a【i】表示位置上的行变换 b【i】表示位置上的列变换 c【i】表示数值上的行变换 d【i】表示数值上的列变换 变换公式很容易按照题解上说的就好 最终答案比较难考虑：行列位置变换与行列数值变化都考虑进来 #include<map> #include<set> #include<math.h> ...