牛客2020跨年场 BCE

B:https://ac.nowcoder.com/acm/contest/9854/B
题意：给你两个长度为n的序列a和b，你现在要对a中所有的数求和。同时对于b中每个元素，你可以把它加/减到a的序列和中，当然也可以不进行加/减。
现在要你输出a的序列和在模y下的最大值。
思路：看到y的范围不难想到dp，我们这里采用二维的形式，dp[i][j]表示第i个位置可以取到的数字大小。如此，状态转移方程也就很好想了。

    if(dp[i-1][j])//有才能转移
        {
            dp[i][(j+a[i])%y]=1;
            dp[i][(j+a[i]+b[i])%y]=1;
            dp[i][(j+a[i]-b[i])%y]=1;
        }

至此代码也就写出来了。

#include<bits/stdc++.h>
using namespace std;
int n,y;
int a[100005],b[100005];
bool dp[100005][105];
int main()
{
    cin>>n>>y;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    dp[1][a[1]]=1;//其实这里为什么不对a[1] 进行取模我是不明白的。
    dp[1][(a[1]+b[1])%y]=1;
    dp[1][(a[1]-b[1])%y]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=101;j++)//前i个数里和为j的情况
        {
            if(dp[i-1][j])//有才能转移
            {
                dp[i][(j+a[i])%y]=1;
                dp[i][(j+a[i]+b[i])%y]=1;
                dp[i][(j+a[i]-b[i])%y]=1;
            }
        }
    }
    for(int i=101;i>=0;i--)
    {
        if(dp[n][i])
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

C：https://ac.nowcoder.com/acm/contest/9854/C
题意：给你一个长度为n的序列，要你输出与它们每个数都互质的最小值。
思路：互质当且仅当gcd(a, b) = 1。由互质定义不难发现如果1不存在序列当中，那么输出1就好了。当1存在序列当中时，就要输出一个不是序列中任何数的因数的质数。为什么会是一个质数，因为质数与质数之间肯定是互质的。
现在问题就变成如何找到1-1e5之间的质数和如何对序列中的每个数进行质数分解了。直接使用质数筛就可以解决目前的问题了。至此代码也就出来了。

//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int t,n,m;
int prime[maxn] = {0};
int num_prime = 0;    
int isNotPrime[maxn] = {1, 1};   
bool tong[maxn]={0};
bool vis[maxn]={0};
int a[maxn];
void shai()    
{     
     for(int i = 2 ; i < maxn ; i ++)       
       {            
        if(! isNotPrime[i])  
        {                      
             prime[num_prime ++]=i;     
         }               
        for(int j = 0 ; j < num_prime && i * prime[j] <  maxn ; j ++)
        {                     
            isNotPrime[i * prime[j]] = 1;  
              if( !(i % prime[j] ) )       
                break;           
        }         
    }        
    return ;   
}  
void fenjie(int m)
{
    for(int i=0;i<=num_prime;i++)
    {
        while(m%prime[i]==0&&m!=0)
        {
            m/=prime[i];
            vis[prime[i]]=1;
        }
        if(m<prime[i])
        {
            break;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        tong[a[i]]=1;
    }
    if(tong[1]==0)
    {
        cout<<1<<endl;
        return 0;
    }
    shai();
    for(int i=0;i<n;i++)
    {
        fenjie(a[i]);
    }
    for(int i=0;i<=num_prime;i++)
    {
        if(vis[prime[i]]==0)//这个质数就是不是序列中数的因子的最小质数
        {
            cout<<prime[i]<<endl;
            break;
        }
    }

     return 0;
}

E:https://ac.nowcoder.com/acm/contest/9854/E
题意：给你一个因变量，要你输出自变量。注意的是变量的范围。
思路：首先打表发现 ,那么就知道了当n>120时，无解。接着对式子的值进行打表发现，对于 其函数值为 , 的函数值是 , 的函数值是 ,至此答案也就出来了。
对了，一定要开longlong，不开longlong的我从早改到晚。

//team lots of balloons
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int t,n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n==1)
        {
            cout<<1<<endl;
            continue;
        }
        if(n>120)
        {
            cout<<-1<<endl;
            continue;
        }
        if(n & 1 )
        {
            n++;
            n=n>>1;
            cout<<(1ll<<(n-1))+2<<endl;
        }
        else
        {
            n=n>>1;
            cout<<(1ll<<(n-1))+1<<endl;


        }
    }
     return 0;
}

写在最后：
B题第17行我也没弄明白，代码写出来和wqy_03 的几乎一模一样。别问，问就是我抄的！