【题目记录】——2021牛客暑期多校训练营3

偏执的太偏执、 2022-09-01 13:58 156阅读 0赞

### 2021牛客暑期多校训练营3 ###

*  E Math 数学
 *  J Counting Triangles 图论

题目集地址【[2021牛客暑期多校训练营3][2021_3]】  
这次训练我们只做出了J题，题目集有点难。

# E Math 数学 #

[E Math][]  
题意：  
给一个数字n，输出所有满足 x y + 1 ∣ x 2 + y 2 , 1 ≤ x ≤ y ≤ n xy+1|x^2+y^2, 1\\le x\\le y \\le n xy\+1∣x2\+y2,1≤x≤y≤n条件的数对(x,y)  
思路：  
这其实是一道纯数学题，当时一直没推出来，现在的代码是看答案的公式后写出来的，比较重要的其实就是这个推公式的过程。具体应该就是使用基本的数学知识，推出来的解是(x,kx-y)。  
AC代码：

#include<bits/stdc++.h>
    
    using namespace std;
    
    typedef long long ll;
    const ll Max=1e18;
    
    ll a[1010000];
    int main()
    { 
        ll i;
        ll x,y,k;
        a[0]=1;
        int bi=1;
        for(i=2; i<=1e6; i++)//这里之所以要小于1e6，是因为y也要小于Max
        { 
            x=i;
            y=x*x*x;
            k=x*x;
            while(1)
            { 
                a[bi++]=y;
                if(y>(Max+x)/k)break;
                ll t=k*y-x;
                x=y;
                y=t;
            }
        }
        sort(a,a+bi);
        int T;
        ll n;
        cin>>T;
        while(T--)
        { 
            cin>>n;
            ll pos = upper_bound(a,a+bi,n)-a;
            cout<<pos<<endl;
        }
        return 0;
    }

# J Counting Triangles 图论 #

题目地址【[J Counting Triangles][]】  
题意：  
给一个n结点的完全图，按照题目给定规则给不同的边涂黑色或白色，要求数出所有3边颜色相同的三角形。  
思路：  
就是将完全图所有的环先计算出来，然后再遍历一遍找到不符合条件的情况，并将数值减去，从而得出结果。  
AC代码:

#include <bits/stdc++.h>
    namespace GenHelper { 
    unsigned z1,z2,z3,z4,b,u;
    unsigned get() { 
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() { 
        while (!u)
            u = get();
        bool res = u & 1;
        u >>= 1;
        return res;
    }
    void srand(int x) { 
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
        u = 0;
    }
    }
    using namespace GenHelper;
    using namespace std;
    typedef long long ll;
    bool edge[8005][8005];
    unordered_set<ll>SB,SW;
    int main() { 
        int n, seed;
        scanf("%d%d",&n,&seed);
        srand(seed);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                edge[j][i] = edge[i][j] = read();
        ll ans=1LL*n*(n-1)*(n-2)/6,res=0;//核心部分代码从这里开始，前面都是题目中给定的代码
        for(int i=0; i<n; i++) { 
            int b=0,w=0;
            for(int j=0; j<n; j++) { 
                if(i==j)
                    continue;
                if(edge[i][j]) { 
                    res+=w;
                    b++;
                } else { 
                    res+=b;
                    w++;
                }
            }
        }
        printf("%lld\n",ans-res/2);
        return 0;
    }

[2021_3]: https://ac.nowcoder.com/acm/contest/11254?&headNav=www
[E Math]: https://ac.nowcoder.com/acm/contest/11254/E
[J Counting Triangles]: https://ac.nowcoder.com/acm/contest/11254/J