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 的几乎一模一样。别问,问就是我抄的!

京公网安备 11010502036488号