PE工具编写

前几天把PE结构认真看了一下,顺便写了下类似peinfo的工具练练手,只不过是控制台的(windows sdk没怎么学,win32汇编也忘的差不多了,所以还是写成控制台的吧。。)。以前了解pe文件的时候总是走马观花,所以基本上印象全无。这次认认真真写写代码,收获还是比较大的。
说实话,pe结构的学习真的不难,但是非常考验耐心,特别是数据目录那里和资源结构那里,一层套一层,一定要耐心才行。
记下几个我认为重要的点,或者说收获:
0.rva和raw的转化
先看rva在哪个块(块表里面有一个块的起始rva和VirtualSize),块的起始raw也是可以得到的(也在对应的块表中)。然后raw=块起始raw+(rva-块起始rva)
简单吧。

git入门笔记

git add xxx.txt                           把文件修改添加到暂存区
git commit -m “版本说明”       把暂存区的所有内容提交到当前分支
git status                                      查看目前工作区状态(有无文件被修改之类)
git diff                                            查看新旧版本的修改之处
git log                                            查看历史版本记录
git reset –hard HEAD^          向前回退一个版本
git reset –hard HEAD^^       向前回退两个版本
git reset –hard HEAD~n        向前回退n个版本
git reflog                                       查看键入的历史命令

又是熬夜

今天偶然看到一本叫《Windows 内核安全与驱动开发》的书。。。。。。。的电子试读版,看的挺过瘾,熬夜看了半宿,现在又陷入什么都想学的状态了。。但是毕业设计都还没做啊。。

容斥专题

容斥专题:容斥专题题集
复习了一下容斥,发现原来容斥可以用位运算写,以前一直使用dfs写的。。弱爆了。。
这两种做法各有适用的场合。
重新做了一下zoj3687
dfs版的容斥
题意:n天n个章节,给你m个约束条件,一个约束条件d,c表示第d天不能复习第c章节。问总共有多少种复习的方式(答案mod 55566677)。
思路:典型的容斥题目。算出满足所有约束的方案数,最后n!减一下即可。以前做的时候忘了约束会有重复,这次做又忘了。。真是渣渣。首先完全相同的约束只保留一个,否则会多算。然后,如果d或c有重复,则说明这两个约束条件同时满足的方案数为0,不能递归下去了。

主席树

今天看了下主席树,感觉好神奇,代码精简而且实用,例如静态区间第k大之类的题,用主席树直接秒杀线段树套平衡树之类的写法。就是空间有点大。。
具体请参考:
1.clj的论文
2.博文一篇,代码写的很精炼:http://im.librazy.org/article/837/note-chairtree-via-functional-segtree/
其实很好理解的。
入门题:
hdu2665
静态区间第k小,注意题目描述可能不恰当。。

类似积分

题目:给你三种图形,圆心在x轴上的圆,中心在x轴上且边与x轴平行的正方形,中心在x轴上且边与x轴成45度的正方形。三种图形的边长、半径都是<=10的非负数。且中心坐标是绝对值<=10的整数。给你n个图形(n<=10),问你共覆盖了多少面积,精确到整数位
思路:这题比赛时没多想,其实抓住答案的精度非常粗略且图形很少,范围很小就比较好做了。用积分的思想,x从-20递增到20,每次增长0.001,对于特定的x,枚举所有图形,找到最大的y,y*0.001就是这个小矩形区域的面积,累加*2即可。

cf375D Tree and Queries

昨天学了莫队算法,发现真的是很神奇,特别是简化版的,按sqrt(n)分块的算法,非常好写。这道题是佳神推荐的,发现确实很好,写下题解,大牛请直接关闭本页。。
题意:题目的意思是给你一棵树,每个节点都有一个正整数值。然后给你m个询问,每次询问你一棵子树中出现次数至少为kj次的数有多少个。题目中所有数都是<=10^5
思路:这题其实是前面写的树那题和分块那题的结合。首先dfs这棵树,得到dfs序。
于是问题转化为:给出一个长为n的序列,m个询问,每次询问[l,r]上有多少个数出现次数至少为qi次
这个问题可以这样:用一个数组cn[i],表示数i出现的次数。再用一个树状数组cc[],其中第i个元素表示出现次数为i次的数有几个。然后就是前面所讲的分块算法了,这在《莫队算法相关》这篇文章里讲过了。每次单步转移(也就是类似[l,r]->[l,r+1]的转移),需要更新cn[],时间是O(1),更新cc[],时间O(lgn).求解时计算getsum(n)-getsum(qi-1),时间为O(lgn).这样复杂度是O((n^1.5)lgn),n=1e5.算了一下大概在5*10^8左右。开始用线段树出现次数为x的数的个数,结果TLE,改成树状数组就过了,不过应该是数据不卡O((n^1.5)lgn)的原因,因为正解貌似是O(n^1.5)的。。待进一步思考
ps:del和insert的时候,少写了if,导致有时候一个数删去之后出现了0次,这时候对出现0次的数的个数+1,结果就出错了。。