专栏首页HansBug's Lab3298: [USACO 2011Open]cow checkers

3298: [USACO 2011Open]cow checkers

3298: [USACO 2011Open]cow checkers

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 65  Solved: 26

[Submit][Status][Discuss]

Description

   一天,Besssie准备和FJ挑战奶牛跳棋游戏。这个游戏上在一个M*N(1<=M<=1,000,000;1<=N<=1,000,000)的棋盘上,  这个棋盘上在(x,y)(0<=x棋盘的左下角是(0,0)坐标,棋盘的右上角是坐标(M-1,N-1)。  Bessie每次都是第一个移动棋子,然后Bessie与Fj轮流移动。每一轮可以做以下三种中的一种操作:   1)在同一行,将棋子从当前位置向左移动任意格;  2)在同一列,将棋子从当前位置向下移动任意格;   3)将棋子从当前位置向下移动k格再向左移动k格(k为正整数,且要满足移动后的棋子仍然在棋盘上)   第一个不能在棋盘上移动的人比赛算输(因为棋子处在(0,0)点)。  共有T个回合(1<=T<=1,000),每次给出一个新起始点的坐标(x,y),确定是谁赢。 

Input

第1行:两个用空格隔开的整数M和N;   第2行:一个整数T;   第3到第T+2行:两个用空格隔开的整数x和y. 

Output

第1到T行:包含“Farmer John”或者是“Bessie”,表示谁赢了这轮游戏。

Sample Input

3 3 1 1 1

Sample Output

Bessie

HINT

Source

Silver

题解:实际上,一上来此题目不难想到可以通过DP(或者记忆化搜索也行)来搞,但这样问题来了——N,M<=1000000,显然会爆。。。

于是只好来另辟蹊径——(明确两个概念: 死点:表示当某一方在还未走这一步之前如果落到了这个位置将必死无疑的点 活点:正好相反)

1.题目中说从(N-1,M-1)走到(0,0),既然这样,我们何不看作从(0,0)走到(N-1,M-1)呢?

2.题目中说可以横向走,可以纵向走,可以斜向走,这不就意味着只要某一点被认定为死点,则这一个点横向、纵向、斜向上的其他点都是活点么(很明显如果某人走到了死点横向、斜向、纵向上的其他点上的话,他就可以把对手一步送到死点上,结束战斗。。。)

3.由2可知,所有的死点必然不在同一行,同一列,同一对角线上,也就是说对于某一x或者y坐标而言,其上死点的坐标是唯一的

4.所以综上所述,可以通过简单的O(N)预处理来实现求出每一个x坐标上的死点位置,然后接下来对于每个询问只要O(1)判断是否相同即可

于是,我们来开始找规律:

如上图,黑色的斜线表示对称轴,蓝箭头连着的是对称的,而红色箭头均为与对称轴平行的线,很明显所有下半边的点所在的线间隔都是1单位,这样一来规律就很分明了——对于当前的x坐标,要么已经通过之前的某点对称得到了结果,如果没得到的话,那就根据上一个同侧的点从斜线方向挪一格,然后对称一下得出上半边那个点,实现快速求解

 1 /**************************************************************
 2     Problem: 3298
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:72 ms
 7     Memory:4132 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;
12    a:array[0..1000005] of longint;
13 function max(x,y:longint):longint;
14          begin if x>y then max:=x else max:=y; end;
15 begin
16      fillchar(a,sizeof(a),-1);
17      a[0]:=0;l:=0; readln(n,m);
18      for i:=1 to max(m,n) do
19          begin if a[i]>-1 then continue;
20          inc(l);a[i]:=i+l;if (i+l)<=1000005 then a[i+l]:=i; end;
21      readln(n);
22      for i:=1 to n do
23          begin
24               readln(j,k);
25               if k>j then begin l:=k;k:=j;j:=l end;
26               if a[j]<>k then writeln('Bessie') else writeln('Farmer John');
27          end;
28 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1627: [Usaco2007 Dec]穿越泥地

    1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  So...

    HansBug
  • 1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

    1734: [Usaco2005 feb]Aggressive cows 愤怒的牛 Time Limit: 5 Sec  Memory Limit: 64 MB...

    HansBug
  • 1593: [Usaco2008 Feb]Hotel 旅馆

    1593: [Usaco2008 Feb]Hotel 旅馆 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 39...

    HansBug
  • 1627: [Usaco2007 Dec]穿越泥地

    1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  So...

    HansBug
  • C++拾取——使用stl标准库实现排序算法及评测

            今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义...

    方亮
  • C++拾取——使用stl标准库实现排序算法及评测

    今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义。这让它在专心研...

    方亮
  • Python应用 | 三行代码实现GIF动画

    图片看腻了,来一点动画吧。 很酷的花朵GIF动画,想了解一下如何利用Python实现吗?

    算法与编程之美
  • Python应用 | 三行代码实现GIF动画

    图片看腻了,来一点动画吧。 很酷的花朵GIF动画,想了解一下如何利用Python实现吗?

    double
  • Python大牛一步步教你用Python制作迷宫GIF

    安装 可以通过PyPi安装 或者通过Git 为什么你需要这个库? 问:我是一个Python迷,并且对迷宫的生成和迷宫解决的办法非常感兴趣。我很羡慕别人能够做出生...

    企鹅号小编
  • 用Python制作迷宫GIF

    问:我是一个Python迷,并且对迷宫的生成和迷宫解决的办法非常感兴趣。我很羡慕别人能够做出生成迷宫的动画。我如何能够用Python自己做一个迷宫动画,然后把我...

    小小科

扫码关注云+社区

领取腾讯云代金券