牛客练习赛#105(A-D)

牛客练习赛#105

A.切蛋糕的贝贝

• 题意

  • 有一个正n边形，想通过下列的切法切成面积比为1:1:4:5:1:4的6块
  • 切法：1,通过重心的对角线切一刀；2,重心与一个顶点切一刀
  • 问这个n边形能否切成题目要求的6块，若能则输出切的次数

• 题解

  • 小数论+思维。按照题目给定的切法，n边形有n个顶点，所以最多切成n块，这n块要分成面积比为114514的话，必须有n为16的倍数。
  • n%16!=0时，无解。否则，只需要切5刀。方法为对半切成8:8，一边8对半切为4:4，另一个8切成1:1:1:5，总共5刀。

• 代码

#include 

using namespace std;

void solve() {
    int n; cin>>n;
    if(n%16) cout<<-1<<'\n';
    else cout<<5<<'\n';
}

int main() {
    int t=1; //cin>>t;
    while(t--) solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

B.抱歉，这没有集美

• 题意

  • 对于n的排列数组a，问存在多少种排列存在gcd(ai, i)为偶数

• 题解

  • 打表。逆向思维，求存在gcd为偶数的对立事件，即求事件总数-排列中gcd(ai, i)为奇数恒成立的事件数量。sum=n!，打表可知sub= { A( foolr( (n+1)/2 ) }^2.即res=sum-sub。

  • 证明。如果ai为奇数那么放在哪个位置都可以，因为奇数因子不可能有偶数，所以不管与奇数还是偶数的gcd都不会是偶数；如果是偶数一定是放在奇数位置，才不会出现gcd为偶数。所以对于n讨论

    • n为奇数时，n+1/2个奇数位置中放n-1/2个偶数和1个奇数。所以gcd全为奇数的情况为
      $$C_{\frac{n+1}{2}}^1\times (\frac{n+1}{2})!\times (\frac{n-1}{2})!=[(\frac{n+1}{2})!{]}^2$$

    • n为偶数的情况，gcd全为奇数的情况数量
      $$(\frac{n}{2})!\times (\frac{n}{2})!=[(\frac{n}{2})!{]}^2$$

• 代码

#include 

using namespace std;
const int mod=1e9+7;

int main() {
    int n; cin>>n;
    int sum=1,sub=1;
    for(int i=1;i<=n;i++) sum=1ll*sum*i%mod;
    for(int i=1;i<=(n+1)/2;i++) sub=1ll*sub*i%mod;
    sub=1ll*sub*sub%mod;
    sum=(sum-sub+mod)%mod;
    cout<<sum<<'\n';
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

C.打牌的贝贝

• 题意

  • 有2n张牌，其编号为1～2n，A和B都有随机的n张牌
  • 游戏规则：每次都是A出一张牌，如果A没牌出那么A输；否则B需要出一张比A更大的牌，如果B出不了更大的牌，那么B输
  • 问A和B各自赢的情况数量为多少

• 题解

  • 组合数/卡特兰数。首先必须明确这不是博弈论，因为A B不是轮流先手的公平游戏。对于A出的一张牌，B只需出一张大的牌即可。那么在1～2n的排列中，把A手中的牌视为左括号，B视为右括号，1～2n为合法的括号序列就是B赢的数量，也就是卡特兰数。C(2n,n)-caltonla即为A赢的数量。
  • 注意多组数据，不要在线算，预处理出来就行。还有我真的服了，卡cin不得好死

• 代码

#include 

using namespace std;
const int mod=1e9+7,N=1e6+5,M=2e6+10;
typedef long long ll;

ll fac[M],infac[M];

ll qmi(ll a,ll b) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init() {
    fac[0]=infac[0]=1;
    for(int i=1;i<M;i++) {
        fac[i]=fac[i-1]*i%mod;
        infac[i]=infac[i-1]*qmi(i,mod-2)%mod;
    }
}

ll c(ll a,ll b) {
    return fac[a]*infac[b]%mod*infac[a-b]%mod;
}

void solve() {
    ll n; cin>>n;
    
    ll res=c(2*n,n);
    ll ans=res*qmi(n+1,mod-2)%mod;
    res=(res-ans+mod)%mod;
    
    cout<<res<<' '<<ans<<'\n';
}

int main(){
    init();
    
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin>>t;
    while(t--) solve();
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

D.点分治分点

• 题意

  • 查找每个点到s的所有简单路径中，所有路径中最小值的最大值

• 题解

  • 最短路。从s点跑一遍spfa之后，更新到的点就是有可到达路径的。要得到答案只需要在更新条件中做更改即可，更新方式如代码所示。

• 代码

#include 
#include 
#include 
#include 

using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e5+10;

int n,m,s,dist[N];
bool vis[N];
vector<PII> g[N];

void add(int u,int v,int w) {
    g[u].push_back({v,w});
}

void spfa() {
    memset(dist,-1,sizeof dist);
    queue<int> q;
    q.push(s); vis[s]=1; dist[s]=0x3f3f3f3f;
    
    while(q.size()) {
        int u=q.front(); q.pop();
        vis[u]=0;
        for(auto [v,w]:g[u]) 
            if(dist[v]<min(dist[u],w)) {//min的含义为更新的是此条路径中的最小边权，而<才更新的意思是答案dist[v]求的是所有从s到v的路径中最大值
                dist[v]=min(dist[u],w);
                if(!vis[v]) q.push(v),vis[v]=1;
            }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>s;
    while(m--) {
        int u,v,w; cin>>u>>v>>w;
        if(u!=v) add(u,v,w);
    }
    
    spfa();
    for(int i=1;i<=n;i++) cout<<(dist[i]==0x3f3f3f3f ? -1:dist[i])<<' ';
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47