topcoder: Xscoregame

这一题用递归很简单,直接深度优先搜索所有排序,取最大值即可,但是完全没有DP的思想而且求解时间不可接受;但是如果要DP,如何减少状态数?要知道本题的输入数列排序是影响最终结果的。

下面的解法是DP的,这个DP的妙处在于仍然用输入数列A的子数列组合As作为状态,但是这个状态下面仍然分一些子状态,不过不是用这个子数组的所有排序作为子状态而是用一种hash的方式,即将该子数组的可能结果(子数组每一种排序按题目算法所求得的状态值R=x+x^As[i])对64(2的6次方)求余所得作为子状态的index。

为什么可以这么做?因为题目中数组A最大的数为50(6bit,可覆盖),所以在一个状态转移到下一状态时,即某个子数组新加入一个元素的时候,其实只需要考虑状态值R的低6位不同的情况即可,因为只有低6位有后效性,只有低6位相同的所有排序只需取最大状态值(这里不用求具体排序,主要求最大值),其他都不用考虑了,而不同的低6位值可能带来不同的有效子状态。说白了,就是当前低6位不一样的,现在不能判定以后谁优谁劣,而当前低6位相同的,已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支,于是求解效率就呈几何级数地提高了。

 

topcoder: YetAnotherORProblem2

这题显示只有18%的AC率,题目本身不难,估计都是败在执行时间上了;我的解法如下,典型的DP思维,子问题是:如果已知长度为n-1的情况下,和或操作相等的数列,求长度为n的情况;状态index为每个满足条件的数列的和Sn-1(因为和或相等,也是该数列的或),状态值为该index对应的数列有多少种。状态转移方程为:

if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]

 

topcoder: YetAnotherTwoTeamsProblem

这是一道标记为hard的题,确实比较hard

开始用了一个比较简单暴力的方法,其实也是DP思路,但是状态取的比较偷懒,直接用了所有的可能组合作为状态,虽然在求解过程中可以利用到已经搜索过的状态,但是整个搜索空间还是太大了,导致虽然结果正确,但是严重超时了:

又做了一次伸手党,看了解答后醒悟了,其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。 点我展开分析内容

topcoder: ZigZag

再来水一道简单题:题目地址

想法很自然,记录下当前的方向,一旦出现方向不一致的就把总数加一,同时方向改变,否则continue,然而其实已经包含了动态规划思想

上代码:

看了下别人提交的,思路一样,只不过有人上来先把整个序列的变化趋势算一遍,即遍历seq,然后算出seq[i]-seq[i-1]的值记录下来记为V[i],其实要的就是一个正负号,然后再次遍历还是记录当前的方向,乘以当前遍历到的那个趋势V[i],乘积发生变化时就在结果上加一并改变当前方向值。

topcoder practice: ZooExchangeProgram

为了兴趣,也为了保持coding的能力,重新开始写一些算法题;为了对算法了解的更透彻,也为了锻炼表达能力,干脆在博客里面对解题代码进行详解,代码是自己写的,但也不排除参考了别人的解法,消化吸收了就是自己的,不是吗?

题面:

太长了,就不贴了,链接在此

代码及详解:

Mac新手键盘映射探索

作为Linux老司机都是重度终端依赖症患者,unix终端对ctrl键的摧残各位老司机都懂的;换了Mac后发现键盘极其反人类,右边control没有,左边control那么小而且位置感人,ctrl+r这种分分钟用的着的快捷键在Mac上换了各种姿势都不爽,这是要把左手按残的节奏阿,左手可是很重要的,咳,我说的是敲代码。

谷歌了一把键盘映射,发现一个叫keyremap4macbook的应用,几个论坛里面都强烈推荐,现在的版本叫做karabiner;先安装了前者,居然还要我重启,为了左手的解放勉为其难的重启了下,结果还是徒劳,完全没有任何反应,估计是版本的问题。这种ugly的非App Store应用折腾了我半天还无效,干脆就放弃了。

接着再求助搜索引擎,找到了这个,虽然是短短一行,但是却提醒了我,看来还是需要再探索一下Mac系统自身设置。人肉探索了一段时间后,发现了一个可以利用的点,如图所示,虽然注释文字描述的比较抽象,但是下面的菜单列表对正常智商的人来说一目了然了,显然是个映射关系,那么我们将那个“大户”command键合control键对调一下是否合理呢,我目前看来是合理的,作为程序员最需要效率的就是在terminal中挥散汗水的时间,而其他的操作对快捷键要求不高,那么我们需要的正是让control键无处不在,触手可及!

PTRACE的权限检查,自由是有前提的~

系统调用PTRACE的一切开始于这里:
COMPAT_SYSCALL_DEFINE4(ptrace, compat_long_t, request, compat_long_t, pid,
               compat_long_t, addr, compat_long_t, data)

首先提供了attach的绿色通道:
if (request == PTRACE_ATTACH || request == PTRACE_SEIZE) {
        ret = ptrace_attach(child, request, addr, data);
attach做的事情就是把当前进程变成了被trace进程的父进程,同时把被trace进程加入到当前进程的ptraced链表中;
__ptrace_link(task, current);
list_add(&child->ptrace_entry, &new_parent->ptraced);
    child->parent = new_parent;
但是这样做是有前提的,具体请看后面的分析,这里先按下不表。

attach?wtf?为啥要在用之前attach,搞得这么神秘,难道直接用不可以吗?
不可以,因为你不能直接访问其他进程的地址空间,否则地址空间的隔离不就变成笑话了。
所以这个ptrace系统调用入口做了个很重要的check:
ret = ptrace_check_attach(child, request == PTRACE_KILL ||
                  request == PTRACE_INTERRUPT);
    if (!ret) { //只有返回为0,即判断条件成立,才继续执行对ptrace的request
        ret = compat_arch_ptrace(child, request, addr, data);
        if (ret || request != PTRACE_DETACH)
            ptrace_unfreeze_traced(child);
    }
child->ptrace && child->parent == current
只有过了这一关,才能进行后面的操作(除了kil和interrupt,他们自己的处理逻辑里面有此类的判断或者无需),那难道随便就可以attach,那我就麻烦一点先attach呗;显然不会这么傻,前面卖了个关子,这里来看看attach里面做的权限检查,必须是有权的人才能随便搞的,屁民是要守法的!!

权限管理的水比较深,博主还没吃透,所以这里先简单列一下我能看懂的部分:
etval = __ptrace_may_access(task, PTRACE_MODE_ATTACH);
这里有两个条件,1)我自己人改自己人ok(这里的suid euid等等的请看后面链接);2)我的上层命名空间ok(我理解是,比如像root用户这种大boss)
    tcred = __task_cred(task);
    if (uid_eq(cred->uid, tcred->euid) &&
        uid_eq(cred->uid, tcred->suid) &&
        uid_eq(cred->uid, tcred->uid)  &&
        gid_eq(cred->gid, tcred->egid) &&
        gid_eq(cred->gid, tcred->sgid) &&
        gid_eq(cred->gid, tcred->gid))
        goto ok;
    if (ptrace_has_cap(tcred->user_ns, mode))
        goto ok;
另外还要做命名空间能力的检测,看看目标进程的命名空间有没有被ptrace的能力:
ns_capable(__task_cred(task)->user_ns, CAP_SYS_PTRACE)

参考链接

修改运行中代码之神器——PTRACE的秘诀

ptrace是个神奇的系统调用,是gdb等工具的实现基础,它可以用来监控进程的执行,读取或修改进程的寄存器和memory内容包括代码段。有的底层码农老司机甚至也会觉得奇怪,代码段不都是不可写的吗,为啥ptrace就能修改呢?

下面解释一下,老司机直接看后面代码秒懂:
  • 首先,代码段不可写,其实是在页表中对代码段相应的页设置了不可写的flag,而页表只能控制进程地址空间的访问权限。
  • 其次,这里的不可写只对用户态进程起作用。当然,进程的地址空间是隔离的,而进程在用户态只能通过自己地址空间的虚拟地址访问内存,所以当前进程在用户态也无法访问其他进程的地址空间。
  • 最后,在内核态就能随便修改其他进程的代码段了?是的,但是你得先找到目标代码段地址空间对应的物理页,然后再映射到内核地址空间,然后新的地址空间的访问权限决定了你能如何访问这些物理页;ptrace中如下这段代码实现了这些功能,如何能执行到这些代码又是另外一个话题了;这里面牵涉到权限管理等等的问题,ptrace系统调用已经考虑的很周全了,博主会在下一篇博客里面详解ptrace系统调用的权限检查~
ptrace_request()
    case PTRACE_POKETEXT:
    case PTRACE_POKEDATA:
        return generic_ptrace_pokedata(child, addr, data); //调用__access_remote_vm
 最后的关键代码:
ret = get_user_pages(tsk, mm, addr, 1,
                write, 1, &page, &vma);
……
maddr = kmap(page);
            if (write) {
                copy_to_user_page(vma, page, addr,
                          maddr + offset, buf, bytes);
                set_page_dirty_lock(page);
            } else {
                copy_from_user_page(vma, page, addr,
                            buf, maddr + offset, bytes);
            }
            kunmap(page);

requests.exceptions.SSLError when running a py2exe generated EXE file

最近做个兴趣小项目,需要用python来get/post https请求,用到了requests模块,因为要在windows下使用,考虑到易用性和小白玩家的需求,使用py2exe生成exe。参考链接看起来很简单,统共分三步:1,安装py2exe;2,准备一个配置脚本,我们叫他build_exe.py;3,执行一条命令python build_exe.py py2exe

先把这个简单的初级版本放这里:

#usage: python build_exe.py py2exe

from distutils.core import setup
import py2exe

setup(console=[‘myqqbot.py’])

但是这里其实还是有坑的,安装py2exe要注意,并不是直接pip install py2exe就可以了,py2exe是人家python3专用的,python2的是py2exe_py2,悲剧吧,所以装包前最好还是pip search下,免得浪费时间还不知道错在哪。配置脚本貌似简单,大家应该能想到这里面其实是有很多玩法的,以至于需要一个脚本而不是直接传参。

 

生成过程很顺利,不过几秒exe文件已经躺在dist目录下了。但是双击他,console一闪而过,都不知道发生了什么。Windows就是这么变态,反正把你当小白,不给你任何错误信息。在超级难用的cmd里面用命令行调用exe后发现了问题:

requests.exceptions.SSLError: [Errno 2] No such file or directory

万能的stackoverflow告诉我们,不要慌我有药,药在这。so大夫告诉我们在exe文件执行的时候环境变量发生了改变,找不到这个pem文件了,我们需要给一个静态的pem文件路径,或者设置一个REQUESTS_CA_BUNDLE环境变量,因为不知道这个exe文件会在什么环境下执行,不能保证所在的环境中有这个pem文件,所以我们必须在打包的时候打一个pem文件进去。到此产生两个新问题:1,如何获取cacert.pem文件;2,怎么用py2exe打包,当然你肯定能想到直接放到生成的dist目录下面就可以了,但是这样是不是太low了,我们要有更elegant的方法。 Continue reading “requests.exceptions.SSLError when running a py2exe generated EXE file”