csps51(a)

系统管理员 2023-08-17 16:48 89阅读 0赞

T1的暴力死掉了。。。。。。

T3大众分。。。。。。

T2打了几个小表，发现了一些规律，成功yy出了$O(nlogalogn)$的暴力，拿到了73pts，弥补了爆炸的T1。

T1.

考场上看了看，遥远的国度。由于我没做过，感觉硬刚可能GG，于是先放了。

然而最后打了40pts暴力爆零了。。。。

正解其实很简单，考虑当前根与原根的关系，讨论一下就好了。

T2.

由于两个log，50w的数据范围，很大的优化空间，我果断地走向了暴力的道路。

这题如果强制在线，我的方法应该就是正解了。

思想很简单，我并没有转化题意，所以从一个完全不同的角度去考虑：

某一个数，除非它是目前最小的，那么它必然在某一时刻会被$f\[x-1\]\[y-1\]$更新，并且从此之后一直被它更新。

那么，我们可以发现，这两项的差成为了定值，为$a\[y\]$。

而在它被上一列更新之前，就会一直被自己的前一项更新，以等差数列的形式增长。

那么我们要求某一项$f\[x\]\[y\]$值的时候，就可以一直去找它的$f\[x-1\]\[y-1\]$项，直到这一项已经是等差数列的形式，然后求出当前项，递推回去即可。

我们考虑如何确定当前项已经是等差数列。显然我们可以预处理出来，对于每个$a\[y\]$，它到第几项不再是等差数列。(l\[x\])

我们考虑怎么预处理。二分答案，对于每一个二分的值，我们假设当前仍然是等差数列，比较它与$f\[x-1\]\[y-1\]+a\[y\]$的大小，若小于，说明当前项由上一列更新更优，不再是等差数列。

下一个问题是，如何求出$f\[x-1\]\[y-1\]$的值。由于之前的数我们已经将它何时不再成为等差数列处理了出来，所以我们需要找到第一个成为等差数列的位置。

继续二分答案，查询区间中最大的$l\[x\]$是否能被这个数利用。

我们可以用ST表来实现$O(1)$查询，每次求出一个$l\[x\]$，在ST表末尾加入它即可。

询问直接调用之前的求值函数即可。

代码实现很简单，而且这大概是在线的唯一做法了。

理论复杂度爆了，所以加了一些减枝，卡了卡常，A掉了。

正解是将所有操作离线，维护一个下凸包，在凸包上三分。

也许可以算自己A掉的A组题？

T3.

母函数，NTT。

转载于:https://www.cnblogs.com/hzoi-cbx/p/11587560.html

发表评论取消回复

表情：

评论列表（有 0 条评论，89人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客练习赛51 A-E

目录 * \[A - abc\](https://ac.nowcoder.com/acm/contest/1083/A) * \[B - 子串查询\](htt...

深藏阁楼爱情的钟/ 2024年04月18日 13:01/ 0 赞/ 57 阅读

相关 csps51(a)

T1的暴力死掉了。。。。。。 T3大众分。。。。。。 T2打了几个小表，发现了一些规律，成功yy出了$O(nlogalogn)$的暴力，拿到了73pts，弥补了爆炸的T1。

系统管理员/ 2023年08月17日 16:48/ 0 赞/ 90 阅读

相关 51单片机的系统扩展之8255A

8255： 8255芯片是Intel公司生产的可编程并行[I/O接口][I_O]芯片，有3个8位并行I/O口。具有3个通道3种工作方式的可编程并行接口芯片（40引脚）。

「爱情、让人受尽委屈。」/ 2022年10月21日 11:53/ 0 赞/ 212 阅读

相关 CSP安全策略

介绍内容安全策略 (CSP) 是一个附加的安全层，用于帮助检测和缓解某些类型的攻击，包括跨站脚本 (XSS) 和数据注入等攻击。这些攻击可用于实现从数据窃取到网站破坏

灰太狼/ 2022年10月12日 12:16/ 0 赞/ 124 阅读

相关使用 RTX51 Full 时 A43 错误解决

// source\RTXCONF.A51(3): error A43: RESPECIFIED PRIMARY CONTROL 主要报出上面错误. 也就是 RTXC

绝地灬酷狼/ 2022年09月18日 14:56/ 0 赞/ 69 阅读

相关 51单片机系列--LCD1602A

Lcd液晶屏幕带有背光显示，可选择蓝光白光黄光三种背光颜色的屏幕，它更具有美光性，在实际生活中有广泛的应用。实物图 ![在这里插入图片描述][202107181908

谁践踏了优雅/ 2022年08月30日 04:08/ 0 赞/ 187 阅读

相关 CodeSmith的csp文件

我的程序的思路是： 1. 用户在UI中输出参数； 2. 参数被存在一个XML文件中，这个文件的格式就是codesmith的csp文件格式。 3. codesmith脚本，

梦里梦外;/ 2022年08月27日 13:42/ 0 赞/ 144 阅读

相关 CSP开发基础--CSP入门简介

转载自：https://blog.csdn.net/liuhuiyi/article/details/7778742 CSP加密服务提供者(Cryptographic Ser

我会带着你远行/ 2022年05月21日 00:59/ 0 赞/ 369 阅读

相关 CSP开发-CSP模块的实现

转载自：https://blog.csdn.net/anda0109/article/details/50035783 前面几篇主要介绍了如何开发基于CSP的应用，即通过Cr

分手后的思念是犯贱/ 2022年05月21日 00:59/ 0 赞/ 414 阅读

相关 51 Nod 1046 A^B Mod C

题目链接：[点我][Link 1] 给出3个正整数A B C，求A^B Mod C。例如，3 5 8，3^5 Mod 8 = 3。 Input 3个正整数A

谁借莪１个温暖的怀抱￠/ 2022年05月15日 03:59/ 0 赞/ 107 阅读