作者归档：Eurce

[POJ 1925]

继续DP。

这题看了数据规模后，一直陷在惯性思维里面：总以为复杂度应该是O(N^2)，结果怎么想也推不出DP公式。

主要是因为这里每个建筑对应的落点有两个值：x坐标和跳数，这两个值之间并无优劣关系，无法简易去重。考虑使用类似边表的方式将每个建筑的所有落点全部存下，再状态转移，发现内存和复杂度都太大。

然后无奈之下写了个SPFA，状态点是xc[1000001]，保存的是到某x坐标时的最小跳数。这种复杂度是O(5000*10^6)，略微超了。

最后看了discuss才明白每个建筑对应的起跳点是有范围的，可以算出来的。由此可以将复杂度降到O(5000*sqrt(10^6))，便能过了。

#include<cstdio>
#include<cstring>
#include<cmath>

int n,x[5000],y[5000],xc[1000001],xi,yi,xj,mn;

int main()
{
    int i,j,k,l;
    i=-0.5;
    scanf("%*d");
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++) scanf("%d%d",x+i,y+i);
        memset(xc,127,sizeof xc);
        mn=0x7f7f7f7f;
        yi=y[0];
        xc[0]=0;
        for(i=1;i<n;i++)
        {
            xi=ceil(x[i]-sqrt((2.0*y[i]-yi)*yi));
            if(xi<0) xi=0;
            for(;xi<x[i];xi++)
            {
                xj=x[i]+x[i]-xi;
                if(xj>=x[n-1]) mn=xc[xi]+1<mn?xc[xi]+1:mn;
                else xc[xj]=xc[xi]+1<xc[xj]?xc[xi]+1:xc[xj];
            }
        }
        if(mn>=0x7f7f7f7f) puts("-1");
        else printf("%d\n",mn);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

int n,x[5000],y[5000],xc[1000001],xi,yi,xj,mn;

int main()

{

int i,j,k,l;

i=-0.5;

scanf("%*d");

while(~scanf("%d",&n))

{

for(i=0;i<n;i++) scanf("%d%d",x+i,y+i);

memset(xc,127,sizeof xc);

mn=0x7f7f7f7f;

yi=y[0];

xc[0]=0;

for(i=1;i<n;i++)

{

xi=ceil(x[i]-sqrt((2.0*y[i]-yi)*yi));

if(xi<0) xi=0;

for(;xi<x[i];xi++)

{

xj=x[i]+x[i]-xi;

if(xj>=x[n-1]) mn=xc[xi]+1<mn?xc[xi]+1:mn;

else xc[xj]=xc[xi]+1<xc[xj]?xc[xi]+1:xc[xj];

}

if(mn>=0x7f7f7f7f) puts("-1");

else printf("%d\n",mn);

}

return 0;

}

回顾了一下自己没有想出解法的原因，都是太过于沉浸在惯性思维中，无法跳出来从其他角度构建思路。这种毛病一直都有。究其原因，大概是总无法确定先前的思路是否真的无解，从而放不下，每次思路有所进展后又绕回来重新回到死路上，从而让思考的深度和效率都大打折扣。如果能够把握思路，将不可能的不确定性全部排除，也许就能高效地找到正确求解方向了。

我想如果要做到这些，也没有其他办法的，只有多练多想了。

继续努力。

[POJ 3280]

发表回复

Cheapest Palindrome

典型的DP。

首先用一个DP判断s[i…i+l]是否回文，这可以根据s[i+1…i+l-1]是否回文以及s[i]==s[i+l]得到。这里最外层循环是l，也即回文串的长度。随后是要计算将s[1…i-1]和s[i+l+1…m]转化成完全相同的最小花费，这里可以用另一个DP预处理得到。

#include<cstdio>
#include<cstring>

int n,m,a[26],d[26],mn,dp[2001][2001];
char s[2002],p[2001][2001];

inline bool isp(int l,int r)
{
    if(l>=r) return true;
    return p[l][r];
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int i,j,k,l;
    char c[2];
    while(~scanf("%d%d",&n,&m))
    {
        scanf("%s",s+1);
        memset(p,0,sizeof p);
        mn=0x7fffffff;
        for(i=0;i<n;i++)
        {
            scanf("%s%d%d",c,&j,&k);
            l=c[0]-'a';
            a[l]=j;
            d[l]=k;
        }
        for(i=1;i<m;i++)
        {
            dp[i][0]=dp[i-1][0]+min(a[s[i]-'a'],d[s[i]-'a']);
            dp[0][i]=dp[0][i-1]+min(a[s[m+1-i]-'a'],d[s[m+1-i]-'a']);
        }   
        for(i=1;i<m;i++)
        {
            for(j=1;j+i<m;j++)
            {
                if(s[i]==s[m+1-j]) dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=min(
                        dp[i-1][j]+min(a[s[i]-'a'],d[s[i]-'a']),
                        dp[i][j-1]+min(a[s[m+1-j]-'a'],
                        d[s[m+1-j]-'a']));
            }
        }
        for(l=0;l<m;l++)
        {
            for(i=1;i+l<=m;i++)
            {
                if(isp(i+1,i+l-1)&&s[i]==s[i+l])
                {
                    p[i][i+l]=1;
                    mn=min(dp[i-1][m-i-l],mn);
                }
            }
        }
        printf("%d\n",mn);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int n,m,a[26],d[26],mn,dp[2001][2001];

char s[2002],p[2001][2001];

inline bool isp(int l,int r)

{

if(l>=r) return true;

return p[l][r];

}

inline int min(int a,int b)

{

return a<b?a:b;

}

int main()

{

int i,j,k,l;

char c[2];

while(~scanf("%d%d",&n,&m))

{

scanf("%s",s+1);

memset(p,0,sizeof p);

mn=0x7fffffff;

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

{

scanf("%s%d%d",c,&j,&k);

l=c[0]-'a';

a[l]=j;

d[l]=k;

}

for(i=1;i<m;i++)

{

dp[i][0]=dp[i-1][0]+min(a[s[i]-'a'],d[s[i]-'a']);

dp[0][i]=dp[0][i-1]+min(a[s[m+1-i]-'a'],d[s[m+1-i]-'a']);

}

for(i=1;i<m;i++)

{

for(j=1;j+i<m;j++)

{

if(s[i]==s[m+1-j]) dp[i][j]=dp[i-1][j-1];

else

dp[i][j]=min(

dp[i-1][j]+min(a[s[i]-'a'],d[s[i]-'a']),

dp[i][j-1]+min(a[s[m+1-j]-'a'],

d[s[m+1-j]-'a']));

}

for(l=0;l<m;l++)

{

for(i=1;i+l<=m;i++)

{

if(isp(i+1,i+l-1)&&s[i]==s[i+l])

{

p[i][i+l]=1;

mn=min(dp[i-1][m-i-l],mn);

}

printf("%d\n",mn);

}

return 0;

}

[POJ 1191]

发表回复

棋盘分割

分类里属于DP。分别用DP和搜索两种方法进行了求解。一开始想的就是搜索，加了一个求剩余块均方差的剪枝就AC了，110MS。后面的DP就没有任何优化，直接是整个5维数组全算一遍的，但也0MS了。

搜索：

#include<cstdio>
#include<cstring>
#include<cmath>

int n,a[9][9],b[9][9];
double md;
double mnmsd;

void dfs(int d,int xl,int yb,int xr,int yt,double e,double r)
{
    int i,j,k,l;
    double f;
    if(d==n-1)
    {
        f=b[xr][yt]-b[xr][yb-1]-b[xl-1][yt]+b[xl-1][yb-1];
        e+=pow(f-md,2);
        double msd=sqrt(e/n);
        mnmsd=msd<mnmsd?msd:mnmsd;
        return;
    }
    if(sqrt((e+pow(r/(n-d)-md,2))/n)>=mnmsd) return;
    for(i=xl;i<xr;i++)
    {
        f=b[i][yt]-b[xl-1][yt]-b[i][yb-1]+b[xl-1][yb-1];
        dfs(d+1,i+1,yb,xr,yt,e+pow(f-md,2),r-f);
        f=b[xr][yt]-b[i][yt]-b[xr][yb-1]+b[i][yb-1];
        dfs(d+1,xl,yb,i,yt,e+pow(f-md,2),r-f);
    }
    for(j=yb;j<yt;j++)
    {
        f=b[xr][j]-b[xl-1][j]-b[xr][yb-1]+b[xl-1][yb-1];
        dfs(d+1,xl,j+1,xr,yt,e+pow(f-md,2),r-f);
        f=b[xr][yt]-b[xl-1][yt]-b[xr][j]+b[xl-1][j];
        dfs(d+1,xl,yb,xr,j,e+pow(f-md,2),r-f);
    }
}

int main()
{
    int i,j,k,l;
    while(~scanf("%d",&n))
    {
        mnmsd=1e30;
        md=0;
        memset(b,0,sizeof b);
        k=0;
        for(i=1;i<=8;i++)
        {
            for(j=1;j<=8;j++)
            {
                scanf("%d",&a[i][j]);
                md+=a[i][j];
                k+=a[i][j];
                b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
            }
        }
        md/=n;
        dfs(0,1,1,8,8,0,k);
        printf("%.3f\n",mnmsd);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

int n,a[9][9],b[9][9];

double md;

double mnmsd;

void dfs(int d,int xl,int yb,int xr,int yt,double e,double r)

{

int i,j,k,l;

double f;

if(d==n-1)

{

f=b[xr][yt]-b[xr][yb-1]-b[xl-1][yt]+b[xl-1][yb-1];

e+=pow(f-md,2);

double msd=sqrt(e/n);

mnmsd=msd<mnmsd?msd:mnmsd;

return;

}

if(sqrt((e+pow(r/(n-d)-md,2))/n)>=mnmsd) return;

for(i=xl;i<xr;i++)

{

f=b[i][yt]-b[xl-1][yt]-b[i][yb-1]+b[xl-1][yb-1];

dfs(d+1,i+1,yb,xr,yt,e+pow(f-md,2),r-f);

f=b[xr][yt]-b[i][yt]-b[xr][yb-1]+b[i][yb-1];

dfs(d+1,xl,yb,i,yt,e+pow(f-md,2),r-f);

}

for(j=yb;j<yt;j++)

{

f=b[xr][j]-b[xl-1][j]-b[xr][yb-1]+b[xl-1][yb-1];

dfs(d+1,xl,j+1,xr,yt,e+pow(f-md,2),r-f);

f=b[xr][yt]-b[xl-1][yt]-b[xr][j]+b[xl-1][j];

dfs(d+1,xl,yb,xr,j,e+pow(f-md,2),r-f);

}

int main()

{

int i,j,k,l;

while(~scanf("%d",&n))

{

mnmsd=1e30;

md=0;

memset(b,0,sizeof b);

k=0;

for(i=1;i<=8;i++)

{

for(j=1;j<=8;j++)

{

scanf("%d",&a[i][j]);

md+=a[i][j];

k+=a[i][j];

b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];

}

md/=n;

dfs(0,1,1,8,8,0,k);

printf("%.3f\n",mnmsd);

}

return 0;

}

DP：

#include<cstdio>
#include<cstring>
#include<cmath>

int n,a[9][9],b[9][9];
double md,dp[9][9][9][9][16];

double calc(int xl,int yb,int xr,int yt,int c)
{
    if(c==1) return pow(b[xr][yt]-b[xl-1][yt]-b[xr][yb-1]+b[xl-1][yb-1]-md,2);
    int i;
    double e=1e30,f;
    for(i=xl;i<xr;i++)
    {
        f=dp[xl][yb][i][yt][1]+dp[i+1][yb][xr][yt][c-1]*(c-1);
        e=f<e?f:e;
        f=dp[xl][yb][i][yt][c-1]*(c-1)+dp[i+1][yb][xr][yt][1];
        e=f<e?f:e;
    }
    for(i=yb;i<yt;i++)
    {
        f=dp[xl][yb][xr][i][1]+dp[xl][i+1][xr][yt][c-1]*(c-1);
        e=f<e?f:e;
        f=dp[xl][yb][xr][i][c-1]*(c-1)+dp[xl][i+1][xr][yt][1];
        e=f<e?f:e;
    }
    return e/c;
}

int main()
{
    int h,i,j,k,l;
    double e,f;
    while(~scanf("%d",&n))
    {
        memset(b,0,sizeof b);
        memset(dp,127,sizeof dp);
        md=0;
        for(i=1;i<9;i++)
            for(j=1;j<9;j++)
            {
                scanf("%d",&a[i][j]);
                b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
                md+=a[i][j];
            }
        md/=n;
        for(h=0;h<8;h++)
            for(i=0;i<8;i++)
                for(j=1;j+h<9;j++)
                    for(k=1;k+i<9;k++)
                        for(l=1;l<=n;l++)
                            dp[j][k][j+h][k+i][l]=calc(j,k,j+h,k+i,l);
        printf("%.3f\n",sqrt(dp[1][1][8][8][n]));
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

int n,a[9][9],b[9][9];

double md,dp[9][9][9][9][16];

double calc(int xl,int yb,int xr,int yt,int c)

{

if(c==1) return pow(b[xr][yt]-b[xl-1][yt]-b[xr][yb-1]+b[xl-1][yb-1]-md,2);

int i;

double e=1e30,f;

for(i=xl;i<xr;i++)

{

f=dp[xl][yb][i][yt][1]+dp[i+1][yb][xr][yt][c-1]*(c-1);

e=f<e?f:e;

f=dp[xl][yb][i][yt][c-1]*(c-1)+dp[i+1][yb][xr][yt][1];

e=f<e?f:e;

}

for(i=yb;i<yt;i++)

{

f=dp[xl][yb][xr][i][1]+dp[xl][i+1][xr][yt][c-1]*(c-1);

e=f<e?f:e;

f=dp[xl][yb][xr][i][c-1]*(c-1)+dp[xl][i+1][xr][yt][1];

e=f<e?f:e;

}

return e/c;

}

int main()

{

int h,i,j,k,l;

double e,f;

while(~scanf("%d",&n))

{

memset(b,0,sizeof b);

memset(dp,127,sizeof dp);

md=0;

for(i=1;i<9;i++)

for(j=1;j<9;j++)

{

scanf("%d",&a[i][j]);

b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];

md+=a[i][j];

}

md/=n;

for(h=0;h<8;h++)

for(i=0;i<8;i++)

for(j=1;j+h<9;j++)

for(k=1;k+i<9;k++)

for(l=1;l<=n;l++)

dp[j][k][j+h][k+i][l]=calc(j,k,j+h,k+i,l);

printf("%.3f\n",sqrt(dp[1][1][8][8][n]));

}

return 0;

}

[POJ 3373]

1条回复

Changing Digits

好久没做POJ了。依然跟随POJ题目分类表，这题属于”记忆化搜索”。

貌似是要求高精度，但稍微分析下便知道，由于k<=10,000，那么n最多改变4位数字便一定能被k整除的，因此这里还是使用int除法，递归修改n的每位数字时顺便求出当前模值即可。搜索的思路很容易出，由条件3和4，易得到搜索的方向：（1）由改变较少位数开始；（2）从高位开始。但是剪枝还是稍微想了一下。最后发现，根据dfs的传入参数，若该次dfs失败，可以用数组标记该参数组合无法满足题意。后续的搜索中，每次根据参数检查数组中对应位置是否已有标记，若是则直接返回0。其实不算难的一题，做的人却不多。另外，也开始习惯用vim敲程序了，开着fedora，窗口A左面vim，右面terminal（编译+运行），窗口B开着chrome读题，很是顺手哈哈。

#include<stdio.h>
#include<string.h>

int nl,K,b[102][5][10000];
char n[102];

int dfs(int i,int m,int mod)
{
    int j,k,l;
    char c,cc;
    if(i==nl)
    {
        if(!mod)
        {
            puts(n);
            return 1;
        }
        else return 0;
    }
    if(b[i][m][mod]) return 0;
    if(!m)
    {
        k=mod*10+n[i]-'0';
        if(k>=K) k%=K;
        j=dfs(i+1,m,k);
        if(j) return 1;
        else
        {
            b[i+1][m][k]=1;
            return 0;
        }
    }
    if(i)
    {
        c='0';
        cc=n[i];
        n[i]=c;
        k=mod*10+n[i]-'0';
        if(k>=K) k%=K;
        if(c==cc) j=dfs(i+1,m,k);
        else j=dfs(i+1,m-1,k);
        if(j) return 1;
        n[i]=cc;
    }
    for(c='1';c<='9';c++)
    {
        cc=n[i];
        n[i]=c;
        k=mod*10+n[i]-'0';
        if(k>=K) k%=K;
        if(c==cc) j=dfs(i+1,m,k);
        else j=dfs(i+1,m-1,k);
        if(j) return 1;
        n[i]=cc;
    }
    b[i][m][mod]=1;
    return 0;
}

int main()
{
    int i,j;
    while(~scanf("%s%d",n,&K))
    {
        nl=strlen(n);
        memset(b,0,sizeof b);
        if(nl==1)
        {
            if(n[0]=='0'+K) puts(n);
            else puts("0");
            continue;
        }
        for(i=j=0;i<=nl&&!j;i++)
            j=dfs(0,i,0);
    }
    return 0;
}

#include<stdio.h>

#include<string.h>

int nl,K,b[102][5][10000];

char n[102];

int dfs(int i,int m,int mod)

{

int j,k,l;

char c,cc;

if(i==nl)

{

if(!mod)

{

puts(n);

return 1;

}

else return 0;

}

if(b[i][m][mod]) return 0;

if(!m)

{

k=mod*10+n[i]-'0';

if(k>=K) k%=K;

j=dfs(i+1,m,k);

if(j) return 1;

else

{

b[i+1][m][k]=1;

return 0;

}

if(i)

{

c='0';

cc=n[i];

n[i]=c;

k=mod*10+n[i]-'0';

if(k>=K) k%=K;

if(c==cc) j=dfs(i+1,m,k);

else j=dfs(i+1,m-1,k);

if(j) return 1;

n[i]=cc;

}

for(c='1';c<='9';c++)

{

cc=n[i];

n[i]=c;

k=mod*10+n[i]-'0';

if(k>=K) k%=K;

if(c==cc) j=dfs(i+1,m,k);

else j=dfs(i+1,m-1,k);

if(j) return 1;

n[i]=cc;

}

b[i][m][mod]=1;

return 0;

}

int main()

{

int i,j;

while(~scanf("%s%d",n,&K))

{

nl=strlen(n);

memset(b,0,sizeof b);

if(nl==1)

{

if(n[0]=='0'+K) puts(n);

else puts("0");

continue;

}

for(i=j=0;i<=nl&&!j;i++)

j=dfs(0,i,0);

}

return 0;

}

这段时间有点迷茫，不知道接下来学什么好，能够交流的人也好少。又买了Effective C++和APUE，还是希望能把C++和Linux学得扎实一点。

今天也去了下阿里巴巴组织的大学生课堂，好久没听过课了，加上坐得比较远，实际没听到多少内容。倒是见识到好多牛人，都能各种和讲师交流了。就目前自己了解到的信息，还是很想去阿里的，但现在还不太够格。

亲爱的妈妈，不是我不想追女生，只是现在只能一心追时间啊。

Fedora 19 + Win 7 + Mac OS X

发表回复

抱歉标题党了……其实这并不是关于单机三系统的文章，只是一点牢骚。

8月24日，这个值得纪念的日子里，我迎娶了又一位小老婆……没错，就是那13年新款的Mac Book Air。

包括像什么第4代I5下HD5000核显的强悍性能以及超低功耗，采用PCI-E接口的256G SSD带来的比上一代多50%的速度提升，以及仅仅1.3kg的机身重量和12小时的超强续航，我想都没有必要再作赘述。如果要用一个字总结我对小老婆的爱，那我希望是能用她再写100百万行代码。

新的Mac系统现在还不能完全操控自如，但其触摸版已经给我留下了非常深刻的印象。虽然这么多年都习惯用鼠标，但尝试了几种常用手势后我就很快适应了——手势操作独有的便利性实在太过好用。

与其而来的还有另一个好处：现在我有两台笔记本了（大老婆HP dm3-1010tx)，再也不用怕系统崩掉就什么也做不了了。再加上dm3的CentOS6.4刚好被我玩坏了（贪图方便+脑袋一抽 sudo chmod 777 /usr/ -R……好孩子千万不要学），便又开始手痒各种折腾啦。

一直以来都很想尝试Archlinux。常常看到各种论调“学会xxx，你就会了xxx；但学会Arch，你便学会了Linux”，“Arch是适合真正有动手能力的人的”……等等等等，再加上论坛上不时传来各种Arch用户的哀嚎和呻吟，实在让我是心痒难耐阿！！！于是就在昨天晚上，我正式踏上了这条愚蠢的不归路。

看到这里，再回头看看标题，其实已经可以猜到我最后失败了……但在这里也希望把我做过的所有无谓挣扎稍作记录，因为我很清楚自己以后还会再来受虐……

Archlinux的资料和社区在我用过的几个linux发行版里算是非常优秀的了。包括很赞的Archlinux Wiki以及中文社区，不难看出很多人为这个系统付出了大量心血，并且用Arch的人很多都抱有乐于分享的精神。最初我是根据安装指南来进行的，但无奈第一步网络配置就有问题：我是在实验室环境安装arch的，但这里有（1）有线的静态ip；（2）有线的动态ip（需登陆网关）；（3）无线的动态ip（需登陆网关）。由于是在命令行下进行系统安装，我是不知道如何能打开浏览器然后登陆网关了……然后配置静态ip上网的时候，dns怎样也配置不上，按照wiki上的建议，是修改/etc/resolv.conf，增加nameserver 8.8.8.8，但没有用。而由于由源安装软件时，是必须对源地址进行dns解释的。这一步我想了很久很久，各种尝试仍然无果。最后只能非常愚蠢的增加了类似http://141.219.155.230/archlinux/$repo/os/$arch这样的源，然后总算是顺利安装上了后面一大堆东西，包括grub检测win7启动项以及安装gdm和gnome。昨晚是9点多开始装的，一直到凌晨3点左右，才第一次见到gnome3的桌面……当时真的是有种不敢相信自己眼睛的感觉阿……竟然成功了。。。

但快乐果然是短暂的，随之而来的又有一大堆新问题，远远不是安装指南上寥寥数语就解决一切的那么简单（话说论坛上那些是真的好心人吗？）……最严重的问题在于pacman很多软件都没有，按照安装指南的做法，是需要安装一个叫yaourt的工具，作用是在AUR仓库中查找所需软件。但是根据指南的做法，直接添加源后安装会提示PGP签名错误。而按照WIKI的方法，下载了foo.tar.gz后，需要安装Haskell，而后者又依赖GHC。而这个GHC我怎么装也装不上。然后到这里已经是5点了，实在熬不住，就睡觉去了。

第二天中午吃完饭过来一开机，gdm没问题，gnome又进不去了。实在是心力交瘁弄不下去了……莫名其妙的问题好几百千万个，就算是官方WIKI上面很多内容也不对，实在是对这个系统没有信心：就算勉强能安装好，由于其滚动更新的特性，估计在我手里也只是快速滚向灭亡。

但大老婆放着不管也不行阿，这arch总不能就用来引导win7吧。还是先弄个靠谱点的凑合着用吧。Ubuntu什么的，实在没有太多好感。Debian倒是没用过，但安装盘竟然有3张DVD，吃不消。Gentoo、Slackware之类的，想想便毛骨悚然。。。OpenSUSE、Mint之类的却又不太好玩。回归CentOS吧，又不是很甘心。那么就Fedora吧，新出的19还没用过，虽然只是短期维护的系统，但其基于RH，而且界面很漂亮。我并没有长久使用这个版本的意思，现在拿起来玩玩刚刚好。

官网下载iso，刻碟，安装过程一路顺畅，没用多久就再次回到了gnome3。这版的Fedora比CentOS还方便，包括挂载NTFS格式的win7分区都不用再安装东西了。Network-Manager也是已经把pptp等VPN都预装好了。作了不多的一些配置后就能很顺手的使用了。暂时先这样吧。

或许真的是能力不够吧，第一次尝试Arch就这样失败了。但比起自我埋怨，更失望的是发现Arch Wiki和社区给出的流程资料竟然都不够完善。我相信其实有很多新手会像我一样尝试Arch，但仔细阅读了大量资料后迎面而来的还一直只是莫名其妙的错误，又有多少人会觉得很有意思？如果是出于锻炼人的目的，或许真有人能从中学到很多东西。但反正我是觉得，这样的学习方式不适合我。

最后上一张CentOS的遗照吧，到现在为止用过最喜欢的linux了。

Learning Vim

发表回复

发生错误，请稍后重试。

Pythoning…

发表回复

读了a byte of python后，顺手把a byte of vim也读了。唔，就是用起来还不是很顺手……

刚做的codeforces r195d2c，C一下就过了。。。python就一直TLE。看了下status，竟然没有用python3做的，python2的倒是有几个。明明只是N=10^5，O(N*lgN)的复杂度，却要各种找优化……看来python还真是非高手不能用：用C就是怎样烂的代码只要复杂度没错基本都能过，用python就非得尽量优化不可啊。。。

贴个code纪念一下吧：

n = int(input())
a = list(map(int, input().split()))

mxa = max(a)
v = 1 << 30
while v > mxa:
    v >>= 1

while True:
    d = -1
    for i in range(n):
        if a[i] & v:
            d &= a[i]
    if d % v == 0:
        break
    v >>= 1

b = [i for i in a if i & v]
print(len(b))
print(' '.join(map(str, b)))

n = int(input())

a = list(map(int, input().split()))

mxa = max(a)

v = 1 << 30

while v > mxa:

v >>= 1

while True:

d = -1

for i in range(n):

if a[i] & v:

d &= a[i]

if d % v == 0:

break

v >>= 1

b = [i for i in a if i & v]

print(len(b))

print(' '.join(map(str, b)))

这是C的，对比一下就清楚了，python是最后才构建b[]的，每次赋值太慢了：

int n,a[100000],k,b[100000];

int main()
{
	int i,d,v;
	while(~scanf("%d",&n))
	{
		k=0;
		for(i=0;i<n;i++) scanf("%d",a+i);
		for(v=1<<30;1;v>>=1)
		{
			k=0;
			d=-1;
			for(i=0;i<n;i++)
			{
				if(a[i]&v)
				{
					d&=a[i];
					b[k++]=a[i];
				}
			}
			if(d%v==0) break;
		}
		printf("%d\n",k);
		for(i=0;i<k-1;i++) printf("%d ",b[i]);
		printf("%d\n",b[k-1]);
	}
	return 0;
}

int n,a[100000],k,b[100000];

int main()

{

int i,d,v;

while(~scanf("%d",&n))

{

k=0;

for(i=0;i<n;i++) scanf("%d",a+i);

for(v=1<<30;1;v>>=1)

{

k=0;

d=-1;

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

{

if(a[i]&v)

{

d&=a[i];

b[k++]=a[i];

}

if(d%v==0) break;

}

printf("%d\n",k);

for(i=0;i<k-1;i++) printf("%d ",b[i]);

printf("%d\n",b[k-1]);

}

return 0;

}

Back to BUPT!

发表回复

20天的暑假，实在是不敢再呆在家里了，毕竟休息放松的目的已经达到了，还有很多要学……

假期一行代码都没有写。倒是读了一下A Byte of Python。薄薄的100多页，却是让人读完后就能马上动手，觉得这样才是真正快速上手一门语言的最好方式！以前也借过同学的大部头Python学习手册，这本书当时读起来真是太无味了……详尽的语言细节介绍不是不好，但对于一个新手来说，这些东西真的可以放一放再说。

也读了一本《别逗了,费曼先生》，非常喜欢。除了感慨费曼先生的才华，书里让我印象最深、同时也是最令我敬佩的一点是他对科学和教育的毫不妥协。生活中的费曼是一个好奇心旺盛（当过艺术家，做过鼓手），爱开玩笑以及做恶作剧的大男孩，但当被邀请参加学术会议、审阅教材时，他仿佛变了另一个人。即使得罪会议小组里的全部其他人，他也坚持自己的意见；即使其他审阅教材的评委都随意打分，他也坚持亲自阅读全部教材再给分。或许是为了点出本书主题，全书的最后一篇文章也是费曼一次关于科研态度的演讲。虽然都是非常简单的道理，但如今自己作为研究生时环视左右，能做到的又有几人？……

隐隐约约地觉得，身边追求成功的人，大致可以分为两种：一种人积累的是自我，追求独立人格和思想，比起“目的”，更在乎“手段”，目标是找到“正确的事”；另一种人积累的是客体，追求的是外在世界的认可，比起“手段”，更在乎“目的”，其人生态度大概可归纳为“实用主义”。在我看来，费曼是属于前者的。我无法判断怎样的人生更为理想，毕竟人人都有自己的生存方式。但若就我自身而言，可能要在第一条路上永不回头了（会倒在哪里呢？）。

之后也希望能好好珍惜研二这宝贵的最后一年。比起（眨眼即逝的）研一，加倍地燃尽自我吧。

ps: 又发现一个好blog。

[POJ 1961] & [POJ 2406]

发表回复

Period、Power Strings

研一离校前最后的两题了。

两题都是KMP，题意也比较相近的：给出字符串s（长度最多10^6），求模式为r^k的以s[0]开头的子串的k值。好久没写KMP了，但推了下明确思路后还是两题都1A了，对算法理解得也算还行吧……：

1961:

int t,sl,p[1000000],d[1000000];
char s[1000001];

int main()
{
	int i,j,k;
	while(~scanf("%d%s",&sl,s)&&sl)
	{
		memset(d,0,sizeof d);
		p[0]=-1;
		d[0]=1;
		for(i=1,j=-1;i<sl;i++)
		{
			while(j!=-1&&s[i]!=s[j+1]) j=p[j];
			if(s[i]==s[j+1]) j++;
			p[i]=j;
			if(j!=-1&&i==j+((j+1)/d[j])) d[i]=d[j]+1;
			else d[i]=1;
		}
		printf("Test case #%d\n",++t);
		for(i=0;i<sl;i++)
			if(d[i]>1) printf("%d %d\n",i+1,d[i]);
		puts("");
	}
	return 0;
}

int t,sl,p[1000000],d[1000000];

char s[1000001];

int main()

{

int i,j,k;

while(~scanf("%d%s",&sl,s)&&sl)

{

memset(d,0,sizeof d);

p[0]=-1;

d[0]=1;

for(i=1,j=-1;i<sl;i++)

{

while(j!=-1&&s[i]!=s[j+1]) j=p[j];

if(s[i]==s[j+1]) j++;

p[i]=j;

if(j!=-1&&i==j+((j+1)/d[j])) d[i]=d[j]+1;

else d[i]=1;

}

printf("Test case #%d\n",++t);

for(i=0;i<sl;i++)

if(d[i]>1) printf("%d %d\n",i+1,d[i]);

puts("");

}

return 0;

}

2406:

int sl,p[1000000],d[1000000];
char s[1000001];

int main()
{
	int i,j,k,l;
	while(~scanf("%s",s))
	{
		sl=strlen(s);
		if(sl==1&&s[0]=='.') break;
		p[0]=-1;
		d[0]=1;
		for(i=1,j=-1;i<sl;i++)
		{
			while(j!=-1&&s[i]!=s[j+1]) j=p[j];
			if(s[i]==s[j+1]) j++;
			if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;
			else d[i]=1;
		}
		printf("%d\n",d[sl-1]);
	}
	return 0;
}

int sl,p[1000000],d[1000000];

char s[1000001];

int main()

{

int i,j,k,l;

while(~scanf("%s",s))

{

sl=strlen(s);

if(sl==1&&s[0]=='.') break;

p[0]=-1;

d[0]=1;

for(i=1,j=-1;i<sl;i++)

{

while(j!=-1&&s[i]!=s[j+1]) j=p[j];

if(s[i]==s[j+1]) j++;

if(j!=-1&&i==j+(j+1)/d[j]) d[i]=d[j]+1;

else d[i]=1;

}

printf("%d\n",d[sl-1]);

}

return 0;

}

出乎意料地暑假竟然放满了。又可以制定各种不切实际的计划了吗？…

[Hackerrank]

发表回复

最近好多天都没更新，其实是跑去做比赛啦：20/20 Hack July

（又）是qoshi同学推荐的比赛，本来也想偷懒水水过去，但稍微做了下后发现还挺好玩。。。然后由于这比赛竟然持续9天，到后面就完全陷在里面无法自拔了。。。

hackerrank这个网站貌似是几个印度人办的，刚开张没多久的样子，不过界面做得好漂亮，很多设计也非常人性化，虽然BUG也不少，但总体来说在这里做题还是很享受的。

这次的20/20 Hack July比赛应该是类似月赛的形式吧，虽然不似codeforces、topcoder那么知名，但却也有不少神牛的（比如winger，09年ICPC世界冠军）。赛制是9天7题，包括5题算法题和2题GAME。其中算法题是按case给分的，没有罚时，没有提交惩罚。GAME则是提交AI程序，具体的内容包括两种，一种是单人，一种有对手的。

前3题都是比较简单的，第一题是输入一串字符，要求判断是否能构成对称字符串；第二题是输入一串字符，问总共能构成多少种对称字符串；第三题是问2^n的前k和后k个数字是多少，用了long double和2分后也是一下就过了。

第4题Computer Game则卡了3天。题意是输入n和两个int数组a[n]和b[n]，其中a[i]和b[j]间有边当且仅当它们非互质。问a[i]和b[j]两两配对，最多能有多少对？

这是一题典型的最大二分匹配。一开始我是建了一张大图，即边表里直接存a[i]到b[j]的边，过了几组小数据，后面都是超内存了（稠图的情况）。这个时候，Arios（又）来拯救我了……被告知可以考虑建两个边表，第一个存的是a[i]到p[k]，第二个存p[k]到b[j]，其中p[k]是某个素数。这样内存的问题解决了，开始TLE了。那几天里想了很多优化（大多没有用），又看了其他一些二分图匹配算法（也没比匈牙利好），也随便记录下吧就当是愚蠢的见证。。。说说最主要的优化点，其实就在于每轮匈牙利时，遍历边表时，由于边表是两重的，是可以从之前遍历到的位置开始继续遍历的，例如a[n]={2,4,7},b[n]={8,6,10}，a[0]、a[1]都通过p[0]=2与b[0]、b[1]、b[2]相连，在迭代的过程中，如果a[0]时已经遍历到了b[1]，那么到a[1]时直接检查b[2]就可以了，前面的元素都是已经在父迭代里遍历过的，这样可以将遍历复杂度降到O(9*N)，这个9是因为每个int最多有9个不同的素因子。另外就是再开了一个表，用来记录某素因子对应的第一个还没匹配的b[j]，每轮匈牙利时先尝试O（1）地匹配尚未匹配的元素。

另外还加了一堆稀里糊涂的scanf(“%d”)改getchar()，递归改非递归，按b[i]素因子个数小到大建表等等……也不知到哪个有用哪个没用，程序也写得一团遭，但总算是过了……这题最后就17个人拿了满分，应该也算本场最难的一题了吧。

第5题，这题我纯粹是利用规则漏洞了。主要是题目重复提交竟然不罚分，a、b的范围太小，时间复杂度卡得也不紧，直接O(lgN)试出test case然后O(9*10^10)离线算出结果就过了。Arios这题推出了数学解法，再次OTL一下。。。

第6题，单人GAME，这题大家分数都差不多了。

第7题Ultimate Tic Tac Toe，我觉得是本场最好玩的一题了。正如其名“最终井字棋”，它的棋盘分为大井字和小井字，大井字里每格是一个小井字，每个小井字的胜负判定和原本的井字棋相同，大井字根据小井字的结果来判断胜负，也即某方赢了某格小井字棋，就相当与在大井字里走了一步。这里有个先后手间的制约：先手如果走的是某个小井字的i,j位置，那么后手需要在第i,j个小井字里走；但如果第i,j个小井字胜负已定，那么后手可以选大井字中的任意位置。最后的胜负由大井字的结果决定。

规则还是很简单的……但要写出百战百胜的AI，也不是一件容易的事……根据Arios的说法，这种称为“博弈搜索”，即根据既定的盘面评估出自己最优的走法，然后分析对手最优走法以作修正，依次迭代迭代直到一定深度。

最后几天其实大家都已经拿完前面所有分了，因此排名也就全看这一题了。这题我的评分策略应该还是不准确，总是有几个人让我保持全败记录（winger貌似对所有人都轻松全胜…）。期间也出现过一些低级错误（交错语言直接扣4分啦，程序各种TLE判负啦）……最后排名第9，也还算过得去吧。

然后就是最后的global leaderboard了，虽然只是很小规模的比赛，但还是做得很开心。。。希望这次能收到T-shirt吧。。。