AtCoder Beginner Contest 340 C - Divide and Divide【打表推公式】

article/2024/2/25 20:53:41

原题链接:https://atcoder.jp/contests/abc340/tasks/abc340_c

Time Limit: 2 sec / Memory Limit: 1024 MB

Score: 300 points

问题陈述

黑板上写着一个整数 N。
高桥将重复下面的一系列操作,直到所有不小于2的整数都从黑板上移除:

  • 选择写在黑板上的一个不小于2的整数x。
  • 擦去黑板上出现的一个x。然后,在黑板上写下两个新的整数 ⌊x/2​⌋ 和 ⌈x/2​⌉。
  • 高桥必须支付 x 日元才能完成这一系列操作。

这里,⌊a⌋表示不大于a的最大整数,⌈a⌉表示不小于a的最小整数。

当不能再进行操作时,高桥支付的总金额是多少?
可以证明,无论操作的顺序如何,他支付的总金额是不变的。

Constraints

  • 2≤N≤10^17

Sample Input 1Copy

3

Sample Output 1Copy

5

样本输出 1

下面是高桥如何执行操作的示例:

  • 最初,黑板上写着一个 3。
  • 他选择了 3。他支付了3日元,擦去了黑板上的一个3,并在黑板上写下了⌊3/2⌋=1和⌈3/2⌉=2
  • 黑板上写着一个2和一个1。
  • 他选择了2。他支付了2日元,擦去了黑板上的一个2,并在黑板上写下了⌊2/2⌋=1和⌈2/2⌉=1
  • 黑板上写了三个1。
  • 由于所有不小于2的整数都已从黑板上擦除,因此过程结束。

高桥为整个过程总共支付了3+2=5日元,因此打印5。

Sample Input 2Copy

340

Sample Output 2Copy

2888

Sample Input 3Copy

100000000000000000

Sample Output 3Copy

5655884811924144128

解题思路:

首先这个题目n非常大,肯定不能暴力,像这种题要么就是有什么规律,要么就是可以打表直接推出计算公式的,这个题目我当时是打表然后直接推出了计算公式做出来的,这个题目不难,但是我觉得有点意思,所以这里来说一下我的思路,我看了榜上有很多D,E都做出来了但是这个题目没做出来的,D纯纯最短路模板题,然后E区间维护(树状数组,线段树)模板题,没什么意思,这个C比D,E有意思多了,下面我贴一个我打表的图:

第一个图n=10,下面红色框框里面的每一行的和都是10,其他的图也是如此,这里我只列举了几个数据,那么对于任意的n的红色框框中会有几行呢,多打表几个数据会发现,n有几个因子2,那么就会有几行,那么这一部分的计算方式就是n*(row),row表示n的因子2的个数,那么对于红色框框的下面这一部分(也就是最后一行)怎么计算呢,我们可以知道的是最后一行有一部分1和一部分2,根据题意1属于无效数据,所以我们只需要关心最后一行有多少个2即可,实际上下面还有一行全是1,只是1是无效数据,这一行我就没列举出来了,最后一行的2实际上就是在一部分1上面加1,由于n的所有因子2在上面红色框操作结束之后到最后一行都会变成1,在最后一行1上面加1,实际上就是n除去所有因子2之后的余数,假设n有k个因子2,那么余数r=n-(2^k),那么这一部分会让r个1变为2,会有r*2的贡献,这一部分的计算方式就是r*2,那么总的计算公式就是n*row+r*2。

时间复杂度:计算n有多少个因子2,时间为O(logn)。

空间复杂度:O(1)。

cpp代码如下:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;
typedef long long LL;
LL n;
int main()
{cin >> n;LL v = 2;LL ans = 0;  while (v <= n){ans += n;  //有多少个因子2就加多少个nv *= 2;}v /= 2; //上面求出来的是大于n的最小的2的幂,这里除以2就是小于等于n的最大的2的幂ans += 2ll * (n - v); //n-v就是余数了cout << ans << endl;return 0;
}

http://www.ngui.cc/article/show-1899205.html

相关文章

浅析Linux追踪技术之ftrace:Event Tracing

文章目录 概述使用Event Tracing使用set_event接口使用enable接口 Event配置Event formatEvent Filtering过滤规则设置过滤器 Event TriggerTrigger语法 Trace marker相关参考 概述 Event Tracing&#xff08;事件追踪&#xff09;利用在内核代码中加入的各种Tracepoint&#…

C++ 堆排序

C 堆排序 堆排序是一种基于二叉堆数据结构的排序算法&#xff0c;其原理如下&#xff1a; 构建最大堆&#xff1a;将待排序的数组看作一个完全二叉树&#xff0c;并通过调整节点的位置构建一个最大堆。最大堆满足每个父节点的值都大于或等于其子节点的值。构建最大堆的过程可以…

猫头虎分享:Win11系统家庭版组策略编辑器怎么打开? Windows11家庭版没有gpedit.msc如何解决?

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

智胜未来,新时代IT技术人风口攻略-第一版(弃稿)

文章目录 抛砖引玉 鸿蒙生态小科普焦虑之下 理想要落到实处校园鼎力 鸿蒙发展不可挡培训入场 机构急于吃红利企业布局 鸿蒙应用规划动智胜未来 技术人风口来临 鸿蒙已经成为行业的焦点&#xff0c;未来的发展潜力无限。作为一名程序员兼UP主&#xff0c;我非常荣幸地接受了邀请…

Android 10.0 锁屏壁纸 LockscreenWallpaper

前言 一、设置壁纸 通过系统设置进行锁屏壁纸和桌面壁纸的设置。 Setting 部分的代码&#xff1a; packages/apps/WallpaperPicker2/src/com/android/wallpaper/module/DefaultWallpaperPersister.java private int setStreamToWallpaperManagerCompat(InputStream inputStre…

算法-3-基本的数据结构

单双链表 1.单链表双链表如何反转 import java.util.ArrayList; import java.util.List;public class Code01_ReverseList {public static class Node {public int value;public Node next;public Node(int data) {value data;}}public static class DoubleNode {public int…

spring boot整合cache使用Ehcache 进行数据缓存

之前的文章 spring boot整合 cache 以redis服务 处理数据缓存 便捷开发 带着大家通过spring boot整合了 cache 缓存 那么 我们就来说说 其他服务的缓存 而spring boot默认的缓存方案就是 cache 用simple模式 spring boot的强大在于它的整合能力 它将其他缓存技术整合 统一了接…

KY141 最大连续子序列

最长连续子序列和&#xff0c;区间DP ti #include<bits/stdc.h>using namespace std;int n, a[10010]; int res1, res2, ans; int dp[10010];int main() {while(cin>>n && n){memset(dp, 0, sizeof dp);bool f 1;for(int i 0; i < n; i ){cin>&g…

【Tauri】(2):使用Tauri应用开发,使用开源的Chatgpt-web应用做前端,使用rust 的candle做后端,本地运行小模型桌面应用

视频演示地址 https://www.bilibili.com/video/BV17j421X7Zc/ 【Tauri】&#xff08;2&#xff09;&#xff1a;使用Tauri应用开发&#xff0c;使用开源的Chatgpt-web应用做前端&#xff0c;使用rust 的candle做后端&#xff0c;本地运行小模型桌面应用 1&#xff0c;做一个免…

政安晨:在Jupyter中【示例演绎】Matplotlib的官方指南(二){Image tutorial}·{Python语言}

咱们接着上一篇&#xff0c;这次咱们讲使用Matplotlib绘制图像的简短尝试。 我的这个系列的上一篇文章在这里&#xff1a; 政安晨&#xff1a;在Jupyter中【示例演绎】Matplotlib的官方指南&#xff08;一&#xff09;{Pyplot tutorial}https://blog.csdn.net/snowdenkeke/ar…