Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:跪求代码~~~

Posted by Yudus at 2010-09-16 23:13:07 on Problem 2338
In Reply To:跪求代码~~~ Posted by:Yudus at 2010-04-18 09:27:51
> 实在是测不出来了,还是WA,哪位大牛给份能AC的代码啊?
最近闲着无聊,又重写了一遍,终于AC了,没人给我代码,我自己贴出来吧。。。。。。

#include <iostream>

using namespace std ;

const int MAX = 1000 ;

char s[MAX] ;

int char_to_num( char c ){//把字符转换成数字,非法字符返回-1
    if( c >= '0' && c <= '9' ){
        return c - '0' ;
    }
    if( c >= 'a' && c <= 'f' ){
        return c - 'a' + 10 ;
    }
    return -1 ;
}

int string_to_num( int base , int beg , int end ){//把字符串转换成base进制的数字,出错返回-1
    int res = 0 ;
    for( int i = beg ; i <= end ; ++i ){
        if( res > 16 ){//大于16进制的无效
            return -1 ;
        }
        res += char_to_num( s[i] ) ;
        res *= base ;
    }
    res /= base ;
    if( res > 16 || res < 2 ){//大于16或小于2进制的无效
        return -1 ;
    }
    return res ;
}

int find_scope( int beg ){//找到beg后第一个#或最大长度的位置
    while( s[beg] != '#' && beg != strlen( s ) ){
        ++beg ;
    }
    return beg-1 ;
}

bool in_scope( int num , int beg , int end ){//判断从起点到终点的字符是否在num范围内
    int a[MAX] = { 0 } ;
    for( int i = beg ; i <= end ; ++i ){
        a[i] = char_to_num( s[i] ) ;
    }
    for( int i = beg ; i <= end ; ++i ){
        if( a[i] >= num ){
            return false ;
        }
    }
    return true ;
}

bool first_round( void ){
    int count = 0 ;
    for( int i = 0 ; i < strlen( s ) ; ++i ){
        if( s[i] == '#' ){
            ++count ;
        }
        //判断表达式是否含有非法字符
        if( !( ( s[i] >= '0' && s[i] <= '9' ) || ( s[i] >= 'a' && s[i] <= 'f' ) || s[i] == '#' ) ){
            return false ;
        }
    }
    if( count == 2 && s[0] == '#' ){//首字符不为#,也就是说#123#是错的
        return false ;
    }
    if( count % 2 ){//判断#是否为偶数个
        return false ;
    }
    if( count == 0 ){//没有#的情况,必须为10进制
        if( !in_scope( 10 , 0 , strlen( s )-1 ) ){
            return false ;
        }
        else{
            return true ;
        }
    }
    //把第一个出现的#和最后一个#排除掉,剩下的#一定是两两挨着的!
    bool first_jing = false ;
    for( int i = 0 ; i < strlen( s )-1 ; ++i ){
        if( first_jing && s[i] == '#' ){
            if( !( ( s[i+1] == '#' && i+1 < strlen( s )-1 ) || ( s[i-1] == '#' && i-1 >= 0 ) ) ){
                return false ;
            }
        }
        if( !first_jing && ( s[i] >= 'a' && s[i] <= 'f' ) ){//第一个#前的数字必须为10进制,如a#1#是非法的
            return false ;
        }
        if( !first_jing && s[i] == '#' ){//标记first_jing
            first_jing = true ;
        }
    }
    return true ;
}

bool judge( void ){
    if( !first_round() ){//先进行第一轮基本判断
        return false ;
    }
    int beg = 0 ;
    int end = find_scope( beg ) ;
    int curbase = string_to_num( 10 , beg , end ) ;
    beg = end + 1 ;
    while( beg < strlen( s ) ){
        if( curbase == -1 && beg != strlen( s ) - 1 ){//如果进制超出16位并且不为最后的数
            return false ;
        }
        if( beg+1 < strlen( s ) && s[beg] == '#' ){//这里s[beg+1]一定也为#
            end = find_scope( beg+1 ) ;
            if( end == beg ){//如果两#之间没有数字,直接no
                return false ;
            }
            if( !in_scope( curbase , beg+1 , end ) ){//判断后面的数字能不能用curbase进制表示
                return false ;
            }
            //更新进制
            curbase = string_to_num( curbase , beg+1 , end ) ;
            beg = end ;
        }
        beg += 2 ;
    }
    return true ;
}

int main( void ){
    int ncase ;
    cin >> ncase ;
    while( ncase-- ){
        cin >> s ;
        if( judge() ){
            cout << "yes" << endl ;
        }
        else{
            cout << "no" << endl ;
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator