首页 > 专题系列 > Java解POJ > POJ 1832 连环锁 [解题报告] Java
2013
11-10

POJ 1832 连环锁 [解题报告] Java

连环锁

问题描述 :

许多人一定很熟悉九连环(如下图),九个环被串在一起,操作规则如下:第一个(右边)环可以任意装卸,如果第k个环没有被卸掉,而第k个环前边(右边)的所有环都被卸掉,则第k+1个环(第k个环左边的环)可以任意装卸(如果存在的话)。

用0表示此换被卸掉,1表示此环没有被卸掉,则九连环的每个状态可以用一个长度为9的二进制串来表示,如:111111001经过一次操作可以变成111111000,也可以变成111111011,111111111经过一次操作可以变成111111110,也可以变成111111101。



任务描述:

你现在要操作的是一个n连环,n为正整数,给出n连环的两种状态,计算出从第一种状态变换到第二种状态所需要的最少步数。

输入:

第一行是一个正整数m,表示有m组测试数据。

每组测试数据一共3行,第一行是一个正整数n (0 < n < 128),后两行每一行描述一种状态,n个数(0或1),用空格隔开。

输出:

对于每一组测试数据输出一行,一个非负整数,表示从第一种状态变换到第二种状态所需要的最少步数。

样例输入:

2
3
0 0 0
1 0 0
4
1 0 0 0
0 1 1 0

样例输出:

7
11

解题代码:

方法(1)
import java.math.*;
import java.util.*;

public class Main {
    static BigInteger[] base = new BigInteger[128];
    static void init(){
        base[0] = BigInteger.ONE;
        for (int i=1; i< 128; i++){
            base[i] = base[i-1].multiply(BigInteger.valueOf(2));
        }
    }
    public static void main(String args[]){
        init();
        Scanner cin = new Scanner(System.in);
        int m,n = cin.nextInt();
        int[] a = new int[128];
        int[] b = new int[128];
        while ((n--)!=0){
            m = cin.nextInt();
            for (int i=0; i< m; i++){
                a[i] = cin.nextInt();
                if (i!=0){
                    a[i] = a[i]^a[i-1];
                }
            }
            for (int i=0; i< m; i++){
                b[i] = cin.nextInt();
                if (i!=0){
                    b[i] = b[i]^b[i-1];
                }
            }
            BigInteger start = BigInteger.ZERO;
            BigInteger end = BigInteger.ZERO;
            for (int i=0; i< m; i++){
                if (a[m-i-1]!=0) start = start.add(base[i]);
                if (b[m-i-1]!=0) end = end.add(base[i]);
            }
            System.out.println(end.max(start).subtract(end.min(start)));
        }
    }
}

方法(2)

//* @author: 
/*
对于一个状态可认为它是从一个都没有的时候转化而来的,其步数为
第一个"1"处的权值 - 第2个"1"处的权值 + 第3个"1"处的权值 - 第4个"1"处的权值 +......(从左到右算)
     即第2*k+1个"1"时是加,第2*k个"1"是减,
而某一位的权值为2^(i+1)-1,(i从右到左,从0开始算)
      所以两种状态转化最小步数为两种状态步数差的绝对值,如:

s1     1   0    0    0
s2    0    1    1    0
权值:15   7    3    1

sum1=15

sum2=7-3=4

所以最终结果为|4-15|=11

    因为n< 128,所以要用高精度
*/




import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class cin
{
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int leave=0;
static int nextInt()throws IOException
{
   return Integer.parseInt(next());
}
static String nextLine()throws IOException
{
   return in.readLine();
}
static String next() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   leave--;
   return st.nextToken();
}
static boolean hasNext() throws IOException
{
   while(leave==0)
   {
    String temp=in.readLine();
    if(temp==null)return false;
    st=new StringTokenizer(temp);
    leave=st.countTokens();
   }
   return true;
}
}

class MyBigInt   //大整数类
{
    static int num,VALUE=1000000000;
    int data[];
    static void init(int n)
    {
    num=n;
    }
    
    MyBigInt(int x)
    {
    data=new int[num];
    Arrays.fill(data,0);
    data[num-1]=x%VALUE;
        data[num-2]=x/VALUE;
    }
    
    MyBigInt add(MyBigInt a) //+
    {
    int i,c=0,t;
    MyBigInt sum=new MyBigInt(0);
    for(i=num-1;i>=0;i--)
    {
       t=data[i]+a.data[i]+c;
       sum.data[i]=(t)%VALUE;
       c=t/VALUE;
    }
    return sum;
    }
    
    MyBigInt sub(MyBigInt a) //大数-小数
    {
    int i,c=0,t;
    MyBigInt s=new MyBigInt(0);
    for(i=num-1;i>=0;i--)
    {
       t=data[i]-a.data[i]+c;
       if(t< 0)
       {
        t+=VALUE;
        c=-1;
       }
       else c=0;
       s.data[i]=t;
    }
    return s;
    }
    
    boolean bigThan(MyBigInt a)
    {
    int i=0;
    for(i=0;i< num;i++)
    {
         if(data[i]>a.data[i])return true;
         else if(data[i]< a.data[i])return false;
    }
    return true;
    }
    
    void print()
    {
    int i;
    boolean ok=false;
    for(i=0;i< num;i++)
    {
       if(ok)
       {
        System.out.printf("%09d",data[i]);
       }
       else if(data[i]>0)
       {
        ok=true;
        System.out.print(data[i]);
        continue;
       }
    }
    if(!ok)System.out.print("0");
    }
}

class Answer
{
String s1,s2;
static MyBigInt v[];
static void init()
{
   MyBigInt.init(5);
   v=new MyBigInt[128];
   int i;
   v[0]=new MyBigInt(1);
   for(i=1;i< 128;i++)
   {
    v[i]=v[i-1].add(v[i-1]).add(v[0]);
//    v[i].print();
//    System.out.println();
   }
}

Answer(String a,String b)
{
   s1=a;
   s2=b;
}

void out()
{
   MyBigInt v1=valueOf(s1),v2=valueOf(s2);
//   v1.print();
//   v2.print();
   if(!v1.bigThan(v2))
   {
    v2.sub(v1).print();
   }
   else v1.sub(v2).print();
   System.out.println();
}

MyBigInt valueOf(String s)
{
   int i=0,k=s.length();
   MyBigInt value=new MyBigInt(0);
   while(i< s.length())
   {
    while(i< s.length()&&s.charAt(i)!='1')
    {
     i+=2;
    }
    if(i< s.length())value=value.add(v[(k-i)/2]);
    i+=2;
    while(i< s.length()&&s.charAt(i)!='1')
    {
     i+=2;
    }
    if(i< s.length())value=value.sub(v[(k-i)/2]);
    i+=2;
   }
   return value;
}
}

public class Main 
{
    public static void main(String args[]) throws IOException
    {
    int t;
    Answer.init();
    Answer data;
    t=cin.nextInt();
    while((t--)>0)
    {
       cin.nextInt();
       data=new Answer(cin.nextLine(),cin.nextLine());
       data.out();
    }
    }
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。