2006 年百度之星程序设计大赛初赛题目 4

厚积薄发

剪刀石头布
& p3 u6 O/ M4 e
N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩 M 次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。

! @8 p( w% b! R+ ?9 N输入格式：

输入文件包含多组测试数据。每组测试数据第一行为两个整数 N 和 M （ 1 ≤ N ≤ 500 ， 0 ≤ M ≤ 2000 ），分别为小孩的个数和剪刀石头布游戏进行的次数。接下来 M 行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号，为小于 N 的非负整数。符号的可能值为“ = ”、“ > ”和“ < ”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。
$ P* L1 W: W1 c7 g
输出格式：

1 ~% ?4 U/ q, c8 q0 I0 \% n每组测试数据输出一行，若能猜出谁是裁判，则输出身为裁判的小孩的编号，并输出在第几次游戏结束后就能够确定谁是裁判。如果无法确定谁是裁判，或者发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出相应的信息。具体输出格式请参考输出样例。

输入样例

7 ~1 o& `1 s' d% L5 f0 h
3 3
; H. Z5 r: R/ v3 J1 e8 P) y
$ z& m' o$ J  P. v4 b# ^! X0<1

/ i# M9 p  V5 f4 ^  P1<2

1 E8 N; S) B8 v! ~2 {* Z6 [2<0

3 5

0<1
2 c' q7 f- ]* M1 o/ a4 N1 Z* f
; Y5 R2 I- q3 B' b( h* L/ z0>1
: K, D' q' A! ^3 E4 Q3 G
1<2

4 b$ d1 @+ A* Q( q/ j( D1>2

0 k4 v- z3 R* K: V. i& k7 F0<2

4 4

0<1

0>1

0 N! F6 h# E; W. j# [9 z( \7 G2<3
5 s/ ^6 \1 ?: }" _3 k( L9 N
$ x; C$ x' i: [) x5 r3 \3 U3 L, u2>3
/ }* D6 W* g8 z) V0 d+ n8 D
8 m$ K6 ~2 n& H$ \6 v! g4 Z1 0

( o/ Q. O# L. U# |, R, E- h3 y
输出样例

# j* b- u7 C7 FCan not determine

Player 1 can be determined to be the judge after 4 lines
& P' V7 M0 p+ U, e3 A/ J
Impossible
# c0 P8 o  I3 q1 D
$ ~3 C1 w0 F# v! Q' ]# OPlayer 0 can be determined to be the judge after 0 lines

: q' K% B0 C( A: i) O. c

; O' s) }9 q- e; k说明：

共有 5 个测试数据集，每个测试数据集为一个输入文件，包含多组测试数据。每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分，对每个测试数据集分别执行一次程序，每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。

所有数据均从标准输入设备（ stdin/cin ）读入，并写出到标准输出设备 （ stdout/cout ）中。

+ [& Y- @7 E' t7 m) p五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ，各有 10 组测试数据。
0 Z) h$ h  s# j$ ]7 U# j& s" p
example1：
3 m- j* }1 o* U" P" h8 f. Q8 K
1 ]; l/ ]/ i( W/ b( C/ V  d1 Y5 `- L/*剪刀石头布*/
3 ]) P: c% `: t+ F8 z#include <iostream>
/ F& P0 Z3 a# E8 M- c, F4 a: _#include <vector>
$ s: }0 B: J3 |* h#include <string>
" u; g2 I* s8 i, |) v0 x* Zusing namespace std;
3 {& X* u0 S& N
) w) A2 _: T8 J1 ?struct numNod
{
( W2 v# ]  B6 S8 u2 o& S- r    int value;//小孩的编号
    vector<int> win;//胜出的数字队列 暂定20个 以后编写动态增加数组后再修改
    vector<int> lose;//输掉的数字队列 暂定20个 以后编写动态增加数组后再修改
    numNod *next;
};//如果某个数字结构体的胜出队列中和失败队列中出现二次或者两次以上的同数字结果则说明这个数字是裁判
//另外值得注意的是只有裁判才会出现平局的情况
7 b+ K. m  v1 d* N1 p3 k( t
class Run
{
public:
    Run();
    int Compare( int num1, int num2, char sign );
+ v1 s2 y$ J3 Gprivate:
( Z' v5 b" X& H2 e5 B    numNod *p;
0 Q% |- ?% b" F0 r& T7 d0 x9 N* P% w    int CheckUp();//检查函数,检查裁判是否已经得出
    int numOfCheck;//猜拳进行的次数
/ O8 j, x2 o$ _  f3 Y    numNod* SearchNum( int num );//查找p所指向队列是否有num这个数字结构,有的话返回指向num的地址,没有的话返回的地址是NULL
    void ReworkList( numNod *p, char sign, int num2 );//第一种情况,给出指向数字结构体指针,输赢标志(1,2,3),比较对象(数字)
6 p% C3 J5 q9 F$ E    void ReworkList( int num1, char sign, int num2 ); //第二种情况,即结构体数字队列没有这个数字要重新生成
$ q$ c+ U. q; k$ G* U};

2 A. ~! V8 [, g" hRun::Run()
{
    this->p = NULL;
    this->numOfCheck = 0;
}
* S6 y/ Z' `6 ]8 j7 A3 M
+ j" |; V; t$ ?, O; t/ F4 g: onumNod* Run::SearchNum( int num )
{
! K1 I4 m2 S( \0 ]* [$ O8 b    if( !this->p )
) N  |  F" o7 l9 x' U    {
4 K$ m' U# J& G        return NULL;
2 @& }  j! Z( N9 s5 Z    }
    else
    {
        numNod *pTmp = this->p;
' E" R+ |4 T  H# q$ F" ]3 `        while( pTmp->value != num && pTmp->next )
            pTmp = pTmp->next;
% P+ ]9 Z* _0 Z: @( j" @- k, S- N0 J        //至此查找完毕开始检测是否已经找到
        if( pTmp->value == num )
        {
            return pTmp;
        }
3 I& o: ~6 W. A& b1 z        else
        {
            return NULL;
' Y' q1 _( @+ P0 Y7 h. U0 k        }
. \) ?5 `$ l. S; ]) g    }
  N1 |( Y, S5 @}

void Run::ReworkList( numNod *p, char sign, int num2 )
{
    if( sign == '>' )
! p/ s0 K- r3 K, {    {
        p->win.push_back( num2 );
: Q) D% B* h  }  |# q    }
1 @6 a$ N' J9 f3 o% C    else if ( sign == '<' )
    {
        p->lose.push_back( num2 );
    }
. z7 _4 G$ O7 x3 J: e' R    else if( sign == '=' )//平局
    {
% ]0 B$ S! Q/ i" J, O. }        p->win.push_back( num2 );
9 Y$ D" D0 f& n" e% O        p->lose.push_back( num2 );
    }
    else//非法比较字符
    {
        cout << "Sign Error!" << endl;
        return;
    }
}

' b7 g8 X: t, J/ }  h& Fvoid Run::ReworkList( int num1, char sign, int num2 )
{
    numNod *pTmp = this->p;
* c% {8 V8 V( i7 V- I
    if( this->p == NULL )
    {
        this->p = new numNod;
% b8 B$ L7 }2 m5 S& @        this->p->next = NULL;
2 B/ F6 p: P' Z7 H        this->p->value = num1;
        pTmp = this->p;
; d  [, B3 f4 X4 C9 ^0 R    }
( s; N; k4 B. B$ I! t. U    else
    {
    while( pTmp->next )
        pTmp = pTmp->next;
* B5 P; {: a$ v    pTmp->next = new numNod;
) b. U2 m6 S, j" N    pTmp->next->value = num1;
    pTmp->next->next = NULL;
    pTmp = pTmp->next;
    }
   
    if( sign == '>' )
    {
4 ?; l  V" [0 z, W* G        pTmp->win.push_back( num2 );
1 c1 }4 q! A/ e4 _9 m4 ]    }
    else if ( sign == '<' )
    {
! g4 O  P; i* n$ t' m$ a- j        pTmp->lose.push_back( num2 );
: J+ u% a7 _# f& R# c9 U    }
    else if( sign == '=' )//平局
! `/ V& \- T# E, z    {
        pTmp->win.push_back( num2 );
7 b+ E; ?6 U+ C        pTmp->lose.push_back( num2 );
! J: ~! s$ g* R5 f8 h$ b    }
2 E6 S4 [3 Q0 G% N1 f5 u% r    else//非法比较字符
  V' {% U* a3 e" f+ d    {
; a. k; \+ p4 T5 L; N5 W        cout << "Sign Error!" << endl;
        return;
6 z9 y0 p& z/ G5 y6 \7 V; A! B    }
$ @6 N+ V9 ^% H: m/ `- Q6 ^}

& n( l7 {0 h: F+ y- _, ?, ~5 {int Run::Compare( int num1, int num2, char sign )
% i4 L/ X1 B; X: P{
    numNod *pTmp;
. F1 O6 C1 p& {. W; L    int result(-1);
9 F' ]( l  I) D& e5 Y" L   
- t# ^- ]( v* B1 U& A0 G    //检查队列有没有num1 和 num2  有点话处理 每有生成
    pTmp = this->SearchNum( num1 );
    if( pTmp )//如果已经有
    {
5 T5 {3 w% k  h5 k7 v4 Q9 p/ W        this->ReworkList( pTmp, sign, num2 );
    }
    else
: ]( @# L* X/ H. P7 q; I  h    {
% o% k7 n+ X! {  `  V        this->ReworkList( num1, sign, num2 );
    }
    //处理第二个数字
    pTmp = this->SearchNum( num2 );
; v4 }  }0 N* {5 v" N    if( pTmp )//如果已经有
    {
        this->ReworkList( pTmp, sign, num1 );
    }
    else
& i# M, i9 D, a9 S1 I    {
        this->ReworkList( num2, sign, num1 );
: u9 b  M1 m6 @' |7 y9 g) m+ r3 \    }
    ++ this->numOfCheck;
+ f/ j8 U7 V4 Y3 B+ c    result = this->CheckUp();
! p( ]: {' C8 M" q/ a- n, s) Z    if( result != -1 )
6 W/ p) r# e% ]& U# w    {
        return result;
3 @% D) ]; n( [1 K3 j2 o7 M0 r( w    }
- S- d2 n; n- _. Y. l    return -1;
}

" Q% S8 |$ p& d/ k3 aint Run::CheckUp()//返回-1表示没有得出裁判,否则返回裁判的编号
% A* }1 h$ C  ?3 V$ ^2 z{
  v* r' X3 Z# b. f/ y3 _7 G    numNod *pTmp = this->p;
# i  [- @0 F$ L: f/ A' Q    int numOfSame = 0;//win lose列有相同有相同数字的次数
8 x* W+ S& m' y3 _0 q1 U    while( pTmp )
    {
        for( vector<int>::size_type i = 0; i < pTmp->win.size(); ++ i )
        {
7 ^8 h) o) A5 C            for( vector<int>::size_type j = 0; j < pTmp->lose.size(); ++ j )
            {
                if( pTmp->win == pTmp->lose[j] )
; I6 O) C" G7 S+ ^. \% S7 |                    ++ numOfSame;
! G3 L5 U+ q7 f0 p( y, S            }
        }
        if( numOfSame > 1 )
' b( J1 h# v/ c2 U        {
% L  l( s: {- e' V4 Y& _            return pTmp->value;//返回裁判数字编号
        }
+ _$ k  L7 g, Y, a0 W0 M- b+ Q        numOfSame = 0;
        pTmp = pTmp->next;
    }
    return -1;
+ S; t+ f* X* c7 F( p}

int main()
{
    Run example1;
    cout << "请输入选手人数 和 比赛次数" << endl;
- W# Q" y& L- S8 @8 _" ]    int num1(0), num2(0);
% d1 A8 H' E0 y    cin >> num1 >> num2;
    if( num1 == 1 && num2 == 0 )
0 J, Q* ]+ r5 L" A& y- k5 g    {
        cout << "Player 0 can be determined to be the judge after 0 lines" << endl;
1 h' s) Z3 A" C. |2 j* ~        return 0;
; L! Q9 D8 q" {8 m+ _    }
6 F4 E( x- |9 u# I    else if( num2 == 0 && num1 > 1 )
    {
        cout << "Can not determine " << endl;
, O3 S- B: S& F% o9 {2 m        return 0;
    }
    cout << "请输入" << num2 << "次的比赛结果,让程序来猜测裁判是谁,输入格式例如 1 < 0" << endl;
3 H. Y' w( A0 E* n    int num3(0), num4(0);
& P2 ?# ^9 n6 u9 q; U, b    char sign;
  v( t9 M( v- R9 L( G. C    //string string1;
/ D! ^  t2 }9 R) _; A1 T& F- x5 V    int comparlines(0);
$ T/ Y# U! r# ]4 K7 r. I7 s    while( cin >> num3 >> sign >> num4 && comparlines < num2 )
: V7 Q: S3 ?0 X+ q/ u9 b    {
  E3 J! J) N. @3 D) @9 P        //cout << "Debug:: string1:" << string1 << endl;
" S4 o; L) s1 @; u3 _& z) e7 _; F% F        //num3 = string1[0];
        //sign = string1[1];
        //num4 = string1[2];
        //cout << "Debug:: num3" << string1[0] << endl;
2 ~4 P/ f" R" ]% V# b; r        if( num3 < 0 || num3 > num1 || num4 < 0 || num4 > num1 )
2 [, t2 x1 J- ~, J2 M        {
            cout << "存在选手编号非法输入,程序退出!" << endl;
            return -1 ;
        }
. `- ?( M  q6 V! l        int rs = example1.Compare( num3, num4, sign );
: A* e3 O) _: f+ T& q6 l        if( rs != -1 )
        {
% I1 G, t6 ~) ?  {& Z9 X            cout << "Player" << rs << "can be determined to be the judge after " << comparlines << " lines" << endl;
            return 0;
        }
        ++ comparlines;
        if( comparlines == num2 )
        {
            cout << " Can not determine " << endl;
7 c. k- K6 w9 t1 ~: x& X* E            return 0;
        }
    }
   
    return 0;
0 [* [  ]6 ~3 |) P' B4 O}


7 `6 @9 Z0 t1 G- e( g
8 n' }: h+ [: T4 x: m、
( Y. L; [0 k- P2 g4 R3 a& K4 Z3 V3 S
$ D/ o, C- J2 o


0 }; U. @& u! R5 A+ G% r* {来源：编程爱好者acm题库

1164678512

Acm惹不起，呵呵

1164678512

Acm惹不起，呵呵

qiuyeliu

eueis 发表于 2011-8-31 17:04
; j! A6 n; \; |% ]0 i0 s, p# H8 R一起交流！对这个话题感兴趣的朋友们

" ^) O1 u$ ]' f$ @Acm 一般用C吧

大鲵2003