作者归档：Eurce

books and reading

虽然一直以来都很喜欢写C++（其实是不会其他语言），也确实体会到C++语言的各种好处（清晰的变量类型，灵活的内存处理，强大的STL等等等等），但发现确实对面向对象的C++没有任何好感。

主要是书里面讲到的太多解决问题的“巧妙”方法，在我看来却是太投机取巧了。换言之，我认为如果非要这样才能写出高效的代码，那对程序员的要求实在是太苛刻了，况且这里还没有涉及实际项目的要求以及和他人的协作。当然，这本书还是让我明白到了C++设计时的一些思想，这是仅仅粗读C++ primer所无法领会的。

自己的一点粗浅体会，也写在这里吧：总体感觉就是，C++最初被设计出来时，是在考虑执行效率的前提下为程序员尽可能地提供了自由的功能实现方案。然而随着时间的推移，越来越多的技术被发明/发现出来，而C++也在不断进行扩充。直到今天在我学习的时候，发现她身上存在着太多的历史包袱，从一开始的继承C的语法以及面向过程，到后面的面向对象和模板泛型编程，虽然包罗万有，却又让人无所适从。做项目不比做题目，当一个庞大系统要实现出来时，往往代码的规范一致性和可维护性要比执行效率更重要，这也导致了很多高效的写法事实上无法应用于工程。而且，作为一门古老的语言，它提供的很多功能其实是累赘的（例如在本书P151中作者明确表示“protect继承的意义至今仍然困惑我”），并不能真正反映软件设计的需求。

相比起来，更为“现代”的语言，比如pyhton，在这一点上做得要好很多。其开发者相信“应当只用一种——而且是最好的一种——明确的方式去做一件事。”（“There should be one – and preferably only one – obvious way to do it.”），大概也是其得到广泛普及的重要原因。但个人认为，就语言学习来说，python这种“单调”的语法也对暂时不需要写项目的我没有太大吸引力。接下来想看的是Ruby作者写的松本行弘的程序世界。

还是贴几段书中有趣的小例程，第一次知道C++还可以这么写：

模板编程（这里最多只能500，不知道为何）：

#include<iostream>
using namespace std;

template<int n>
struct F {
    enum { value = 1 + F<n-1>::value };
};

template<>
struct F<0> {
    enum { value = 1 };
};

int main()
{
    cout << F<500>::value << endl;
    return 0;
}

#include<iostream>

using namespace std;

template<int n>

struct F {

enum { value = 1 + F<n-1>::value };

};

template<>

struct F<0> {

enum { value = 1 };

};

int main()

{

cout << F<500>::value << endl;

return 0;

}

用boost的：

#include<iostream>
#include<vector>
#include<boost/lambda/lambda.hpp>

using namespace boost::lambda;

int d[]={ 2, 7, 1, 8, 2, 8 };

std::vector<int> v(d, d+6);

int main()
{
    std::for_each(v.begin(), v.end(),
            std::cout << _1 * 2 + 10 << "\n");
    return 0;
}

#include<iostream>

#include<vector>

#include<boost/lambda/lambda.hpp>

using namespace boost::lambda;

int d[]={ 2, 7, 1, 8, 2, 8 };

std::vector<int> v(d, d+6);

int main()

{

std::for_each(v.begin(), v.end(),

std::cout << _1 * 2 + 10 << "\n");

return 0;

}

以及：

#include <boost/random/random_device.hpp>
#include <boost/random/uniform_int_distribution.hpp>

int main() {
    std::string chars(
        "abcdefghijklmnopqrstuvwxyz"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "1234567890"
        "!@#$%^&*()"
        "`~-_=+[{]{\\|;:'\",<.>/? ");
    boost::random::random_device rng;
    boost::random::uniform_int_distribution<> index_dist(0, chars.size() - 1);
    for(int i = 0; i < 8; ++i) {
        std::cout << chars[index_dist(rng)];
    }
    std::cout << std::endl;
}

#include <boost/random/random_device.hpp>

#include <boost/random/uniform_int_distribution.hpp>

int main() {

std::string chars(

"abcdefghijklmnopqrstuvwxyz"

"ABCDEFGHIJKLMNOPQRSTUVWXYZ"

"1234567890"

"!@#$%^&*()"

"`~-_=+[{]{\\|;:'\",<.>/? ");

boost::random::random_device rng;

boost::random::uniform_int_distribution<> index_dist(0, chars.size() - 1);

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

std::cout << chars[index_dist(rng)];

}

std::cout << std::endl;

}

编译这个还要专门写makefile（用的是os x下brew安装的boost库）：

CC = g++

BASE_FLAGS = -g -wAll

# INCLUDE BASE DIRECTORY AND BOOST DIRECTORY FOR HEADERS
LDFLAGS = -I/usr/local/Cellar/boost/1.54.0/include

# INCLUDE BASE DIRECTORY AND BOOST DIRECTORY FOR LIB FILES
LLIBFLAGS = -L/usr/local/Cellar/boost/1.54.0/lib

# SPECIFIY LINK OPTIONS
LINKFLAGS = -lboost_system-mt -lboost_random-mt

# FINAL FLAGS -- TO BE USED THROUGHOUT
FLAGS = $(BASE_FLAGS) $(LLIBFLAGS) $(LDFLAGS) $(LINKFLAGS)

# NOTE FOR BOOST -- YOU ONLY NEED TO INCLUDE THE PATH BECAUSE IT ONLY INSTALLS HEADER FILES
main: main.cpp
		$(CC) $(FLAGS) -o main.out main.cpp

CC = g++

BASE_FLAGS = -g -wAll

# INCLUDE BASE DIRECTORY AND BOOST DIRECTORY FOR HEADERS

LDFLAGS = -I/usr/local/Cellar/boost/1.54.0/include

# INCLUDE BASE DIRECTORY AND BOOST DIRECTORY FOR LIB FILES

LLIBFLAGS = -L/usr/local/Cellar/boost/1.54.0/lib

# SPECIFIY LINK OPTIONS

LINKFLAGS = -lboost_system-mt -lboost_random-mt

# FINAL FLAGS -- TO BE USED THROUGHOUT

FLAGS = $(BASE_FLAGS) $(LLIBFLAGS) $(LDFLAGS) $(LINKFLAGS)

# NOTE FOR BOOST -- YOU ONLY NEED TO INCLUDE THE PATH BECAUSE IT ONLY INSTALLS HEADER FILES

main: main.cpp

$(CC) $(FLAGS) -o main.out main.cpp

但貌似用clang编译时还是报找不到库…不管了反正不用xcode

[POJ 3020]

发表回复

Antenna Placement

二分图匹配。

其实是很久以前做的题目了。今天被Usozki问了下这题怎么做，看了他的代码，感觉值得改进的地方不少……便自己着手重做了下这题，希望能讲清边表的写法。由于之前hackerhank出过一题很刁钻的匈牙利，觉得已经把这个算法弄得很透彻了（包括递归改非递归、每轮匈牙利时局部链表指针改全局、每次不重新memste标记数组等等），但这次重写这题还是用了很久。

这里用了一个题目的特点（可以染色成国际象棋棋盘那样的二分图），使得每个匹配的共算了两次；又或者其实可以每次仅从一种颜色的点出发，这样就只算一次匹配。

这是今天写的代码：

#include<cstdio>
#include<cstring>

char s[40][11];

int h,w,bi,hd[400],d[40][10],b[400],f[400],el,si;

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

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

int hun(int i)
{
    int j,k,l;
    for(l=hd[i];l!=-1;l=e[l].p)
    {
        j=e[l].v;
        if(b[j]==bi) continue;
        b[j]=bi;
        if(f[j]==-1||hun(f[j]))
        {
            f[j]=i;
            return 1;
        }
    }
    return 0;
}

void init()
{
    int i,j;
    si=el=0;
    memset(hd,-1,sizeof hd);
    memset(d,-1,sizeof d);
    for(i=0;i<h;i++)
    {
        scanf("%s",s[i]);
        for(j=0;j<w;j++)
            if(s[i][j]=='*') d[i][j]=si++;
        if(i)
            for(j=0;j<w;j++)
                if(d[i][j]!=-1&&d[i-1][j]!=-1)
                    adde(d[i][j],d[i-1][j]);
        for(j=1;j<w;j++)
            if(d[i][j]!=-1&&d[i][j-1]!=-1)
                adde(d[i][j],d[i][j-1]);
    }
    memset(b,-1,sizeof b);
    memset(f,-1,sizeof f);
}

void solve()
{
    int c=0;
    for(bi=0;bi<si;bi++)
        c+=hun(bi);
    printf("%d\n",si-c/2);
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d",&h,&w))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

char s[40][11];

int h,w,bi,hd[400],d[40][10],b[400],f[400],el,si;

struct E

{

int v,p;

}e[1600];

inline void adde(int u,int v)

{

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

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

}

int hun(int i)

{

int j,k,l;

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

{

j=e[l].v;

if(b[j]==bi) continue;

b[j]=bi;

if(f[j]==-1||hun(f[j]))

{

f[j]=i;

return 1;

}

return 0;

}

void init()

{

int i,j;

si=el=0;

memset(hd,-1,sizeof hd);

memset(d,-1,sizeof d);

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

{

scanf("%s",s[i]);

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

if(s[i][j]=='*') d[i][j]=si++;

if(i)

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

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

adde(d[i][j],d[i-1][j]);

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

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

adde(d[i][j],d[i][j-1]);

}

memset(b,-1,sizeof b);

memset(f,-1,sizeof f);

}

void solve()

{

int c=0;

for(bi=0;bi<si;bi++)

c+=hun(bi);

printf("%d\n",si-c/2);

}

int main()

{

scanf("%*d");

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

{

init();

solve();

}

return 0;

}

这里建图是先编号，再检查上方和左方是否存在点，然后加边的。代码里函数功能应该都区分得很明显了。这样写出来的边表，是做很多图论题时必须使用的数据结构（甚至其他类型题目里也经常用到）。无论是时间、空间，还是代码实现难度方面都是很好的。

另外也贴下以前写的，当时不会用边表，但是代码还算是比较齐整了：

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

int t,n,h,w,a[40][10],b[400],d[400][400],f[400];
char s[40][11];

int dfs(int i)
{
    int j,k,l;
    for(j=0; j<n; j++)
    {
        if(!b[j]&&d[i][j])
        {
            b[j]=1;
            if(f[j]==-1||dfs(f[j]))
            {
                f[j]=i;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i,j,k,l;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,-1,sizeof(a));
        memset(d,0,sizeof(d));
        memset(f,-1,sizeof(f));
        n=0;
        scanf("%d%d",&h,&w);
        for(i=0; i<h; i++)
        {
            scanf("%s",s[i]);
            for(j=0; j<w; j++)
                if(s[i][j]=='*') a[i][j]=n++;
        }
        for(i=0; i<h; i++)
        {
            for(j=i&1; j<w; j+=2)
            {
                if(a[i][j]>-1)
                {
                    if(i>0&&a[i-1][j]>-1) d[a[i][j]][a[i-1][j]]=1;
                    if(i<h-1&&a[i+1][j]>-1) d[a[i][j]][a[i+1][j]]=1;
                    if(j>0&&a[i][j-1]>-1) d[a[i][j]][a[i][j-1]]=1;
                    if(j<w-1&&a[i][j+1]>-1) d[a[i][j]][a[i][j+1]]=1;
                }
            }
        }
        for(i=j=0; i<n; i++)
        {
            memset(b,0,sizeof(b));
            j+=dfs(i);
        }
        printf("%d\n",n-j);
    }
    return 0;
}

#include<stdio.h>

#include<string.h>

int t,n,h,w,a[40][10],b[400],d[400][400],f[400];

char s[40][11];

int dfs(int i)

{

int j,k,l;

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

{

if(!b[j]&&d[i][j])

{

b[j]=1;

if(f[j]==-1||dfs(f[j]))

{

f[j]=i;

return 1;

}

return 0;

}

int main()

{

int i,j,k,l;

scanf("%d",&t);

while(t--)

{

memset(a,-1,sizeof(a));

memset(d,0,sizeof(d));

memset(f,-1,sizeof(f));

n=0;

scanf("%d%d",&h,&w);

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

{

scanf("%s",s[i]);

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

if(s[i][j]=='*') a[i][j]=n++;

}

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

{

for(j=i&1; j<w; j+=2)

{

if(a[i][j]>-1)

{

if(i>0&&a[i-1][j]>-1) d[a[i][j]][a[i-1][j]]=1;

if(i<h-1&&a[i+1][j]>-1) d[a[i][j]][a[i+1][j]]=1;

if(j>0&&a[i][j-1]>-1) d[a[i][j]][a[i][j-1]]=1;

if(j<w-1&&a[i][j+1]>-1) d[a[i][j]][a[i][j+1]]=1;

}

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

{

memset(b,0,sizeof(b));

j+=dfs(i);

}

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

}

return 0;

}

[POJ 1487]

发表回复

Single-Player Games

还是高斯消元法。

这题的特点是输入是用树来表示的，并且需要做类似编译原理那样的词法和语法分析。处理字符的时候小心一点，问题不会太大（但还是被负数的’-‘阴到了。。）。用递归来表示每个括号的匹配情况，符号移到等式右端（取负），数值直接累加，递归返回时每个值除去子树规模再累加到父节点数组上即可。由于输入规模不大，除了字符串处理也没有其他麻烦了。

解线性方程组的时候，注意每个方程已经指定了主元了，如果系数为0即对应变量无解，所有依赖于该变量的其他变量也无解。但其他剩余有解的变量还是要解出来的。这题比之前那题取模的要好处理，方程比较整齐，而且可以直接用浮点数。

#include<cstdio>
#include<cstring>

const double eps=1e-6;

int n,ml,t;
double ab[26][27],m[1000000],d[26];
char c,b[26];

inline double abs(double e)
{
    return e>0?e:-e;
}

int getint()
{
    int d=c-'0';
    while((c=getchar())>='0'&&c<='9')
        d=d*10+c-'0';
    return d;
}

void calc(double *f)
{
    ml+=n+1;
    double *e=&m[ml];
    int i,l=0;
    c=getchar();
    while(1)
    {
        while(c==' ')
            c=getchar();
        if(c==')') break;
        l++;
        if(c=='(') calc(e);
        else if(c=='-'||c>='0'&&c<='9')
        {
            if(c=='-')
            {
                c=getchar();
                e[n]-=getint();
            }
            else e[n]+=getint();
        }
        else if(c>='a'&&c<='z')
        {
            e[c-'a']-=1;
            c=getchar();
        }
    }
    for(i=0;i<=n;i++)
        f[i]+=e[i]/l;
    c=getchar();
}

void init()
{
    int i;
    ml=0;
    memset(ab,0,sizeof ab);
    memset(m,0,sizeof m);
    for(i=0;i<n;i++)
    {
        ab[i][i]=1;
        scanf("%*s%*s");
        while((c=getchar())!='(');
        calc(ab[i]);
    }
}

void solve()
{
    int i,j,k,l;
    double e,f;
    memset(b,0,sizeof b);
    printf("Game %d\n",++t);
    for(i=0;i<n;i++)
    {
        if(abs(ab[i][i])<eps)
        {
            b[i]=-1;
            continue;
        }
        for(j=i+1;j<n;j++)
        {
            if(abs(ab[j][i])<eps) continue;
            e=ab[j][i]/ab[i][i];
            for(k=i;k<=n;k++)
                ab[j][k]-=ab[i][k]*e;
        }
    }
    for(i=n-1;i>-1;i--)
    {
        if(b[i]==-1) continue;
        for(j=0;j<n&&!(abs(ab[i][j])>eps&&b[j]==-1);j++);
        if(j<n)
        {
            b[i]=-1;
            continue;
        }
        d[i]=ab[i][n]/ab[i][i];
        for(j=i-1;j>-1;j--)
        {
            if(abs(ab[j][i])<eps) continue;
            ab[j][n]-=ab[i][n]*ab[j][i]/ab[i][i];
            ab[j][i]=0;
        }
    }
    for(i=0;i<n;i++)
    {
        if(b[i]==-1)
            printf("Expected score for %c undefined\n",'a'+i);
        else
            printf("Expected score for %c = %.3f\n",'a'+i,d[i]);
    }
    puts("");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<cstdio>

#include<cstring>

const double eps=1e-6;

int n,ml,t;

double ab[26][27],m[1000000],d[26];

char c,b[26];

inline double abs(double e)

{

return e>0?e:-e;

}

int getint()

{

int d=c-'0';

while((c=getchar())>='0'&&c<='9')

d=d*10+c-'0';

return d;

}

void calc(double *f)

{

ml+=n+1;

double *e=&m[ml];

int i,l=0;

c=getchar();

while(1)

{

while(c==' ')

c=getchar();

if(c==')') break;

l++;

if(c=='(') calc(e);

else if(c=='-'||c>='0'&&c<='9')

{

if(c=='-')

{

c=getchar();

e[n]-=getint();

}

else e[n]+=getint();

}

else if(c>='a'&&c<='z')

{

e[c-'a']-=1;

c=getchar();

}

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

f[i]+=e[i]/l;

c=getchar();

}

void init()

{

int i;

ml=0;

memset(ab,0,sizeof ab);

memset(m,0,sizeof m);

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

{

ab[i][i]=1;

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

while((c=getchar())!='(');

calc(ab[i]);

}

void solve()

{

int i,j,k,l;

double e,f;

memset(b,0,sizeof b);

printf("Game %d\n",++t);

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

{

if(abs(ab[i][i])<eps)

{

b[i]=-1;

continue;

}

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

{

if(abs(ab[j][i])<eps) continue;

e=ab[j][i]/ab[i][i];

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

ab[j][k]-=ab[i][k]*e;

}

for(i=n-1;i>-1;i--)

{

if(b[i]==-1) continue;

for(j=0;j<n&&!(abs(ab[i][j])>eps&&b[j]==-1);j++);

if(j<n)

{

b[i]=-1;

continue;

}

d[i]=ab[i][n]/ab[i][i];

for(j=i-1;j>-1;j--)

{

if(abs(ab[j][i])<eps) continue;

ab[j][n]-=ab[i][n]*ab[j][i]/ab[i][i];

ab[j][i]=0;

}

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

{

if(b[i]==-1)

printf("Expected score for %c undefined\n",'a'+i);

else

printf("Expected score for %c = %.3f\n",'a'+i,d[i]);

}

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

另外这题也是我在POJ上有记录的第200题，貌似里面夹杂的水题不少。。。但还是值得纪念：

[POJ 2947]

发表回复

Widget Factory

高斯消元法。

其实就是线性代数里解线性方程组，但这题还要求等式两边mod7。

解向量中xi的取值范围是[3,9]，共有m个方程，判断是否有解，如果有解，要判断是否有唯一解。

这题一开始走了弯路，想象以前解普通线性方程组那样用浮点数依次选列主元后化成上三角来求解。但发现在这题mod7条件下，行不通。

后来发现可以用一个很差的时间复杂度完全使用整数进行处理。。。由于数据规模不大，发现这样是可行的。每次消元处理后都也要注意各种取模，不然很易RE。

反正最后就是各种暴力。。。就过了。。。

#include<cstdio>
#include<cstring>

int n,m,d[300];
int ab[300][301],t[301];
char s[4],e[4];

int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}

int lcm(int a,int b)
{
    if(!a||!b) return 0;
    return a*b/gcd(a,b);
}

int chk(char s[])
{
    if(!strcmp(s,"MON")) return 1;
    if(!strcmp(s,"TUE")) return 2;
    if(!strcmp(s,"WED")) return 3;
    if(!strcmp(s,"THU")) return 4;
    if(!strcmp(s,"FRI")) return 5;
    if(!strcmp(s,"SAT")) return 6;
    return 7;
}

inline int calc(int a,int b)
{
    a=(a%7+7)%7;
    b=(b%7+7)%7;
    for(int d=3;d<=9;d++)
        if(a*d%7==b) return d;
    return -1;
}

void solve()
{
    int i,j,k,l,o,p;
    memset(ab,0,sizeof ab);
    for(i=0;i<m;i++)
    {
        scanf("%d%s%s",&j,s,e);
        k=chk(s);
        l=chk(e);
        ab[i][n]=l-k+1;
        while(j--)
        {
            scanf("%d",&k);
            ab[i][k-1]++;
        }
    }
    for(i=0;i<m;i++)
        for(j=0;j<=n;j++)
            ab[i][j]%=7;
    for(i=l=0;i<n;i++)
    {
        for(j=l;j<m&&!ab[j][i];j++);
        if(j==m) continue;
        if(j>l)
        {
            memcpy(t,ab[j],sizeof t);
            memcpy(ab[j],ab[l],sizeof t);
            memcpy(ab[l],t,sizeof t);
        }
        for(j=l+1;j<m;j++)
        {
            if(!ab[j][i]) continue;
            p=lcm(ab[j][i],ab[l][i])/ab[j][i];
            for(o=i;o<=n;o++)
                ab[j][o]*=p;
            p=ab[j][i]/ab[l][i];
            for(o=i;o<=n;o++)
            {
                ab[j][o]-=ab[l][o]*p;
                ab[j][o]%=7;
            }
        }
        l++;
    }
    for(i=m-1;i>-1;i--)
    {
        for(j=0;j<=n&&!ab[i][j];j++);
        if(j==n)
        {
            puts("Inconsistent data.");
            return;
        }
    }
    memset(d,-1,sizeof d);
    for(i=l-1;i>-1;i--)
    {
        for(j=0;j<n&&!ab[i][j];j++);
        if(j==n) continue;
        for(k=j+1;k<n&&!ab[i][k];k++);
        if(k<n)
        {
            puts("Multiple solutions.");
            return;
        }
        d[j]=calc(ab[i][j],ab[i][n]);
        for(k=i-1;k>-1;k--)
        {
            if(!ab[k][j]) continue;
            p=lcm(ab[i][j],ab[k][j])/ab[k][j];
            for(o=0;o<=n;o++)
                ab[k][o]*=p;
            p=ab[k][j]/ab[i][j];
            for(o=0;o<=n;o++)
            {
                ab[k][o]-=ab[i][o]*p;
                ab[k][o]%=7;
            }
        }
    }
    for(i=0;i<n;i++)
        if(d[i]==-1)
        {
            puts("Multiple solutions.");
            return;
        }
    for(i=0;i<n-1;i++) printf("%d ",d[i]);
    printf("%d\n",d[n-1]);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&n)
        solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#include<cstdio>

#include<cstring>

int n,m,d[300];

int ab[300][301],t[301];

char s[4],e[4];

int gcd(int a,int b)

{

if(a%b==0) return b;

return gcd(b,a%b);

}

int lcm(int a,int b)

{

if(!a||!b) return 0;

return a*b/gcd(a,b);

}

int chk(char s[])

{

if(!strcmp(s,"MON")) return 1;

if(!strcmp(s,"TUE")) return 2;

if(!strcmp(s,"WED")) return 3;

if(!strcmp(s,"THU")) return 4;

if(!strcmp(s,"FRI")) return 5;

if(!strcmp(s,"SAT")) return 6;

return 7;

}

inline int calc(int a,int b)

{

a=(a%7+7)%7;

b=(b%7+7)%7;

for(int d=3;d<=9;d++)

if(a*d%7==b) return d;

return -1;

}

void solve()

{

int i,j,k,l,o,p;

memset(ab,0,sizeof ab);

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

{

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

k=chk(s);

l=chk(e);

ab[i][n]=l-k+1;

while(j--)

{

scanf("%d",&k);

ab[i][k-1]++;

}

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

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

ab[i][j]%=7;

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

{

for(j=l;j<m&&!ab[j][i];j++);

if(j==m) continue;

if(j>l)

{

memcpy(t,ab[j],sizeof t);

memcpy(ab[j],ab[l],sizeof t);

memcpy(ab[l],t,sizeof t);

}

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

{

if(!ab[j][i]) continue;

p=lcm(ab[j][i],ab[l][i])/ab[j][i];

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

ab[j][o]*=p;

p=ab[j][i]/ab[l][i];

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

{

ab[j][o]-=ab[l][o]*p;

ab[j][o]%=7;

}

l++;

}

for(i=m-1;i>-1;i--)

{

for(j=0;j<=n&&!ab[i][j];j++);

if(j==n)

{

puts("Inconsistent data.");

return;

}

memset(d,-1,sizeof d);

for(i=l-1;i>-1;i--)

{

for(j=0;j<n&&!ab[i][j];j++);

if(j==n) continue;

for(k=j+1;k<n&&!ab[i][k];k++);

if(k<n)

{

puts("Multiple solutions.");

return;

}

d[j]=calc(ab[i][j],ab[i][n]);

for(k=i-1;k>-1;k--)

{

if(!ab[k][j]) continue;

p=lcm(ab[i][j],ab[k][j])/ab[k][j];

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

ab[k][o]*=p;

p=ab[k][j]/ab[i][j];

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

{

ab[k][o]-=ab[i][o]*p;

ab[k][o]%=7;

}

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

if(d[i]==-1)

{

puts("Multiple solutions.");

return;

}

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

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

}

int main()

{

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

solve();

return 0;

}

[POJ 2348]

发表回复

Euclid’s Game

博弈问题。

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