竞赛讨论区 > D题怎么优化?
头像
繁水
发布于 2022-04-05 15:59
+ 关注

D题怎么优化?

#include <bits/stdc++.h>
#define ll unsigned long long 
using namespace std;
const ll N=1e18;
ll ans=1;
map<ll,int> m;  //map让所有2的幂赋1
ll a[100];
int c=0;
void mi2(){//让所有2的幂赋1
	while (ans<=N){
		m[ans]=1;
		a[++c]=ans;
		ans*=2;
	}
}
ll cnt=0;
int main(){
	mi2();
	int T;
	scanf("%d",&T);
	while (T--){
		cnt=0;
		ll n;
		scanf("%lld",&n);
		cnt=0;
		ll N=n;
		if (m[n]==1){//2的幂直接出2*n-1
			printf("%lld\n",2*n-1);
			continue;
		}
		while (n>2){
			while (m[n]!=1){
				n=n/2; 
			}
			cnt+=n;
			n=n+1;
		}
		printf("%lld\n",2*(-cnt+(*upper_bound(a+1,a+c+1,N)))-1);
	}
	return 0;
}
这样写一直超时,但是我大概算了一下也才O(T*log(n))啊,为什么会超时

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐