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

1. 题目

 

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

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

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

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

输入

第一行，分别输入三个数n，c，b（2<=n<=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;
}

3.3 总结

还是那句话，当你的代码需要考虑特殊输入情况时，你就要想办法改改它了，尽管它看起来万无一失。