首页 > 其他分享 >CSP-J 2020 普及组讲解

CSP-J 2020 普及组讲解

时间:2023-05-31 15:55:14浏览次数:37  
标签:分数 剪枝 复杂度 2020 讲解 100 CSP

CSP-J 2020

T1 优秀的拆分

题目的本质是求 \(n\) 的二进制表示。求 \(n\) 的二进制表示,或者每次暴力分解出小于等于 \(n\) 的最大的 \(2\) 的正整数次幂。时间复杂度 \(O(\log {n})\)。

T2 直播获奖

给定 \(n\) 个人的分数,对于每个 \(i\),请你求出前 \(i\) 个人的第 \(k = \max (1, \lfloor p * w \% \rfloor)\) 大的分数。

求排名时避免使用浮点数运算。

50 分

对于前 \(i\) 个人的分数,暴力模拟。

时间复杂度 \(O(n^2 \log n)\)。

85 分

每次只新增一个人的成绩,用插入排序维护。

时间复杂度 \(O(n^2)\)。

100 分

分数最大为 \(600\),用桶排序求第 \(k\) 大分数。

时间复杂度 \(O(600 * n)\)。

考场造测试数据

T3 表达式

20 分

特殊考虑全为 & 或者 | 的情况,暴力模拟。

50 分

在 \(20\) 分的基础之上,模拟后缀表达式计算。

时间复杂度 \(O(q * n)\)。

100 分

T4 方格取数

25 分

暴搜。

35 分

考虑使用最优性剪枝,令 \(f[i][j]\) 表示到 \((i, j)\) 的最大得分,如果走到 \((i, j)\) 时得分不优于 \(f[i][j]\) 就不用搜下去。尝试后发现这样的局部剪枝是错误的。

这里忽略了一个问题,向上、向下、向右走到 \((i, j)\) 时,后续能够走的路径是不相同的。应该将其定义为 \(f[i][j][0], f[i][j][1], f[i][j][2]\) 表示向下、向右、向上走到 \((i, j)\) 时的最大得分,再做剪枝。

100 分

只能向右走,状态转移图存在拓扑序(所有状态朝着一个“方向”进行转移),满足无后效性。

又由于从某个方向到达某个格子的分数肯定越大越好,存在最优子结构。

因此分析得到本题的正解为动态规划,考虑使用记忆化搜索求解。

状态数 \(3 * n * m\),每个状态最多做三个方向转移,因此总时间复杂度 \(3 * n * m * 3 = O(n * m)\)。

标签:分数,剪枝,复杂度,2020,讲解,100,CSP
From: https://www.cnblogs.com/xhr0817-blog/p/17446388.html

相关文章

  • Blazor HyBrid 授权讲解
    BlazorHyBrid授权讲解本文介绍ASP.NETCore对BlazorHybrid应用中的安全配置和管理及ASP.NETCoreIdentity的支持。BlazorHybrid应用中的身份验证由本机平台库处理,因为后者提供了浏览器沙盒无法给予的经过增强的安全保证。本机应用的身份验证使用特定于操作系统的机......
  • git pull 和push讲解:016
    pull和push大致流程:(将远程仓库同步到本地仓库)>(在本地仓库修改并提交)>(推送修改内容到远程仓库) 1.首先创建一个文件夹,打开GitBash终端,cd到这个文件夹内 2.将(远程仓库)的克隆到这个文件夹内:gitclone远程仓库连接 3.打开终端,然后cd进入项目文件 4.然后建立与(......
  • Spring之状态机讲解
    目录1状态机1.1什么是状态1.2四大概念1.3状态机1.4springstatemachine2示例Demo2.1订单状态图2.2建表2.3依赖和配置2.3.1pom.xml2.3.2application.yml2.4状态机配置2.4.1定义状态机状态和事件2.4.2定义状态机规则2.4.3配置持久化2.4.3.1持久化到内存2.4.3.2持久......
  • 保姆级讲解,让ChatGPT成为机器人的智慧大脑
    ChatGPT是生成式人工智能,如果能接入机器人,可以让机器人更加智能。 我手上没有硬件,但我们可以模拟尝试机器人的制作逻辑,这个设计分成两部分:硬件、软件。 一、硬件:机器人 1.机器人可以听取人类的对话 2.机器人要接入ChatGPT 3.机器人可以根据ChatGPT的指示做出响......
  • 【2023 · CANN训练营第一季】应用开发深入讲解之AIPP
    应用开发深入讲解之AIPPAIPP(ArtificialIntelligencePre-Processing)人工智能预处理,在AlCore上完成数据预处理。动态&静态AIPP分为静态AIPP和动态AIPP两种,对比如下:2.抠图&填充AIPP改变图片尺寸需要遵守如下图中的顺序,即先Crop再Padding,每个操作仅能执行一次。3.色域转换在执行R......
  • 【2023 · CANN训练营第一季】应用开发深入讲解之模型转换工具
    应用开发深入讲解之模型转换工具1.基本概念昇腾张量编译器(AscendTensorCompiler,简称ATC)是异构计算架构CANN体系下的模型转换工具,它可以将开源框架的网络模型或AscendIR定义的单算子描述文件(json格式)转换为昇腾AI处理器支持的.om格式离线模型。模型转换过程中,ATC会进行算子调度......
  • 【2023 · CANN训练营第一季】应用开发深入讲解之模型离线推理
    应用开发深入讲解之模型离线推理模型离线推理是指使用已经转好的om模型对输入图片进行推理,主要步骤如下图所示:1.Host&Device内存管理与数据传输Host&Device上的内存申请与释放,内存间的相互拷贝。代码中加载输入数据时,需要申请Host内存进行存储,当输入数据处理完毕后,需要将处理完成的......
  • 【2023 · CANN训练营第一季】应用开发深入讲解之DVPP
    应用开发深入讲解之DVPP1.基本概念昇腾Al处理器内置图像处理单元DVPP(DigitalVideoPre-Processor),提供强大的媒体处理硬加速能力。主要功能模块有:2.常见接口a.内存申请与释放b.通道创建与释放c.图片描述信息创建与销毁d.图片描述参数设置3.JPEGD图片解码4.VPC视觉预处理......
  • 计算机操作系统中实现进程间同步的信号量概念讲解
    在计算机操作系统中,信号量(Semaphore)是一种用于实现进程间同步和互斥的机制。信号量提供了两个基本操作:P(Proberen)和V(Verhogen),它们在进程间进行同步操作。P(Proberen)操作:P操作也被称为"申请"操作或"阻塞"操作。当一个进程执行P操作时,它试图申请一个信号量。如果该信号量的值大于0,......
  • 卡尔曼滤波的讲解
    https://www.zhihu.com/question/23971601    ......