求助,关于时间复杂度

P1001 A+B Problem

qwq___qaq @ 2022-09-25 23:54:00

RT,这是我写的一个倍增的代码:

#include<bits/stdc++.h>
using namespace std;
int s,t,c,a,b;
int main(){
    cin>>a>>b;
    c=a+b;
    if(c>=0){
        while(c){
            t=1;
            while(t*2<=c)
                t*=2;
                s+=t,c-=t;
            }
        cout<<s<<endl;
    } else{
        while(c){
            t=-1;
            while(t*2>=c)
                t*=2;
            s+=t,c-=t;
        }
        cout<<s<<endl;
    }
    return 0;
}

现在只有 TLE 90,T 的那个点是极限数据,但是我感觉这个复杂度应该是没有问题的,是一个 O(\log^2(a+b)) 的复杂度。是复杂度算错了吗?


by Reliauk @ 2022-09-26 00:00:09

@_sto_pengzijunorz t*2 会爆 int


by cmk666 @ 2022-09-26 00:09:12

bzd,但我 O(n) 能过


by NightStriker @ 2022-09-26 07:27:35

@_sto_pengzijunorz

开long long就好了,这年头TLE都能是任何错误了。


by Konjac_16 @ 2022-09-26 08:39:03

@ljp 显然,如果不开 long long,在 while 循环里 t 溢出为负数,则会死循环


by As_Nerve @ 2022-10-03 17:34:36

我不会


by Albatross_LC @ 2022-10-06 16:52:33

long long或


by qianwanlang @ 2022-10-21 22:04:03

这道题分明很简单,

为什么你做的这么简单难?


by lyy120331 @ 2023-02-19 10:34:06

@qianwanlang 对呀还行吧


|