本文主要是介绍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【打表推公式】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!