2/12考试总结
时间安排
8:30–8:50 读题,T1 不知道是个啥,T2是个dp ,T3可能也是 dp 之类的。
8:50–9:30 T1,读了好几遍才理解了题意,对于部分分有爆搜。考虑正解,想到预处理后O(1) 查询,问题是如何由已知的信息得到所有可能询问的答案,想了几种 子集dp 之类的东西,都不太对。
9:30–10:20 T2,看了一眼发现有 70 分是送的。正解貌似可以前缀和优化一下什么的。仔细分析了一下发现不好维护,暴力前缀和预处理的话时间空间都不允许,尝试着化简式子看看能不能 O(1) 做,貌似做不了。
10:20–11:13 T3,分析题目可以找到一些性质,然后根据这个建图,部分分可以暴力在图上跑。考虑能不能推广,需要快速知道图上的信息,猜了好几个结论都是假的。
11:13–12:00 瞪T1,T3。
12:00–13:00 瞪T1 。
回顾反思
T1:
正解是 dfs 搜索,或者使用状压做类似过程,复杂度是 n2nn2^nn2n 的。
比赛时一开始读题理解题意耽误了一点时间。
题目中有 ∃∀\exist \forall∃∀ 两种逻辑运算,将 ∃\exist∃ 当做限制,问题是如何预处理出一个限制是否被满足。考场上,我局限于先以某种方式钦定一个限制,然后考虑在限制下的所有可能状态的解,那么这样复杂度就是枚举限制的复杂度与枚举状态复杂度的积,是不能通过的。但是实际上,根本不需要事先钦定某个限制,可以直接将限制的钦定融进状态的枚举中,考虑直接一位一位枚举状态,对于某一位,讨论是采取限制 1 还是限制 2 ,然后得到在此限制下下一位的合法状态,递归进入下一位。这样,递归进入某一位是,之前的所有位的信息都能被有效利用,而非再次搜索产生冗余。
这道题,我在最开始题意的理解上出现了一些偏差,绕了一些弯子;其次,我局限于钦定限制然后找状态,但是实际上可以枚举状态然后讨论限制,边枚举边做;再者,我对 dfs 的复杂度没有信心,没有仔细去计算 dfs的实际复杂度。
要认真分析复杂度,一般的 dfs 会有很多不必要的冗余,若能够做到最大化利用每一段递归公共的部分减少重复冗余操作,其复杂度会极大的降低。
T2:
思路基本和正解相同,考虑组产生的分界,但是角度又略有不同。正解主要考虑是 A 组先满还是 B 组先满,而我则是考虑在给定的 K 的关键点内 B 组是否满了。这两种角度对于部分分计算的复杂度是一样的,但是我涉及的组合数整体的分布不如正解的 “亲近” ,比较难以优化计算;其次,正解的式子几乎只涉及了值域为 n 的 i 以及种数为 n\sqrt nn 的 K,那么枚举 K 对 i 暴力预处理就行了,而我还涉及到另一个值域为 n 的变量 xk ,于是预处理也很困难。于是进行不下去了。
还是要尝试多种角度的思考问题,不仅是这种思路能走多远的问题,更直接的,不同的角度会对式子产生不同的影响。
对于具体的计算方法,
对于每个询问涉及到某种分布或者某段的组合数的计算,直接计算或者预处理都不好做,可以考虑优化暴力,将询问对应的区间离线下来,对相应数值跑莫队,这样可以做到根号。
对于正解,其计算难点在于出现了以 k 为参数的式子,这个 k 值域是 1->n ,若对于每个 1-> n 都预处理是不现实的。但是注意题目条件 ∑k≤2∗n\sum k\leq 2*n∑k≤2∗n ,那么不同的 k 的种数最多只有 n\sqrt nn 级别,于是将 k 离线下来只对这根号个 k 预处理就可以了。
很多题目都涉及了对 ∑k≤lim\sum k\leq lim∑k≤lim 这个条件性质的利用,如该题中 k 种类数不超过根号、虚树等。
T3:
想到建图了,建了图,但是对于图的性质没有剖析完全,模型中出现了许多冗余边。具体的,正解的建图是若干条链,相邻的链连边,而我对于一条链与许多不相邻的链也连了边,但实际上这些边即使不加,也存在相应的等价的路径。于是我的图模型不像题解那样简洁,比较乱,也没有规律可循。
这种建模题,连边时要谨慎,考虑到这条边是否有加的必要,是否不需要这条边也能表现出相应的等价关系,精简模型,透露本质。
题目有充要性质:相同的 ai 对应的 pi 递减,且对于一个 pi 大于 i 之前最近的一个满足 aj=ai-1 的 pj 。由此建图,是若干条相连的链。
这个图比较简单,信息可以直接递推处理。
三道题都没有涉及什么比较复杂的算法和数据结构,T1是暴力题,T2是经典套路题,T3难度也不算很高,其实都在个人可控范围内,T1,T2都是应该 AC 的题目,理想分数应该在 250+ 以上。
相关文章:
2/12考试总结
时间安排 8:30–8:50 读题,T1 不知道是个啥,T2是个dp ,T3可能也是 dp 之类的。 8:50–9:30 T1,读了好几遍才理解了题意,对于部分分有爆搜。考虑正解,想到预处理后O(1) 查询,问题是如何由已知的信息得到所有…...
第三章虚拟机的克隆,快照,迁移删除
1.虚拟机的克隆 如果你已经安装了一台linux操作系统,你还想再更多的,没有必要再重新安装,你只需要克 隆就可以,看演示。 方式1,直接拷贝一份安装好的虚拟机文件,再用虚拟机打开这个文件方式2,使用vmware的…...
华为OD机试 - 任务总执行时长(Python)| 真题含思路
任务总执行时长 题目 任务编排服务负责对任务进行组合调度。 参与编排的任务又两种类型, 其中一种执行时长为taskA, 另一种执行时长为taskB。 任务一旦开始执行不能被打断,且任务可连续执行。 服务每次可以编排 num 个任务。 请编写一个方法,生成每次编排后的任务所有可…...
LeetCode 热题 C++ 114. 二叉树展开为链表
给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 示例 1…...
Spring的事务控制-基于AOP的声明式事务控制
Spring的事务控制-基于AOP的声明式事务控制 Spring事务编程概述 事务是开发中必不可少的东西,使用JDBC开发时,我们使用connection对事务进行控制,使用MyBatis时,我们使用SqlSession对事务进行控制,缺点就是ÿ…...
SSO(单点登陆)
Single Sign On 一处登陆、处处可用 0、前置概念: 1)、单点登录业务介绍 早期单一服务器,用户认证。 缺点:单点性能压力,无法扩展 分布式, SSO(single sign on)模式 解决 : 用户身份信息独…...
线程和QObjects
QObject的可重入性: QThread继承了QObject,它发出信号以指示线程开始或完成执行,并提供一些插槽。 QObjects可以在多个线程中使用发出调用其他线程中槽的信号,并将事件发布到在其他线程中“活动”的对象。这是可能的࿰…...
最新中文版FL Studio21水果软件下载安装图文教程
FL Studio是目前流行广泛使用人数最多音乐编曲制作软件,这款软件相信广大网友并不陌生,今天带来的是FL中文版本,所有的功能都能在线编辑,用户直接就能操作,同时因为是21水果是最新版,所以增加了新的功能&am…...
pandas数据分析35——多个数据框实现笛卡尔积
什么是笛卡尔积。就是遍历所有组合的可能性。 比如第一个盒子有[1,2,3]三个号码球,第二个盒子有[4,5]两个号码球。那么从每个盒子里面分别拿一个球共有3*2两种可能性,其集合就是{[1,4],[2,4],[3,4],[1,5],[2,5],[3,5]},这个就是笛卡尔积。 三个盒子也是…...
【C语言学习笔记】:数组倒序排列,数组倒置
数组倒置就是将数组元素中的数据倒过来! 举个例子,比如下面程序: #include <stdio.h>int main(void) { int a[5] {1, 2, 3, 4, 5}; int b[5]; //用来存放倒置后的数据 int i, j; for (i0, j4; i<5, j>0; i, --j)…...
sni+tomcat漏洞复现
sni SNI产生背景 SSL以及TLS(SSL的升级版)为客户端与服务器端进行安全连接提供了条件。但是,由于当时技术限制,SSL初期的设计顺应经典的公钥基础设施 PKI(Public Key Infrastructure)设计,PKI 认为一个服务器只为一个…...
Linux ALSA 之十:ALSA ASOC Machine Driver
ALSA ASOC Machine Driver一、Machine 简介二、ASoC Machine Driver2.1 Machine Driver 的 Platform Driver & Platform Device 驱动模型2.2 在 Probe() 中注册声卡三、snd_soc_register_card 函数3.1 bind DAIs3.2 New a sound card3.3 Create card new widgets3.4 Probe …...
Spring 面试题(一):Spring 如何处理全局异常?
❤️ 博客首页:水滴技术 🚀 支持水滴:点赞👍 收藏⭐ 留言💬 🌸 订阅专栏:Spring 教程:从入门到精通 文章目录1、如何处理全局异常2、代码示例2.1、定义统一的“响应结果对象”2.2、…...
Threadlocal为何引发内存泄漏问题
首先我们要先了解什么是泄漏问题和什么是内存溢出 内存泄漏表示程序员申请了内存,但是该内存一直无法被释放 内存溢出表示申请内存不足,就会报错 为何引发内存泄漏问题 因为每个线程都有自己独立的ThreadLocalMap对象,key为ThreadLocal&…...
如何写好 Python 的 Lambda 函数?
当你需要完成一件小工作时,在本地环境中使用这个函数,可以让工作如此得心应手,它就是 Lambda 函数。 Lambda 函数是 Python 中的匿名函数。有些人将它们简称为lambdas,它们的语法如下: lambda arguments: expression…...
大数据技术架构(组件)32——Spark:Spark SQL--Execute Engine
2.2、Spark SQL2.2.1、Execute EngineSparkSql的整体提交执行流程和Hive的执行流程基本上一致。站在通用的角度,对于SparkSql来说,从Sql到Spark的RDD执行需要经历两个大的阶段:逻辑计划和物理计划逻辑计划层面会把用户提交的sql转换成树型结构…...
Leetcode.1138 字母板上的路径
题目链接 Leetcode.1138 字母板上的路径 Rating : 1411 题目描述 我们从一块字母板上的位置 (0, 0)出发,该坐标对应的字符为 board[0][0]。 在本题里,字母板为board ["abcde", "fghij", "klmno", "pqr…...
一个自动配置 opengrok 多项目的脚本
前段时间在服务器上配置 opengrok 阅读代码,项目有很多个,一个一个手动配置比较繁琐。 我从搭建 tomcat 和 opengrok,到配置和索引完 5 个 Android 项目,用了差不多一整天。 要是再让我手动配置几个项目,估计真要崩溃…...
JAVA同步代码块 同步方法
JAVA同步代码块 & 同步方法 为了解决多线程操作共享数据时产生的安全问题 例如以下代码 if (ticket < 0) {// 卖完了break; } else {ticket--;System.out.println(Thread.currentThread().getName() "在卖票,还剩下" ticket "张")…...
分享111个助理类简历模板,总有一款适合您
分享111个助理类简历模板,总有一款适合您 111个助理类简历模板下载链接:https://pan.baidu.com/s/1JafYuLPQMmq37K4V0wiqWA?pwd8y54 提取码:8y54 Python采集代码下载链接:https://wwgn.lanzoul.com/iKGwb0kye3wj 设计师助理…...
Allegro如何更改临时高亮的颜色设置操作指导
Allegro如何更改临时高亮的颜色设置操作指导 在用Allegro做PCB设计的时候,当移动或者高亮某个对象之前,会被临时高亮一个颜色,方便查看,类似下图 运行高亮命令的时候,器件被临时高亮成了白色 软件默认的是白色,如何更改成其它颜色? 具体操作如下 点击Display选择Color…...
知识图谱嵌入技术研究综述
作者 张天成 1 , * 田 雪 1 , * 孙相会 1 , * 于明鹤 2 , * 孙艳红 1 , * 于 戈 摘要 知识图谱 是一种用图模型来描述知识和建模事物之间的关联关系的技术。 知识图谱嵌入 作为一种被广泛采用的知识表示方法。 主要思想是将知识图谱中的实体和关系嵌入到连续的向量空间中…...
Scratch少儿编程案例-水果忍者-超完整
专栏分享 点击跳转=>Unity3D特效百例点击跳转=>案例项目实战源码点击跳转=>游戏脚本-辅助自动化点击跳转=>Android控件全解手册点击跳转=>Scratch编程案例👉关于作者...
练 习
1.判断三个中最重的//依次输入相应的人的体重double people1, people2, people3;cout << "请输入第一个人体重" << endl;cin >> people1;cout << "请输入第二个人体重" << endl;cin >> people2;cout << "请…...
Urho3D整体结构
Urho3D引擎编译成一个库。从概念上讲,它由几个代表不同子系统或功能的“子库”组成。其中每个都位于Source/Urho3D目录下的子目录中: 容器:提供STL替换类和共享指针。数学:提供相交测试中使用的矢量、四元数和矩阵类型以及几何形状。Core:提供执行上下文…...
大数据技术之Hudi
Hudi概述 1.1 Hudi简介 Apache Hudi(Hadoop Upserts Delete and Incremental)是下一代流数据湖平台。Apache Hudi将核心仓库和数据库功能直接引入数据湖。Hudi提供了表、事务、高效的upserts/delete、高级索引、流摄取服务、数据集群/压缩优化和并发&a…...
libxlsxwriter条件格式
今天来看一个libxlsxwriter的高级用法:一个条件格式的示例。 说它“高级”,也是基于非Excel专家的小白们的视角。对,没错,本小白正是这样的小白。 1 一个简单的问题 来看我们今天的场景问题:有一列数据,有…...
nodejs+vue+elementui在线求助系统vscode
目 录 摘 要 1 前 言 3 第1章 概述 4 1.1 研究背景 4 1.2 研究目的 4 1.3 研究内容 4 第二章 开发技术介绍 5 前端技术:nodejsvueelementui,视图层其实质就是vue页面,通过编写vue页面从而展示在浏览器中,编写完成的vue页面要能够和控制器类进…...
电子技术——BJT差分输入对
电子技术——BJT差分输入对 本节我们来讨论BJT差分输入对。 共模输入 下图是BJT差分输入对的基本原理图: 首先我们考虑两端输入共模信号 VCMV_{CM}VCM : 此时 vB1vB2VCMv_{B1} v_{B2} V_{CM}vB1vB2VCM 因为电路的对称结构,所以 i…...
[MySQL教程②] - MySQL介绍和发展史
目录 ❤ MySQL介绍 ❤ 什么是数据库 ❤ 什么是数据 ❤ 数据库管理系统 ❤ NoSQL特性总览 ❤ NoSQL的分类、特点、典型产品 ❤ 常见的数据库产品有哪些? ❤ Oracle公司产品介绍 Oracle数据库版本介绍 Oracle的市场应用 MySQL数据库版本介绍 MyS…...
湖南大型网站建设公司排名/seo外包公司哪家专业
MIRACL用户手册译:叶道全yedaoq126.com摘要Miracl库包含100余个例程,涉及多倍精度运算(multiprecision arithmetic)的各个方面。定义了两种新的数据类型——表示大整数的big类型和表示有理数的flash(short for floating-slash)类型。大整数例程基于Knuth…...
本地wordpress模板编辑/南宁网站推广排名
实验介绍 定时器毫不夸张地说就是单片机的灵魂,因此关于定时器的相关知识是必须掌握的。定时器就是用来计数的,当配置好定时器的频率后,以该频率进行计数,我们一般还要配合中断来进行操作,当定时器计数到我们想要的值…...
做英语阅读的网站/怎样做网站
今天做网站【标签】筛选功能时,出现了这么个奇葩的问题。 我是直接通过<a>标签中href来跳转的,url中包含汉字 <a href"/tags/标签A">标签A</a> 后台代码是这样的: RequestMapping(value "/tags/{tagname}&…...
信主网站/广告开户
题目:用*号输出字母C的图案。 程序分析:可先用*号在纸上写出字母C,再分行输出。 程序代码: #include <stdio.h> int main() {printf("用 * 号输出字母 C!\n");printf(" ****\n");printf(" *\n&…...
数字化校园建设网站/数据分析师培训机构
文章目录 引言I iOS16.0 横竖屏切换适配1.1 获取当前屏幕横竖屏状态1.2 iOS16.0调完转屏方法后,需要重新更新view的frame1.3 自定义页脚II 解决UITableViewCell兼容问题(iOS14适配)2.1 问题分析2.2 解决方案III iOS10 系统关于UITableView的适配问题3.1 代理方法的执行顺序3…...
大连做网站建设/免费行情网站
div是块级元素,它不论大小默认占一行,而且可以设置宽高以及外边距span是行内元素,它占它自身大小的位置,而且不能设置宽高以及边距同时div也可以变为span (display:inline),这样div将变为行内元素span也可以变为div(display:block…...