题解 - Vijos

2

//初学OI就看到这道题，但是一直不会写
//后来见惯了诡异的神仙递归就觉得这道题简单了。。。
//这道题用递归来写就很容易呀~
#include<iostream>
using namespace std;
void chu(int x)
{
    if(x==0)
     {
        cout<<"0";
        return ;
     }
    int len=-1,a,i,pan=0;
    a=x;
    while(a)
    {
        len++;
        a/=2;
    }
    for(i=len;i>=0;i--)
    {
        if(x&(1<<i))
        {
            if(pan)
             cout<<"+";
            if(i!=1)
            {
                cout<<"2(";
                chu(i);
                cout<<")";
            }
            else
             cout<<"2";
            pan=1;
        }
    }
    return ;
}
int main()
{
    int n;
    cin>>n;
    chu(n);
    return 0;
}

1

aph。 (chenqianrong) LV 10 @ 2 年前

#include<iostream>
using namespace std;

string fun(int n,int i=0,string s=string("")){
    if(n==0)
        return string("0");
    do
        if(n&1)
            s=(i==1?"2":"2("+fun(i)+")")+(s==""?"":"+")+s;//拼接字符串，应题意，要把低次方接在后面
    while(++i,n>>=1);//每次向右移位
    return s;
}
int main(){
    int n; cin>>n;
    cout<<fun(n);
    return 0;
}

1

RP++ (贪吃蛇) LV 8 @ 4 年前

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1002],b[1002],k,t;
void find(int x)
{
    int p=1,q=0;
    if(n!=0)
    {
        int p=1,q=0;
        cout<<"2";
        while(p<=x)
        {
            p=p*2;
            ++q;
        }
        if(q-1==0||q-1==2)cout<<"("<<q-1<<")";
        if(q-1>=3)
        {
            cout<<"(";
            find(q-1);
            cout<<")";
        }
        x=x-p/2;
        if(x>0)
        {
            cout<<"+";
            find(x);
        }
    }
}
int main()
{   
    cin>>n;
    m=n;
    find(n);
    return 0;
}

1

吴哥——传奇 LV 8 @ 7 年前

so water

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

void aha(long long a)
{
    long long k=1,j=-1,e=0;
    if(a==2)
    {
        printf("2");
        return;
    } 
    while(k<a)
    {
        k=k*2;
        j++;
    }
    if(a==k)
        j++;
    else
        k=k/2;
    for(int i=j;i>=0&&k>=1;i--,k=k/2)
    {
        if(a>=k)
        {
            a=a-k;
            if(e==1)
                printf("+");
            else
                e=1;
            printf("2");
            if(i==0&&k==1)
            {
                printf("(0)");
            }
            else if(i>=2&&k>=4)
            {
                printf("(");
                aha(i);
                printf(")");
            } 
        }
    }
    return;
}
int main()
{
    long long a;
    scanf("%lld",&a);
    aha(a);
    return 0;
}

1

hahayang LV 10 @ 7 年前

const
  a:array[0..14] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384);
var
  n:longint;
procedure dfs(n:longint);
var
  i:longint;
begin
  for i:=14 downto 0 do if a[i]<=n then begin
    if i=1 then write(2)
    else if i=0 then write('2(0)')
    else begin
      write('2(');
      dfs(i);
      write(')')
    end;
    dec(n,a[i]);
    if n>0 then write('+')
    else exit
  end;
end;
begin
  read(n);
  dfs(n)
end.

1

学霸wx LV 7 @ 8 年前

简单的递归，不过效率不高
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int n,now;
bool r=0;
void print(int k,int r2=0)
{
if(!k)return;
int step=-1,p=k;
while(k!=0)
{
step++;
k/=2;
}
k=p;
if(r2)cout<<"+";
if(step==1)
{
cout<<"2";
print(k-2,1);
return;
}
if(step==0)
{
cout<<"2(0)";
return;
}
if(step>1)
{
cout<<"2(";
print(step);
cout<<")";
}
if(k-pow(2,step)!=0)print(k-pow(2,step),1);
}
int main()
{
cin>>n;
print(n);
return 0;
}

0

上海娄山 LV 8 @ 3 年前

//flag用于标记输出时前面是否需要加+号
#include<bits/stdc++.h>
using namespace std;
int n;
void dfs(int n,bool flag){
    if(n==0)return;
    if(flag)cout<<"+";
    if(n==2)cout<<"2";
    else if(n==1)cout<<"2(0)";
    //else if(n==0)return;
    else{
        int i;
        for(i=0;;i++){
            if(pow(2,i)>n)break;
        }
        i--;
        if(i==1)cout<<"2";
        else{
            cout<<"2(";
            dfs(i,0);
            cout<<")";
        }
        dfs(n-pow(2,i),1);
    }
}
int main(){
    cin>>n;
    dfs(n,0);
}

0

dzz751593 LV 7 @ 5 年前

#include<iostream>
#include<algorithm>
using namespace std;

void print2(int n){
if(n==1){
cout<<"2(0)";
return;
}
if(n==2){
cout<<'2';
return;
}
int i=0;//指数
int s=2;//用于寻找最接近n的2的幂次方
while(s<=n){
s<<=1;

i++;
} //s=2^(i+1)>n
s>>=1; //s=2^i<=n
if(n==s){//2^i=n
cout<<"2(";
print2(i);
cout<<')';
}else{ //2^i<n
print2(s);
cout<<'+';
print2(n-s);
}
}

int main(){
int n;
cin>>n;
print2(n);
return 0;
}

0

feidaoluoye LV 9 @ 7 年前

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
void dfs(int n)
{
int a[20];
memset(a,0,sizeof(a));
int flag = 0;
int i = 0,j;
while(n>0)
{
a[i++] = n%2;
n/=2;
}
for(i=15;i>=0&&a[i]==0;--i);
for(j=i;j>=0;--j)
if(a[j]==1)
{
if(j>1){
if(flag)
cout<<"+";
cout<<"2(";
dfs(j);
cout<<")";
flag = 1;
}
else if(j==1){
if(flag)
cout<<"+";
cout<<"2";
flag = 1;
}
else{
if(flag)
cout<<"+";
cout<<"2(0)";
}
}
}
int main()
{
int n;
cin>>n;
dfs(n);
return 0;
}

0

slzxwrt LV 8 @ 7 年前

分治
#include<cstdio>

int a[15];
int work(int l,int r,int p)
{
if (l>r) return l-1;
int mid=(l+r)/2;
if (a[mid]==p) return mid;
if (a[mid]<p) return work(mid+1,r,p);
else if (a[mid]>p) return work(l,mid-1,p);
}
void done(int n)
{
int k=work(0,14,n);
if (k>=0 && k<=2)
{
if (k==1) printf("2");
else printf("2(%d)",k);
}
else
{
printf("2(");
done(k);
printf(")");
}
if (n!=a[k])
{
printf("+");
done(n-a[k]);
}
}
int main()
{
int n;
scanf("%d",&n);
a[0]=1;
for (int i=1;i<15;i++)
a[i]=a[i-1]*2;
done(n);
return 0;
}

0

施支林 LV 8 @ 7 年前

Var
n,cf,num:longint;
k:char;

Procedure dfs(x:longint);
Var
num,cf:longint;
Begin
if x<3 then
begin
write(x);
exit;
end;
while x>0 do
begin
num:=1;
cf:=0;
while num*2<=x do
begin
num:=num*2;
inc(cf);
end;
if cf=1 then
begin
if k=')' then
write('+2');
if k='(' then
begin
write('2');
k:=')';
end;
end
else
begin
if k=')' then
write('+2(')
else
write('2(');
k:='(';
dfs(cf);
write(')');
k:=')';
end;
x:=x-num;
end;
End;

Begin
readln(n); k:='(';
while n>0 do
begin
num:=1;
cf:=0;
while num*2<=n do
begin
num:=num*2;
inc(cf);
end;
if cf=1 then
begin
if k=')' then
write('+2');
if k='(' then
begin
write('2');
k:=')';
end;
end
else
begin
if k=')' then
write('+2(')
else
write('2(');
k:='(';
dfs(cf);
write(')');
k:=')';
end;
n:=n-num;
end;
readln;
End.
日常一水题

0

zhvzhh LV 4 @ 7 年前

import java.util.*;
import java.lang.String;
import java.lang.Integer;
import java.util.Scanner;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        System.out.print(Resolve(a));
    
    }
    
    public static String[] tps=new String[]{
                    "2(0)+",
                    "2+",
                    "2(2)+",
                    "2(2+2(0))+",
                    "2(2(2))+",
                    "2(2(2)+2(0))+",
                    "2(2(2)+2)+",
                    "2(2(2)+2+2(0))+",
                    "2(2(2+2(0)))+",
                    "2(2(2+2(0))+2(0))+",
                    "2(2(2+2(0))+2)+",
                    "2(2(2+2(0))+2+2(0))+",
                    "2(2(2+2(0))+2(2))+",
                    "2(2(2+2(0))+2(2)+2(0))+",
                    "2(2(2+2(0))+2(2)+2)+"};
    
    
    public static String Resolve(int n)
    {
        char[] ts=Integer.toBinaryString(n).toCharArray();
        String r="";
        for(int i=0;i<ts.length;i++)
        {
            if(ts[i]=='1')
            {
                r+=tps[ts.length-i-1];
            }
        }
        return r.substring(0,r.length()-1);
    }
}

不知道有没有人这样写过。。。
渣渣小水比，大神们见笑了

0

Stockholm LV 8 @ 8 年前

##这个题由于条件的限制，只需要到2^14即可，然后打个表，比较简单##

上代码
#include<iostream>
#include<algorithm>

using namespace std;
int i,j,m,n;
int h[15]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};
string c[15]={"2(0)","2","2(2)","2(2+2(0))",
"2(2(2))","2(2(2)+2(0))","2(2(2)+2)","2(2(2)+2+2(0))",
"2(2(2+2(0)))","2(2(2+2(0))+2(0))","2(2(2+2(0))+2)",
"2(2(2+2(0))+2+2(0))","2(2(2+2(0))+2(2))","2(2(2+2(0))+2(2)+2(0))",
"2(2(2+2(0))+2(2)+2)"};
int main()
{
freopen("m.in","r",stdin);
freopen("m.out","w",stdout);
int kg=1;
cin>>n;
while(n)
{
for(i=0;i<=14;i++)
if(n<h[i])
break;
if(i)
i--;
if(kg)
{kg=0;}
else
cout<<"+"<<c[i];
n-=h[i];
}
}

评测状态 Accepted
题目 P1597 2的幂次方
递交时间 2017-02-18 19:01:32
代码语言 C++
评测机 ShadowShore
消耗时间 0 ms
消耗内存 736 KiB
评测时间 2017-02-18 19:01:33
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 736 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 736 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 736 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 732 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 732 KiB, score = 10
Accepted, time = 0 ms, mem = 736 KiB, score = 100
为了让同学们更好的了解这个题，我修改了一些东西，导致你复制粘贴大法失效。。。比如输出。。。

Stockholm @ 8 年前

另：感谢@zzzyf的题目：SYT的幂次方

0

205610760 LV 8 @ 8 年前

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
using namespace std;

int n;

void ask(int n){
if(n==2){
putchar('2');
return;
}
if(n<=0){
putchar('0');
return;
}
vector<int>v;
int tot=0;
while(n){
if(n&1)v.push_back(tot);
tot++;
n>>=1;
}
for(int i=v.size()-1;i>=0;i--){
putchar('2');
if(v[i]!=1){
putchar('(');
ask(v[i]);
putchar(')');
}
if(i>0)putchar('+');
}
}

int main(){
scanf("%d",&n);
ask(n);
}

0

我是燕浩波 LV 8 @ 8 年前

为何我递归最后一组数据超时？……
```pascal
program yange;
var
i,j,n:longint;
S:array[0..14] of longint;
procedure once(x:longint);
var
i,j,a,b,y:longint;
begin
repeat
i:=0;
repeat
i:=i+1;
until x<=S[i];
if x<S[i]
then j:=i-1
else j:=i;
a:=S[j];
y:=j;
write('2');
if j>2 then
begin
write('(');
once(y);
write(')');
end
else if j=2
then write('(2)')
else if j=0
then write('(0)');
b:=x-a;
x:=x-a;
if b<>0
then write('+');
until b=0;
end;
begin
readln(n);
for i:=0 to 14 do
S[i]:=1;
for i:=0 to 14 do
for j:=1 to i do
S[i]:=2*S[i];
once(n);
end.

0

lksjg LV 8 @ 9 年前

#include<cstdio>
using namespace std;
void ok(int n)//2(2(2)
{
int x=1,y=0,s=0,h=n;
while(s!=n)
{
x=1,y=0;
while(x<=h)
{
y++;
x=x*2;
}
y--;x=x/2;
if(y==1) printf("2");
else if(y==0) printf("2(0)");
else if(y==2) printf("2(2)");
else {
printf("2(");
ok(y);
printf(")");
}
s=s+x;h=h-x;
if(s!=n) printf("+");
}
}
int main()
{
int n;
scanf("%d",&n);
ok(n);
return 0;
}

0

masnn LV 7 @ 9 年前

var
n:string;
function ch(i1:string):string;
var
o1,t:string;
n,c,i:longint;
begin
c:=1;
val(i1,n);
i:=0;
o1:='';
while true do
begin
if c>n then
break;
c:=c*2;
inc(i);
end;
while c>0 do
begin
if (c<=n)and(c<>2) then
begin
n:=n-c;
if (i<>2)and(i<>0) then
begin
str(i,t);
o1:=o1+'2('+ch(t)+')+';
end
else
if i=2 then
o1:=o1+'2(2)+'
else
o1:=o1+'2(0)+';
end
else
if (c=2)and(c<=n) then
begin
o1:=o1+'2+';
n:=n-c;
end
else
begin
c:=c div 2;
dec(i);
end;
end;
exit(copy(o1,1,length(o1)-1));
end;
begin
readln(n);
n:=ch(n);
writeln(n);
end.

0

TenderRun LV 10 @ 9 年前

#include <iostream>
#include <stdio.h>
using namespace std;
char str[16][150]={
"2(0)",
"2",
"2(2)",
"2(2+2(0))",
"2(2(2))",
"2(2(2)+2(0))",
"2(2(2)+2)",
"2(2(2)+2+2(0))",
"2(2(2+2(0)))",
"2(2(2+2(0))+2(0))",
"2(2(2+2(0))+2)",
"2(2(2+2(0))+2+2(0))",
"2(2(2+2(0))+2(2))",
"2(2(2+2(0))+2(2)+2(0))",
"2(2(2+2(0))+2(2)+2)"
};
int num[17]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
int main()
{
int a,i=14,j;
scanf("%d",&a);
for(i;i>=0;i--)
{
if(a>=num[i])
{
a-=num[i];

printf("%s",str[i]);
break;
}

}
i--;
for(int j=i;j>=0;j--)
{
if(a>=num[j])
{
a-=num[j];

printf("+%s",str[j]);
}
}
printf("\n");
return 0;
}

lambdacat @ 8 年前

绝妙！
唐复之 @ 8 年前

打表
学霸wx @ 8 年前

啪啪啪……鼓掌

0

972964894 LV 9 @ 9 年前

program exercise(input,output);
var n:longint;
procedure print(x:longint);
var i,j:longint;
begin
if x=0 then
begin
write(0);
exit;
end;
while x>0 do
begin
write(2);
i:=x;
j:=0;
while i>1 do
begin
i:=i div 2;
inc(j);
end;
if j<>1 then
begin
write('(');
print(j);
write(')');
end;
x:=x-1 shl j;
if x>0 then
write('+');
end;
end;

begin
readln(n);
print(n);
writeln;
end.

0

wang_yanheng LV 10 @ 9 年前

30行秒杀
#include <stdio.h>
void print(int n){
int i, k;
for(k=0; k<=15 && (n&(1<<k))==0; k++);
for(i=15; i>k; i--){
if(n&(1<<i)){
putchar('2');
if(i != 1){
putchar('(');
print(i);
putchar(')');
}
putchar('+');
}
}
putchar('2');
if(k != 1){
putchar('(');
if(k == 0)
putchar('0');
else
print(k);
putchar(')');
}
}
int main(){
int num;
scanf("%d", &num);
print(num);
return 0;
}

题解

111 条题解

2的幂次方

信息

状态

开发

支持

题解

111 条题解

2的幂次方

信息

状态

开发

支持

还没有账户？

登录