牛客练习赛77 部分题解

印度阿三17 2021-02-26

展开全文

A 小G的sum

的最小的约数是，的最大的约数是。

#include<bits/stdc  .h>
using namespace std ;
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    int n ;
    cin >> n ;
    long long ans1 = n ;
    long long ans2 = 1ll * n * (n   1) / 2 ;
    cout << ans1   ans2 << '\n' ;
    return 0 ;
}

B 小G的GCD

$\sum_{i = 1}^{n}F(i) = \sum_{i = 1}^{n}\sum_{j = 1}^{\left \lfloor \frac{i}{k} \right \rfloor}k*j$

#include<bits/stdc  .h>
using namespace std ;
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    int n , k ;
    long long ans = 0 ;
    cin >> n >> k ;
    auto cal = [&](int x)
    {
        return 1ll * k * x * (x   1) / 2 ;
    } ;
    for(int i = 1 ; i <= n ; i   )  ans  = cal(i / k) ;
    cout << ans << '\n' ;
    return 0 ;
}

C 小G的约数

$G(n)=\sum_{i=1}^{n}i*\left \lfloor \frac{n}{i} \right \rfloor$ ，整除分块即可。

#include<bits/stdc  .h>
using namespace std ;
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    int n ;
    cin >> n ;
    auto cal = [&](long long l , long long r)
    {
        long long a1 = l ;
        long long n = r - l   1 ;
        long long d = 1 ;
        return n * a1   n * (n - 1) * d / 2 ;
    } ;
    auto G = [&](long long n)
    {
        long long ans = 0 ;
        for(long long l = 1 , r ; l <= n ; l = r   1)
        {
         r = n / (n / l) ;
         ans  = 1ll * cal(l , r) * (n / l) ;
        }
        return ans ;
    } ;
    cout << G(G(n)) << '\n' ;
    return 0 ;
}

D 小G的LY数对

开局有人分钟过了，以为直接暴力 $O(n*C_{30}^2*log)$ 做就行，成瓜皮。

仔细分析 $a_i\oplus 2^s\oplus 2^t=b_j$ 等价于 $a_i\oplus 2^s=b_j\oplus 2^t$

具体写的时候要容斥，因为会算重复。

时间复杂度降低为 O(n*30) 。

#include<bits/stdc  .h>
using namespace std ;
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    int n , m ;
    cin >> n >> m ;
    vector<int> a(n) ;
    vector<int> b(m) ;
    for(int i = 0 ; i < n ; i   )  cin >> a[i] ;
    for(int i = 0 ; i < m ; i   )  cin >> b[i] ;
    vector<int> c , d ;
    for(int i = 0 ; i < n ; i   )
        for(int j = 0 ; j < 30 ; j   )
            c.push_back((a[i] ^ (1 << j))) ;
    for(int i = 0 ; i < m ; i   )
        for(int j = 0 ; j < 30 ; j   )
            d.push_back((b[i] ^ (1 << j))) ;
    long long ans = 0 ;
    sort(c.begin() , c.end()) ;
    sort(d.begin() , d.end()) ;
    int cur = 0 ;
    int siz1 = c.size() , siz2 = d.size() ;
    for(int i = 0 ; i < siz1 ; i   )
    {
        int j = i ;
        while(j   1 < siz1 && c[j   1] == c[j])  j    ;
        while(cur   1 < siz2 && d[cur] < c[i])  cur    ;
        int p = cur ;
        if(c[i] == d[cur])
        {
            while(p   1 < siz2 && d[p   1] == d[p])  p    ;
            ans  = 1ll * (j - i   1) * (p - cur   1) ;
            //cout << c[i] << ' ' << j - i   1 << ' ' << p - cur   1 << '\n' ;
            cur = p ;
        }    
        i = j ;
    }
    //cout << ans << '\n' ;
    sort(a.begin() , a.end()) ;
    sort(b.begin() , b.end()) ;
    cur = 0 ;
    siz1 = a.size() , siz2 = b.size() ;
    for(int i = 0 ; i < siz1 ; i   )
    {
        int j = i ;
        while(j   1 < siz1 && a[j   1] == a[j])  j    ;
        while(cur   1 < siz2 && b[cur] < a[i])  cur    ;
        int p = cur ;
        if(a[i] == b[cur])
        {
            while(p   1 < siz2 && b[p   1] == b[p])  p    ;
            ans -= 1ll * (j - i   1) * (p - cur   1) * 30 ;
            cur = p ;
        }    
        i = j ;
    }

    cout << ans / 2 << '\n' ;
    return 0 ;
}

E 小G的GLS图

首先分析是否存在某种数学关系，从而避免建图找割点。但是手画一些 case ，会发现不建图无法找到割点。

然后就开始思考如何简化建边，不能直接暴力建边 O(n^2) 。然后思考质因子分解，每个质因子在个数存在，直接建边是 O(x^2) 的，但是发现我其实只要建出一个长度是的环就好了，没必要建出稠密图。

因此建出图跑一遍 tarjan 求割点就好了。

时间复杂度的瓶颈是质因子分解。

#include<bits/stdc  .h>
using namespace std ;
const int maxn = 1e7   10 ;
int cnt = 0 ;
bool vis[maxn] ;
int prime[maxn] ;
int id[maxn] ;
void get_prime(int up) //素数筛
{
    memset(vis , 0 , sizeof(vis)) ;
    vis[1] = 1 ;
    for(int i = 2 ; i <= up ; i   )
    {
        if(!vis[i]) 
        prime[   cnt] = i , id[i] = cnt ;
        for(int j = 1 ; j <= cnt && i * prime[j] <= up ; j   )
        {
            vis[i * prime[j]] = 1 ;
            if(i % prime[j] == 0) break ;
        }
    }
}
vector<int> v[700000   10] ;
void init(int x , int c)
{
    int now = 1 ;
    for(int i = 1 ; prime[i] * prime[i] <= x ; i   )
    {
        if(x % prime[i] == 0)  
        {
            while(x % prime[i] == 0)  x /= prime[i] ;
            now *= prime[i] ;
            v[i].push_back(c) ;
        }
    }
    if(x > 1)  v[id[x]].push_back(c) ;
}
int head[maxn] ;
int num = 1 ;
int dfn[maxn] , low[maxn] , parent[maxn];
int ans = 0 ;
int cut[maxn] ;
struct Node
{
    int v , next ;
} edge[maxn] ;
void add(int u , int v)
{
    edge[num].v = v ;
    edge[num].next = head[u] ;
    head[u] = num    ;
}
void add1(int u , int v)
{
    add(u , v) ;
    add(v , u) ;
}
void dfs(int u)
{
    static int count = 0 ;
    int children = 0 ;
    int v ;
    dfn[u] = low[u] =    count ;
    for(int i = head[u] ; i != 0 ; i = edge[i].next)
    {
        v = edge[i].v ;
        if (dfn[v] == 0)
        {
            children    ;
            parent[v] = u ;
            dfs(v) ;
            low[u] = min(low[u] , low[v]) ;
            if(cut[u] == 0 && (parent[u] == -1 && children >= 2 || parent[u] != -1 && low[v] >= dfn[u]))
            {
                ans    ;
                cut[u] = 1 ;
                //cout << u << '\n' ;          
            }
            
        }
        else if (v != parent[u])
        low[u] = min(low[u], dfn[v]) ;
    }
}
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    get_prime(10000000) ;
    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i   )
    {
        int x ;
        cin >> x ;
        init(x , i   1) ;
    }
    memset(head , 0 , sizeof(head)) ;
    memset(parent , -1 , sizeof(parent)) ;
    memset(dfn , 0 , sizeof(dfn)) ;
    for(int i = 1 ; i <= cnt ; i   )
    {
        int siz = v[i].size() ;
        if(siz >= 2)
        {
            for(int j = 0 ; j < siz - 1 ; j   )
                add1(v[i][j] , v[i][j   1]) ;
            add1(v[i][0] , v[i][siz - 1]) ;
        }
    }
    for(int i = 1 ; i <= n ; i   )
        if(dfn[i] == 0)  dfs(i) ;
    cout << ans << '\n' ;
    return 0 ;
}