The Fourth Dimension Space

HDOJ 1698 Just a Hook 线段树

摘要: 题目的意思是给你一个数组，大小是N,初始的时候,a[1-N]均为1,然后有Q个操作，每次操作修改某个区间中的值，求最后整个区间1-N的和。线段树解决 #include<iostream>using namespace std;int const maxn=100100;struct node{ &nb... 阅读全文

posted @ 2010-07-17 11:42 abilitytao 阅读(260) | 评论 (0) | 编辑收藏

            先我对今天的A题表示深深的无语，居然是直接暴力，有点技术含量行不行啊。。。打一张10^7次方的素数表，居然可以过。。。
            C题其实很简单，数据中给了个10^6次方的数据，很明显是用来hash的。。。
            其他的题基本没看，卡了第一题后心态不是太好了。。。恩听说H是个简单题来着。。。看来我还缺乏些判断简单题的眼力。。。
            老实说我觉得今天的题出的不好，当然我不能直接那么说。不过要继续努力哈，只是结对前最后一次比赛居然这么囧。

posted @ 2010-07-15 20:37 abilitytao 阅读(208) | 评论 (0) | 编辑收藏

NOJ 1177 跳马 SG函数，博弈

先贴个代码，博弈问题还要继续深究，special thanks to thinkking!
原题：

相信大家都玩过象棋，象棋中马跳日。Alice 和Bob现在想玩一个游戏，在一个n * n的棋盘，棋盘中放了m个马。游戏规则如下：

1） Alice先手

2） 玩家轮流操作，每次合法操作是将其中一个马按照日移到其左上方一点，注意只能往左上方移动。最左上方的位置是（ 1 ， 1 ），同一位置可以有多个马，但是每次移动只能移动一个马。

玩家都很有谋略，他们都以最优策略来下每一步。问最后谁能取胜

Input

第一行输入整数t ( t < = 100 ), 则有t 个case。每个case 先输入棋盘的大小 n ( n < = 500 ) ，马的个数 m（ m < = 20000 ）下面m行输入马的坐标位置 x ，y （ 1 = < x < = 500 1 = < y < = 500 ）

Output

对于每个case 输出谁会获得最终胜利。注意：马只要是日就可以跳，而不需要满足象棋中的一些其他规矩

SampleInput

SampleOutput

Case 1: Alice
Case 2: Bob


#include<iostream>
#include<cmath>
using namespace std;

int n,m;
int dir[2][2]={{-1,-2},{-2,-1}};

bool god(int x,int y)
{
    if(x<1||x>500||y<1||y>500)
        return false;
    return true;
}
int const maxn=510;
int SG[maxn][maxn];

struct node
{
    int x,y;
}q[20020];

int v[3];
int main()
{

    int ca;
    scanf("%d",&ca);
    int cn=0;
    for(int i=1;i<=500;i++)
    {
        for(int j=1;j<=500;j++)
        {
            memset(v,0,sizeof(v));
            for(int k=0;k<2;k++)
            {

                int nx=i+dir[k][0];
                int ny=j+dir[k][1];
                if(god(nx,ny))
                {
                    v[SG[nx][ny]]=1;
                }
            }
            for(int k=0;k<=2;k++)
            {
                if(v[k]==0)
                {
                    SG[i][j]=k;
                    break;
                }
            }

        }
    }
    while(ca--)
    {
        cn++;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d%d",&q[i].x,&q[i].y);
        
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            ans^=SG[q[i].x][q[i].y];
        }
        if(ans)
            printf("Case %d: Alice\n",cn);
        else
            printf("Case %d: Bob\n",cn);
    }
    return 0;
}