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

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

3.3 总结

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/274152.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

精密星历解析

总结一下用到的精密星历&#xff0c;区分一下&#xff1a; 精密星历与广播星历比较 1、精密星历比广播星历精度高&#xff0c;这一点大家都知道&#xff1b; 2、精密星历中给出的卫星的位置&#xff0c;是卫星质心&#xff0c;广播星历解算的是卫星的天线相位中心。 精密星历…

CTF题型 php反序列化进阶(1) php原生类 例题和总结

CTF题型 php反序列化进阶(1) php原生文件操作类 例题和总结 文章目录 CTF题型 php反序列化进阶(1) php原生文件操作类 例题和总结特征原理 我们可以通过PHP自身本来就有的类来进行文件操作扫描目录的三个类DirectoryIterator(支持glob://协议)FilesystemIterator&#xff08;继…

接口测试基础+requests库

接口测试基础requests库 接口测试基础URL格式协议IP地址端⼝号资源路径查询参数 练习HTTP请求请求行请求头请求体浏览者开发工具 Requests库Requests库安装和简介设置http请求语法应用案例py02_tpshop_search.pypy03_tpshop_login.pypy04_ihrm_login.py 接口测试基础 URL格式 …

【JAVA快速编写UI】 Java 编写一个编码转换和加解密工具,可以创建一个简单的 GUI 应用程序(例子)

EncodingDecodingTool/ ├── src/ │ ├── main/ │ │ ├── java/ │ │ │ └── com/ │ │ │ └── rockmelodies/ │ │ │ └── encodingdecodingtool/ │ │ │ ├── MainApp.java │ │ │ …

力扣大厂热门面试算法题 43-45

43. 字符串相乘&#xff0c;44. 通配符匹配&#xff0c;45. 跳跃游戏 II&#xff0c;每题做详细思路梳理&#xff0c;配套Python&Java双语代码&#xff0c; 2024.03.18 可通过leetcode所有测试用例。 目录 43. 字符串相乘 解题思路 完整代码 Python Java 44. 通配符…

企企通:AI技术赋能供应链智能化升级,打造数字产业集群

2024年全国两会期间&#xff0c;政府工作报告中首次提出开展“人工智能”行动&#xff0c;深化大数据、人工智能等技术的研发应用&#xff0c;打造具有国际竞争力的数字产业集群。 图源&#xff1a;中国政府网 近年来&#xff0c;人工智能发展呈现加速态势&#xff0c;技术迭代…

基于java的宠物信息交流平台设计(含源文件)

随着世界经济信息化、全球化的到来和互联网的飞速发展&#xff0c;推动了各行业的改革。若想达到安全&#xff0c;快捷的目的&#xff0c;就需要拥有信息化的组织和管理模式&#xff0c;建立一套合理、动态的、交互友好的、高效的“多鱼”旧物交易平台。当前的信息管理存在工作…

json-server库的使用,实现数据模拟

项目目录 安装 npm i -g json-server0.17.4 启动单个json服务&#xff0c;在cookbook目录下执行命令&#xff1a; json-server ./mock/a.json -p 9000 待实现 使用0.17.4版本即可。

Spring Security的开发

文章目录 1,介绍2, 核心流程3, 核心原理3.1 过滤器链机制3.2 主体3.3 认证3.4 授权3.5 流程图4, 核心对象4.1 UserDetailsService 接口4.2 PasswordEncoder 接口4.3 hasAuthority方法4.4 hasAnyAuthority方法4.5 hasRole方法4.5 hasAnyRole方法5, 核心注解5.1 @PreAuthorize5.1…

Python-GEE绘制DEM精美图片

目录 上传矢量和DEM获取添加颜色条参考文章 先连接上GEE的自己的项目 import ee import geemap geemap.set_proxy(port33210) ee.Authenticate() ee.Initialize(projecta-flyllf0313)上传矢量和DEM获取 使用Google Earth Engine&#xff08;GEE&#xff09;和Google Earth Eng…

iOS图片占内存大小与什么有关?

1. 问&#xff1a;一张图片所占内存大小跟什么有关&#xff1f; 图片所占内存大小&#xff0c;与图片的宽高有关 我们平时看到的png、jpg、webp这些图片格式&#xff0c;其实都是图片压缩格式。通过对应的算法来优化了大小以节省网络传输与本地保存所需的资源。 但是当我们加…

OSPF特殊区域(stub\nssa)

stub区域——只有1类、2类、3类&#xff1b;完全stub区域——只有1类、2类 NSSA区域&#xff1a;本区域将自己引入的外部路由发布给其他区域&#xff0c;但不需要接收其他区域的路由 在NSSA区域的路由器上&#xff0c;引入外部路由时&#xff0c;不会转换成5类LSA&#xff0c…

电商数据采集效率开挂【Python电商数据采集API接口】

数据监测 监测线上电商平台的商品、店铺数据&#xff0c;包括商品销量/库存/价格/店铺等级/发货地/促销活动等信息&#xff0c;支持十多个国内主流电商平台。 在线维权 实现多平台在线一键投诉&#xff0c;与各大电商投诉平台系统对接&#xff0c;实时同步投诉进展。 渠道管…

Jenkins实现CICD(3)_Jenkins连接到git

文章目录 1、如何完成上述操作&#xff0c;并且不报如下错&#xff1a;2、连接不上git&#xff0c;操作如下&#xff1a;3、将上边产生的3个文件拷贝到&#xff1a;C:\Windows\System32\config\systemprofile\.ssh4、新建下图凭证&#xff1a;创建步骤&#xff1a; 5、公钥填到…

AIGC元年大模型发展现状手册

零、AIGC大模型概览 AIGC大模型在人工智能领域取得了重大突破&#xff0c;涵盖了LLM大模型、多模态大模型、图像生成大模型以及视频生成大模型等四种类型。这些模型不仅拓宽了人工智能的应用范围&#xff0c;也提升了其处理复杂任务的能力。a.) LLM大模型通过深度学习和自然语…

Java 环境一键部署

文章目录 一、场景说明二、脚本职责三、参数说明四、操作示例五、注意事项 一、场景说明 本自动化脚本旨在为提高研发、测试、运维快速部署应用环境而编写。 脚本遵循拿来即用的原则快速完成 CentOS 系统各应用环境部署工作。 统一研发、测试、生产环境的部署模式、部署结构、…

香港科技大学广州|智能制造学域博士招生宣讲会—同济大学专场

时间&#xff1a;2024年3月28日&#xff08;星期四&#xff09;10:00 地点&#xff1a;同济大学嘉定校区济人楼310 报名链接&#xff1a;https://www.wjx.top/vm/mmukLPC.aspx# 宣讲嘉宾&#xff1a;崔华晨 助理教授 跨学科重点研究领域 •工业4.0 •智能传感器、自动光学检…

基于单片机的模糊PID炉温控制系统设计

摘 要 电热炉是在工业热处理的生产中广泛使用的一种设备&#xff0c;电热炉的温度控制系统存在时变性&#xff0c;非线性&#xff0c;滞后性等特征&#xff0c;难以用常规PID的控制器对系统达到很好的控制效果。当控温精度的要求高时&#xff0c;使用传统的控制理论方法难以达…

海外代理IP在跨境电商中的五大应用场景

在我国跨境电商的发展中&#xff0c;海外代理IP的应用日益广泛&#xff0c;它不仅帮助商家成功打入国际市场&#xff0c;还为他们在多变的全球电商竞争中保持优势。下面是海外代理IP在跨境电商中五个关键的应用场景。 1、精准的市场分析 了解目标市场的消费者行为、产品趋势以…
最新文章