牛客练习赛77部分题目题解

蒟蒻勉强打了3题，第4题开始不会了。。
这里放了前4题的代码和题解。

• A 小G的sum

  显然对于任意一个数i，最大的约数为i，最小的约数为1.
  因此答案就是n+(1+2+3...n)=n+(1+n)*n/2
  注意开long long

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    long long ans;
    ans=n+(1+n)*n/2;
    cout<<ans<<endl;
}

• B 小G的GCD

  根据f(x)的定义我们可以知道，f(x)=(1+2+3+...int(x/k))*k
  因此我们枚举f(i)求和就可以了。
  代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n,k;
  long long solve(int x){
   // if(x<k)return 0;
    int t=x/k;
    return 1ll*(1+t)*t/2*k;
  }
  int main()
  {
    long long ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        ans+=solve(i);
    }
    cout<<ans<<endl;
    return 0;
  }

• C 小G的约数

  首先G(n)我们可以暴力计算，然后发现要算G(G(n))的话，会超时的。
  再回过来看f(n)的定义是f(n)=n的约数和。
  G(n)=f(1)+f(2)+...f(n)
  可以发现G(n)其实的是n个1+n/2个2+n/3个3+...n/n个n
  即G(n)=n1+int(n/2)2+int(n/3)3+...int(n/i)i+...int(n/n)*n
  可以发现这其实是一个整除分块，对于k=int(n/i)我们可以分出其中的一个连续块，令区间[l,r]中的任意一个i，使得int(n/l)=int(n/r)=int(n/i)。
  而这个r=n/(n/l)
  这里的复杂度为O(logn)
  那么我们直接计算出G（n）以后，再利用整除分块计算G(G(n))就可以了。
  代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n;
  long long g;
  int main()
  {
    cin>>n;
    for(int i=1;i<=n;i++){
        g+=n/i*i;
    }
    long long ans=0;
    for(long long l=1,r;l<=g;l=r+1){
        r=g/(g/l);
        ans+=(g/l)*(l+r)*(r-l+1)/2;
    }
    cout<<ans<<endl;
    return 0;
  }

事实上，在做本题之前我只做过一题整除分块，对这玩意也是一知半解。我在比赛中，想到的是上面的那个式子可以转化成n*n-(n%1+n%2+n%3+...n%n)
因此我们只要求后面的那个式子就好了。
首先可以发现对于i>n/2的情况，是一个等差数列。即在(n/2,n]区间内是等差数列，公差为1。
同理可以发现，(n/3,n/2]是公差为2的等差数列。
因此我们可以枚举这些区间，到什么时候结束呢？
我们可以计算从以n/sqrt(n)开始的区间，到最后的(n/2,n]的区间利用等差数列公式求和，sqrt(n)之前的我们可以暴力计算。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
long long g;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        g+=n/i*i;
    }
    long long ans=g*g;
    int t=sqrt(g);
    for(int i=1;i<=g/t;i++){
        ans=ans-g%i;
    }
    for(int i=2;i<=t;i++){
        long long len=g/(i-1)-g/i;
        ans=ans-(g%(g/(i-1))+g%(g/i+1))*len/2;
    }
    cout<<ans<<endl;
    return 0;
}

• D 小G的LY数对

  这题暴力也没想到。。
  看了一下别人的题解，也是利用暴力+哈希过的。
  之前没有用过unorder_map
  基本思路就是先把a数组里的数放到unorder_map中，然后暴力枚举b数组中的数并且枚举(i,j)两个位置修改b数组的数，修改完以后看一下map中这个数字有多少个放到答案里面进行统计。
  这样做估计的复杂度是O(30^2*n)，加上map的巨大常数，直接T了。
  参考了一下，有人用bitset先判数字是否在a中出现，然后再去看有多少个答案进行统计。
  算是卡过去了。
  先把代码贴一下，明天有时间写一下哈希的代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n,m,b[300040],c[30];
  unordered_map<int,int>mp;
  bitset< 1<<30 >v;
  inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
  }
  int main()
  {
    mp.reserve(300005);
    n=read();m=read();
    int i,j,k,x;
    for(i=1;i<=n;i++){
        x=read();
        v[x]=true;
        mp[x]++;
    }
    for(i=1;i<=m;i++){
        b[i]=read();
    }
    long long ans=0;
    int tmp;
    for(i=0;i<30;i++){
        for(j=i+1;j<30;j++){
            for(k=1;k<=m;k++){
                tmp=b[k];
                tmp^=(1<<i);
                tmp^=(1<<j);
               if(v[tmp]) ans+=mp[tmp];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
  }

今天把哈希表的代码补上。速度快很多

#include<bits/stdc++.h>
using namespace std;
const int mod=1000007;
int n,m,b[300040];
inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
struct node{
    int to,next,w;
}p[300050];
int tot,head[2000050];
void add(int x){
    int a=x%mod;
    for(int i=head[a];~i;i=p[i].next){
        if(p[i].to==x){
            p[i].w++;
            return;
        }
    }
    p[tot].to=x;p[tot].w++;p[tot].next=head[a];head[a]=tot++;
}
int query(int x){
    int a=x%mod;
    for(int i=head[a];~i;i=p[i].next){
        if(p[i].to==x){

            return p[i].w;
        }
    }
    return 0;
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();
    int i,j,k,x;
    for(i=1;i<=n;i++){
        x=read();
        add(x);
    }
    for(i=1;i<=m;i++){
        b[i]=read();
    }
    long long ans=0;
    for(int i=0;i<30;i++){
        for(int j=i+1;j<30;j++){
            for(int k=1;k<=m;k++){
                int tmp=b[k];
                tmp^=(1<<i);
                tmp^=(1<<j);
                ans+=query(tmp);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}