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

2024-02-13 19:36

本文主要是介绍AtCoder Beginner Contest 340 C - Divide and Divide【打表推公式】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题链接: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;
}

这篇关于AtCoder Beginner Contest 340 C - Divide and Divide【打表推公式】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/706428

相关文章

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

uva 10916 Factstone Benchmark(打表)

题意是求 k ! <= 2 ^ n ,的最小k。 由于n比较大,大到 2 ^ 20 次方,所以 2 ^ 2 ^ 20比较难算,所以做一些基础的数学变换。 对不等式两边同时取log2,得: log2(k ! ) <=  log2(2 ^ n)= n,即:log2(1) + log2(2) + log2 (3) + log2(4) + ... + log2(k) <= n ,其中 n 为 2 ^

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

JavaEE7 Servlet 3.1(JSR 340)规范中文版

http://www.iteye.com/news/27727-jinnianshilongnian     Jave EE 7中的部分规范已正式获得批准通过,其中包括JSR340 Java Servlet 3.1规范,去年翻译了该规范,在此分享出来,希望对某些朋友有所帮助,不足之处请指正。   点击直接下载    在线版目录   Servlet3.1规范翻译

二维旋转公式

二维旋转公式 ros的tf工具包可以很方便的实现任意坐标系之间的坐标转换。但是,如果只是想简单的测试想法,而又不想编写过于庞杂的代码,考虑自己写二维旋转的函数。而与二维旋转问题对偶的另一个问题便是二维坐标系旋转变换。这两个问题的形式基本一样,只是旋转的角度相差一个负号。就是这个容易搞混,所以做个笔记,以备查用。 1. 二维旋转公式(算法) 而(此文只针对二维)旋转则是表示某一坐标点 ( x

word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决

word转PDF后mathtype公式乱码以及图片分辨率降低等一系列问题|完美解决 问题描述 最近在投一篇期刊论文,直接提交word文档,当时没有查看提交预览,一审审稿意见全是:公式乱码、公式乱码、乱码啊!!!是我大意了,第二次提交,我就决定将word文档转成PDF后再提交,避免再次出现公式乱码的问题。接着问题又来了,我利用‘文件/导出’或‘文件/另存为’的方式将word转成PDF后,发现公式