牛客算法周周练4 B,C,D,E

B：Rinne Loves Xor
题目就是要你求所有的从1到n，bi异或aj，j<=i,ai异或bj,j<=i。这样理解比题目说的从加上上次好想一点，因为是异或这种关系我们很容易就要想到二进制从二进制着手，把所有位数出现了多少个0和出现了多少个1统计下就行了，然后算下当前位的a的0和b的1有多少种搭配方法和b的0和a的1有多少搭配方法，再乘上当前的位子对应的权值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555,mod=1e9+7;
ll a[N],b[N],s[N][2],A[N][2],B[N][2];
int main(){
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++){
        ll ans=0;
        for(int j=0;j<=31;j++){
            A[j][(1<<j&a[i])?1:0]++;//统计a和b在当前位有多少个0和1
            B[j][(1<<j&b[i])?1:0]++;
            ans+=A[j][0]*B[j][1]+A[j][1]*B[j][0]<<j;
            ans%=mod;
        }
        printf("%lld ",ans);
    }
    return 0;
}

C:阶乘
题目很容易理解，主流的解题方式都是二分，我这介绍一种打表的方法。
首先存下sqrt(1e9)以内的素数有哪些，然后对于我们要求的那个数，我们因数分解后剩下的最大的素数的多少次方那个数就是答案，思路不难，剩下看代码如何处理。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555,m=(1<<30);
int a[N];
bool vis[N];
vector<int>q,v[N];
int main(){
    for(int i=2;i<=100000;i++){//欧拉筛素数
        if(vis[i])continue;
        q.push_back(i);
        for(int j=i;j<=100000;j+=i){
            vis[j]=true;
        }
    }
    for(int i=0;i<q.size();i++){//提前存好素数^n的值是多少
        v[i].push_back(0);
        int num=1,t=q[i];
        while(num<=30){
            int x=t;
            while(x%q[i]==0&&x){
                v[i].push_back(t);num++;x/=q[i];
            }
            t+=q[i];
        }
    }
    int T=read();
    while(T--){
        int n=read(),ans=0;
        for(int i=0;i<q.size();i++){
            int num=0;
            while(n%q[i]==0&&n){//因数分解，取最大的因数分解后的值
                n/=q[i];
                num++;
            }
            ans=max(ans,v[i][num]);
        }
        ans=max(ans,n);
        printf("%d\n",ans);
    }
}

D：小石的签到题
看下过题的人数，这题好像并没有想的那么复杂。于是乎暴力枚举下3，4，5，6，7，8的情况，果断猜测1先手输，否则先手必胜。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
int main(){
    int n=read();
    if(n==1)cout<<"Yang"<<endl;
    else cout<<"Shi"<<endl;
    return 0;
}

E：装备合成
这题好像也都是二分写的，但是咱不信邪用数学方法写了出来。
思路是贪心，假设先把所有零件都用来做y装备，做2件x装备和做1件y装备的a类材料需求一样，b类材料需求是2件a比1件b多5个，所以我们先全部做y装备，然后每多5个b类材料就能把1件y装备换成2件x装备，注意考虑下特殊情况，单独多出个2的情况以及b材料就算全部做y装备也不够配。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<1)+(s<<3)+(c^48);c=getchar();
    }
    return f*s;
}
const int N=1555555;
int main(){
    ll T;scanf("%lld",&T);
    while(T--){
        ll x=read(),y=read();
        ll ans=x/4,v=0;y-=ans;
        if(x%4>=2&&y>=3){
            v=1;y-=3;
        }
        if(y<=0)ans+=y;
        else{
            ans+=min(ans,y/5);
        }
        cout<<ans+v<<endl;
    }
    return 0;
}