Codeforces Beta Round #83 (Div. 1 Only)题解【ABCD】

Codeforces Beta Round #83 (Div. 1 Only)

A. Dorm Water Supply

题意

给你一个n点m边的图，保证每个点的入度和出度最多为1

如果这个点入度为0，那么这个点就是水龙头点。

如果这个点的出度为0，那么这个点就是储存点。

现在让你把所有水龙头到储存点的路径都输出出来，且输出这条路径的边权最小值

题解

显然是个仙人掌图，所以直接XJB暴力就好了

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
vector<int>E[maxn],S[maxn],ans1,ans2,ans3;
int n,m,in[maxn],vis[maxn];
void dfs(int x,int y,int f){
    if(vis[x])return;
    vis[x]=1;
    if(E[x].size()==0){
        ans1.push_back(f);
        ans2.push_back(x);
        ans3.push_back(y);
        return;
    }
    for(int i=0;i<E[x].size();i++){
        dfs(E[x][i],min(y,S[x][i]),f);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        E[a].push_back(b);
        S[a].push_back(c);
        in[b]++;
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(in[i]==0&&E[i].size()){
            dfs(i,10000000,i);
        }
    }
    cout<<ans1.size()<<endl;
    for(int i=0;i<ans1.size();i++){
        cout<<ans1[i]<<" "<<ans2[i]<<" "<<ans3[i]<<endl;
    }
}

B - Basketball Team

题意

一场比赛需要n个球员，一共有m个俱乐部，每个俱乐部有s[i]个球员，你是第H个俱乐部的经理。

你已经钦定了你俱乐部的一个球员去参加比赛了，问你至少有两个人参加这场比赛的概率是多少？

题解

考虑反面，就只会有一个球员参加比赛的概率是多少。

然后还剩下n-1个位置，然后算一遍就好了……

这居然是CF div1 的B题，吃惊

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int s[maxn],n,m,h,sum;
double ans;
int main()
{
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=m;i++)
        scanf("%d",&s[i]),sum+=s[i];
    if(sum<n)return puts("-1"),0;
    ans=1;
    for(int i=1;i<n;i++){
        ans=ans*(1.*sum-s[h]-i+1)/(1.*sum-i);
    }
    printf("%.12f\n",1-ans);
}

C - Arrangement

题意

有n个数，让你构造字典序为(y-2001)大的序列，满足m对关系，每对关系的描述为:a[i]在b[i]前面

题解

暴力枚举每个位置填什么，然后如果这个的总方案大于等于y的话，说明合法，否则就让y减去这个的方案数。

然后递归下去，算方案用状压dp来做。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 16;
int n,m;
long long k,dp[1<<16];
int before[20],w[20],ans[20],vis[20];
void cal(){
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=0;i<(1<<n);i++){
        int tmp=0;
        for(int j=0;j<n;j++)
            if(i&(1<<j))
                tmp++;
        for(int j=0;j<n;j++)
            if(!(i&(1<<j)) && (ans[j]==-1 || (ans[j]==tmp)) && ((before[j]&i)==before[j]))
                dp[(1<<j)|i]+=dp[i];

    }
}
int main()
{
    scanf("%d%lld%d",&n,&k,&m);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        a--,b--;
        before[b]|=(1<<a);
    }
    k-=2001;
    for(int i=0;i<n;i++)ans[i]=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            if(j==n){
                cout<<"The times have changed"<<endl;
                return 0;
            }
            if(vis[j])continue;
            ans[i]=j;
            cal();
            if(dp[(1<<n)-1]>k){
                vis[j]=1;
                break;
            }
            else k-=dp[(1<<n)-1];
        }
    }
    for(int i=0;i<n;i++)
        cout<<ans[i]+1<<" ";
    cout<<endl;
}

D - Crime Management

题意

让你构造长度为n的序列，你可以在每个位置都放入26个字符中的一种，但是必须满足下列M个要求：

字符C出现的次数为K的倍数

题解

由于题目中输出条件有一个，所有K的乘积小于123，那么我们就可以用最多123个状态表示当前序列的样子，因为我只需要记录当前字符数量%K的数量

然后把矩阵快速幂写出来搞一搞就好了

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 125;
const int mod = 12345;
long long n;
char s[3];
int m,mu[maxn],p[26][maxn],vis[maxn],f[maxn][maxn],bas[maxn],g[maxn][maxn],ans[maxn],res[maxn],c;

int main()
{
    scanf("%lld%d",&n,&m);
    for(int i=0;i<26;i++)
        vis[i]=0,mu[i]=1;
    for(int i=0;i<m;i++){
        scanf("%s%d",s,&c);
        mu[s[0]-'A']*=c;
        p[s[0]-'A'][c]=1;
        vis[s[0]-'A']=1;
    }
    bas[0]=1;
    for(int i=1;i<=26;i++)
        bas[i]=bas[i-1]*mu[i-1];
    int t=bas[26];
    for(int i=0;i<t;i++)
        for(int j=0;j<26;j++)
            if(vis[j])
                f[i][i+bas[j]-(i%bas[j+1]/bas[j]+1!=mu[j]?0:bas[j+1])]++;
    ans[0]=1;
    for(;n;n>>=1){
        if(n%2==1){
            memset(res,0,sizeof(res));
            for(int i=0;i<t;i++)
            for(int j=0;j<t;j++){
                res[j]+=ans[i]*f[i][j];
                res[j]%=mod;
            }
            for(int i=0;i<t;i++)
                ans[i]=res[i];
        }
        memset(g,0,sizeof(g));
        for(int i=0;i<t;i++)
        for(int j=0;j<t;j++)
        for(int k=0;k<t;k++)
        {
            g[i][k]+=f[i][j]*f[j][k];
            g[i][k]%=mod;
        }
        for(int i=0;i<bas[26];i++)
            for(int j=0;j<bas[26];j++)
                f[i][j]=g[i][j];
    }
    int Ans = 0;
    for(int i=0;i<t;i++){
        for(int j=0;j<26;j++){
            if(vis[j]){
                int flag=0;
                for(int k=1;k<=bas[26];k++){
                    if(p[j][k]&&i%bas[j+1]/bas[j]%k==0)
                        flag=1;
                }
                if(!flag)break;
            }
            if(j==25)(Ans+=ans[i])%=mod;
        }
    }
    cout<<Ans<<endl;
}