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:终于AC了,采用跳跃式编码方式的同学看这里~~

Posted by zhrq at 2018-02-05 09:17:16 on Problem 1009
In Reply To:终于AC了,采用跳跃式编码方式的同学看这里~~ Posted by:heroskaka at 2015-03-26 15:40:25
> 拿到这个题目,第一反应是暴力,发现像素个数太大。。。然后发现只有前面2行和最后两行才有变化,其他都是0,结果宽度也有可能很大。。。最后看了看大神的算法,采用跳跃式编码,就是说只在像素发生变化的位置进行编码,而像素没有变化的位置则其编码值与其左边的像素一致。仔细想一想,还是很好明白的,但是证明的话就。。。。采用这个方法,也有需要注意的地方。
> 1.在变化的点及周围8个点编码,第一个位置和最后一个位置也需要编码。
> 2.变化点及周围8个点,如果超出了第一个和最后一个范围可以忽略,但是超出了边界,右边超出的往下放,左边超出往上放,最后都是需要编码的。
> 最后附上代码~搞了2个晚上。。。WA了好几次。。。真不容易。。。
> import java.util.ArrayList;
> import java.util.List;
> import java.util.Scanner;
> 
> public class Main {
> 	
> 	public static void main(String[] args) {
> 		Scanner cin = new Scanner(System.in);
> 		List<String> output = new ArrayList<String>();
> 		String width = cin.nextLine();//获得列数
> 		while(!width.equals("0")){
> 			output.add(width);//别忘了把列数加入到输出中
> 			int wid = Integer.parseInt(width);
> 			String p = cin.nextLine();
> 			int[][] in = new int[2][1000];
> 			int pair = 0;
> 			int totalPixel = 0;
> 			while(!p.equals("0 0")){
> 				int pixel = Integer.parseInt(p.split(" ")[0]);//像素
> 				int number = Integer.parseInt(p.split(" ")[1]);//像素个数
> 				in[0][pair] = pixel;
> 				in[1][pair] = number;
> 				pair++;
> 				totalPixel += number;
> 				p = cin.nextLine();
> 			}
> 			int pos = 1;//标识当前的位置
> 			List<int[]> outputTemp = new ArrayList<int[]>();
> 			//这个地方要注意,起始点和终止点都需要进行编码
> 			for(int i=0;i<=pair;i++){
> 				//当前位置所处的行列
> 				int row = (pos-1)/wid;
> 				int col = (pos-1)%wid;
> 				for(int j=row-1;j<=row+1;j++){
> 					for(int k=col-1;k<=col+1;k++){
> 						int tempPos = j*wid + k + 1;
> 						//这个地方要注意,变化点及周围8个点,超出了也要编码
> 						if(tempPos < 1 || tempPos>totalPixel ){
> 							continue;
> 						}
> 						//获得转化后的像素值
> 						int[] temp = new int[]{tempPos,getMaxPixel(tempPos,in,wid,totalPixel)};
> 						outputTemp.add(temp);
> 					}
> 				}
> 				if(i < pair){
> 					pos += in[1][i];
> 				}
> 			}
> 			//快排,不多说
> 			quickSort(outputTemp);
> 			int temp = 0;
> 			//对临时数据进行合并
> 			for(int i=0;i<outputTemp.size();i++){
> 				if(outputTemp.get(temp)[1] == outputTemp.get(i)[1]){
> 					continue;
> 				}
> 				output.add(outputTemp.get(temp)[1]+" "+
> 						(outputTemp.get(i)[0] - outputTemp.get(temp)[0]));
> 				temp = i;
> 			}
> 			output.add(outputTemp.get(temp)[1]+" "+
> 					(totalPixel - outputTemp.get(temp)[0]+1));
> 			output.add("0 0");
> 			width = cin.nextLine();
> 		}
> 		output.add("0");
> 		cin.close();
> 		for(int i=0;i<output.size();i++){
> 			System.out.println(output.get(i));
> 		}
> 	}
> 	
> 	public static void quickSort(List<int[]> data){
> 		int length = data.size();
> 		quickSortRecursion(data,0,length-1);
> 	}
> 	//快排的递归
> 	public static void quickSortRecursion(List<int[]> data,int low,int high){
> 		if(low < high){
> 			int tempPos = data.get(low)[0];//基准数
> 			int tempPixel = data.get(low)[1];
> 			int i=low;
> 			int j=high;
> 			while(i < j){
> 				while(i < j && data.get(j)[0]
> 						>= tempPos){//先从右边开始,找到第一个比基准数小的
> 					j--;
> 				}
> 				data.set(i, data.get(j));//交换位置
> 				while(i < j && data.get(i)[0]
> 						<= tempPos){//再从左边开始,找到第一个比基准数大的
> 					i++;
> 				}
> 				data.set(j, data.get(i));//交换位置
> 			}//依次循环,直到基准数左边都比它小,右边都比它大
> 			data.set(i, new int[]{tempPos,tempPixel});
> 			quickSortRecursion(data,low,i-1);
> 			quickSortRecursion(data,i+1,high);
> 		}
> 	}
> 
> 	public static int getMaxPixel(int pos,int[][] in,int wid,int totalPixel){
> 		int pixel = getPixelByPos(pos,in);
> 		int maxPixel = 0;
> 		
> 		int row = (pos-1)/wid;
> 		int col = (pos-1)%wid;
> 		for(int i=row-1;i<=row+1;i++){
> 			for(int j=col-1;j<=col+1;j++){
> 				int tempPos = i*wid + j + 1;
> 				if(i<0 || j<0 || j>=wid || tempPos>totalPixel || 
> 						tempPos == pos){
> 					continue;
> 				}
> 				int tempPixel = getPixelByPos(tempPos,in);
> 				if(maxPixel < Math.abs(tempPixel-pixel)){
> 					maxPixel = Math.abs(tempPixel-pixel);
> 				}
> 			}
> 		}
> 		return maxPixel;
> 	}
> 	
> 	public static int getPixelByPos(int pos,int[][] in){
> 		int i=0,j=0;
> 		while(i < pos){
> 			i += in[1][j++];
> 		}
> 		return in[0][j-1];
> 	}
> }

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