wgzs

AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1010];
int poww(int x,int y){
	int res=1;
	while(y){
		if(y&1) res*=x;
		x*=x;
		y>>=1; 
	}
	return res;
}
void init(){
	for(int i=1;i<=1000;i++) a[i]=1e18; 
	a[1]=1;
	for(int i=1;i<=1000;i++){
		int j=1;
		while(poww(2,j)<=a[i-j]&&j<=i) j++;
 		int t=0;
		while(j<=i){
		 	if(poww(2,j)-1+a[i-j]>a[i]) break; 
			else a[i]=min(a[i],poww(2,j)-1+a[i-j]);
			j++;
		}
//		cout<<i<<" "<<a[i]<<endl; 
	}
}
signed main(){
	init();
	int t;
	cin>>t;
	while(t--){
		int x;
		cin>>x;
		cout<<a[x]<<endl;
	}
}

wa代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1010];
void init(){
	for(int i=1;i<=1000;i++) a[i]=1e18; 
	a[1]=1;
	for(int i=1;i<=1000;i++){
		int j=1;
		while((1<<j)<=a[i-j]&&j<=i) j++;
 		int t=0;
		 while(j<=i){
		 	if((1<<j)-1+a[i-j]>a[i]) break; 
			else a[i]=min(a[i],(1<<j)-1+a[i-j]);
			j++;
		}
//		cout<<i<<" "<<a[i]<<endl; 
	}
}
signed main(){
	init();
	int t;
	cin>>t;
	while(t--){
		int x;
		cin>>x;
		cout<<a[x]<<endl;
	}
}

只是将位移运算改成了快速幂为什么就一个AC 一个WA 呢