分类目录归档：acm

[POJ 1286]

第一题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公司办的比赛只是为了宣传+招聘，和技术实际是离天隔九丈了……但是来参加这种比赛的我又算什么……

[POJ 1925]

发表回复

Spiderman

继续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学得扎实一点。

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

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

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;

}