热门标签 | HotTags
当前位置:  开发笔记 > 后端 > 正文

2021/11/3模拟赛

7:50−8:307:50-8:307:50−8:30看题,觉得T3T3T3比较像之前做过的题,T4T4T4的样例都给的比较难受。8:30−9:408:

7:50−8:307:50-8:307:508:30
看题,觉得 T3T3T3 比较像之前做过的题,T4T4T4 的样例都给的比较难受。
8:30−9:408:30 - 9:408:309:40
尝试用各种方法搞 T3T3T3 ,一开始觉得放到树上做各种东西的传递还是不太好调试,跑树的时候重新连边,当成一个有向无环图来搞,然后传递的时候每个节点再用 vector 记录下当前单调上升序列的最大值和长度,然后有需要判断的时候做类似背包的状态转移,但是状态转移比较困难且 STL 用着还是比较吃力了些。
然后就还在树上做,自下而上传递些大小和最大值之类的,我觉得如果选了 iii 号节点,那么它的子节点怎么选择都是固定的,很有 动态规划 的味道了,但是卡在了一个节点如果有多个儿子的情况上。在纸上写写画画也没有完全解决,感觉这还得看有多个子节点的节点能不能选择,且上方的改变可能会影响下边的好多都发生改变。
然后就想把每条链拆开来做,但是不会写。
然后考虑能不能设定某个点必选,但是这样每次设定一个必选的点的话,对于其他链又没有影响,还是会陷进刚刚的怪圈里。
9:40−10:509:40 - 10:509:4010:50
T1T1T1 中每个区间选择的先后顺序对结果无影响,所以 dfs 得到每个点选或不选的结果,然后计算。时间复杂度 O(2N)O(2^N)O(2N) 左右,能过第一档分。然后考虑第二档分,数据范围应该够一个 O(N2)O(N^2)O(N2) 的算法,所以就考虑 动态规划 ,先后无影响,且读入就是每个区间的左右端点,所以就开始想区间DP。把读入的每个区间里包含了多少个区间算出来,然后看任意一个区间(左右端点恰好是之前读入的某个区间的左端点和某个区间的右端点)中有多少个端点,提前用递推处理出来组合数,然后对于每个刚刚处理出来的区间搞个,然后整个区间里对这样的区间搞乘法原理。但是最后没太推出来。
相当于开考了 3h3h3h 才拿了 202020 分,已经开始很慌了,所以那 202020 分也没打表也没对拍也没扣数据验证一下。
10:50−11:2010:50 - 11:2010:5011:20
基于刚刚就用 O(2N)O(2^N)O(2N) 看每个选不选然后再处理,这时候我又想到 T3T3T3 的第一档分也可以看每个选不选,然后检验是否成立,并同时求出最优的答案。但是没调试出来。
11:20−剩下的时间11:20-剩下的时间11:20
T2T2T2 感觉也是组合数学 +动态规划,最后没有搞出来。



T3T3T3 搞上头了,而且节奏错了,还是从低档分写推高档分比较稳一点,正解的话是经典的求树上最长上升子序列。题解中的启发式合并根本没想到。平时题做太少了。

T1T1T1 没有任何措施去保证必得分,搞 T2T2T2 的时间匀出来些打个表,扣数据验证验证啥的,也该稳拿些分。而且把题想太难了,正解其实主要就一个有点像组合的小递推式
fi=2∗fi−1+2xf_i=2*f_{i−1}+2^xfi=2fi1+2x
xxx 就是右端点小于 rir_iri 的区间的数量,读入的时候顺便求个前缀就行。
或者线段树维护DP也可以。


推荐阅读
  • [译]技术公司十年经验的职场生涯回顾
    本文是一位在技术公司工作十年的职场人士对自己职业生涯的总结回顾。她的职业规划与众不同,令人深思又有趣。其中涉及到的内容有机器学习、创新创业以及引用了女性主义者在TED演讲中的部分讲义。文章表达了对职业生涯的愿望和希望,认为人类有能力不断改善自己。 ... [详细]
  • 学习SLAM的女生,很酷
    本文介绍了学习SLAM的女生的故事,她们选择SLAM作为研究方向,面临各种学习挑战,但坚持不懈,最终获得成功。文章鼓励未来想走科研道路的女生勇敢追求自己的梦想,同时提到了一位正在英国攻读硕士学位的女生与SLAM结缘的经历。 ... [详细]
  • 在Android开发中,使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法,并提供了具体的代码实现。通过获取图片的宽高,计算目标宽度和高度,并创建新图实现等比例缩放。 ... [详细]
  • 云原生边缘计算之KubeEdge简介及功能特点
    本文介绍了云原生边缘计算中的KubeEdge系统,该系统是一个开源系统,用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建,并为网络应用程序提供基础架构支持。同时,KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外,KubeEdge还支持跨平台工作,在私有、公共和混合云中都可以运行。同时,KubeEdge还提供数据管理和数据分析管道引擎的支持。最后,本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]
  • 近年来,大数据成为互联网世界的新宠儿,被列入阿里巴巴、谷歌等公司的战略规划中,也在政府报告中频繁提及。据《大数据人才报告》显示,目前全国大数据人才仅46万,未来3-5年将出现高达150万的人才缺口。根据领英报告,数据剖析人才供应指数最低,且跳槽速度最快。中国商业结合会数据剖析专业委员会统计显示,未来中国基础性数据剖析人才缺口将高达1400万。目前BAT企业中,60%以上的招聘职位都是针对大数据人才的。 ... [详细]
  • Android中高级面试必知必会,积累总结
    本文介绍了Android中高级面试的必知必会内容,并总结了相关经验。文章指出,如今的Android市场对开发人员的要求更高,需要更专业的人才。同时,文章还给出了针对Android岗位的职责和要求,并提供了简历突出的建议。 ... [详细]
  • CSS3选择器的使用方法详解,提高Web开发效率和精准度
    本文详细介绍了CSS3新增的选择器方法,包括属性选择器的使用。通过CSS3选择器,可以提高Web开发的效率和精准度,使得查找元素更加方便和快捷。同时,本文还对属性选择器的各种用法进行了详细解释,并给出了相应的代码示例。通过学习本文,读者可以更好地掌握CSS3选择器的使用方法,提升自己的Web开发能力。 ... [详细]
  • 本文介绍了Java工具类库Hutool,该工具包封装了对文件、流、加密解密、转码、正则、线程、XML等JDK方法的封装,并提供了各种Util工具类。同时,还介绍了Hutool的组件,包括动态代理、布隆过滤、缓存、定时任务等功能。该工具包可以简化Java代码,提高开发效率。 ... [详细]
  • 本文介绍了C#中生成随机数的三种方法,并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法,但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数,进一步突显了这个问题。文章指出,随机数生成在任何编程语言中都是必备的功能,但Random类生成的随机数并不可靠。最后,提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]
  • qt学习(六)数据库注册用户的实现方法
    本文介绍了在qt学习中实现数据库注册用户的方法,包括登录按钮按下后出现注册页面、账号可用性判断、密码格式判断、邮箱格式判断等步骤。具体实现过程包括UI设计、数据库的创建和各个模块调用数据内容。 ... [详细]
  • “你永远都不知道明天和‘公司的意外’哪个先来。”疫情期间,这是我们最战战兢兢的心情。但是显然,有些人体会不了。这份行业数据,让笔者“柠檬” ... [详细]
  • 生成对抗式网络GAN及其衍生CGAN、DCGAN、WGAN、LSGAN、BEGAN介绍
    一、GAN原理介绍学习GAN的第一篇论文当然由是IanGoodfellow于2014年发表的GenerativeAdversarialNetworks(论文下载链接arxiv:[h ... [详细]
  • 无线认证设置故障排除方法及注意事项
    本文介绍了解决无线认证设置故障的方法和注意事项,包括检查无线路由器工作状态、关闭手机休眠状态下的网络设置、重启路由器、更改认证类型、恢复出厂设置和手机网络设置等。通过这些方法,可以解决无线认证设置可能出现的问题,确保无线网络正常连接和上网。同时,还提供了一些注意事项,以便用户在进行无线认证设置时能够正确操作。 ... [详细]
  • 本文介绍了游戏开发中的人工智能技术,包括定性行为和非定性行为的分类。定性行为是指特定且可预测的行为,而非定性行为则具有一定程度的不确定性。其中,追逐算法是定性行为的具体实例。 ... [详细]
  • 数据对比分析图PPT(127.0.0.1表示什么)的使用方法和意义
    本文介绍了数据对比分析图PPT的使用方法和意义,解释了127.0.0.1的含义,并提供了相关资源下载。同时还讨论了目标管理的概念和MBO的实施方法。 ... [详细]
author-avatar
米蘭王妃级_608
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有