分类目录归档:模拟

POJ 2309 BST

此题一看,树状数组里神奇的 n & -n 就派上用场了。

输入你,输出 n-(n&-n)+1 和 n+(n&-n)-1 即可。

当然可以用一个递归来划分区间。同样我也写了一下。。比上面的方法可慢了不少。。

# include <iostream>
using namespace std;

int t, n;

void dfs(long long root, long long min, long long max)
{
    if ( root == n )
    {
        cout << min << " " << max << endl;
        return;
    }
    if ( n < root )
        dfs((root+min)>>1, min, root-1);
    else dfs( ((root+max)>>1)+1, root+1, max );
}

int main()
{
    cin >> t;
    while ( t-- )
    {
        cin >> n;
        dfs((1<<30), 1, 2147483647);
    }
    return 0;
}

ACM 山东第一届省赛 Problem F Fairy tale

模拟题。读懂题目,跟着题目模拟就可以了。需要注意的就是geometrical
distance是两点间的直线距离,我理解为行和列差值的和错了一次。

有趣的是此题数据只有找到宝藏的情况。

但是,为什么不再问问能不能出来呢。

# include <cstdio>
# include <cstring>
# define rep(x) for ( x = 1; x <= n; ++x )
const int go[4][2] = {0,1, 0,-1, 1,0, -1,0}; //E,W,S,N
const int pgo[4][2] = {0,1, 0,-1, -1,0, 1,0}; //E,W,N,S prefer!

const int inf = 2147483647;
int n;
int m[35][35];
bool circle;

int x, y, tx, ty, time;

int abs(int x) { return x > 0 ? x: -x; }
int sqr(int x) { return x * x; }

bool inside(int x, int y)
{ return (x > 0 && x <= n && y > 0 && y <= n); }

bool better(int x, int y, int xx,int yy)
{ return sqr(x-tx)+sqr(y-ty) < sqr(xx-tx)+sqr(yy-ty); }

void Init()
{
    int i,j,k,l,p;
    char s[35];
    rep(i)
    {
        scanf("%s", s+1);
        rep(j)
            if ( s[j] == 'E' ) m[i][j] = 0;
            else if ( s[j] == 'W' ) m[i][j] = 1;
            else if ( s[j] == 'S' ) m[i][j] = 2;
            else if ( s[j] == 'N' ) m[i][j] = 3;
    }
    x = y = 1;
    tx = ty = n;
    time = 0;
    circle = false;
}

int cnt = 0;
int sec[103][5];
bool check()
{
    int i;
    for ( i = 1; i < time; ++i )
        if ( sec[i][0] == x && sec[i][1] == y && sec[i][2] == tx && sec[i][3] == ty && sec[i][4] == (time&3) )
        {
            circle = true;
            return true;
        }
    sec[i][0] = x,sec[i][1] = y,sec[i][2]= tx, sec[i][3] = ty, sec[i][4]= (time&3);
    return false;
}

bool step()
{
    int f1 = (m[x][y]+time)&3, f2 = (m[tx][ty]+time)&3;
    if ( x == tx && y == ty ) return true;
    if ( check() ) return false;
    int xx = x + go[f1][0];
    int yy = y + go[f1][1];
    if ( inside(xx,yy) ) x = xx, y = yy; //自动走
    xx = x, yy = y;
    for ( int i = 0; i < 4; ++i ) //喜好行走
    {
        if ( !inside(x + pgo[i][0], y + pgo[i][1]) ) continue;
        if ( better(x + pgo[i][0],y + pgo[i][1], xx, yy) )
            xx = x + pgo[i][0], yy = y + pgo[i][1];
    }
    x = xx, y = yy;
    int txx = tx + go[f2][0];
    int tyy = ty + go[f2][1];
    if ( inside(txx, tyy) ) tx = txx, ty = tyy; //宝藏走
    ++time;
    return false;
}

int main()
{
    int t = 0;
    while ( scanf("%d", &n), n )
    {
        if ( ++t > 1 ) printf("\n");
        Init();
        printf("Case %d:\n", t);
        while ( time < 100 )
        {
            if ( step() )
            {
                printf("Get the treasure! At step %d.\n", time);
                break;
            }
            if ( circle )
            {
                printf("Impossible. At step %d.\n", time);
                break;
            }
            if ( time == 99 ) printf("Not sure.\n");
        }
    }
    return 0;
}