大一训练赛(2019.4.13)【内容：二进制枚举、贪心、DFS】

本次训练共6题，本文附AC代码和题目链接。

nefu 1803 二进制回文

这题注意把n定义成unsigned long long
int的范围为 -2^31 ~ 2^31 - 1
long long的范围为 -2^63 ~ 2^63 - 1
所以本题需要使用unsigned long long (0 ~ 2^64 - 1)

#include <bits/stdc++.h>
using namespace std;
int t,cnt,flag,a[101];
unsigned long long n;//long long会错，因为数据N<2^64
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(cnt=1;n>0;cnt++)
        {
            a[cnt]=n&1;//a数组保存数字n从右到左每一位的二进制值
            n=n/2;
        }//数字n的二进制长度为cnt-1
        flag=0;
        for(int i=1;i<=(cnt-1)/2;i++)
        if(a[i]!=a[cnt-i]){flag=1;break;}
        flag==1?printf("No\n"):printf("Yes\n");
    }
    return 0;
}

nefu 1804 BUFF持续时间

开map记录某个点是否出现，每输入一个时刻x，就扫过区间[x,x+t-1]上的每个点即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,x,ans;
map<ll,ll>a;
int main()
{
    cin>>n>>t;
    while(n--)
    {
        cin>>x;
        for(int i=x;i<=x+t-1;i++)
        if(a[i]==0){a[i]=1;ans++;}
    }
    printf("%lld\n",ans);
    return 0;
}

nefu 1805 史蒂夫的通道1

这题直接模拟即可(看学长的代码用DP写的也行）

#include <bits/stdc++.h>
using namespace std;
int n,ans,flag;
char a[110];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;)
    {
        if(i+3>=n)break;
        flag=0;
        for(int j=3;j>=1;j--)
        {
            if(a[i+j]=='S')
            {flag=1;i=i+j;break;}
        }
        if(flag==0){i=i+3;ans++;}
    }
    if(a[n]=='V')ans++;
    printf("%d\n",ans);
    return 0;
}

nefu 1806 史蒂夫的通道2

这题直接贪心即可，每次尽量都走最远的距离，如果走不了就输出"respawn"。

#include <bits/stdc++.h>
using namespace std;
char a[110];
int n,k,ans,flag;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;)
    {
        if(i>=n)break;
        flag=0;
        for(int j=k;j>=1;j--)
        {
            if(a[i+j]=='S')
            {flag=1;i=i+j;ans++;break;}
        }
        if(flag==0){printf("respawn\n");return 0;}
    }
    printf("%d\n",ans);
    return 0;
}

nefu 1807 次幂

这题有点坑，之前没看清题，“不能找到序列里的另一个数a[j]”，我看成了“能找到”，结果多次WA+TLE整的我直接自闭…
其实并不难，只要处理好枚举的过程即可。开map记录a[i]出现的次数，然后把2的幂次方从小到大依次枚举(枚举到2^31，也就是大于a[i]+a[j]最大值的最小幂次)，让枚举的这些2的幂次减去a[i]，设为tmp，判断tmp是否出现，出现则说明能找到，不符合条件。同时要注意若tmp=a[i]且a[i]的出现次数大于1，也说明能找到，不符合条件。

#include <bits/stdc++.h>
using namespace std;
int n,tmp,ans,flag,a[200010];
map<int,int>vis;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>a[i];vis[a[i]]++;}
    for(int i=1;i<=n;i++)
    {
        flag=0;
        for(int j=0;j<=31;j++)
        {
            tmp=(1<<j)-a[i];
            if(vis[tmp])
            {
                if(tmp!=a[i]){flag=1;break;}//找到了a[j]，并且tmp=a[j]!=a[i]
                if(tmp==a[i]&&vis[a[i]]>1){flag=1;break;}//找到了a[j]，并且tmp=a[j]=a[i]
            }
        }
        if(flag==0)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

nefu 1808 细胞数量-深搜

这题和【nefu 1696 猴群-搜索】重复了，
代码详见我之前写的DFS训练的文章：https://blog.csdn.net/ljw_study_in_CSDN/article/details/88602505