首页 > 其他分享 >浅谈一类高斯求和问题

浅谈一类高斯求和问题

时间:2023-11-30 16:13:49浏览次数:30  
标签:浅谈 填入 求和 times 等差数列 高斯

引入

相信大家都知道高斯求和公式:首项加末项的和乘项数除以二等于等差数列的和。

实际应用中往往不会这么简单,常常会告诉你等差数列的和然后让你反过来求等差数列的信息,这时候对于边界的处理就很重要。

P1014 [NOIP1999 普及组] Cantor 表

显然可以 \(O(N)\) 模拟,但这太慢了。

先来看分子:\(1,2,1,1,2,3,4,3,2,1,\ldots\)

容易发现对于 \(1\to\infty\) 的每个 \(i\),如果 \(i\bmod 2=1\),那么就填入 \(1\to i\),否则填入 \(i\to 1\)。

这不禁让我们想到快速计算的方式,先求出 \(\frac{(1+i)\times i}{2}<n\) 的最大的 \(i\),然后确定具体填的数。

显然可以 \(O(\log N)\) 二分出来,但这太慢了。

移项得到 \((1+i)\times i<2n\),取 \(j=\lfloor\sqrt{2n}\rfloor\)。

而 \((1+j)\times j\) 可能大于也可能小于等于 \(2n\),这要看 \(n\) 的具体取值。

如果出现了大于的情况,因为 \(j\leq\sqrt{2n}<j+1\),所以 \(j\times(j-1)<2n\),只需要判断一次即可。

分母除了填入方向相反外别的完全相同。

CF1426C Increase and Copy

肯定是先 \(+1\) 再复制,元素的值和元素个数越相近总和越大。

令 \(i=\lfloor\sqrt n\rfloor\):

  • \(i^2=n\),\(+1\) 和复制都是 \(i-1\) 次。
  • \(i\times(i+1)\geq n\),多 \(+1\) 一次或者多复制一次。
  • 否则两者都多做一次。

标签:浅谈,填入,求和,times,等差数列,高斯
From: https://www.cnblogs.com/landsol/p/17867613.html

相关文章

  • 「智造」第10期:浅谈工业互联网加速企业服务化转型
    01价值引领在新型工业化和数智化技术发展趋势之下,柔性化生产、网络化协同、服务化延伸促使制造企业的生产方式发生转变,数据资产、平台技术、生态能力成为了重要的生产要素。目标都是要为企业实现价值提升、业务的增长和创新。无论是纵向的从采购、制造到营销的运营管理链路,还是横向......
  • 熵模型-高斯建模
    参考链接高斯建模https://blog.csdn.net/won_t/article/details/131136591端到端的图像压缩----码率估计目录asfdsadasfdsad......
  • 浅谈为什么重写equals方法,就要必须重写hashcode方法
    在hashmap中是要保证key的唯一,如果新的key放入map中,发现和已有的key相同,那么就要覆盖。那么这个“唯一”是怎么确定的?或者说怎么认为两个key是相同的?那么这里的相同是指内容相同,比如newString("aaa"),newString("aaa"),new了两个字符串,是两个对象,但是内容是相同的,我们认为他们......
  • 浅谈智能充电桩系统设计
    安科瑞张田田摘要:文章设计了一款电动车智能充电系统,以智能充电桩为数据采集终端,将采集到的电压电流等信息上传给服务器,数据库接受到信息后进行分析并同时传输到客服端。该系统实现了安全高效充电、数据分析、公平计费、节能环保等功能,很大地提高了用户体验,能够有效管理和控制电动车......
  • P4948 数列求和
    传送门description给定\(n,a,k\),求\(\sum\limits_{i=1}^na^ii^k\)\(n\leq10^{18}\)\(k\leq2\cdot10^3\)solution\(k\)很小,使用第二类斯特林数处理\(i^k\)得:\(\sum\limits_{i=1}^na^i\sum\limits_{j=0}\begin{Bmatrix}k\\j\end{Bmatrix}......
  • 【笔记】kth - 浅谈前 k 优解问题
    【笔记】kth-浅谈前k优解问题第一次见到这一类的trick是在SDOI2013-淘金,现在才知道这个trick还有一堆扩展。Part0.这类问题的一个通用思路:对于目前考虑到的一个状态\(S\),设\(\operatorname{trans}(S)\)为\(S\)的后继状态集合。首先将最优的状态\(S\)放入......
  • 【转】浅谈调试--赖特
    浅谈调试——赖特何为调试及为什么要调试调试是程序运行结果与期望结果不统一时,在手动计算模拟的前提下编译程序,对比不同,修正语法错误和逻辑错误的过程。这是保证计算机信息系统正确性的必不可少的步骤。运行代码只能得到两种结果:Ac或Wa。但是程序很笨,不能直接告诉你错哪里......
  • 简单了解SSM框架的作用,面试浅谈
    SSM和SSH是比较流行的Web框架,今天主要说下SSM(其实是我不了解SSH,哈哈);话不多说进入正题,SSM主要构成Spring,SpringMVC,Mybatis三大部分组成,分别说一下他们的作用;首先关于框架的概念:框架:在这里特指软件框架,它是我们在实际开发中解决项目需求的技术集合。运用框架可以大大简化我们的代码......
  • 高斯数据库HCNA之双机数据库安装
    一、双机数据库安装1、禁用防火墙及SElinuxsystemctlstopfirewalldsystemctldisablefirewalldsed-i-e's,enforcing,disabled,'/etc/selinux/config2、创建用户groupadddbgrpuseradd-gdbgrp-d/home/omm-m-s/bin/bashommechoredhat|passwd--stdinomm3......
  • clickhouse-配置浅谈
    clickhouse,全称:clickstreamwarehouse,简称:ck.属于LOAP分类下的数据库类型,且为列式数据库。在mac下,安装简单。brewinstallclickhouse如果想下载源码,则去github官网down即可。涉及相关配置的文件,也可以在源码中翻找。举例:server配置文件所属目录: /ClickHouse......