洛谷P2556 [AHOI2002]黑白图像压缩(Luogu p2556 [ahoi2002] black and white image compression)

题目描述

选修基础生物基因学的时候, 小可可在家里做了一次图像学试验。 她知道:整个图像其实就是若干个图像点(称作像素)的序列,假定序列中像素的个数总是 8 的倍数, 于是每八个像素可以转换成一个叫做字节的数, 从而这个表示图像的像素序列就被转换成了字节的序列。

所谓的字节就是一个八位的二进制数(当然,为了便于书写,人们经常用它的十进制形式来表示)。这八个像素从前向后依次对应于字节从高位到低位的八个位, 用 0 来表示白色像素、 1 来表示黑色像素。 这种表示方法叫做位图法。 例如字节序列 210、 0、255 表示了 8*3=24 个像素, 由于对应的二进制形式是 11010010、 00000000、11111111, 所以这 24 个像素的颜色依次是黑、 黑、 白、 黑、 白、 白、 黑、 白、白、白、白、白、白、白、白、白、黑、黑、黑、黑、黑、黑、黑、黑。

小可可想: 其实图像中存在着很多连续的同色像素段, 也许换一种方式表达图像能够减少图像的数据量。 她的思路是: 把像素按照颜色分成若干个片段, 同一个片段中各像素颜色相同, 且连续的同色像素都在同一个片段中。同时已知每个片段的最大长度小于 128。

每一个像素片段都是用一个二进制字节量来表示, 最高位表示片段中像素的颜色, 而低七位表示片段中像素的数目。注意:不存在长度为 0 的像素片段。这种表示法叫做像素片段法。

例如位图表示法的字节序列 210、 0、 255 对应的像素序列可以分成七个片段,分别是: 11、 0、 1、 00、 1、 000000000、 11111111。如果用像素片段法来表示的话,二进制字节序列应该写成 10000010、 00000001、 10000001、00000010、 10000001、 00001001、 10001000, 而其对应于十进制字节序列就是 130、 1、 129、 2、 129、 9、 136。

像素片段法是否能有效地减少图像的数据存储量呢?小可可不知道如何用数学的方法加以证明, 于是决心对手头上的图像做些试验, 看看该方法是否真的有效。 请你编写程序完成图像信息的转换, 以协助小可可完成这项试验。

输入格式

文件中以一行的形式存放了一个图像的信息。第一个数是正整数 nn ,表明该图像有 nn 个像素。随后有 \frac{n}{8}8n 个十进制形式的字节量,表示该图像的位图信息。相邻数之间用一个空白字符隔开。

输出格式

以一行的形式输出以像素片段表示法表示的图像信息,各个数都以

十进制的形式出现,相邻数之间用一个空白字符隔开。

输入输出样例

8 0
8
24 210 0 255
130 1 129 2 129 9 136

说明/提示

1\leq n\leq 8\times 10^41≤n≤8×104。

采用读一个数,处理一个数的方法,先把十进制数化为二进制数逆序存放在一个数组里,然后再判断相邻的数字是否相同,相同则继续,反之则根据像素来算出其对应的十进制数,如果像素是 1 ,则最后在 finally 上加 128 ,如果是 0 ,则不用。然后把得出的数放在 OUT 数组中,最后打印出 OUT 数组即可。其中定义了一个 F 变量,主要是在判断是 0 像素,还是 1 像素。

总结: 做这个题目时,没能考虑到一个数全为 0 ,或者一个数二进制的最后一位为 1 ,而下一个数的二进制第一位为 0 的情况。

#include<cstdio>
int a[80000],b[80000];
int main()
{
  int n,k=0,lab=1;
  scanf("%d",&n);
    n/=8;
  for (int i=0;i<n;i++) scanf("%d",&a[i]);
  for (int i=0;i<n;i++)
    for (int j=7;j>=0;j--)
    {
      k=i*8+j;
      b[k]=a[i]%2;
      a[i]/=2;
     }
    int i;
  for (i=1;i<n*8;i++)
    if (b[i]!=b[i-1])
    {
      if (b[i-1]==1) printf("%d ",lab+128); else printf("%d ",lab);
      lab=1;
    }
      else lab++;
  if (b[i-1]==1) printf("%d \n",lab+128); else printf("%d \n",lab);
  return 0;
}
————————

Title Description

When taking basic biogenesis as an elective course, Xiao Keke did an iconography experiment at home. She knows that the whole image is actually a sequence of several image points (called pixels). Assuming that the number of pixels in the sequence is always a multiple of 8, every eight pixels can be converted into a number called bytes, so the pixel sequence representing the image is converted into a sequence of bytes.

The so-called byte is an eight bit binary number (of course, people often use its decimal form for ease of writing). The eight pixels correspond to the eight bits of the byte from high to low from front to back. 0 is used to represent white pixels and 1 is used to represent black pixels. This representation is called bitmap method. For example, byte sequences 210, 0 and 255 represent 8 * 3 = 24 pixels. Since the corresponding binary forms are 11010010, 00000000 and 11111111, the colors of these 24 pixels are black, black, white, black, white, white, white, white, white, white, white, black, black, black, black, black, black, black, black and black.

Xiaokeke: in fact, there are many continuous pixels of the same color in the image. Maybe another way to express the image can reduce the amount of image data. Her idea is to divide the pixels into several segments according to their colors. Each pixel in the same segment has the same color, and the continuous pixels of the same color are in the same segment. At the same time, it is known that the maximum length of each fragment is less than 128.

Each pixel segment is represented by a binary byte. The highest bit represents the color of the pixels in the segment, while the lower seven bits represent the number of pixels in the segment. Note: there is no pixel segment with length 0. This representation is called pixel fragment method.

For example, the pixel sequence corresponding to byte sequences 210, 0 and 255 of bitmap representation can be divided into seven segments: 11, 0, 1, 00, 1, 000000000 and 11111111. If represented by pixel fragment method, the binary byte sequence should be written as 10000001, 00000001, 10000001, 00000010, 10000001, 00001001, 10001000, and its corresponding decimal byte sequence is 130, 1, 129, 2, 129, 9 and 136.

Can the pixel fragment method effectively reduce the amount of image data storage? Little cocoa didn’t know how to prove it mathematically, so she decided to experiment with the image on her opponent’s head to see if the method was really effective. Please write a program to complete the conversion of image information to assist xiaokeke in completing this experiment.

Input format

The information of an image is stored in one line in the file. The first number is a positive integer , NN, indicating that the image has , NN pixels. Then there are \ frac{n}{8}8n decimal bytes representing the bitmap information of the image. Adjacent numbers are separated by a blank character.

Output format

The image information expressed in pixel segment representation is output in the form of one line, and each number is expressed in

In decimal form, adjacent numbers are separated by a white space character.

Sample input and output

8 0
8
24 210 0 255
130 1 129 2 129 9 136

Description / tips

1\leq n\leq 8\times 10^41≤n≤8 × 104。

Using the method of reading a number and processing a number, first convert the decimal number into binary number and store it in an array in reverse order, and then judge whether the adjacent numbers are the same. If they are the same, continue. On the contrary, calculate the corresponding decimal number according to the pixel. If the pixel is ﹤ 1, finally add ﹤ 128 to ﹤ finally. If it is ﹤ 0, it is not needed. Then put the obtained number in the “out” array, and finally print out the “out” array. A , f , variable is defined, which is mainly used to judge whether it is , 0 , pixel or , 1 , pixel.

Conclusion: when doing this topic, we failed to take into account the situation that a number is all 0, or the last binary bit of a number is 1, and the first binary bit of the next number is 0.

#include<cstdio>
int a[80000],b[80000];
int main()
{
  int n,k=0,lab=1;
  scanf("%d",&n);
    n/=8;
  for (int i=0;i<n;i++) scanf("%d",&a[i]);
  for (int i=0;i<n;i++)
    for (int j=7;j>=0;j--)
    {
      k=i*8+j;
      b[k]=a[i]%2;
      a[i]/=2;
     }
    int i;
  for (i=1;i<n*8;i++)
    if (b[i]!=b[i-1])
    {
      if (b[i-1]==1) printf("%d ",lab+128); else printf("%d ",lab);
      lab=1;
    }
      else lab++;
  if (b[i-1]==1) printf("%d \n",lab+128); else printf("%d \n",lab);
  return 0;
}