To_Heart—题集——晚星就像你的眼睛杀人又防火

这篇具有很好参考价值的文章主要介绍了To_Heart—题集——晚星就像你的眼睛杀人又防火。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

连一周一更都做不到,只能说自己太颓废了,,。还有一个月了,至少要做到认真考试不睡觉!

1.CFCF814E

link && submission

dp 妙妙题。

首先有个结论是发现这张图的生成是有个性的,首先同层的序号一定相邻,其次除了和父亲的连边外其他的边都是同层的。这引导我们考虑定义 dp 状态。定义 dp[i][j][k] 表示当前层有 \(i\) 个与上一层连了边,上一层有 j 个度数为 2,k 个度数为 3的方案数。然后再定义 f[i][j] 表示考虑到了第 i 个点,最后一层有 j 个点的方案数。答案是 \(\sum\limits_{i=1}^{n-1} f[n][i] * g[0][c[2]][c[3]]\) 其中 c[2] 表示 \([i-j+1,i]\) 中度数为 2 的点的个数。c[3] 同理。然后这个答案的理由是我们只需要看最后一层有多少个点以及其与上一层的连边情况就可以统计出所有的方案数。

2.CF1491H

link && submission

分块随便做咯。有个非常好玩的是这一场是个中国场专门给中国人写了个提示叫来自于 lxl 的 Ynoi。

考虑对序列分块,记录一个数组 Pa[i] 表示在 i 的祖先上出现的第一个和 i 不同块的下标。这样的好处是你可以在 \(\max(B,\frac{n}{B})\) 的复杂度下算 lca,而且你发现这个的修改有一个势能的关系,即每个点被修改了块长次以后它的父亲一定与它不同块。然后随便维护一下就好了。

这道题能学到的是分块LCA,其实和倍增本质差不多,但是这个的好处是平衡了块长?这样暴力修改居然变得优美起来。所以由LCA想到分块LCA的过程才是这类数据结构的启示。

3.AT_agc030_c

link && submission

你们凭什么不来做这道题?啊你们凭什么不来做这道题?? 算是做过最震撼的构造了。也有可能是我构造本来就做得少

平凡的是 \(k\le 500\) 的部分。可以每一行都放一个相同的数。但是如果说 \(k\) 大于 \(500\) 了呢?

这时候如果还是考虑在原基础上优化,即在每行放相同的基础上放置其他数替换。但是你考虑这个时候每个数周围数的构成。举个例子

1111
2222
3333
4444

对于 1 来说,他的周围是由一个 2 和一个 4 和两个 1 组成。如果我们选择一个 5 来替换 1,那么就有一个 2 和 一个 4 和其他的 24 不匹配了。如果要改变这种情况就只能把所有的 1 换掉但这样就没有 1 了。

但是这时候你发现对于 1 来说,他斜着相邻的分别为两个 2 和 两个 4。你发现我们有机会更换 \(\frac{k}{2}\)1 来让所有的 24 匹配。但是什么情况下可以看斜着的呢?就是把图形斜过来!

考虑斜着放。这下我们发现只要在原本放 1 的位置交替放 15 就可以让矩阵合理,因为你改变一个 1 就会让相邻的两个 24 变化。

发现这种替换的瓶颈是要求矩阵的长宽是偶数。我们发现 \(n=500\) 刚好是偶数,所以直接在 \(n=500\) 的情况下一直替换就最多能替换到 \(2n\) 个数。

4.CF1693E

link && submission

很早之前的一道遗留题目了。非常清新的数据结构好题。

发现每一个位置值改变成左侧小于他的最大值和右侧小于它的最大值的较小值,那么如果我们从大到小枚举值域,如果一个位置左右比他小的最大值都出现了,那么它的值就会被修改而且贡献加 1。这引导我们将贡献的计算放到左右两边最大值上。

发现每个位置可以有三种状态,分别是 左右两边小于它的最大值均没出现和出现了一边(出现了两边时贡献增加然后状态改为两边均没出现),然后可以发现在从高到低枚举值域修改状态时三种状态所在的位置是一段一段连续出现的,而且一定是中间段未知。考虑每一次修改状态后中间段的改变并以此计算贡献即可。

5.CF1651F

link && submission

首先将恢复挂在两次查询的差上。然后发现每次查询其实就是把一个区间推平,以及有可能把下一个位置的值减小。把这个推平操作看成一个颜色块,那么本质是维护每个颜色块内部的信息。好消息是颜色块个数与 m 同阶,所以颜色块的增减可以暴力。发现每个位置随着 T 的函数是个先增大后不变的函数,于是可以用主席树统计每个颜色块内部经过了 T 秒后哪一块满了不会增加了。这个可以线段树二分做到单 log。

6.ABC292G

link && submission

牛逼题。第一次见这种套路。放篇顶级题解。

重要的是套路的积累,大概是可以把字典序分为当前这一位 [i,j] 是相等的字符从而进行 区间dp。真的好牛逼啊。

7.CF1879F

link && submission

春春挠谭题,啥必 st 表码量题。

首先显然大于 \(\max(a_i)\) 的难度是可以等价在难度等于 \(\max(a_i)\) 的情况中的,所以难度实际上是有限的。这引导我们考虑枚举难度,考虑每个难度剩下来的是哪个以及每个难度对剩下来的那个的答案贡献是多少。发现就是操作次数的最大值所在的人至少能获得次小值的贡献。

对于每个难度 x,每一个人每一条命能坚持的次数是 \(\lceil \frac{a_i}{x} \rceil\)。然后你枚举 x 的时候所有的人可以被划分在 \(\lceil \frac{a_i}{x} \rceil\) 个区间里面,第 i 个区间每一条命能撑的次数就是 i 次。然后根据什么什么性质哦这样分下来从头到尾区间个数有 \(n\ln n\) 个。

首先将所有人按照 \(a_i\) 从小到大排序,那么在枚举 x 的时候被划分再同一个区间的人排完序后一定是相邻的。那么我们只需要使用一种数据结构支持每次 \(\mathrm{O(1)}\) 区间查询 \(h_i\) 的最大值和次大值就行了。然后这个居然可以 st 表?大概的处理方法就是 st表 里面直接放最大值和次大值的下标,如果下标不同那就是不同的两个数,然后分讨比较即可。

8.CF587D

link

我什么时候过的这个题?哦我抄的题解啊那没事了。

题解,当个知识学习一下。如果要我来说的话前缀优化的本质就是利用前后缀处理重复连边的问题。

9.CF214B

link && submission

挺逆天的,这里指我。

嘛,如果不考虑我的错误的话那这道题是没什么错误的。需要学习的是这种处理区间异或第 k 大的方法。大概就是把所有的 \(a_i\) 放在一起在 trie 上查就能做到 nlogn 的复杂度。其他的没什么好讲的。你会了这个剩下的都会了。

10.CF1610G

link && submission

首先肯定是要倒着往前做的,因为如果后面一直有匹配的括号而且前面不变的话是要一直删的。然后你又发现如果要删去一对括号,那么他们内部的括号一定被删完了。我们反过来考虑每次操作。设 dp[i] 表示 考虑到 [i,n] 的字符串的最小方案,根据当前这个括号
是否删除转移。如果要删除那么直到后面第一个和它匹配的括号都要删,所以 \(dp[i]=\min(dp[nxt_i+1],c[i]+dp[i+1])\) 其中 c[i] 表示当前这个字符。

很容易发现转移是棵树。那么你就像倍增LCA的预处理一样处理出来所有的转移就好了。注意判断字符串的大小可以 hash。

记录一下最后一步,这种处理很牛逼的。文章来源地址https://www.toymoban.com/news/detail-711556.html

到了这里,关于To_Heart—题集——晚星就像你的眼睛杀人又防火的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 让java程序就像脚本一样去写工具

    背景: 接触了各种语言之后发现,java还是比go,.netcore之类的简单,成熟,我最终选择了jenkins+shell+java去部署我们的代码,此时很多人可能去使用js或者python之类的去写部署逻辑,毕竟java每次打包还是有点麻烦的。现在的话,使用mvn,其实已经可以直接去运行了。  1)run.bat

    2024年02月02日
    浏览(34)
  • 【学Vue就跟玩一样】学习vue就像打游戏一样简单

    目录 前言 一,初入Vue大陆 1.Vue的初体验 1.Vue的特点 2.引入vue 3.可能出现的问题 4.创建Vue实例 5.模板语法 6.数据绑定 7.连接容器的方法 8.data的写法 二,MVVM模型 三,数据代理 1.对数据进行读取和修改  2.事件修饰符 3.键盘事件 最后   🐳对于看到这篇文章的小伙伴呢!肯定是

    2024年02月08日
    浏览(44)
  • 【OpenCV实现图像找到轮廓的不同特征,就像面积,周长,质心,边界框等等。】

    OpenCV是一个流行的计算机视觉库,它提供了许多图像处理和分析功能,其中包括查找图像中物体的轮廓。通过查找轮廓,可以提取许多有用的特征,如面积、周长、质心、边界框等。 以下是几种使用OpenCV查找轮廓时常见的特征: 面积:可以使用 cv2.contourArea() 函数计算轮廓的

    2024年02月06日
    浏览(50)
  • 【译】生成式AI就像一把锤子,没有人知道什么是钉子,什么不是钉子

    原作:科林·弗雷泽 引言:如果您相信 ChatGPT 正走向通用工具之路,那只是以一种狂热的信仰。 /Gemini翻译/ “锤子”比喻可能会显得有些牵强,但对于计算机专业人士再熟悉不过。设想一个没有锤子的世界。你只能用手来敲打钉子,将画挂在墙上。你必须用脚踢击石膏板以拆

    2024年03月25日
    浏览(48)
  • 【c/c++】属于程序员的浪漫,基于easyx.h图形库实现3D Heart

    👻作者简介:M malloc,致力于成为嵌入式大牛的男人 👻专栏简介:本文收录于 初阶数据结构 ,本专栏主要内容讲述了初阶的数据结构,如顺序表,链表,栈,队列等等,专为小白打造的文章专栏。 👻相关专栏推荐:LeetCode刷题集,C语言每日一题。 本章我将详细的讲解如何

    2024年02月08日
    浏览(45)
  • 使用Windows To Go工具制作你的U盘系统【含下载Windows10系统镜像】亲测已成功23.06.21

    WinToGo是一款辅助工具:专为能够让你将系统装进U盘,移动硬盘里,让你在任意电脑都能运行U盘里装的系统! 一、下载,安装“Windows To Go”工具 1、下载Windows To Go工具 口袋系统WinToGo: 安装Win 10到U盘    2、双击WinToGo.exe,完成“安装”  3、安装完成,开始菜单会生成一个W

    2024年02月17日
    浏览(60)
  • uniapp 密码框的眼睛

    效果展示: uniapp input 官网链接:链接 按照官方文档,uni-icon出不来。 通过自己的方法解决了,解决方案如下: 代码: 思路如下:  通过v-if控制显示不同的眼睛(即选中/未选中状态)

    2024年04月13日
    浏览(29)
  • 完全去中心化的编程模式,不需要服务器,也不需要ip,就像一张漫无目的的网络、四处延伸

    这是一篇畅想的文章,只说我的编程理念、实现原理。 现在信息传输架构,大部分都是c/s架构,客户端向服务器传递信息,服务器根据不同的逻辑,开始分发信息。这种架构,很容易就形成信息中心化、信息垄断现象。 那么与之对应的,就是许多反中心化的技术,区块链、

    2024年02月02日
    浏览(38)
  • 虚拟现实中的眼睛跟踪

    本文旨在介绍虚拟现实中眼动跟踪的新兴领域。虚拟现实本身是消费市场上的一项新兴技术,这将为研究创造许多新机会。它提供了一个高度沉浸的实验室环境,并与现实密切相关。一个使用虚拟现实的实验是在高度受控的环境中进行的,可以收集关于受试者动作的更深入的

    2023年04月14日
    浏览(52)
  • 使用 OpenCV 进行面部和眼睛检测

    OpenCV是构建计算机视觉应用程序的强大工具。计算机视觉中最常见的任务之一是人脸检测,它涉及识别图像或视频中人脸的存在、位置和面部特征。 在本文中,我们将学习如何使用 Haar 级联分类器检测图像中的人脸。 先决条件 在开始之前,你需要在计算机上安装 OpenCV。 参

    2024年02月09日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包