题解

132 条题解

  • 2
    @ 2017-03-02 20:02:59

    状态 耗时 内存占用

    #1 Accepted 0ms 65.957MiB
    #2 Accepted 0ms 65.949MiB
    #3 Accepted 0ms 65.957MiB
    #4 Accepted 0ms 65.953MiB
    #5 Accepted 0ms 65.957MiB
    #6 Accepted 0ms 65.957MiB
    #7 Accepted 15ms 65.949MiB
    #8 Accepted 15ms 65.961MiB
    #9 Accepted 15ms 65.957MiB
    #10 Accepted 0ms 65.961MiB
    ```c++
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    #include <cstring>
    #include <iostream>
    #include <string>
    #include <map>
    #include <ciso646>
    #include <stack>
    using namespace std;

    int dp[17000000];

    int ans;
    int n, i;

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

    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    for (i = 4;i <= n;i++)
    {
    if (i%3!=0)
    dp[i] = dp[i / 3+1] + 1;
    else dp[i] = dp[i / 3] + 1;

    }
    dp[1] = 0;
    printf("%d", dp[n]);

    system("pause");

    return 0;
    }

    
    这道题无疑是数据太弱了,我手算了整整一页纸,题解这一页的代码基本都有大大小小的漏洞
    首先连续除以三那个肯定是错的,然后有人提出来说n=n/3+n%3的递推式,但是这个递推式本身是错误的,因为在n=3k+2的情况下,最优解应该是k,k+1,k+1,在那个递推式情况下就会变成k,k,k+2,这样最优解就变成了a[k+2]+1而不是a[k+1]+1.所以那个递推式写的程序连样例都过不去的。然后唯一一个用dp的pascal代码的问题在于a[1]初始化成了1,就是说整个递推式是好运过去的。
    
    下面说说我的想法
    对于3k的情况毫无疑问答案是a[k]+1,因为分成3个k称一次之后就跟k的情况相同
    对于3k+1和3k+2,分别分成k,k,k+1和k,k+1,k+1,运气最差的情况就是那个重的在k+1的堆里,那么答案就是a[k+1]+1.
    
    这道题的数据是越小越容易检测出程序的bug,当数变大的时候所有错误的解法都能得到正确的结论,因为a[k],a[k+1],a[k+2]只有在k很小的时候才会不同
    
    
    
    如果还有什么bug欢迎探讨。。。。我是菜鸟,大牛勿喷
    
  • 1
    @ 2019-06-03 19:53:54

    每次分3堆,如果天平一样重,就说明在天平外的堆中,否则在天平重的那堆上。
    本质上求log3(n)的向上取整。精度问题请用long double。

    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    long double n;
    
    int main()
    {
        cin>>n;
        int ans=0;
        ans=ceil(log(n)/log(3));
        cout<<ans<<endl;
        return 0;
    }
    
  • 1
    @ 2019-02-04 16:03:45

    数学题,很简单。(大佬们可以200秒切掉的)

    其实就是求log3(n);

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    int n;
    int main() {
        scanf("%d",&n);
        int cnt=0;
        while (n) {
            n/=3;
            cnt++;
        }
        printf("%d\n",cnt);
        return 0;
    }
    
  • 1
    @ 2018-09-08 16:00:12
    #include <stdio.h>
    
    int calc(int x) {
        if (x < 4)
            return 1;
        return calc(x / 3 + (x % 3 != 0)) + 1;
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        printf("%d", calc(n));
    }
    
  • 0
    @ 2019-07-25 10:32:21

    #include <iostream>
    using namespace std;
    int main()
    {
    int n,m,i,j;
    cin>>n;
    j=1;
    for(i=1;i<n-1;i++) {j=j*3;if(n>j&&n<=j*3) {m=i+1;break;}}
    if(n<=3) m=1;
    cout<<m;
    return 0;
    }

  • 0
    @ 2017-08-19 23:25:38

    其实这道题可以是分治
    不考虑整数的划分
    二分搜索的思想:每次把n个球分成两份,然后取重的一份,再分,再取...最后得到的就是重球,而称了大约log2(n)次
    然而答案大约是log3(n)次,这就考虑n=3的情况
    。而n=3时,若称出平衡则第三个是重球,若称出不平衡显然重的就是要找的球,所以只用称一次
    所以推广到多个时,每次分成三份就知道重球一定在其中的某一份,就是三分

    #include<cstdio>
    int qpow(int x,int n)
    {
        int ret=1;
        while(n)
        {
            if (n&1) ret*=x;
            x*=x,n>>=1;
        }
        return ret;
    }
    int main()
    {
        int n,ans;
        scanf("%d",&n);
        for (ans=0;qpow(3,ans)<n;ans++);
        printf("%d",ans);
    }
    
    
  • 0
    @ 2017-07-13 15:19:56

    小哥,其实不需要用dp啊。

    #include<iostream>
    using namespace std;
    
    int n;
    
    int Calc (int num) {
        
        if (num==1) return 0;
        else if (num==2||num==3) return 1;
        else
          if (num%3==0) return Calc(num/3)+1;   
            else return Calc(num/3+1)+1;
        
    } 
    
    int main () {
        
        cin>>n;
        cout<<Calc(n)<<endl;
        
      return 0; 
        
    } 
    
  • 0
    @ 2017-04-28 20:50:08

    小学数学书原题!
    规律:3^x<n<=3^(x+1)时
    ans=x+1

  • 0
    @ 2017-03-02 02:09:27

    #include <stdio.h>

    int main()
    {
    int n,m=0;
    scanf("%d",&n);
    while(n>3)
    {
    n=n/3+n%3;
    m++;
    }if(n!=1)m++;
    printf("%d",m);
    return 0;
    }

  • 0
    @ 2016-10-05 20:49:29
    var
      n,t:longint;
    begin
      readln(n);dec(n);
      while n<>0 do
      begin
        n:=n div 3;
        inc(t);
      end;
      writeln(t);
    end.  
    
  • 0
    @ 2016-10-05 20:48:59

    ''' pascal
    var
    n,t:longint;
    begin
    readln(n);dec(n);
    while n<>0 do
    begin
    n:=n div 3;
    inc(t);
    end;
    writeln(t);
    end.

    '''

  • 0
    @ 2016-08-28 12:01:47

    ###**water**
    c++
    #include <cstdio>
    int main() {
    int n,ans = 0;
    scanf("%d",&n);
    while (n) n /= 3,ans++;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2016-08-25 23:06:04

    楼下的真长!厉害!!!
    #include<iostream>
    using namespace std;
    int main()
    {
    int n,s;
    cin>>n;
    s=0;
    do{
    n=n/3;
    s++;
    }while(n!=0);
    cout<<s;
    return 0;
    }
    真是水!!!

  • 0
    @ 2016-08-02 18:50:31
    #include <iostream>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <vector>
    #include <queue>
    #include <bitset>
    
    using namespace std;
    typedef long long lg;
    #define min(a,b) (a>b?b:a)
    #define max(a,b) (a>b?a:b)
    
    lg n;
    
    lg f(lg n)
    {
        //cout<<n<<endl;
        if(n==2||n==1||n==3) return 1;
        if(n&1) n--;
        int t=double(n)/3.0+0.5;
        return f(max(t,n-t-t))+1;
    }
    
    int main()
    {
        ios::sync_with_stdio(0);
        cin>>n;
        cout<<f(n);
        return 0;
    }
    
  • 0
    @ 2015-08-03 14:49:33

    var
    n:longint;
    s1,s2,t:longint;
    begin
    read(n);
    if n<=3 then begin writeln(1); halt; end;
    s1:=3; s2:=9;
    t:=2;
    while true do
    begin
    if (n>s1)and(n<=s2) then begin writeln(t); halt; end;
    s1:=s1*3; s2:=s2*3; t:=t+1;
    end;
    end.

    • @ 2015-08-03 14:51:01

      应该是
      s1:=s1*3; s2:=s2*3;
      可能是粘贴的时候出错了。

  • 0
    @ 2015-02-07 19:54:56

    1.这道题只能说数据非常弱。很多错误的代码都能通过。下面这个就是其中之一:
    #include<iostream>
    using namespace std;
    int main()
    {
    long n, total = 0;
    cin >> n;
    while(n > 0)
    {
    n /= 3;
    total ++;
    }
    cout << total << endl;
    return 0;
    }
    2.这道题描述非常不好:最少称几次,当然是一次了。
    应该说成:让绝顶聪明之人去称量,最多称几次;
    或者说:绝顶聪明之人在点特别背的情况下称几次才能找到那个球。
    3.正确答案如下:
    int f(int n){
    if (n == 1)return 0;
    if(n==2)return 1;
    return f(n / 3+n%3) + 1;
    }
    把球分成3堆才可以,毕竟三分要比二分快很多。
    其次,怎样分成三堆:当然是尽量的平均了。也就是说:天平上两边各有n/3个球,天平下边还剩下(n/3+n%3)个球。
    最后,因为要考虑最坏的情况:当然是破球在最大的那一堆里了。也就是(n/3+n%3).
    这显然与很多除3到0的答案不一样。

  • 0
    @ 2014-08-03 15:00:35

    30题~~~

    记录信息
    评测状态 Accepted
    题目 P1361 天平称量
    递交时间 2014-08-03 14:59:44
    代码语言 C++
    评测机 VijosEx
    消耗时间 30 ms
    消耗内存 272 KiB
    评测时间 2014-08-03 14:59:50
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 272 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 272 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 272 KiB, score = 10
    Accepted, time = 30 ms, mem = 272 KiB, score = 100

  • 0
    @ 2014-03-20 19:35:16

    测试数据 #0: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 732 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    Accepted, time = 15 ms, mem = 732 KiB, score = 100

    var n,k:longint;
    begin
    readln(n);k:=0;
    while n<>0 do begin n:=n div 3;inc(k);end;
    writeln(k);
    end.
    6行秒杀 仅供参考

    • @ 2014-03-20 19:35:46

      抱歉 没想到 发上去就这样了 请大家用;来分句吧!!!
      sorrysorrysorrysorrysorrysorrysorrysorrysorry
      sorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorrysorry

  • 0
    @ 2013-11-08 20:11:18

    var n,m:qword;
    ans:longint;
    begin
    read(n);
    m:=1;
    for ans:=1 to 30000 do
    begin
    m:=m*3;
    if m>=n then
    begin
    write(ans);
    halt;
    end;
    end;
    end.

  • 0
    @ 2013-08-19 15:44:26

    其实用log3的解是错的,但却AC了.................
    wrong:input 3
    output 2
    right: input 3
    output 1
    好像没有设计这种数据...

信息

ID
1361
难度
2
分类
其他 | 数学 点击显示
标签
(无)
递交数
2118
已通过
1298
通过率
61%
被复制
2
上传者