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

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

### 输入输出样例

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。

#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;
}