月度归档：2013年09月

[POJ 2348]

博弈问题。

输入是两个数A、B（设A>=B），有两个人轮流操作，每轮可以从A中减去B*k，k满足A>=B*k，随后令A’=A-B*k，A=max(A’,B)，B=min(A’,B)，再进行下一轮。先使得B==0的人获胜。

分析题意易得，A、B两数的组合每次的mxk=A/B值决定了当前选手是否拥有主动权：若mxk>1，那么自己可以选择(mxk-1)，对手只能选1，下一轮依然自己先选，若下一轮mxk==1还可以本轮自己全取，依然是主动；但若mxk==1，那么自己这轮就无法选择了。由于这里每轮都是最优操作，那么首先获得主动权的人可以赢得比赛。由此迭代更新A、B，并找到首先不为1的A/B值，此轮的先手就是赢家。

另外，最后一组A、B的值无关紧要，因为此时无论谁先手，都必定全取k=A/B。

#include<cstdio>

int a,b;

int main()
{
    int i,w;
    while(~scanf("%d%d",&a,&b)&&a)
    {
        if(a<b) a^=b^=a^=b;
        for(w=1;a%b&&a/b==1;w^=1,i=a,a=b,b=i%b);
        puts(w?"Stan wins":"Ollie wins");
    }
    return 0;
}

#include<cstdio>

int a,b;

int main()

{

int i,w;

while(~scanf("%d%d",&a,&b)&&a)

{

if(a<b) a^=b^=a^=b;

for(w=1;a%b&&a/b==1;w^=1,i=a,a=b,b=i%b);

puts(w?"Stan wins":"Ollie wins");

}

return 0;

}

[POJ 1286]

发表回复

Necklace of Beads

第一题Polya计数，好有意思的定理。

题目输入很简单，就是一个n，问n个在环上等距放置的球，可以用3种颜色染色，用各种方式（旋转/翻转）去除重复染色方案后，输出总染色方案数。

看完Polya定理后，结合题目条件想了一下便推出了解：

若另某个位置为0，顺时针方向依次为位置0、1、……、n-1，那么，可以分别另0号球于0、1、……、n-1开始，沿顺时/逆时针方向依次摆下其余编号的球，那么总共有2n种不同的置换方案的，这也是覆盖了全部置换的情况。接下来便是对每种置换方案计算各自的轮换数了，这步也很简单的，对每个不在自己位置且未标记的球迭代求对应的轮换，每次找到新的轮换都将对应方案的轮换数增一即可。最后sum(pow(3,ci))/2n便是结果了。

本来以为可以1A的。。。结果没考虑n=0的情况。。。还是太嫩了。。。

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

int n,p[24],b[24],c[46];
long long d;

int main()
{
    int i,j,k,l,cl;
    while(~scanf("%d",&n)&&~n)
    {
        memset(c,0,sizeof c);
        for(i=cl=0;i<n;i++)
        {
            for(k=i,l=0;k<n;k++,l++) p[k]=l;
            for(k=0;l<n;k++,l++) p[k]=l;
            memset(b,0,sizeof b);
            for(k=0;k<n;k++)
            {
                if(b[k]) continue;
                c[cl]++;
                for(l=k;!b[l];l=p[l])
                    b[l]=1;
            }
            cl++;
            for(k=i,l=0;k>-1;k--,l++) p[k]=l;
            for(k=n-1;l<n;k--,l++) p[k]=l;
            memset(b,0,sizeof b);
            for(k=0;k<n;k++)
            {
                if(b[k]) continue;
                c[cl]++;
                for(l=k;!b[l];l=p[l])
                    b[l]=1;
            }
            cl++;
        }
        for(i=0,d=0;i<cl;i++)
            d+=pow(3,c[i]);
        if(!n) puts("0");
        else printf("%lld\n",d/(n*2));
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

int n,p[24],b[24],c[46];

long long d;

int main()

{

int i,j,k,l,cl;

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

{

memset(c,0,sizeof c);

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

{

for(k=i,l=0;k<n;k++,l++) p[k]=l;

for(k=0;l<n;k++,l++) p[k]=l;

memset(b,0,sizeof b);

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

{

if(b[k]) continue;

c[cl]++;

for(l=k;!b[l];l=p[l])

b[l]=1;

}

cl++;

for(k=i,l=0;k>-1;k--,l++) p[k]=l;

for(k=n-1;l<n;k--,l++) p[k]=l;

memset(b,0,sizeof b);

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

{

if(b[k]) continue;

c[cl]++;

for(l=k;!b[l];l=p[l])

b[l]=1;

}

cl++;

}

for(i=0,d=0;i<cl;i++)

d+=pow(3,c[i]);

if(!n) puts("0");

else printf("%lld\n",d/(n*2));

}

return 0;

}

但即使AC了也只是略微明白定理如何使用，证明看了一下发现不太好懂，就暂时放下了。

[POJ 2229]

发表回复

Sumsets

数学递推。

看完题面第一时间的想法就是O(NlgN)地枚举。。。竟然过了。然后看了下status，有0ms的，便开始想数学解法。。。

没什么思路后，开始观察规律：将2、4、8、16、32打表出来，没发现什么规律。就把1到32的全打出来了，发现两数之间的计数值间的差值有点像等差数列，又猜了一下便发现递推公式是：
f(x)=1, x=0
f(x)=x-1, x%2==1
f(x)=f(x/2)+f(x-2), else

但AC了之后依然不知道为什么式子是这样的。。。又经过漫长的分析之后发现，可以将x的表示方式分为两类（这里x为偶数，奇数情况容易发现即为x-1的计数值）：
（1）合式中含有1的：这种情况x的表示形式和x/2是相同的，其中x合式中的2便对应着x/2合式中的1，依次类推；
（2）合式中不含1：这里x的合式中至少要有2个1（因为x是偶数），因此其表示形式可以由x-2的形式+1+1得到；

以上两类刚好能不重复地包含x的全部表示形式，因此便能得到前面的公式了。

int n,dp[1000001];

int calc(int i)
{
    if(i&1) i--;
    if(!i) return dp[i]=1;
    if(dp[i]) return dp[i];
    dp[i]=calc(i/2)+calc(i-2);
    if(dp[i]>=1000000000) dp[i]-=1000000000;
    return dp[i];
}

main()
{
    scanf("%d",&n);
    printf("%d\n",calc(n));
}

int n,dp[1000001];

int calc(int i)

{

if(i&1) i--;

if(!i) return dp[i]=1;

if(dp[i]) return dp[i];

dp[i]=calc(i/2)+calc(i-2);

if(dp[i]>=1000000000) dp[i]-=1000000000;

return dp[i];

}

main()

{

scanf("%d",&n);

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

}

[POJ 2057]

发表回复

The Lost House

树形DP。很好的一道题目，这里认真写写。

题目很长，大意就是有一个树形图，出发点是树根，目标（即终点）以等概率的形式分布于每个树枝末端，要求的是在未知哪根树枝为终点的情况，最优搜索方式下的期望总搜索长度。另外这里还有一点附加的是，每个分支点可能有提示，即到达该树枝时可以立即知道目标是否在该子树下。

先不考虑存在提示的情况。对每棵子树的搜索可能有两种结果，成功或失败。若成功则要分别计算下一层每个子树的成功或失败情况，并计算出最优搜索下的搜索长度，这里记为ai；若失败则简单将所有子树的搜索总长累加即可，这里记为bi。另外，由于子树搜索成功是要计算概率的，这和子树上包含的叶子总数有关，因此需要维护一个子树所含叶子总数ni。由此便可以开始分析ai的计算了。

ai的计算也可以分为两部分，首先由概率公式可以得到，每棵子树j搜索成功的这部分概率是不受子树间先后顺序影响的，其对最优搜索期望总长的贡献总是(aj+1)*nj/ni。那么，这里最关键的就是搜索失败时的处理情况。这是本题的难点。

当已知某棵子树搜索失败时，后续子树搜索失败的概率会变低，若设剩余子树所含的总叶子数为nl，具体期望值公式为(bj+2)*(nl-nj)/ni，也即终点应在剩余的nl-nj个叶子中的某个上。这里是确定最优搜索方式的关键，我想了很久。若设l为剩余子树编号，尝试了每次根据(sum(bl+2)-bj-2)*(nl-nj)的最大值来贪心选择下一次搜索的子树，这里的思想是每次都使剩余期望值降低最多，能过test cases，但是submit后WA。这里思路一下子卡死了。便看了discuss，恰巧是magic_pig拯救了我（他是之前情书作者kinfkong的中大校友），他提到要按(bj+2)/nj排序。尝试了一下果然AC了。。。

晚上仔细想了想这样能求解的原因。观察到其形式很类似轮换不等式，朝这个方向推了一下之后便明白了：若交换搜索中次序相邻子树的j和k，是不影响之前和之后其他子树的期望值的。同时，每个子树受其他子树影响的量是bj+2，影响其他子树期望的量是nj，由此便能通过对(bj+2)/nj进行排序来确定最优搜索顺序了。实在是太过精巧的思路。

到这里为止，本题的所有trick基本上排除完了。bi的计算则是简单的sum(bj+2)，若该子树存在提示，取bi=0即可。

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int N,w[1000],hd[1000],el,fl,n[1000];
double a[1000],b[1000];

struct E
{
    int v,p;
}e[999];

struct F
{
    double bv,e;
    int nv;
    bool operator < (const F &p) const
    {
        return e<p.e;
    }
}f[1000];

inline void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

void calc(int u)
{
    if(hd[u]==-1)
    {
        n[u]=1;
        a[u]=b[u]=0;
        return;
    }
    int i,l,v,nl;
    n[u]=0;
    a[u]=b[u]=0;
    for(l=hd[u];l!=-1;l=e[l].p)
    {
        v=e[l].v;
        calc(v);
        n[u]+=n[v];
    }
    for(l=hd[u],fl=0;l!=-1;l=e[l].p)
    {
        v=e[l].v;
        f[fl].bv=b[v]+2;
        f[fl].nv=n[v];
        f[fl].e=(b[v]+2)/n[v];
        fl++;
        a[u]+=(a[v]+1)*n[v]/n[u];
        if(!w[u]) b[u]+=b[v]+2;
    }
    sort(f,f+fl);
    for(i=0,nl=n[u];i<fl-1;i++)
    {
        a[u]+=f[i].bv*(nl-f[i].nv)/n[u];
        nl-=f[i].nv;
    }
}

int main()
{
    int i,j,k,l;
    i=1;j=2;
    double e,f;
    char s[2];
    while(~scanf("%d",&N)&&N)
    {
        el=0;
        memset(hd,-1,sizeof hd);
        scanf("%*d%*s");
        for(i=1;i<N;i++)
        {
            scanf("%d%s",&j,s);
            adde(j-1,i);
            if(s[0]=='N') w[i]=0;
            else w[i]=1;
        }
        calc(0);
        printf("%.4f\n",a[0]);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int N,w[1000],hd[1000],el,fl,n[1000];

double a[1000],b[1000];

struct E

{

int v,p;

}e[999];

struct F

{

double bv,e;

int nv;

bool operator < (const F &p) const

{

return e<p.e;

}

}f[1000];

inline void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

void calc(int u)

{

if(hd[u]==-1)

{

n[u]=1;

a[u]=b[u]=0;

return;

}

int i,l,v,nl;

n[u]=0;

a[u]=b[u]=0;

for(l=hd[u];l!=-1;l=e[l].p)

{

v=e[l].v;

calc(v);

n[u]+=n[v];

}

for(l=hd[u],fl=0;l!=-1;l=e[l].p)

{

v=e[l].v;

f[fl].bv=b[v]+2;

f[fl].nv=n[v];

f[fl].e=(b[v]+2)/n[v];

fl++;

a[u]+=(a[v]+1)*n[v]/n[u];

if(!w[u]) b[u]+=b[v]+2;

}

sort(f,f+fl);

for(i=0,nl=n[u];i<fl-1;i++)

{

a[u]+=f[i].bv*(nl-f[i].nv)/n[u];

nl-=f[i].nv;

}

int main()

{

int i,j,k,l;

i=1;j=2;

double e,f;

char s[2];

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

{

el=0;

memset(hd,-1,sizeof hd);

scanf("%*d%*s");

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

{

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

adde(j-1,i);

if(s[0]=='N') w[i]=0;

else w[i]=1;

}

calc(0);

printf("%.4f\n",a[0]);

}

return 0;

}

这样的题目，完全弄懂之后总是有种难以言喻的快感… 马上又要开始做项目了，还能像现在这样无忧无虑做题的时间也不多了。

[POJ 3254] & [POJ 2411] & [POJ 1185]

1条回复

3题都是状态压缩DP，难度是循序渐进的，便一起写了。

Corn Fields

这题属于最基本的状态压缩DP。直接做的时候想了很久也不清楚如何构造DP，看了discuss后明白到，要使用位向量的形式表示一行的情况，并可以用&的方式判断是否能累加上一行的计数值。由此复杂度是O(m*2^n*2^n)，便能过了。这种题目太特殊了，某行的情况必须要在一个32位的int里放得下，并且每一行的向量总数不能太多，否则指数时间复杂度是难以承受的。但好像也没有别的办法可以有效求解这类问题。

#include<cstdio>
#include<cstring>

const int MOD=100000000;

int m,n,nt,b[12][12],dp[12][1<<12];

void calc(int i,int j,int d)
{
    if(j==n)
    {
        if(!i) dp[i][d]++;
        else
        {
            int k;
            for(k=0;k<nt;k++)
                if((d&k)==0) dp[i][d]=(dp[i][d]+dp[i-1][k])%MOD;
        }
        return;
    }
    if(b[i][j]&&(d&1)==0) calc(i,j+1,(d<<1)+1);
    calc(i,j+1,d<<1);
}

int main()
{
    int i,j;
    while(~scanf("%d%d",&m,&n))
    {
        nt=1<<n;
        memset(dp,0,sizeof dp);
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%d",&b[i][j]);
        for(i=0;i<m;i++)
            calc(i,0,0);
        for(i=j=0;i<nt;i++)
            j=(j+dp[m-1][i])%MOD;
        printf("%d\n",j);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

const int MOD=100000000;

int m,n,nt,b[12][12],dp[12][1<<12];

void calc(int i,int j,int d)

{

if(j==n)

{

if(!i) dp[i][d]++;

else

{

int k;

for(k=0;k<nt;k++)

if((d&k)==0) dp[i][d]=(dp[i][d]+dp[i-1][k])%MOD;

}

return;

}

if(b[i][j]&&(d&1)==0) calc(i,j+1,(d<<1)+1);

calc(i,j+1,d<<1);

}

int main()

{

int i,j;

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

{

nt=1<<n;

memset(dp,0,sizeof dp);

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

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

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

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

calc(i,0,0);

for(i=j=0;i<nt;i++)

j=(j+dp[m-1][i])%MOD;

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

}

return 0;

}

Mondriaan’s Dream

和3254类似，但这里需要用^来判断竖直方块的情况（平行方块是00，垂直方块是1），并且记录的状态是亦或运算后的结果，这样才能反应下一层看到的上层情况，最后输出末行状态全0的计数值即可。

#include<cstdio>
#include<cstring>

int h,w,wt;
long long dp[11][1<<11];

void calc(int i,int j,int d)
{
    if(j>w) return;
    if(j==w)
    {
        if(!i) dp[i][d]++;
        else
        {
            for(int k=0;k<wt;k++)
                if((d^k)==d-k)
                    dp[i][d^k]+=dp[i-1][k];
        }
        return;
    }
    calc(i,j+1,(d<<1)+1);
    calc(i,j+2,d<<2);
}

int main()
{
    int i,j;
    while(~scanf("%d%d",&h,&w)&&h)
    {
        wt=1<<w;
        memset(dp,0,sizeof dp);
        for(i=0;i<h;i++) calc(i,0,0);
        printf("%lld\n",dp[h-1][0]);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int h,w,wt;

long long dp[11][1<<11];

void calc(int i,int j,int d)

{

if(j>w) return;

if(j==w)

{

if(!i) dp[i][d]++;

else

{

for(int k=0;k<wt;k++)

if((d^k)==d-k)

dp[i][d^k]+=dp[i-1][k];

}

return;

}

calc(i,j+1,(d<<1)+1);

calc(i,j+2,d<<2);

}

int main()

{

int i,j;

while(~scanf("%d%d",&h,&w)&&h)

{

wt=1<<w;

memset(dp,0,sizeof dp);

for(i=0;i<h;i++) calc(i,0,0);

printf("%lld\n",dp[h-1][0]);

}

return 0;

}

炮兵阵地

和3254类似，但增加了难度：需要考虑前两行的情况，同时输出的是盘面最大值而不是计数值。虽然有前面两题的基础，但推状态转移时还是想了一下的：需要用一个dp[i][k][kk]形式的数组，记录第i行向量为k且i-1行向量为kk时的最值。由此便能在根据前两行的向量情况更新可行最值了。

但到这里为止算是出了思路，提交的时候还是分别被卡了内存和时间：内存方面，将dp改成滚动数组便ok了，时间方面，当构造第i行最值时记录其可行的解向量，这样到后面便可以根据记录下来的解情况来更新而无需枚举所有2^m*2^m种情况了。

#include<cstdio>
#include<cstring>

int n,m,mt,dp[2][1<<10][1<<10],hd[101],el;
char b[101][10],s[11];

struct E
{
    int d,p;
}e[1000000];

inline void adde(int i,int d)
{
    e[el].d=d; e[el].p=hd[i]; hd[i]=el++;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

void calc(int i,int j,int d,int c)
{
    if(j==m)
    {
        adde(i,d);
        if(i==1)
        {
            dp[i][0][d]=c;
        }
        else
        {
            int ii=i&1,iii=ii^1,l,ll,k,kk;
            for(l=hd[i-1];l!=-1;l=e[l].p)
            {
                k=e[l].d;
                for(ll=hd[i-2];ll!=-1;ll=e[ll].p)
                {
                    kk=e[ll].d;
                    if((d&k)+(d&kk)==0)
                        dp[ii][k][d]=max(dp[ii][k][d],
                                dp[iii][kk][k]+c);
                }
            }
        }
        return;
    }
    if(b[i][j]&&(d&3)==0) calc(i,j+1,(d<<1)+1,c+1);
    calc(i,j+1,d<<1,c);
}

int main()
{
    int i,j,k,l;
    while(~scanf("%d%d",&n,&m))
    {
        mt=1<<m;
        el=0;
        memset(dp,0,sizeof dp);
        memset(hd,-1,sizeof hd);
        for(i=1;i<=n;i++)
        {
            scanf("%s",s);
            for(j=0;j<m;j++)
                if(s[j]=='P') b[i][j]=1;
                else b[i][j]=0;
        }
        adde(0,0);
        for(i=1;i<=n;i++)
        {
            memset(dp[i&1],0,sizeof dp[i&1]);
            calc(i,0,0,0);
        }
        for(i=k=0;i<mt;i++)
            for(j=0;j<mt;j++)
                k=max(dp[n&1][i][j],k);
        printf("%d\n",k);
    }
    return 0;
}

#include<cstdio>

#include<cstring>

int n,m,mt,dp[2][1<<10][1<<10],hd[101],el;

char b[101][10],s[11];

struct E

{

int d,p;

}e[1000000];

inline void adde(int i,int d)

{

e[el].d=d; e[el].p=hd[i]; hd[i]=el++;

}

inline int max(int a,int b)

{

return a>b?a:b;

}

void calc(int i,int j,int d,int c)

{

if(j==m)

{

adde(i,d);

if(i==1)

{

dp[i][0][d]=c;

}

else

{

int ii=i&1,iii=ii^1,l,ll,k,kk;

for(l=hd[i-1];l!=-1;l=e[l].p)

{

k=e[l].d;

for(ll=hd[i-2];ll!=-1;ll=e[ll].p)

{

kk=e[ll].d;

if((d&k)+(d&kk)==0)

dp[ii][k][d]=max(dp[ii][k][d],

dp[iii][kk][k]+c);

}

return;

}

if(b[i][j]&&(d&3)==0) calc(i,j+1,(d<<1)+1,c+1);

calc(i,j+1,d<<1,c);

}

int main()

{

int i,j,k,l;

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

{

mt=1<<m;

el=0;

memset(dp,0,sizeof dp);

memset(hd,-1,sizeof hd);

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

{

scanf("%s",s);

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

if(s[j]=='P') b[i][j]=1;

else b[i][j]=0;

}

adde(0,0);

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

{

memset(dp[i&1],0,sizeof dp[i&1]);

calc(i,0,0,0);

}

for(i=k=0;i<mt;i++)

for(j=0;j<mt;j++)

k=max(dp[n&1][i][j],k);

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

}

return 0;

}

[POJ 3034]

发表回复

Whac-a-Mole

“打地鼠”，好神奇的一题DP…

题意是，有一个n*n的区域，在时刻1~10之间，每时刻会出现一些地鼠。有一个初始位置任意的锤子，在每个时刻，你可以将锤子直线移动最多d个单位，起止点都必须是整点，若有地鼠出现在移动路径上（必须是坐标x,y刚好在直线上），则可以将它们敲掉得分。目标是求t时候后最高得分。

数据规模不是很大，但分析了下复杂度，发现竟然是O(kn^4)级别的……因此需要对某点出发可以移动到的点，以及移动中路过的整点坐标全部预先记录下来……想到这里还觉得太复杂了，怕不是这么做，但是由于d<=5，这样的预处理又是完全合理的……因此开始了一顿乱搞。。。第一次提交WA了之后，读了discuss发现锤子是可以移出区域的。。。稍微作了下修改后便AC了。虽然没有完全能自己想出来，但还是好开心。

#include<cstdio>
#include<cstring>

int n,d,m,ad[30][30],on[30][30][30][30],el;
int b[30][30],dp[30][30],dpt[30][30],t[11];

struct E
{
    int x,y,p;
}e[5000000];

inline int inr(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=d*d;
}

inline int onl(int x1,int y1,int x2,int y2,int x3,int y3)
{
    if(x1==x2) return x3==x1;
    else if(x3==x1&&y3!=y1||x3==x2&&y3!=y2) return 0;
    else return (y3-y1)*(x2-x1)==(y2-y1)*(x3-x1);
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    int i,j,k,l,ll,x,y,xx,yy,sc;
    while(~scanf("%d%d%d",&n,&d,&m)&&n)
    {
        memset(ad,-1,sizeof ad);
        memset(on,-1,sizeof on);
        memset(t,-1,sizeof t);
        el=0;
        while(m--)
        {
            scanf("%d%d%d",&i,&j,&k);
            e[el].x=i+5;
            e[el].y=j+5;
            e[el].p=t[k];
            t[k]=el++;
        }
        for(i=0;i<n+10;i++)
            for(j=0;j<n+10;j++)
                for(k=0;k<n+10;k++)
                    for(l=0;l<n+10;l++)
                        if(inr(i,j,k,l))
                        {
                            e[el].x=k;
                            e[el].y=l;
                            e[el].p=ad[i][j];
                            ad[i][j]=el++;
                        }
        for(i=0;i<n+10;i++)
            for(j=0;j<n+10;j++)
                for(ll=ad[i][j];ll!=-1;ll=e[ll].p)
                {
                    int L,R,D,U;
                    k=e[ll].x;
                    l=e[ll].y;
                    if(i<k) L=i, R=k;
                    else L=k, R=i;
                    if(j<l) D=j, U=l;
                    else D=l, U=j;
                    for(x=L;x<=R;x++)
                        for(y=D;y<=U;y++)
                            if(onl(i,j,k,l,x,y))
                            {
                                e[el].x=x;
                                e[el].y=y;
                                e[el].p=on[i][j][k][l];
                                on[i][j][k][l]=el++;
                            }
                }
        memset(dp,0,sizeof dp);
        for(k=1;k<11;k++)
        {
            memset(b,0,sizeof b);
            memset(dpt,0,sizeof dpt);
            for(l=t[k];l!=-1;l=e[l].p)
            {
                x=e[l].x;
                y=e[l].y;
                b[x][y]=1;
            }
            for(i=0;i<n+10;i++)
            {
                for(j=0;j<n+10;j++)
                {
                    for(l=ad[i][j];l!=-1;l=e[l].p)
                    {
                        x=e[l].x;
                        y=e[l].y;
                        sc=0;
                        for(ll=on[i][j][x][y];ll!=-1;ll=e[ll].p)
                        {
                            xx=e[ll].x;
                            yy=e[ll].y;
                            sc+=b[xx][yy];
                        }
                        dpt[x][y]=max(dpt[x][y],dp[i][j]+sc);
                    }
                }
            }
            memcpy(dp,dpt,sizeof dpt);
        }
        for(i=k=0;i<n+10;i++)
            for(j=0;j<n+10;j++)
                k=max(k,dp[i][j]);
        printf("%d\n",k);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<cstdio>

#include<cstring>

int n,d,m,ad[30][30],on[30][30][30][30],el;

int b[30][30],dp[30][30],dpt[30][30],t[11];

struct E

{

int x,y,p;

}e[5000000];

inline int inr(int x1,int y1,int x2,int y2)

{

return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=d*d;

}

inline int onl(int x1,int y1,int x2,int y2,int x3,int y3)

{

if(x1==x2) return x3==x1;

else if(x3==x1&&y3!=y1||x3==x2&&y3!=y2) return 0;

else return (y3-y1)*(x2-x1)==(y2-y1)*(x3-x1);

}

inline int max(int a,int b)

{

return a>b?a:b;

}

int main()

{

int i,j,k,l,ll,x,y,xx,yy,sc;

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

{

memset(ad,-1,sizeof ad);

memset(on,-1,sizeof on);

memset(t,-1,sizeof t);

el=0;

while(m--)

{

scanf("%d%d%d",&i,&j,&k);

e[el].x=i+5;

e[el].y=j+5;

e[el].p=t[k];

t[k]=el++;

}

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

for(j=0;j<n+10;j++)

for(k=0;k<n+10;k++)

for(l=0;l<n+10;l++)

if(inr(i,j,k,l))

{

e[el].x=k;

e[el].y=l;

e[el].p=ad[i][j];

ad[i][j]=el++;

}

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

for(j=0;j<n+10;j++)

for(ll=ad[i][j];ll!=-1;ll=e[ll].p)

{

int L,R,D,U;

k=e[ll].x;

l=e[ll].y;

if(i<k) L=i, R=k;

else L=k, R=i;

if(j<l) D=j, U=l;

else D=l, U=j;

for(x=L;x<=R;x++)

for(y=D;y<=U;y++)

if(onl(i,j,k,l,x,y))

{

e[el].x=x;

e[el].y=y;

e[el].p=on[i][j][k][l];

on[i][j][k][l]=el++;

}

memset(dp,0,sizeof dp);

for(k=1;k<11;k++)

{

memset(b,0,sizeof b);

memset(dpt,0,sizeof dpt);

for(l=t[k];l!=-1;l=e[l].p)

{

x=e[l].x;

y=e[l].y;

b[x][y]=1;

}

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

{

for(j=0;j<n+10;j++)

{

for(l=ad[i][j];l!=-1;l=e[l].p)

{

x=e[l].x;

y=e[l].y;

sc=0;

for(ll=on[i][j][x][y];ll!=-1;ll=e[ll].p)

{

xx=e[ll].x;

yy=e[ll].y;

sc+=b[xx][yy];

}

dpt[x][y]=max(dpt[x][y],dp[i][j]+sc);

}

memcpy(dp,dpt,sizeof dpt);

}

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

for(j=0;j<n+10;j++)

k=max(k,dp[i][j]);

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

}

return 0;

}

使用了同一种边表struct来存多种数据……虽然看上去很乱搞但自己清楚其实是合理的做法，能够AC实在是太好了。另外今天也去了渣打编程马拉松的北京初赛……地点竟然还是上次北大校赛的北交计算机培训中心。这次的待遇比北大校赛好多了，全程饮料零食供应，中午还一人一份M，只是我肠胃不好也没太敢吃。但如果就比赛本身来说，实在是不怎么样。题目本身说是大数据，其实数据一点也不大，就在百万级别而已。另外就是题目的描述和求解需求都不甚明确，还有前后矛盾的地方……问赛会人员也是越描越黑……最后下午3点的时候上传完解就提前走了。结果到门口竟然还被拦截采访。。。实在是太尴尬了。明显这种非IT公司办的比赛只是为了宣传+招聘，和技术实际是离天隔九丈了……但是来参加这种比赛的我又算什么……