建议二分查找来做,时间复杂度小,不会超时,代码也不用写很多
by _d_h_f @ 2023-11-18 13:18:33
@[_d_h_f](/user/1057109)
不会二分…………
by Huangzy2011 @ 2023-11-18 13:24:50
@[Huangzy2011](/user/1058191) 这道题的二分板子
```cpp
int chk(long long x){
x--;
if(!x)
return 1;
long long l=1,r=1e9;
while(l<=r){
long long mid=l+r>>1;
if(mid*(mid+1)/2==x)//查得到(即位置是一)返回1
return 1;
else if(mid*(mid+1)/2<x)//查到比他更小的就要往大的去查
l=mid+1;
else
r=mid-1;
}
return 0;
}
```
不开 $long long$ 大数据过不了
by _d_h_f @ 2023-11-18 13:29:35
@[_d_h_f](/user/1057109)
然后呢 ?
by Huangzy2011 @ 2023-11-18 13:33:12
用了二分还不行```
#include<bits/stdc++.h>
using namespace std;
long long n,a[10000005];
int x,l,r,mid,t=0,cnt=1,b[1500002];
int main(){
cin>>n;
a[t++]==1;
for(int i=2;i<1e9;i+=cnt){
cnt++;
a[t++]=i;
}
for(int i=1;i<=n;i++){
cin>>x;
l=1;
r=t;
while(l<=r){
mid=(l+r)/2;
if(a[mid]==x)
break;
else if(a[mid]>x)
r=mid-1;
else
l=mid+1;
}
if(a[mid]==x)
b[i]=1;
else
b[i]=2;
}
for(int i=1;i<=n;i++){
if(b[i]==1)
cout<<1<<endl;
if(b[i]==2)
cout<<0<<endl;
}
return 0;
}
```
by Huangzy2011 @ 2023-11-25 14:58:49