poj模拟题总结（一）

模拟是acm算法中基础但深奥的算法，不容轻视。

本次模拟题练习题为1835，2623，2271，2996，2706，1676，1472，1027，3371。

1835 宇航员：可以以左手，脸，头三个参量的方向来确定自己的方向。自己比划比划即可。

2996：棋盘问题，比较水。

2706：线段相交+DFS，注意线段相交的判断。

1676：DFS即可。

1472：典型的递归题，构建栈。同时可以建立一个class，来表示一个多项式，利用操作符重载来简化代码结构。

1027：模拟，代码不像网上说的那么繁琐，我认为还可以。但值得练练。

3371：字符串处理，细心题。

下面将贴出2706，1472，1027代码，这三题在本次练习中稍繁。

2706代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int N=25,M=255;
const int dx[8]={1,2,2,1,-1,-2,-2,-1};
const int dy[8]={2,1,-1,-2,-2,-1,1,2};

struct point
{
    int x,y;
    point(int xx=0,int yy=0)
    {
        x=xx;y=yy;
    }
};

struct line
{
    point a,b;
    line(point aa=point(),point bb=point())
    {
        a=aa;b=bb;
    }
}l[N*N];

int tot,n,m;
bool v[2][N][N],vv[N][N][N][N],vis[N][N];

bool dfs(int x,int y)
{
    vis[x][y]=true;
    if (x==n) return true;
    for (int k=0;k<8;k++)
        if (x+dx[k]>=0 && x+dx[k]<=n && y+dy[k]>=0 && y+dy[k]<=n
        && !vis[x+dx[k]][y+dy[k]] &&vv[x][y][x+dx[k]][y+dy[k]])
        {
            if (dfs(x+dx[k],y+dy[k])) return true;
        }
    return false;
}

int xmult(point a,point b,point c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

bool intersect(point p1,point q1,point p2,point q2)
{
    return xmult(p2,q1,p1)*xmult(q2,q1,p1)<0 && xmult(p1,q2,p2)*xmult(q1,q2,p2)<0;
}

int main()
{
    int i,j,k,x,y,col;
    freopen("in.txt","r",stdin);
    while (1)
    {
        ppp:
        cin >> n >> m;
        if (n==0 && m==0) break;
        memset(v,0,sizeof(v));
        memset(vv,0,sizeof(vv));
        tot=0;
        for (i=1;i<=m;i++)
        {
            cin >> x >> y;
            col=i%2;
            v[col][x][y]=true;
            for (k=0;k<8;k++)
                if (x+dx[k]>=0 && x+dx[k]<=n && y+dy[k]>=0 && y+dy[k]<=n && v[col][x+dx[k]][y+dy[k]])
                {
                    point p2=point(x+dx[k],y+dy[k]);
                    point p1=point(x,y);
                    bool ff=true;
                    for (j=1;j<=tot;j++)
                        if (intersect(l[j].a,l[j].b,p1,p2))
                        {
                            ff=false;
                            break;
                        }
                    if (ff)
                    {
                        l[++tot]=line(p1,p2);
                        if (col==1)
                        {
                            vv[p1.x][p1.y][p2.x][p2.y]=true;
                            vv[p2.x][p2.y][p1.x][p1.y]=true;
                        }
                    }
                }
        }
        for (i=0;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            if (v[1][0][i] && dfs(0,i))
            {
                cout << "yes" << endl;
                goto ppp;
            }
        }
        cout << "no" << endl;
    }
}

1472代码：

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;

class num
{
private:
    int a[12];
public:
    num()
    {
        memset(a,0,sizeof(a));
    }

    num(const num& p)
    {
        memcpy(a,p.a,sizeof(p.a));
    }

    num operator+ (string s)
    {
        int i,tmp;
        if (s=="n") a[1]++;
        else
        {
            tmp=0;
            for (i=0;i<s.size();i++)
                tmp=tmp*10+s[i]-'0';
            a[0]+=tmp;
        }
        return *this;
    }

    num operator+ (num b)
    {
        for (int i=0;i<12;i++)
            a[i]+=b.a[i];
        return *this;
    }

    num operator* (string s)
    {
        int i,tmp;
        if (s=="n")
        {
            for (i=11;i>=1;i--)
                a[i]=a[i-1];
            a[0]=0;
        }
        else
        {
            tmp=0;
            for (i=0;i<s.size();i++)
                tmp=tmp*10+s[i]-'0';
            for (i=0;i<12;i++)
                a[i]*=tmp;
        }
        return *this;
    }

    friend ostream& operator<< (ostream& os,const num& b)
    {
        int i;
        bool ff=false;
        for (i=11;i>1;i--)
        if (b.a[i]!=0)
        {
            if (ff) os << "+";
            else ff=true;
            if (b.a[i]>1)
                os << b.a[i] << "*n^" << i;
            else
                os << "n^" << i;
        }
        if (b.a[1]>0)
        {
            if (ff) os << "+";
            else ff=true;
            if (b.a[1]==1) os << "n";
            else os << b.a[1] << "*n";
        }
        if (b.a[0]>0)
        {
            if (ff) os << "+";
            else ff=true;
            os << b.a[0];
        }
        if (!ff) os << 0;
        return os;
    }
};

num work(int dep)
{
    string order,s;
    num ans;

    cin >> order;
    while (order!="END")
    {
        if (order=="LOOP")
        {
            cin >> s;
            ans=ans+work(dep+1)*s;
        }
        else if (order=="OP")
        {
            cin >> s;
            ans=ans+s;
        }
        cin >> order;
    }
    return ans;
}

int main()
{
    int i,cc;
    string s;
    freopen("in.txt","r",stdin);
    cin >> cc;
    for (i=1;i<=cc;i++)
    {
        cout << "Program #" << i << endl;
        cin >> s;
        cout << "Runtime = " << work(0) << endl;
        if (i<cc) cout << endl;
    }
}

1027代码：

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=10,M=15;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

int tot,rem,sum;
int ans[100][4];
int a[N+2][M+2];

int fill(int x,int y,bool v[][M+1])
{
    int ans=1;
    v[x][y]=true;
    for (int i=0;i<4;i++)
        if (!v[x+dx[i]][y+dy[i]] && a[x+dx[i]][y+dy[i]]==a[x][y])
            ans+=fill(x+dx[i],y+dy[i],v);
    return ans;
}

void clear(int x,int y)
{
    int col=a[x][y];
    a[x][y]=0;
    for (int i=0;i<4;i++)
        if (a[x+dx[i]][y+dy[i]]==col)
            clear(x+dx[i],y+dy[i]);
}

void update()
{
    int i,j,k,p;
    for (j=1;j<=M;j++)
        for (i=1;i<=N;i++)
            if (a[i][j]==0)
            {
                k=i;
                while (k<=N && a[k][j]==0) k++;
                for (p=k;p<=N;p++)
                {
                    a[p-k+i][j]=a[p][j];
                    a[p][j]=0;
                }
            }
    for (j=1;j<=M;j++)
        if (a[1][j]==0)
        {
            k=j;
            while (k<=M && a[1][k]==0) k++;
            for (p=k;p<=M;p++)
                for (i=1;i<=N;i++)
                {
                    a[i][p-k+j]=a[i][p];
                    a[i][p]=0;
                }
        }
}

void work()
{
    bool v[N+1][M+1];
    int ss,x,y,rr,i,j;
    while (1)
    {
        memset(v,0,sizeof(v));
        ss=x=y=rr=0;
        for (j=1;j<=M;j++)
            for (i=1;i<=N;i++)
            if (a[i][j]>0 && !v[i][j])
            {
                int tmp=fill(i,j,v);
                if (tmp>ss) ss=tmp,x=i,y=j;
                rr+=tmp;
            }
        if (ss<=1)
        {
            rem=rr;
            if (rem==0) sum+=1000;
            break;
        }
        sum+=(ss-2)*(ss-2);
        ans[++tot][0]=x;ans[tot][1]=y;
        ans[tot][2]=ss;
        switch(a[x][y])
        {
            case 1:ans[tot][3]='R';break;
            case 2:ans[tot][3]='G';break;
            case 3:ans[tot][3]='B';break;
        }

        clear(x,y);
        update();
    }
}
int main()
{
    int i,j,cc,cas;
    char ch;

    freopen("in.txt","r",stdin);
    cin >> cc;
    getchar();
    for (cas=1;cas<=cc;cas++)
    {
        getchar();
        memset(a,0,sizeof(a));
        tot=sum=rem=0;
        for (i=N;i>=1;i--)
        {
            for (j=1;j<=M;j++)
            {
                ch=getchar();
                switch(ch)
                {
                    case 'R':a[i][j]=1;break;
                    case 'G':a[i][j]=2;break;
                    case 'B':a[i][j]=3;break;
                }
            }
            getchar();
        }
        work();
        printf("Game %d:\n\n",cas);
        for (i=1;i<=tot;i++)
            printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",
               i,ans[i][0],ans[i][1],ans[i][2],char(ans[i][3]),(ans[i][2]-2)*(ans[i][2]-2));
        printf("Final score: %d, with %d balls remaining.\n",sum,rem);
        if (cas<cc) printf("\n");
    }
}