牛客练习赛105（A-D)

A-切蛋糕的贝贝

题解：分成1:1:4:5:1:4份，每次都要沿着两点连线切割，所以n要是16的倍数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=5e5+5;
const ll inf=1e18;
const ll mod=9901;
ll a[N],sum[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll n;cin>>n;
  if(n&&n%16==0) cout<<5;
  else cout<<-1;
}
 

B-抱歉，这没有集美

题解：gcd(x,y)为偶数，那么就说明x,y都是偶数。反向思考，考虑概率为0的情况，就是把所有的偶数都付给奇数点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=5e5+5;
const ll inf=1e18;
const ll mod=1e9+7;
ll a[N],sum[N],fact[N],infact[N],res[N];
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  ll n;cin>>n;
  ll p=n/2;
  ll q=n-p;
  ll ans=1;
  ll sum=1;
  for(ll i=1;i<=n;i++){
    sum=(sum*i)%mod;
  }
  for(ll i=1;i<=p;i++){
    ans=(ans*i)%mod;
  } 
  if(n&1) ans=(ans*q)%mod;//在奇数点中选择p个偶数点
  for(ll i=1;i<=q;i++){
    ans=(ans*i)%mod;
  }
  ans=(sum-ans+mod)%mod;
  cout<<ans;
}

C-打牌的贝贝

题解：贝贝赢得方式必须是出一张牌大于宁宁手上所有牌，所以可以先分配给贝贝n-1张牌，然后将这剩下得n+1张牌中最大的呢张牌给贝贝，那么贝贝一定赢，然后再通过总的减去求出宁宁即可，数目很大，用逆元求组合数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=2e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll fact[N],infact[N];
ll ksm(ll x,ll y){
  ll ans=1;
  while(y){
    if(y&1) ans=(ans*x)%mod;
    x=(x*x)%mod;y>>=1;
  }
  return ans;
}
void init(){
  fact[0]=1;
  for(ll i=1;i<=2000000;i++){
    fact[i]=fact[i-1]*i%mod;
  }
  infact[2000000]=ksm(fact[2000000],mod-2)%mod;
  for(ll i=2000000;i>=1;i--){
      infact[i-1]=infact[i]*i%mod;
  }
}
ll solve(int a,int b){
  return fact[a]*infact[b]%mod*infact[a-b]%mod;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  init();
  ll t;cin>>t;
  while(t--){
    int n;cin>>n;
    cout<<solve(2*n,n-1)<<" "<<(solve(2*n,n)-solve(2*n,n-1)+mod)%mod<<"\n";
  }
}

D-点分治分点

题解：将所有路径按照权值从大到小排序，然后每次将边加到图中，这样每次选出的权值，对于能达到的点而言，都一样是最小值中的最大值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
const ll N=2e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,s;
ll dis[N],vis[N],ans[N];
vector<ll> e[N];
struct sp{
  ll x,y,w;
}a[N];
bool cmp(sp x,sp y){
  return x.w>y.w;
}
void dfs(ll x,ll w){
  vis[x]=1;ans[x]=w;
  for(auto it:e[x]){
    if(!vis[it]){
      dfs(it,w);
    }
  }
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  cin>>n>>m>>s;
  for(ll i=1;i<=m;i++){
     cin>>a[i].x>>a[i].y>>a[i].w;
  }
  sort(a+1,a+1+m,cmp);
  fill(ans,ans+N,-1);
  vis[s]=1;
  for(ll i=1;i<=m;i++){
    ll x=a[i].x;
    ll y=a[i].y;
    e[x].push_back(y);
    if(vis[x]&&!vis[y]){
      dfs(y,a[i].w);
    }
  }
  for(ll i=1;i<=n;i++){
    cout<<ans[i]<<" ";
  }
}