牛客算法周周练2

A. 相反数

签到题。

直接将原数分解后，重组即可。

#include<bits/stdc++.h>
using namespace std;
int n,b;
void solve(int x){
    while(x){
        b=b*10+x%10;
        x/=10;
    }
}
int main(){
    scanf("%d",&n);
    solve(n);
    printf("%d",b+n);
    return 0;
}

B. Music Problem

题目大意：

判断一个序列里是否有子序列的和能够被 $3600$ 整除。

对于这种序列的题目， $dp$ 八成都是可以做的。

$f[i]$ 表示是否拥有在模 $3600$ 意义下和为 $i$ 的子序列。

$temp[i]$ 表示讨论到当前情况是否拥有在模 $3600$ 下和为 $i$ 的子序列。 $($ 也可以理解成 $temp[]$ 是 $f[]$ 的上一版本 $)$

所以就有 $\begin{cases} f[j]=1 & \text{j==0}\\ f[j+a[i]]=1& \text{temp[j]>0} \end{cases}$

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+5;
const int MAX_V=4000 + 5;
int t,n,a[MAX_N];
bool f[MAX_V],temp[MAX_V];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(f,0,sizeof(f));
        memset(temp,0,sizeof(temp));
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            a[i]%=3600;
        }
        for(int i=1;i<=n;i++){
            if(f[0]) break;
            f[a[i]]=1;
            for(int j=1;j<3600;j++){
                if(temp[j]) f[(a[i]+j)%3600]=1;
                if(f[0]) break;
            }
            /*也可以写成
            for(int j=0;j<3600;j++) temp[j]=(f[j] || temp[j]) ? 1 : 0;
            或者
            for(int j=0;j<3600;j++) temp[j]=f[j]>temp[j]?f[j]:temp[j];
            */
            for(int j=0;j<3600;j++) temp[j]=f[j];
        }
        printf((f[0]?"YES\n":"NO\n"));
    }
    return 0;
}

C. 完全平方数

这道题根据题意，再观察一下样例，发现 $[1,1000000000]$ 中最多有 $31622$ 个完全平方数，但观察数据范围， $l$ 可以为0，所以最多有 $31623$ 个完全平方数，于是我们可以打一个暴力出来，时间复杂度 $O(31623n)$

#include<bits/stdc++.h>
using namespace std;
int n;
long long l,r;
int main(){
    scanf("%d",&n);
    while(n--){
        int ans=0;
        scanf("%lld%lld",&l,&r);
        for(int i=(int)sqrt(l);i<=31622;i++){
            if(i*i>=l && i*i<=r) ans++;
            if(i*i>r) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

现在，就是想办法优化暴力，使其变成正解。

我们可以先预处理出 $[0,1000000000]$ 中的所有的完全平方数 $31623$ 个。

因为单调，所以可以二分查找出第一个大于等于 $l$ 的完全平方数，二分查找出第一个大于 $r$ 的完全平方数，在将其下标相减，即可得到答案。

时间复杂度 $O(30n)$

#include<bits/stdc++.h>
using namespace std;
int n;
long long l,r,a[32005];
int main(){
    scanf("%d",&n);
    for(int i=0;i<=31622;i++) a[i]=i*i; 
    while(n--){
        scanf("%lld%lld",&l,&r);
        int L=lower_bound(a,a+31623,l)-a;
        int R=upper_bound(a,a+31623,r)-a;
        printf("%d\n",R-L);
    }
    return 0;
}