牛客寒假第一场题解

链接标题
A题
题意：写的很清楚
思路：找出厎为2和1的三角形然后因为里面多算了直角三角形的面积，再减去直角三角形的面积就行

#include<bits/stdc++.h>
using namespace std;
#define ll long long

inline ll read()
{
    ll num=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch^48);
        ch=getchar();
    }
    return w?-num:num;
}

inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
const ll mod = 1e9+7;
struct mat
{
    ll a[15][15];
    mat()  //重载
    {
        memset(a,0,sizeof(a));
    }
};
mat mul(mat x,mat y)
{
    mat res;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                res.a[i][j] = (res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
    return res;
}
ll qpow(int p)
{
    mat bas;//基础矩阵
    mat res;//单位矩阵
    for(int i=0; i<2; i++)
        res.a[i][i] = 1;
    bas.a[0][0] = bas.a[0][1] = bas.a[1][0] = 1;
    bas.a[1][1] = 0;
    while(p)
    {
        if(1&p)
            res = mul(res,bas);
        bas = mul(bas,bas);
        p>>=1;
    }
    return res.a[0][1];//或者res.a[1][0]
}
int main()
{
//    ll n , x ,y ,a ,b;
//    n =read();
//    x =read();y =read();a =read();b =read();
   ll n, m;
   n =read(), m = read();
   ll zhi = 0, dun =0 , deng =0 ;
   if(m<2||m<2)cout<<0 <<endl;
   else {
           zhi = 4*(n-1)%mod*(m-2)%mod+4*(m-1)*(n-2)%mod-mod-mod;
           dun +=2*(n-1)%mod*(m-2)%mod*m%mod;
           dun +=(m-1)%mod*(n-2)%mod*2*n%mod;
           deng = (m-2)%mod*(n-1)%mod*n%mod*2+(m-1)%mod*(n-2)%mod*2*m%mod;
           cout<<(deng+dun-zhi)%mod<<endl;
   }

    return 0;
}

B题
思路：概率题，两个期望和

#include <cstdio>
 #include <iostream>
 #include <algorithm>
 #include <cmath>
 #include <string>
 #include <vector>
 #include <set>
 #include <queue>
 #include <cstring>
 #include <cassert>
#define ll long long
using namespace std;
void clear(unsigned char *pta, int size )
{
    while(size>0)
    {
        *pta++ = 0;
        size --;
    }
}
int pre[100000];
int unionsearch(int root){
    int son , tmp;
    son = root;
    while(pre[root]!=root) root = pre[root];
    while(son !=root){
        tmp = pre[son];
        pre[son] = root;
        son = tmp;
    }
    return root;
}
void join(int root1 , int root2){
    int x ,y;
    x = unionsearch(root1);
    y = unionsearch(root2);
    if(x!=y){
        pre[x]=y;
    }
}
int arr[100000],brr[100000];
int main()
{
    double n , x , a ,b;
    cin >>n >>x>>a>>b;
    double sum =0 ;
    sum  = n*x/100*1.0*a+(n*(1-x/100*1.0)*b);
    printf("%.2f\n",sum) ;
}

c题（不是我负责的领域TAT）
d题
思路：？？？不会有人不会把

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin >>n;
    vector<int> v;
    for(int i=0;i<n-1;i++){
        int k1 ;cin>>k1;
        v.push_back(k1);
        }
    sort(v.begin(),v.end());
    int num =1;int f=0 ;
    for(int i=0;i<n-1;i++){
        if(v[i]!=num){
            cout<<num;
            f =1 ;
            break;
        }num++;
    }
    if(!f)cout<<n;cout<<endl;
}

E题
思路：看着像数论，其实是暴力哒，根据题意模拟就行

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    ll num=0,w=0;
    char ch=0;
    while(!isdigit(ch))
    {
        w|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch^48);
        ch=getchar();
    }
    return w?-num:num;
}

inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

ll ***(ll n){ 
    ll num = 2;
    ll  x=sqrt(n);
    for(ll i=2;i<=x;i++){
        if(n%i==0){
            if(i!=x || n/i!=i){ 
                   num+=2;
            }
            else num++;
        }
    }
    return num;
}

int main()
{
    ll n ;
   n =read();
    ll sum =0;
    n = ***(n);
    while(n != 2)
    {
        n = ***(n);
        sum ++;
    }
    cout << sum+1 << endl;
    return 0;
}

F题（赛后补的）
思路：有两种，官方的是并查集，另一种是深搜，dfs的没了解，就学了一下并查集的做法，并查集的做法就是：
1.先判断出黑点的两种存在方式①在路的尽头②路的里面包含
2.通过两种存在方式考虑做法，第一种很简单，直接累加就行第二种比较麻烦，因为他是在路的里面所以需要画个图感受一下在这个黑点的两边的白点是可以通过相乘的数量就是该白点包含这个黑点的路径数量（后面的需要和这个容斥一下）
3.关于第二个里面两边的白点是可以通过相乘的数量具体操作使用并查集来存储在同一边的白点数量

牛客寒假第一场题解

全站热榜