[数据结构与算法]2021.10.1 训练

A - CQXYM Count Permutations

题意：

给定一个正整数n,排列一个2n长的序列，序列中的值p_i∈[1,2n],满足p_i<p_i+1（i<=n）
问有多少个这样的序列。

分析：

思维题。对称性，全排列满足上述条件的恰好一半，也就是：(2n)!/2。

代码：

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<map>
using namespace std;

typedef long long ll;

int t;
ll n,ans;
ll mod=1000000007;
///a
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        ans=1;
        for(ll i=3;i<=2*n;i++)
			ans=ans*i%mod;
        cout<<ans<<endl;
    }
    return 0;
}

B - Diameter of Graph

题意：

给定 n，m，k,问是否存在满足以下条件的无向连通图：
** n个点、m条边，无重边，无自环（两个不同的点确定一条唯一的边）；**
直径<k-1,其中直径指：max{ dis(i，j) }，（dis指两点之间的最短距离），一条边的长度规定为1；

分析：

首先复习一波~数据结构，无向连通图：
1. 前提 : 任何两个节点之间都是连通的，都存在一条路径，并且图中没有方向。因此，一个有n个结点的无向连通图至少有n-1条边,最多有(n-1)n/2条边。
????????则有n-1=<m<=(n-1)n/2。

2. 一个结点，无边为平凡图，又称零图，它也是无向连通图。
????????即：当n=1，m=0时，直径为0，k-1>0,（k>1），YES.

3. 无向完全图，任意两个结点之间都有边连接,路径长度均为1，直径等于0。
????????则有：n个结点的无向完全图，边数m=(n-1)n/2，k-1>1,（k>2）,YES.

4. 无向不完全图，要使结点之间距离最小考虑构造星型图（如下图所示）,易得其最大直径为2。
????????此时有：n个结点，m>=n-1,k-1>2,(k>3),YES.

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<queue>

using namespace std;

typedef long long ll;

///b

ll t,n,m,k;

int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        if(m < n-1 || k <= 1 || m > n*(n-1)/2){
            cout<<"NO"<<endl; continue;
        }
	    if(m==0&&n==1){
            cout<<"YES"<<endl;continue;
        }
	    if(k>3||(k>2&&(n*(n-1)/2==m))){
            cout<<"YES"<<endl;continue;
        }
	    cout<<"NO"<<endl;
    }
    return 0;
}