当前位置：首页 > article >正文

电子科技大学链时代工作室招新题C语言部分---题号G

article 2024/12/26 20:31:56

1. 题目

问题的第一段也是非常逆天，说实话，你编不出问题背景可以不编。

这道题的大概意思就是， Pia要去坐飞机，那么行李就有限重。这时Pia想到自己带了个硬盘，众所周知，硬盘上存储的数据就是0和1的二进制序列。

对于一段二进制序列，每有一个从0到1的过渡，或是从1到0的过渡（也就是每有一个0和1的分界），就会导致硬盘的重量轻微增加一点，为了不超重，Pia就需要修改一下硬盘上存储的数据。

然而硬盘上的某些位置是坏掉的，坏掉的位置只能存入0，其中，第一个位置永远是好的，最后一个位置永远是坏的。

输入

第一行，分别输入三个数n，c，b（2<=n<=5. $10^{5}$ ，1<=c,b<=n-1）。

n表示二进制序列的长度，c表示所需分界位置的数量，b表示损坏位置的个数。

第二行输入损坏位置的位置信息。

输出

输出符合条件的二进制序列。

2. 第一版解法

2.1 思路

1. 首先我们肯定需要依据n开辟一个数组，但接下来我们就有两种选择，将数组元素全部初始化为0或全部初始化为1。

2. 如果我们将数组全部初始化为0，那么我们在将某个元素改为1时，需要先检查其是否为损坏的位置，每次都需要遍历储存位置信息的数组。

3. 如果我们将数组初全部始化为1，那么我们只需要在初始化结束之后把损坏的位置改为0即可，并在之后的过程中，确保只将1改为0，而不将0改为1。

4. 第一个位置始终是好的，最后一个位置始终是坏的。这个条件对边界上的位置进行了限制，边界上的位置有什么特殊的吗？

我们发现，边界上出现1，最多只会导致1次变化，而中间位置上出现1（不与边界1相连），一定会导致2次变化。

所以，如果题上要求的变化次数为奇数，那么一号位一定是1；如果题上要求的变化次数为偶数，则一号位上一定不是1。

add原本指向数组开头，这里将与一号位相连的1都抛开不看了(有问题，下一版会该)

if(c%2 == 0)
{
    bit[0] = '0';
}
else
{
    bit[0] = '1';
    c--;//所需减一
    while(*(++add) == '1');
}

5. 在将一号位调整好之后就可以先将其抛开不看了，将add当作数组开头进行进一步调整。

6. 接下来我们的做法是记录每一段1的起始与结束位置，如果当前发生字节改变的位置比要求的少，那么就将某一段1分割为两段，中间用0隔开；如果当前发生字节改变的位置比要求的多，那么就将某一段1全部置为0。

2.2 代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct posi
{
    char* start;
    char* end;
}posi;

int main()
{
    int n = 0, c = 0, b = 0, count = 0;//硬盘大小，所需字节改变处数量，受损坏字节数量，1的段数
    char sep[] = {'0'};
    scanf("%d %d %d", &n, &c, &b);
    char* bit = (char*)malloc(sizeof(char) * (n + 1));//存结果
    bit[n] = '\0';
    bit[n-1] = '0';
    char* add = bit;
    for(int i = 0; i < n - 1; i++)
    {
        bit[i] = '1';
    }
    int* Bre = (int*)malloc(sizeof(int) * b);//损坏字节的位置
    for(int i = 0; i < b; i++)
    {
        scanf("%d", &Bre[i]);
        bit[Bre[i]-1] = '0';
    }
    if(c%2 == 0)
    {
        bit[0] = '0';
    }
    else
    {
        bit[0] = '1';
        c--;//所需减一
        while(*(++add) == '1');
    }
    posi* ret = (posi*)malloc(sizeof(posi) * n / 2);
    for(ret[count].start = strtok(add, sep); ret[count].start != NULL; ret[++count].start = strtok(NULL, sep))//记录每段1的起始和结束位置
    {
        char* tmp = ret[count].start;
        while(*tmp != '\0'){tmp++;}
        ret[count].end = tmp - 1;
    }
    int i = 0;
    if(count == 0)
    {
        if(add >= bite + 3&&2 * count != c)//1111110
        {
            bit[1] = '0';
            ret[count].start = bite + 2;
            ret[count].end = add - 1;
            count++;
        }
        else//10000000
        {
            printf("%s\n", bit);
    
            free(bit);free(Bre);free(ret);
    
            return 0;
        }
    }
    while(2 * count < c&&i < n / 2)//改变的少了
    {
        if(ret[i].end - ret[i].start >= 2)
        {
            *(ret[i].start + 1) = '0';
            ret[count].start = ret[i].start + 2;
            ret[count].end = ret[i].end;
            count++;
            ret[i].end = ret[i].start + 1;
        }
        else
        {
            i++;
        }
    }
    
    while(2 * count > c&&i < n / 2)//改变的多了
    {
        while(ret[i].start <= ret[i].end)
        {
            *(ret[i].start++) = '0';
            *(ret[i].end--) = '0';
        }
        i++;
        count--;
    }

    for(int j = 0; j < n; j++)
    {
        if(bit[j] == '\0')
        bit[j] = '0';
    }
    printf("%s\n", bite);
    
    free(bit);free(Bre);free(ret);
    
    return 0;
}

2.3 总结

这一段代码的问题就在于add那里，将开头连续的1一并忽视掉。

这就会导致需要单独处理一开始就只有开头连续1的情况，我们已经说过，当你开始考虑特殊情况时，你就已经输了一半。

不止如此，这还会导致我们能产生的最多字节变化的数量减少，因为开头的连续1也可以断开产生更多变化字节。

3. 最终版解法

3.1 思路

这一版就将add给删除了，当b为奇数时，将一号位置为1，然后直接将二号位置为0。

这样做就可以达到目的了，而且无需考虑特殊情况，可以说add这个变量简直是画蛇添足。

3.2 代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct posi
{
    char* start;
    char* end;
}posi;

int main()
{
    int n = 0, c = 0, b = 0, count = 0;//硬盘大小，所需字节改变处数量，受损坏字节数量，1的段数
    char sep[] = {'0'};
    scanf("%d %d %d", &n, &c, &b);
    char* bit = (char*)malloc(sizeof(char) * (n + 1));//存结果
    bit[n] = '\0';
    bit[n-1] = '0';
    for(int i = 0; i < n - 1; i++)
    {
        bit[i] = '1';
    }
    int* Bre = (int*)malloc(sizeof(int) * b);//损坏字节的位置
    for(int i = 0; i < b; i++)
    {
        scanf("%d", &Bre[i]);
        bit[Bre[i]-1] = '0';
    }
    if(c%2 == 0)
    {
        bit[0] = '0';
    }
    else
    {
        bit[0] = '1';
        bit[1] = '0';
        c--;//所需减一
    }
    posi* ret = (posi*)malloc(sizeof(posi) * n / 2);
    for(ret[count].start = strtok(bite + 1, sep); ret[count].start != NULL; ret[++count].start = strtok(NULL, sep))//记录每段1的起始和结束位置
    {
        char* tmp = ret[count].start;
        while(*tmp != '\0'){tmp++;}
        ret[count].end = tmp - 1;
    }
    int i = 0;
    
    while(2 * count < c&&i < n / 2)//改变的少了
    {
        if(ret[i].end - ret[i].start >= 2)
        {
            *(ret[i].start + 1) = '0';
            ret[count].start = ret[i].start + 2;
            ret[count].end = ret[i].end;
            count++;
            ret[i].end = ret[i].start + 1;
        }
        else
        {
            i++;
        }
    }
    
    while(2 * count > c&&i < n / 2)//改变的多了
    {
        while(ret[i].start <= ret[i].end)
        {
            *(ret[i].start++) = '0';
            *(ret[i].end--) = '0';
        }
        i++;
        count--;
    }

    for(int j = 0; j < n; j++)
    {
        if(bit[j] == '\0')
        bit[j] = '0';
    }
    printf("%s\n", bit);
    
    free(bit);free(Bre);free(ret);
    
    return 0;
}