迁移网易博客到WordPress

网易博客已经关闭有一段时间了,虽然已经好久没写博客了,但是还是想把以前的记录留下来。找了好久没找到好的搬迁方法,直到看到一篇博客提到了bus2wp这个工具。用bus2wp需要先把博客迁移到博客大巴,然后用博客大巴导出的xml转换成WordPress的格式。因为博客大巴现在也还挂着,所以这条路也走不通了。于是我就试着改了一下bus2wp,让它直接读取网易博客关闭前导出的xml格式。代码取名叫netease2wp,以GPLv3发布,需要的同学可以在这里找到。使用方法推荐看看这篇博客,只需要把里边提到的博客大巴导出的xml换成从网易博客导出的xml的并把bus2wp换成我在bus2wp基础上改的netease2wp就行了。 最后可以按照这篇博客提到的方法把博客中的图片也导入到WordPress。

这次迁移完了不知道下次写博客会是什么时候,突然有点怀念过去,哈哈哈。

Hello, ACM-ICPC World Finals![2014年1月5日]

好久没有写博客了,而写日记的习惯到了大学也早已丢失。但是这件事情我觉得有必要记下来,就像当初NOIP拿到一等奖需要记录下来,获得NOI参赛资格需要记录下来一样。

距离上一次写关于OI/ACM的日志(OI的结束,ACM的开始[2011年10月26日])已经两年多了,那篇写于我第一次参加ACM区域赛之后。从那时到现在期间发生了很多事情,我没有将他们记录下来,而借着这次机会,我希望将它们整理出来。
收到人大的录取通知书之后(我不是保送的),我第一个想到的事情就是加入ACM队,所以开学之前我联系了cy好多次,问关于加入ACM队的事情。所以开学不久我就和ACM队当时的队员联系上了,然后一起做了几次网络赛,并确定了队友,zx和wyw。印象最深的就是那年参加的上海赛区的比赛了,那也是我参加的第一场区域赛。我们只AC了两道题目就获得了银牌。而其中我写的一道题我犯了一个特别愚蠢的错误,把点积的公式复制过去,想改成叉积公式,结果变量位置改对了但是忘记把加号改成减号了,不过好在最后被我发现了。而ACM的第一年也就以这枚银牌结束了。
接下来就是大一下学期,各种个人赛事聚集的学期。我参加了两个有分量的比赛吧,一个是清华大学举办的智能体大赛,一个就是百度之星了。那次智能体大赛的大概意思是写一个大飞机的AI,控制大飞机如何发射子弹;写一个小飞机的AI,使得在小飞机存活的时间里,小飞机静止不动的时间尽可能长。然后比较两人小飞机对战对方大飞机的得分情况来判断胜负。到最后,写得比较好的小飞机AI应该都是用的离散化加动规来做的吧,后来由于大飞机AI的升级,简单的离散化加动规也不能有很好的效果,于是我加入了预测功能,因此我的小飞机AI变得很强,而至于大飞机的AI,到了最后则几乎大家都差不多了,所以影响倒没那么大了。从提交截止前的最后的战况来看我和hpf,zyc的AI是形成了剪刀石头布的态势,但是由于抽签淘汰赛的缘故,最后止步于半决赛。这次比赛给了四强选手2000RMB的奖金,也是我参加的所有比赛里唯一拿到奖金的一次了。至于百度之星,那是我第一次参加,不过对百度之星早有耳闻。那次百度是和北大合作办的,所以题目是提交到OpenJudge上的,因而初赛和复赛都没出现特别坑爹的情形,虽然题目还是很难,但至少测评很正常。我复赛做了两场的样子,第一场是果断的悲剧了,而第二场却神奇的拿到了一个用堆来做的贪心题目的AC。就因为这个AC,我成功的晋级的百度之星决赛。当时觉得特别高兴,毕竟这也是我第一次晋级这种大型赛事的决赛(高中的时候做过一次有道难题,好像两百多名。。。)。同时,高中时和我一起搞OI的同学wsc也凭借高超的骗分技术拿到的决赛资格。到了决赛,百度的高富帅气质毕露啊,各种玩,各种好吃的,比以后我参加的所有比赛都要好!而当时我和wsc也都是抱着玩一玩的心情尽情的享受吧,毕竟真正的决赛肯定是比不过那些神牛的啊!如我所料,决赛的题目还是写AI,这次是写一个打麻将的AI,虽然我从小就会打麻将,但是写的AI还是很正常的败给了各路神牛。
然后就是大二上了,又是一个新的赛季,而这个赛季对我的打击是特别大的。我还是和zx,wyw组队,本打算今年收获一枚金牌甚至冲击World Finals,却没想到长春拿铁,金华拿银。在结束了这个赛季之后,zx和wyw就退役了,这时候wdp找到我,表达了一起组队的意愿,我也答应了,然后就和wdp,whd组成了一个新的队伍。wdp和我是同一届的,他大一的时候为了搞好GPA(虽然GPA还是没我高,哈哈)所以没参加ACM队的训练,大二才和whd,ybh一起组队参赛。whd比我小一届,不过确实我比较看好的新生中的一个,也是当时人大所有ACM队员里边Codeforces Rating最高的一个。在这学期的训练中,我们也确定了各自的分工:我和whd写题(我侧重难题,whd则凭借超快的编程速度偏重代码量大的题目),wdp负责各种助攻(开新题,分配题目,想题解,出数据,查bug)。在这学期的训练结束后,我们已经很有默契了。而也正是这个新的队(对了,队名是Acme),让我重新找回了ACM的信心。
大二下同样是各类个人赛事的比较集中的一学期,这一次参加了腾讯的编程马拉松和微软的编程之美。两个比赛的线上比赛都是算法类的题目,而到了决赛则都是项目开发了(而且饭也不好吃,腾讯居然让我们吃盒饭,我觉得你们不差那点钱吧。。。),所以我对这两个比赛的印象并不是很好。这一学期Acme的训练依旧照常进行着,我们每周有两场训练,周三一次个人专题练习,周六一次组队练习。而这些练习的成果,在长沙邀请赛和北大校赛上的到了体现(这是我们区域赛前唯一的两次比较正式的比赛)。那一次的长沙邀请赛据说有好多World Finals队参加,而我们如愿的拿到了一枚金牌以及学校第6的排名(Ranklist);而北大校赛我们则排在学校第四(清华、北大、北理工在我们前边)。接下来是暑假的时候,我和whd一起组队做电子科大的集训,以及当做个人赛做北京师范大学的暑假集训(wdp在学英语,所以到后期才加入),成绩也还不错。
接下来就是大三了,由于数学建模的缘故,我们队没有参加前两次网络赛(其中第一场我们后来当做个人练习做了一次,我当时一个人就做到了学校排名第6),后面的三场我们都是严格模拟真实比赛的情形来做的,其中最好的一次是最后一场(Ranklist),我们做到了学校排名第6。我们还做了10场多校联合,其中有3次队伍排名进入前10。同时,我做了好久的Codeforces也终于在参加区域赛前第一次变红了。这些成绩让我觉得Acme今年进World Finals是很有希望的。果然,我们在第一站成都悲剧的挂掉之后还是顶住了压力,在长沙以学校排名第4的成绩顺利出线(Ranklist)。
今天ACM-ICPC官网终于登出了晋级World Finals的名单,而我终于可以大声的喊出:“Hello, ACM-ICPC World Finals!”

ACME Training Six to Eight – SGU problems solving[long-term,individual]

本次训练为刷SGU前100题,我负责100-139,wdp负责140-169,whd负责170-199。
link:
100 A+B
101 Domino 欧拉回路
102 Coprimes 最大公约数
103 Traffic Lights 动态计算边权的最短路
104 Little Shop of Flowers 动态规划
105 Div 3 数学题
106 The Equation 扩展欧几里得算法解不定方程
107 987654321 problem 暴力打表
108 Self-numbers II 类似宽搜的算法
109 Magic of David Copperfield II 二分染色 构造
110 Dungeon 计算几何
111 Very simple problem 高精度开根号运算 牛顿迭代法
112 a^b – b^a 高精度
113 Nearly prime numbers 简单数论
114 Telecasting station 贪心
115 Calendar 时间处理
116 Index of super-prime 数论 动态规划
117 Counting 快速幂
118 Digital root 高精度
119 Magic pairs 数学
120 Arhipelago 计算几何
121 Bridges painting 构造法
122 The book 构造法 Ore定理
123 The sum 递推
124 Broken line 计算几何 射线法判断点是否在简单多边形内
125 Shtirlits 搜索
126 Boxes 2406 数学 二进制下的欧几里得算法
127 Telephone directory
130 Circle 动态规划
131 Hardwood floor 状态压缩的动态规划
132 Another Chocolate Maniac 状态压缩的动态规划 DFS预处理可行转移

133  Border 排序
134  Centroid 树形DP
135  Drawing Lines 数学题
136  Erasing Edges 计算几何
137  Funny Strings 数论 构造法
138  Games of Chess 构造法
139  Help Needed! 判断15数码是否有解

2012.12.16 ACME Training Five – The 7th(2012) ACM Programming Contest of HUST – Onsite Contest(Semilive)[team,live]

We started about 50 mins after the contest had begun.
#I AC 61 mins
Brute force
#E AC 105 mins
Greedy
#A AC 113 mins 2 wrong tries by WHD
#C AC 126 mins 1 wrong try
AC automation
#H AC 153 mins 1 wrong try
Math
#F AC 224 mins 1 wrong try
Game theory
#B AC 259 mins 5 wrong tries
The solution for this problem is first written by WHD. I rewrote it and got AC after 1 wrong try.
#J AC 284 mins 4 wrong tries by WHD
WHD used a right algorithm to solve this problem, but made a small mistake. After I found it out, WHD corrected it and got AC.

2012.12.9 ACME Training Four – The 7th(2012) ACM Programming Contest of HUST – Preliminary Contest[team]

#B AC 31 min 1 wrong try by WHD
#A AC 50 min by WDP
#D AC 75 min 3 wrong tries by WHD
#G AC 79 min 5 wrong tries
It can be solved by brute force, but I used DP to solve it, so I wasted a lot of time.
#C AC 94 min 1 wrong try
For a query, if b>sqrt(n), we can response it by brute force.
After do some preparations in O(n^1.5), we can response qeuries whose b<=sqrt(n) in O(1).
#F AC 118 min 1 wrong try by WHD
#E AC 179 min by WDP

2012.12.5 ACME Training Three – Graph Theory Problems[individual]

URAL 1272 Non-Yekaterinburg Subway
Disjoint-set

URAL 1156 Two Rounds
Bipartite graph
Knapsack problem

URAL 1128 Partition into Groups
Bipartite graph
I got RE because I used a variable at a wrong place (it should be j, but I wrote i there) and wasted lots of time to debug it.

URAL 1400 Cellular Characters
BFS
I got WA because I used “\n” when output. When I changed it to “%n” I got AC.

URAL 1630 Talisman
It must be a straight line, a point, a triangle or a tetrahedron.

2012.12.2 ACME Training One – The 2012 ACM-ICPC Asia Chengdu Regional Contest[team]

This is my first cooperation with my new teammates, WDP and WHD. Our team is called ACME, which can be understood as AC me, or it original meaning the peak.
#A AC 8min 1 wrong try by WHD
#I AC 17min
It is a typical DP problem.
#B AC 76min 1 wrong try
It is a math problem. WDP told me the meaning of the problem, and I come up with a formula soon.
Let f(p) be p*sum{p^n*(1-p)^i*C(i,n+1)*(n-i);i=0 to n}.
The answer will f(p)+f(1-p).
However for some certain i, p^n*(1-p)^i*C(i,n+1)*(n-i) can be too small, to avoid underflow errors we can calculate ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) instead.
When we use it, we use e^ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) and if ln(p^n*(1-p)^i*C(i,n+1)*(n-i)) is too small we just ignore it.
We come up with a n^1.5*logn algorithm for problem C and got TLE. We also used the algorithm proved to be right to solve problem K, but didn’t get AC. I think it must be some bugs when facing edge cases.

[The 2009 ACM-ICPC Asia Harbin Regional Contest]G.Fuzzy Google Suggest

字典树。

CODE:

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#include <cassert>

#include <sstream>

#include <map>

#include <vector>

#include <set>

using namespace std;

 

struct Trie

{

    Trie* f;

    Trie* c[26];

    int d;

};

Trie pool[4*1024*1024];

Trie* top=pool;

Trie* root;

#define f(x) ((x)-‘a’)

 

void calc(Trie* p,char* s,int d,set<Trie*>& get)

{

    if (p)

    {

       if (*s)

       {

           calc(p->c[f(*s)],s+1,d,get);

           if (d)

           {

              for (int i=0;i<26;i++)

                  calc(p->c[i],s,d-1,get);

              for (int i=0;i<26;i++)

                  calc(p,s+1,d-1,get);

              for (int i=0;i<26;i++)

                  calc(p->c[i],s+1,d-1,get);

           }

       }

       else get.insert(p);

    }

}

 

 

int main()

{

    root=top++;

    int n,m;

    cin>>n;

    for (int i=0;i<n;i++)

    {

       char db[16];

       cin>>db;

       Trie* p=root;

       char* s=db;

       while (*s)

       {

           if (!p->c[f(*s)]) top->f=p,p->c[f(*s)]=top++;

           p=p->c[f(*s)];

           p->d++;

           s++;

       }

    }

    cin>>m;

    for (int i=0;i<m;i++)

    {

       char s[1024];

       int d;

       cin>>s>>d;

       set<Trie*> get;

       calc(root,s,d,get);

       int answer=0;

       for (set<Trie*>::reverse_iterator it=get.rbegin();it!=get.rend();it++)

       {

           Trie* p=*it;

           int delta=p->d;

           while (p!=root)

           {

              p=p->f;

              set<Trie*>::iterator t=get.find(p);

              if (t!=get.end()) delta=0;

           }

           answer+=delta;

       }

       cout<<answer<<endl;

    }

}