随笔 - 147  文章 - 71  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜

http://www.spoj.pl/problems/PALIN/

【题意简述】
输入一个正整数k,输出大于k的最小回文整数。
【分析】
由于题目给的数字超级大(1000000位),所以暴力模拟显然会严重超时,于是考虑从数的特点来求解。

首先假设一个n位10进制数字可以表示为 A[0]A[1]A[2]...A[N-1],那么
1.我们希望从中间开始修改数字,使数增加的尽量少。
如:133151330,显然我们不会去改变它使之成为133252331,因为他显然比133161331来的大。
2.如果给你的数已经是一个Palindrome数,那你显然应该从最中间的开始改起。
如:808,显然你不会把它改成909而是把它改为818。
3.如果存在前半部分的某个数A[i]小于后半部分对应的数A[N-1-i],那么我们必须把前半部分的那个数变成后半部分的数才能满足Palindrome的条件,可是显然这增加过多,所以我们希望在它后面的某些数A[j]拿去增加 ,这样数字变大了,而且我们不需要使A[i]变大(显然A[i]在A[j]前面几位,增加A[j]的话,数字增加的更少)。
4.如果某数全为9,那么显然它的下一个Palindrome必然为10...01,其中有(N-1)个0。

于是得到下列算法:
a.首先判断串中是否全为9,如果是则输出10..01(0有N-1个),否则转下一步。
b.用2个指针i,j指向前、后半部分,显然i从前半部分的最右边,j从后半部分的最左边开始扫描。自然这里还需要考虑到N的奇偶性,即:i=(len>>1)-1,j=i+1+(len&0x1);
c.记录对应位置的数字的大小情况,并把前半部分的内容copy到后半部分对应的位上。
d.如果存在前半部分的某些数小于后半部分的某些数,或该数本身为Palindrome数,那么进行进位操作,即从最中间开始+1.一直加到没有进位。

import java.util.*;
import java.io.*;

public class SPOJ_5{
    
    
public static void main(String rgs[]) throws Exception
    
{
        BufferedReader stdin 
= 
            
new BufferedReader(
                
new InputStreamReader(System.in));        
        String s 
= stdin.readLine();  
        
int m,t = Integer.parseInt(s);
        
int[] dp=new int[1000002];
        
for(m=0;m<t;m++){
            s 
= stdin.readLine();                    
            StringBuilder str
=new StringBuilder(s);
            
            
int len=str.length(),i,j;
            
boolean alln=true;
            
for(i=0;i<len && alln;i++){
                
if(str.charAt(i)!='9')
                    alln
=false;
            }

            
if(alln){
                System.out.print(
"1");
                
for(i=0;i<len-1;i++)
                    System.out.print(
"0");
                System.out.println(
"1");
                
continue;
            }

            
            
boolean flag=true;;
            i
=(len>>1)-1;
            j
=(len>>1)+(len&0x1);
            Arrays.fill(dp,
0);
            
while(j<len){
                
if(str.charAt(i)>str.charAt(j))
                    dp[j]
=-1;
                
else if(str.charAt(i)<str.charAt(j))
                    dp[j]
=1;
                i
--;
                j
++;
            }

            i
=(len>>1)+(len&0x1);
            
while(i<len){
                
if(dp[i]==-1)
                    
break;
                
if(dp[i]==1){
                    flag
=false;
                    
break;
                }

                i
++;
            }

            
if(i==len)
                flag
=false;
            
for(i=(len>>1)+(len&0x1);i<len;++i){
                
if(dp[i]!=0)
                    str.setCharAt(i,str.charAt(len
-1-i));
            }

            
            
if(!flag){                
                i
=(len>>1);
                
if(len%2==0)
                    i
--;
                
int buf=1;
                
while((buf==1&& (i>=0)){
                    buf
=(str.charAt(i)+1-'0')/10;
                    
int p=(int)(str.charAt(i)-'0'+1)%10;
                    
char c=(char)(p+48);
                    str.setCharAt(i,c);
                    str.setCharAt(len
-1-i,c);
                    i
--;
                }

            }

            
            System.out.println(str);
        }

     }

}
posted on 2009-08-26 10:35 飞翔天使 阅读(319) 评论(0)  编辑  收藏 所属分类: spoj

只有注册用户登录后才能发表评论。


网站导航: