随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

2009年8月7日

zoj1405_Tanning Salon

        这个题目我错了很久,一直错的原因是我没有真正的理解题目的意思。
        在 1 ABAB  这组数据上错了,改过来之后就过了,下一次一定要好好读题。
        这一次是尽量用C++来写,在用rfind函数的时候出了一点小问题,应该是从这个字符往前推一位开始查找,若是第一个字符,就不能调用函数了,不然就会出错。所以就多加了一个判断,影响了程序的可读性。下一次要找到一个不需要这样判断的方法。
#include<iostream>
#include
<string>
#define DEBUG 1
using namespace std ;

const int cap = 33 ;

char salon[cap] ;
string in ;

int check( int avai )
{
    
int i, j, pos(-1), flag, away(0) ;
    
for( i=0; i<in.size(); ++i ){
        
if( i >= 1 )
            pos 
= in.rfind( in[i], i ) ;
        
if( pos >= 0 ){
            flag 
= 0 ;
            
for( j=0; j<avai; ++j ){
                
if( salon[j] == in[i] ){
                    salon[j] 
= '\0' ;
                    flag 
= 1 ;
                    
break ;
                }

            }

            
if!flag )    {
                
for( j=0; j<avai; ++j ){
                    
if!salon[j] ){
                        flag 
= 1 ;
                        
break ;
                    }

                }

            }

            
if!flag )
                
++away ;
        }

        
else{
            
for( j=0; j<avai; ++j ){
                
if!salon[j] ){
                    salon[j] 
= in[i] ;
                    
break ;
                }

            }

        }

    }

    
return away ;
}


void output( int away )
{
    
if( away )
        cout 
<< away << " customer(s) walked away." << endl ;
    
else
        cout 
<< "All customers tanned successfully." << endl ;
}


int main( )
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif

    
int avai, away ;
    
while( cin >> avai ){
        
if( avai == 0 )
            
break ;
        cin 
>> in ;
        away 
= check( avai ) ;
        output( away ) ;
    }
    
    
return 0 ;
}

posted @ 2009-08-07 11:50 祝你好运! 阅读(218) | 评论 (0)编辑 收藏

2009年7月26日

zoj1002 Fire Net

        好久都没有写解题总结了,手生了。抓紧时间做题,不然等到开学了,就不能这么爽的做题了。

        这个题数据量不大,可以用回溯。刚开始做的时候,是用广搜,但是写起来超麻烦,代码量极大,很容易出错。参考了大牛们的做法,才想起来和N皇后问题很像。我们可以从一个点出发,然后往右下扩散,扩散完了之后,再回溯,再扩散…… 问题解决。

#include<iostream>
#define DEBUG 0
using namespace std ;

int n, maxi ;
char a[5][5] ;

bool legal( int x, int y )
{
    
int i, j ;
    
for( i=x-1; i>=0--i ){
        
if( a[i][y] == '@' )
            
return false ;
        
else if( a[i][y] == 'X' )
            
break ;
    }

    
for( j=y-1; j>=0--j ){
        
if( a[x][j] == '@' )
            
return false ;
        
else if( a[x][j] == 'X' )
            
break ;
    }

    
return true ;
}


void trace( int x, int y, int geshu )
{
    
if( x == n )
        maxi 
= maxi>geshu ? maxi:geshu ;
    
else{
        
if( y == n )
            trace( x
+10, geshu ) ;
        
else {
            
if( a[x][y]=='.' && legal( x, y ) ){
                
// 回溯标记 
                a[x][y] = '@' ;
                trace( x, y
+1, geshu+1 ) ;
                a[x][y] 
= '.' ;
            }

            trace( x, y
+1, geshu ) ;
        }

    }

}


int main()
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif

    
int i, j ;
    
while( cin >> n ){
        
if!n )
            
break ;
        
for( i=0; i<n; ++i ){
            
for( j=0; j<n; ++j ){
                cin 
>> a[i][j] ;
            }

        }

        maxi 
= 0 ;
        
// 从0,0开始回溯 
        trace( 000 ) ;
        cout 
<< maxi << endl ;
    }

    
    
return 0 ;
}

posted @ 2009-07-26 17:33 祝你好运! 阅读(186) | 评论 (0)编辑 收藏

2009年6月5日

hdu1016_Prime Ring Problem

        简单而且经典的搜索题,用回溯做。对于什么是回溯什么是DFS我分不清。就是按位逐个判断,直到找到结果,或者出界退出。

#include<iostream>
#include
<cmath>
using namespace std ;
int n, a[111], k, ans[22], anscnt ;
int p[42]= {0,0,2,3,0,5,0,7,0,0,0,11,0,13,0,0,0,17,0,19,0,
           
0,0,23,0,0,0,0,0,29,0,31,0,0,0,0,0,37,0,0,0,41}
 ;

int rev[100][20], revcnt ;

void DFS( int m, int geshu )
{
    
int i, j ;
    
if( geshu == n && p[1+m] ){
        cout 
<< ans[0] ;
        
for( i=1; i<n; ++i ){
            cout 
<< " " << ans[i] ;
            rev[revcnt][i] 
= ans[i] ;
        }

        
++revcnt ;
        cout 
<< "\n" ;
    }

    
else if( geshu == n )
        
return ;
    
for( j=2; j<=n; ++j ){
        
if( j<p[j+m] && !a[j] ){
            a[j] 
= 1 ;
            ans[geshu] 
= j ;
            DFS( j, geshu
+1 ) ;
            a[j] 
= 0 ;
        }

    }

}


int main( )
{
    
int i, j ;
    
for( j=1; cin >> n; ++j ){
        cout 
<< "Case "<< j << ":\n" ;
        
for( i=0; i<111++i )
            a[i] 
= 0 ;
        revcnt 
= 0 ;
        k 
= 1 ;
        ans[
0= 1 ;
        anscnt 
= 1 ;
        DFS( 
11 ) ;
        cout 
<< "\n";
    }

    
return 0 ;
}

posted @ 2009-06-05 10:55 祝你好运! 阅读(113) | 评论 (0)编辑 收藏

2009年5月30日

hdu2303_The Embarrassed Cryptographer

        好几天都没有刷题了,心里好烦躁啊!

        今天终于又做了一个不是很水的题目,数论的,大整数取余,直接暴力过了。其中又学了一种素数的筛选法,效率比我以前用的方法都要高。他不计算,只是筛选。这样一来效率就高了很多。还有一个地方,就是大整数的取余,从高位,到低位,边乘边取余,根据的是同余定理。


#include <stdio.h>
#include 
<string.h>
#include 
<stdlib.h>

int p[1000000] ;
char pr[1000000] ;
int len, pnum, num[14] ;

void prime( )
{
    
int i, j ;
    
// 筛选素数 
    for( i=2; i<1000000++i ){
        pr[i] 
= 1 ;
    }

    
for( i=2,pnum=0; i<1000000++i ){
        
if( pr[i] ){
            p[pnum
++= i ;
            
for( j=i+i; j<1000000; j+=i )
                pr[j] 
= 0 ;
        }

    }

}


int mod( int n )
{
    __int64 m
=0 ;
    
int i ;
    
// 求余数 
    for( i=len-1; i>=0--i ){
        m 
= ( m*100000000+num[i] ) % n ;
    }

    
return m ;
}


int main()
{
    
char a[111] ;
    
int i, j, div, flag ;
    
    prime( ) ;
    
    
while( scanf("%s%d", a, &div ) && div && a[0]!='0' ){
        len 
= strlen( a ) ;
        
for( i=0; i<14++i )
            num[i] 
= 0 ;
        
for( i=0; i<len; ++i ){
            
//逢一亿进位 
            j = (len+7-i) / 8 - 1 ;
            num[j] 
= num[j]*10 + a[i]-'0' ;
        }

        len 
= (len+7)/8 ;
        flag 
= 1 ;
        
for( i=0; p[i]<div && i<pnum; ++i ){
            
if( mod( p[i] ) == 0 ){
                flag 
= 0 ;
                
break ;
            }

        }

        
if( flag )
            printf(
"GOOD\n") ;
        
else
            printf(
"BAD %d\n", p[i] ) ;
    }

    system(
"pause");
    
return 0 ;
}

posted @ 2009-05-30 15:38 祝你好运! 阅读(202) | 评论 (0)编辑 收藏

2009年5月22日

hdu2048错排的概率

          应该说是一个纯数学的题目,考察错排的概率。

#include <stdio.h>
#define DEBUG 1
int main()
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif
    
    __int64 i, n, sets, s, fenmu ;
    
double p, temp ;
    scanf(
"%I64d"&sets ) ;
    
while( sets-- ){
        scanf(
"%I64d"&n ) ;
        p 
= 1 ;
        s 
= 1 ;
        fenmu 
= 1 ;
        
for( i=1; i<=n; ++i ){
            s 
*= -1 ;
            fenmu 
*= i ;
            p 
+= s/(double)fenmu ;
        }

        printf(
"%.2lf%%\n"100*p ) ;
    }

}

posted @ 2009-05-22 00:02 祝你好运! 阅读(317) | 评论 (0)编辑 收藏

2009年5月21日

hdu1465 错排

         这一题就是单纯的考察错排,也就是考察递推。

基本形式:d[1]=0;   d[2]=1
递归式:d[n]= (n-1)*( d[n-1] + d[n-2])

这就是著名的错排公式

 

#include <stdio.h>
#define DEBUG 1
int main()
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif

    __int64 i, n, s, geshu, a1, a2, temp ;
    
while( EOF != scanf("%I64d"&n ) ){
        a1 
= 0 ;
        a2 
= 1 ;
        
for( i=1; i<=n; ++i ){
            temp 
= a2 ;
            a2 
= (i-1* (a1+a2) ;
            a1 
= temp ;
        }

        printf(
"%I64d\n", a2 ) ;
    }

    
return 0 ;
}

 

posted @ 2009-05-21 23:17 祝你好运! 阅读(286) | 评论 (0)编辑 收藏

2009年5月12日

zoj1951_Goldbach's Conjecture

          判定素数的,水题,主要是练习一下筛选法。
#include <stdio.h>
#include 
<math.h>
#define DEBUG 1
short a[1000000] ;
int main()
{
    
#if DEBUG
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
     
#endif
    
int i, j, n, flag ;
    
double temp ;
    
for( i=2; i<1000000++i ){
        
if( a[i] )
            
continue ;
        
for( j=i; j<1000000; j+=i )
            a[j] 
= 1 ;
        temp 
= sqrt( i ) ;
        flag 
= 1 ;
        
for( j=2; j<=temp; ++j ){
            
if( i%== 0 ){
                flag 
= 0 ;
                
break ;
            }

        }

        
if( flag )
            a[i] 
= 0 ;
    }

    
while( scanf("%d"&n ) && n ){
        
for( i=3; i<n; i+=2 ){
            
if!a[i] && !a[n-i] ){
                printf(
"%d = %d + %d\n", n, i, n-i ) ;
                
break ;
            }

        }

    }

    
return 0 ;
}

posted @ 2009-05-12 17:03 祝你好运! 阅读(96) | 评论 (0)编辑 收藏

2009年5月11日

hdu2816_I Love You Too

     摘要:            本来是一道水题,模拟的。但是我当时把一个int变量定义成char型的,结果是死活都调试不出来!一直WA 。最后还是自己检查出来了。  1#include <stdio.h> 2#include <memory.h>...  阅读全文

posted @ 2009-05-11 12:48 祝你好运! 阅读(132) | 评论 (0)编辑 收藏

2009年5月10日

hdu1181变形课

        典型的Floyd传递闭包,只要知道了算法,做起来和简单。
#include <stdio.h>
#include 
<string.h>
#include 
<memory.h>
#define DEBUG 1
const int N=28 ;
int map[N][N] ;

void Floyd( )
{
    
int i, j, k ;
    
for( k=0; k<26++k )
    
for( i=0; i<26++i )
    
for( j=0; j<26++j )
        map[i][j] 
= map[i][j] || ( map[i][k] && map[k][j] ) ;
}


int main()
{
    
#if DEBUG
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
     freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
     
#endif
     
int len ;
     
char a[2000] ;
     
while( EOF != scanf("%s",a) ){
        
if( a[0== '0' ){
            Floyd( ) ;
            
if( map[1][12] )
                printf(
"Yes.\n") ;
            
else
                printf(
"No.\n") ;
            memset( map, 
0sizeof(map) ) ;
            
continue ;
        }

        len 
= strlen( a ) ;
        map[a[
0]-'a'][a[len-1]-'a'= 1 ;
    }

    
return 0 ;
}

posted @ 2009-05-10 19:48 祝你好运! 阅读(498) | 评论 (0)编辑 收藏

2009年5月8日

zoj1092_Arbitrage

        刚开始的时候我不知道这一题该如何来做,我当时想到了用搜索,但是数据量太大,可能会超时。队友这一题说可以用最短路径的方法来做。我实在是想不起来如何做,因为最短路径的算法我只学了Dijsktra。我在网上搜了一下,发现别人用的全是Floyd算法。我就学习了一下Floyd。其精髓就是一个三重循环。以最外层变量为中枢点。不断的求得两个点之间的最短路径。现在我只理解到了这里,有待于以后的提高!
       对于这一题,只要能够找到一个顶点,让他的值比1大,就说明可以钱生钱。

#include <stdio.h>
#include 
<string.h>
#include 
<memory.h>
#define DEBUG 1
int n ;
char mo[31][30] ;
double map[31][31] ; 

int Find( char *t )
{
    
int i ;
    
for( i=1; i<=n; ++i )
        
if!strcmp( mo[i], t ) )
            
return i ;
}


void Floyd( )
{
    
int i, j, k ;
    
for( k=1; k<=n; ++k )
        
for( i=1; i<=n; ++i )
            
for( j=1; j<=n; ++j )
                
if( map[i][j] < map[i][k]*map[k][j] )
                    map[i][j] 
= map[i][k]*map[k][j] ;
}


void In( )
{
    
int i, x, y, sets ;
    
char a[30], b[30] ;
    
double rate ;
    
for( i=1; i<=n; ++i )
           scanf(
"%s", mo[i] ) ;
    scanf(
"%d"&sets ) ;
    
for( i=1; i<=sets; ++i ){
        scanf(
"%s %lf %s", a, &rate, b ) ;
        x 
= Find( a ) ;
        y 
= Find( b ) ;
        map[x][y] 
= rate ;
    }

}


void Judge( )
{
    
int flag, i ;
    flag 
= 0 ;
    
for( i=1; i<=n; ++i ){
        
if( map[i][i] >= 1 ){
            flag 
= 1 ;
            
break ;
        }

    }

    
if( flag )
        printf(
"Yes\n") ;
    
else
        printf(
"No\n") ;    
}


int main()
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif
    
    
int i ;
    
for( i=1; scanf("%d"&n) && n; ++i ){
        printf(
"Case %d: ", i ) ;
        memset( map, 
0sizeof(map) ) ;
        In( ) ;
        Floyd( ) ;
        Judge( ) ;
    }

    
return 0 ;
}

posted @ 2009-05-08 00:47 祝你好运! 阅读(209) | 评论 (0)编辑 收藏