牛客练习赛60 (前四题)

A

让求一个和式的值，按照和式内容模拟要两个for，n^2复杂度会TLE，所以显然是不可取的
那么因为是位运算& 所以我们考虑去按位算贡献，对于每一位，我们会进行
k*(k-1)次计算也就是排列数A(k,2) 那么该位对答案的贡献就是就是(1<<i) * k * (k-1) 其中k为该位上为1的个数
所以存下来每个数的每一位1的个数 (因为只有1&1才能对答案有贡献)
然后遍历每一位计算贡献的值即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
ll a[100005];
ll q[65];
int main()
{
   int n;cin>>n;
   ll sum=0;
   for(int i=1;i<=n;i++) {
      cin>>a[i],sum+=a[i];
       for(int j=0;j<64;j++){
           if((a[i]>>j)&1) q[j]++;
       }
   }
   for(int i=0;i<64;i++){
      // cout<<i<<" "<<q[i]<<endl;
       sum+=q[i]*(q[i]-1)*(1ll<<i);
   }
   cout<<sum<<endl;
   return 0;
}

B

让计算三角形的周长，这里的周长指的是曼哈顿距离，因为三角形每次是选择三个点

那么也就是每两个点之间的距离会被选中n-2次
n只有1e3 所有直接两个for暴力计算两个点之间的曼哈顿距离乘上n-2即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
pall a[1005];
ll mod=998244353;
int main()
{
   int n;cin>>n;
   for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
   ll sum=0;
   for(int i=1;i<=n;i++){
       for(int j=i+1;j<=n;j++){
           sum=(sum+((n-2)*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y))%mod)%mod)%mod;
       }
   }
   cout<<sum<<endl;
   return 0;
}

C

是个dp
考虑一个二维dpdp[i][j]表示以i结尾的长度位j的合法的方案数
因为我们要去除那些重复的所以拉一个二维数组 q[i][j]表示当前位置为i的下一个字符为j的位置
这样可以不会多算了也就是满足题中的要求
那么转移方程容易得到 dp[id][j+1]=dp[id][j+1]+dp[i][j] 其中id为i的下一个字符的位置
初始状态就是dp[0][0]=1
复杂度n * n * 26

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
ll x,y;
ll mod=1e9+7;
ll dp[1005][1005];
ll q[1005][130]={0};
char s[1005];
int main()
{
   ll n,kk;
   cin>>n>>kk;
   cin>>s+1;
   dp[0][0]=1;
   for(int i=0;i<n;i++){
       for(int j=i+1;j<=n;j++){
           if(q[i][s[j]]==0) q[i][s[j]]=j;
       }
   }
   for(int i=0;i<n;i++){
       for(int j=0;j<=i;j++){
           if(dp[i][j]!=0){
               for(int k='a';k<='z';k++){
                   int id=q[i][k];
                   if(id!=0) dp[id][j+1]=(dp[id][j+1]+dp[i][j])%mod;
               }
           }
       }
   }
   ll ans=0;
   for(int i=kk;i<=n;i++) ans=(ans+dp[i][kk])%mod;
   cout<<ans<<endl;
   return 0;
}

D

第一眼看到就是exgcd跑不了
因为是个不定方程嘛

然后题意已经说了保证有解而要求的是ax+by+cz=k的一组解(x,y,z)
exgcd是解决二元不定方程的，所以我们去枚举一下a的值，然后得到了by+cz=k-ax
我们去计算(k-ax)%gcd(b,c) 是不是为0 为0就说明了这个不定方程有解
然后跑一遍exgcd 让y变为最小正整数解在计算z是否≥0即可

牛客练习赛60 (前四题)

全站热榜

创作者周榜