牛客练习赛24 - AB

A - 石子阵列 - 排列组合

链接：https://www.nowcoder.com/acm/contest/157/A
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

xb有m种石子，每种无限个，Ta想从这些石子中取出n个，并按顺序排列起来，为了好看，相邻的石子不能相同。xb想知道有多少种排列的方法。

输入描述:

第一行有两个正整数n，m。

输出描述:

第一行一个整数，表示在m种石子中取出n个的排列方案数模1000000007后的值。

示例1

输入

复制

1 1

输出

复制

1

示例2

输入

复制

2 3

输出

复制

6

示例3

输入

复制

3 3

输出

复制

12

备注:

对于100%的测试数据：
1 ≤ n, m ≤ 1000
数据量较大，注意使用更快的输入输出方式。

思路：

啊，这个是排列组合，高中学的都快忘光了qwq

一共有n个位置，第一个位置的选法有m种，第二个位置不能和第一个位置一样，有（m-1）种……第i个位置不能和第i-1个位置一样，有（ m-1）种。

答案就是：m*(（m-1）^（n-1））

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
  
using namespace std;
const int mod=1000000007;
 
long long pow_mod(long long a,long long b){
    long long res=1;
    while(b>0){
        if(b&1)res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}
int main(){
    long long n,m;
    scanf("%lld%lld",&n,&m);
    m=(m*pow_mod(m-1,n-1))%mod;
    printf("%lld\n",m);
}

B - 凤凰 - 并查集

链接：https://www.nowcoder.com/acm/contest/157/B
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

    凤凰于飞，翙翙其羽，亦集爰止。

                                        ——《诗经·卷阿》

    传说，凤凰是百鸟之王。有一天，凤凰要召开百鸟大会，百鸟国是一个由n个节点组成的树，每个节点有一只鸟，开会的节点定在1号节点。每只鸟可以花费1s通过一条边，由于每根树枝(边)的载重有限，只允许一只鸟同时通过。作为会议的策划师，HtBest想知道百鸟国的所有鸟在1点集合最少需要多少秒。

 

输入描述:

第一行有一个正整数n，表示百鸟国节点个数。
接下来n-1行，第i行两个正整数ai,bi用空格隔开，表示树上节点ai,bi之间有一条边。

输出描述:

第一行一个整数，表示集合最少需要的时间。

 

示例1

输入

复制

3
1 2
2 3

输出

复制

2

示例2

输入

复制

3
1 2
1 3

输出

复制

1

示例3

输入

复制

4
1 2
2 3
2 4

输出

复制

3

备注:

对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

思路：

与根节点直接相连的子树之间互不干扰，所以我们要求的就是每一棵子树用时的最大值。

对于一棵子树来说，用时就是这棵树上的节点个数，比如说下面这个图，中间的子树一共有6个节点，那么就用时6s，可以这样考虑，这棵子树的6个点都要依次通过A点到达根节点，所以用时6s。

可以通过并查集来求。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>

using namespace std;
const int maxn=1000005;
int pre[maxn],num[maxn];

int f(int x){
    if(pre[x]==x)return x;
    pre[x]=f(pre[x]);
    return pre[x];
}

void link(int a,int b){
    int fa=f(a),fb=f(b);
    if(fa!=fb){
        num[fa]+=num[fb];
        pre[fb]=fa;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        pre[i]=i;
        num[i]=1;
    }
    int m=n-1,a,b;
    while(m--){
        scanf("%d%d",&a,&b);
        if(a!=1&&b!=1){
            link(a,b);
        }
    }
    int ans=0;
    for(int i=2;i<=n;i++){
        ans=max(ans,num[f(i)]);
    }
    printf("%d\n",ans);
}