首页 > 试题广场 >

魔力手环

[编程题]魔力手环

热度指数：5031 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。

输入描述:

输入数据包括两行： 第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔 第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.

输出描述:

输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。

示例1

输入

3 2 1 2 3

输出

8 9 7

算法知识视频讲解

Java

朱大葱

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            long[] array = new long[n];
            for (int i = 0; i <n ; i++) {
                array[i] = scanner.nextInt();
            }
            for (int i = 0; i < k ; i++) {
                long temp =array[0];
                for (int j = 0; j < n; j++) {
                    if (array[j]>=100){
                        array[j]%=100;
                    }

                    if(j==n-1){
                        array[j] = (array[j]+temp%100)%100;
                    }else{
                        array[j] = (array[j]+array[(j+1)%n]%100)%100;
                    }
                }
            }
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i]);
                if (i!=array.length-1){
                    System.out.print(" ");
                }
            }
        }
    }
}
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%
尴尬!!!

发表于 2017-08-02 14:57:04 回复(0)

Java

YiBuLZ

import java.util.Scanner;
//请见http://blog.csdn.net/zheng548/article/details/71075163

public class Main {
    /**
     * 利用矩阵快速幂
     参考：http://www.cnblogs.com/vongang/archive/2012/04/01/2429015.html
     http://www.lai18.com/content/1108003.html?from=cancel
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        //用一个二维数组存储
        int[][] arr= new int[1][n];
        for (int i = 0; i < n; i ++) {
            arr[0][i] = sc.nextInt();
        }
        //初始化单元矩阵
        int[][] mul = new int[n][n];
        for (int i = 0; i < n; i ++) {
                if (i < n - 1) {
                    mul[i][i] = 1;
                    mul[i + 1][i] = 1;
                } else {
                    mul[i][i] = 1;
                    mul[0][i] = 1;
                }
        }

        for (; k > 0; k >>= 1) {
           if ((k & 1) == 1) {
               arr = Core(arr, mul);
           }
           mul = Core(mul, mul);
        }
        int i;
        for (i = 0; i < n - 1; i ++) {
            System.out.print(arr[0][i] + " ");
        }
        System.out.println(arr[0][i]);
    }

    private static int[][] Core(int[][] a, int[][] b) {
        int rowRes = a.length;
        int columnRes = b[0].length; //TODO:
        int columnA = a[0].length; // == b.length;

        int[][] c = new int[rowRes][columnRes];
        for (int i =0; i < rowRes; i ++) {
            for (int j = 0; j < columnRes; j ++) {

                for (int k = 0; k < columnA; k ++) {
                    if (a[i][k] == 0 || b[k][j] == 0) {
                        continue;          //剪枝
                    }

                    c[i][j] += a[i][k] * b[k][j];
                }
                //100取余运算
                if (c[i][j] >= 100) {
                    c[i][j] %= 100;
                }
            }
        }
        return c;
    }

}

编辑于 2017-05-01 20:52:32 回复(3)

Java

旭>_

贴一个java的

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	// 矩阵乘法加对100取余
	private static int[][] mutAndMod(int[][] a,int[][] b){
		int n1 = a.length;
		int n2 = a[0].length;
		int[][] ret = new int[n1][n2];
		for(int i=0;i<n1;i++){
			for(int j=0;j<n2;j++){
				int temp = 0;
				for(int k=0;k<n2;k++){
					temp += a[i][k] * b[k][j];
				}
				ret[i][j] = temp%100;
			}
		}
		return ret;
		
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int k = sc.nextInt();
			int[][] band = new int[1][n];
			for(int i=0;i<n;i++){
				band[0][i] = sc.nextInt();
			}
			int[][] src = new int[n][n];
			for(int i=0;i<n;i++){
				if(i+1<n){
					src[i][i] = 1;
					src[i+1][i] = 1;
				}else{
					src[i][i] = 1;
					src[0][i] = 1;
				}
			}
            // 结果
			int[][] ans = new int[1][n];
			for(int i=0;i<n;i++){
				ans[0][i] = band[0][i];
			}
            /*
			for(int i=0;i<n;i++){
				System.out.println(Arrays.toString(src[i]));
			}
			*/
			while(k>0){
				if(k%2==1){
					ans = mutAndMod(ans,src);
				}
				//System.out.println(Arrays.toString(ans[0]));
				src =  mutAndMod(src,src);
				k >>=1;
				
			}	
            System.out.print(ans[0][0]);
            for(int i=1;i<n;i++){
                System.out.print(" " + ans[0][i]);
            }
            System.out.println();
			
		}
		sc.close();
	}
	
}

发表于 2017-03-28 17:41:48 回复(3)