洛谷题解 P1010 【幂次方】

原题链接: P1010 幂次方 - 洛谷 | 计算机科学教育新生态

分析

看各位大佬都用二进制等高端算法,蒟蒻都不会啊!QAQ只好用了最朴素的递归与模拟。

这里要理清这两点:

  1. 在分解一个数时,不能出现重复的,因为$2^x+2^x=2^{x+1}$。
  2. 分解出来的幂的指数要尽可能的大。

然后,程序的具体思路是:

  1. 先找一个尽可能大的幂。
  2. 特判,将指数为0和1的单独挑出来输出。
  3. 递归指数。
  4. 减去已经找到的幂次方数,返回第一步。

这样说可能有点迷,上代码更简单!

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void dfs(int k)//传入一个数
{
while (k!=0)//如果这个数还没有处理完
{
int t=2,i;//指数为1
for (i=1;t<=k;i++)//指数不断增加,直到当前幂次方已经大于k
t*=2;
i--; t/=2;//因为这时候t已经比k大了,所以指数减一
if (i==0)//如果指数为零
{
cout<<"2(0)";
k-=1;//同k-=t
goto last;
}
if (i==1)//如果指数为一
{
cout<<"2";
k-=2;//同k-=t
goto last;
}
cout<<"2(";
dfs(i);//递归指数
// cout<<i;//可以把这一步取消注释,把上一步进行注释,观察指数未分解时是否正确
cout<<")";
k-=t;//减去已经找到的幂次方数
last:
if (k!=0)
cout<<"+";//如果k没处理完,输出加号
}
}

洛谷题解 P1010 【幂次方】

https://www.cbw2007.tk/articles/luogu-P1010-sol/

作者

CBW2007

发布于

2019-07-12

更新于

2023-01-07

许可协议

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论