首页 > 其他分享 >ABC250简要题解

ABC250简要题解

时间:2022-12-01 20:58:39浏览次数:47  
标签:神秘 简要 题解 个数 哈希 ABC250 指针

重点在于简要

A,B,C,语法题,跳了。

D是埃筛求个质数枚举一下,跳了、

E

神秘的哈希。

对于前 \(i\) 个数搞个可加哈希,这样能 \(O(1)\) 比较。给了个神秘的哈希方式是 \(\sum a_i\times (a_i+353448299)\) (这质数换一个也成)。神秘的哈希。

我们的红太阳有个更神秘的哈希。就是给每个权值重新rand 一个新权值,然后直接加起来。

哈希果然神秘。

题解区还有一个做法就是对于每种 \(a_i\) 找到最靠前的出现的相同的 \(b_i\),答案就是前 \(x\) 个数的集合的最大值到不属于前 \(x\) 个数的集合的最小值之间。

他说复杂度是 \(O(n+Q)\) 的,就是拿 unordered_map 硬搞就行了。

F

旋转卡壳(\(2^4\))。

就整个双指针,移动的时候用向量叉积实时计算面积即可。

对于左指针,找到最合适的右指针的位置。

G

反悔贪心入门题。

就是如果卖出的话尽可能选个最小的位置买入这支。但是可能有问题,所以考虑反悔贪心。

搞一个堆,每次取出价格最小的。假设买入这支股票的价格为 \(a\),卖出价格为 \(b\) ,那答案加上 \(b-a\),再将\(b\) 插到堆里,这样再取出 \(b\) 的时候相当于消掉了 \(b\) 的贡献。

Ex

非常 NOIP 啊

先将每个点离得最近的关键点的距离求出来(最短路),然后对于每个询问,考虑询问两点间是否可达的时候,一条边能被走当且仅当这条边的边权加上这条边两端点分别到关键点的距离的和小于等于 \(t\),正好询问 \(t\) 单调不降,所以直接用并查集加边即可

标签:神秘,简要,题解,个数,哈希,ABC250,指针
From: https://www.cnblogs.com/cc0000/p/16942648.html

相关文章

  • jeecg问题解决方案
    1.jeecg数据库脚本问题  注意:jeecg3.5.2之前版本,不需要数据库脚本,程序会自动初始化数据库。从3.5.2+开始,需要手工执行SQL脚本,初始化数据库。  2.  Eclipse内存溢......
  • JOISC 2021 简要题解
    「JOISC2021Day1」饮食区维护\(n\)个队列,支持\(m\)次操作:在\([l,r]\)号队列的尾端均加入\(k\)个颜色\(c\)的球。将\([l,r]\)号队列的前\(k\)个球pop......
  • 【题解】LOJ #6672(感谢强大 alpha!!1【4】)
    考虑完整的一段的GF为\(u\),那么答案为\([x^n]u^{m}\)(令\(m=k-1\))。考虑\(u\)是什么,发现和此默慈金数相关——我们令\(M\)为默慈金数的GF,根据递推式\(M_{n+1}......
  • NOIP2022 题解
    A.种花有的人把名字写进题面,想“不朽”。签到题。枚举c和f的最左边那一列的位置,然后做一个类似前缀和的东西。B.喵了个喵压轴题。首先\(k=2n-2\)有一个非常好......
  • 【题解】ABC237G Row Column Sums 2(感谢强大 alpha!!1【3】)
    题意:求\(n\timesn\)方阵个数,满足每列之和为\(R_i\),每行之和为\(C_i\)。数据范围:\(0\leqR_i,C_i\leq2\),\(n\leq10^7\)。转二分图,相当于限定左侧每个点和右侧......
  • 剑指offer题解C++版
    一,常见数据结构1,数组3-找出数组中重复的数字4-二维数组中的查找5-替换空格29-顺时针打印矩阵leetcode989-数组形式的整数加法leetcode26-删除有序数组中的重复......
  • 问题解决系列:遇到tomcat的假死问题,如何排查问题
    (文章目录)问题场景线上,有时候会遇到一种这样的情况:tomcat没有奔溃退出,输出日志也没有异常,但是界面访问就一直卡着。假如遇到这种情况,没错,你遇到了tomcat假死问题了。那么......
  • Charles中contents出现中文乱码问题解决
    检查证书是否过期,如过期,先重置过期证书再安装证书  SSLProxyingSettings中include设置*:443  即可解决contents中文乱码问题......
  • R6PL - Harbinger vs Sciencepal题解
    R6PL-HarbingervsSciencepal题面翻译彩虹6是大学里非常流行的游戏。你的两个朋友小A和小B是优秀的玩家,他们想要参与竞争。所以他们决定组建自己的团队。有2*N的......
  • NOIP2022T1题解
    [NOIP2022]种花(民间数据)题目描述小C决定在他的花园里种出\(\texttt{CCF}\)字样的图案,因此他想知道\(\textttC\)和\(\textttF\)两个字母各自有多少种种花的方......