Codeforces Beta Round #9 题解

传送门

[A] Die Roll

题意

小Y,小W和小D进行扔骰子(六面)游戏,谁投出的点数最大算谁胜利,现在已知小Y和小W的得分,请你帮小D求出她获胜的概率。

注意:

  1. 以"分子/分母"输出,特别的,若不可能获胜输出"0/1",100%获胜输出"1/1"
  2. 小Y和小W非常绅士,如果小D的得分和他们一样,他们也会算作小D获胜

算法

初中数学——列举法求概率。

把1~6枚举一遍即可。

注意约分。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int gcd(int a,int b) {
    if (a%b==0) return b;
    else return gcd(b,a%b);
}

int main() {
    int a,b; scanf("%d%d",&a,&b);
    int s=0;
    for (re int i=1;i<=6;i++) s+=(i>=a)&&(i>=b);
    int d=gcd(s,6);
    if (s==0) puts("0/1");
    else printf("%d/%d\n",s/d,6/d);
    return 0;
}

[B] Running Student

题意

有n个车站,给出客车的速度和跑步的速度。

你从原点上了客车,只能在后面的站下车。下车后可以跑到学校。

问你在哪个站下车能最快到学校。若时间相同,输出离学校的距离最近的。

算法

暴力枚举每个车站。

注意精度。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline double dis(double xa,double ya,double xb,double yb) {
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}

const double EPS=1e-6;

int n,vb,vs;
int x[110];
int xs,ys;

mainint main() {
    n=read(),vb=read(),vs=read();
    for (re int i=1;i<=n;i++) x[i]=read();
    xs=read(),ys=read();
    double Min=2e9; int ans=0;
    for (re int i=2;i<=n;i++) {
        double d=(double)x[i]/(double)vb+dis(x[i],0,xs,ys)/(double)vs;
        if (fabs(d-Min)<EPS) {
            if (dis(x[i],0,xs,ys)<dis(x[ans],0,xs,ys)) ans=i;
        }
        else if (d<Min) Min=d,ans=i;
    }
    cout<<ans<<endl;
    return 0;
}

[C] Hexadecimal's Numbers

题意

输入n,输出1-n的自然数中各数位只包含0和1的数的个数。

算法

试着从$1$开始构造,可以构造出$10$和$11$,然后又分别可以构造出$100$、$101$和$110$、$111$。

发现每次产生的两个数是$10n$和$10n+1$。

递归统计即可。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

int n,ans=0;

inline void find(int k) {
    if (k>n) return;
    ans++;
    find(k*10); find(k*10+1);
}

int main() {
    scanf("%d",&n);
    find(1);
    printf("%d\n",ans);
    return 0;
}

[D] How many trees?

题意

用n个点组成二叉树,问高度大于等于h的有多少个。

算法

经典的DP。

设$f[i][j]$表示用$i$个节点构造出的高度小于等于$j$的二叉树的数量。

枚举左子树的节点数$k$,那么右子树就有$i-k-1$个节点。

利用乘法原理和加法原理可以得到状态转移方程:

$f[i][j]=\Sigma_{k=0}^{i-1}f[k][j-1]\times f[i-k-1][j-1]$

边界为$f[0][i]=1$,最后答案为$f[n][n]-f[n][h-1]$。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int f[40][40]; //f[i][j]表示i个节点能构造出高度小于等于j的二叉树的数量  

mainint main() {
    int n=read(),h=read();
    for (re int i=0;i<=n;i++) f[0][i]=1;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++)
            for (re int k=0;k<i;k++)
                f[i][j]+=f[k][j-1]*f[i-k-1][j-1];
    printf("%I64d\n",f[n][n]-f[n][h-1]);
    return 0;
}

[E] Interesting Graph and Apples

题意

给出n个点,m条边,问是否能通过加一些边,使得n个点构成有且仅有n条边的单个环。如果能,输出YES以及加上的边的条数,并按字典序打印加上的边的两个端点。如果有多组解,输出字典序最小的一种方法。否则输出NO即可。

算法

考虑怎样才是一个环。首先,所有节点要联通;其次,每个节点的度都为$2$。

前者容易用并查集维护,后者可以直接用$deg$数组记录。

那么对于输入的每条边,将两个端点合并,然后度数分别加一。

这样后再判一遍,若有节点的度大于$2$,则必定无解。

然后从小到大地枚举两个端点。若能连上,就连上,并储存答案。

最后判断整个图是否联通即可。

注意特判一下$n=1$的情况。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Union_Find_Set {
    int root[100];
    
    inline void init(const int& n) {
        for (re int i=1;i<=n;i++) root[i]=i;
    }
    
    inline int find(int x) {
        if (root[x]!=x) root[x]=find(root[x]);
        return root[x];
    }
    
    inline void merge(int a,int b) {
        a=find(a),b=find(b);
        if (a!=b) root[a]=b;
    }
    
    inline bool judge(int a,int b) {
        a=find(a),b=find(b);
        return a==b;
    }
};

Union_Find_Set S;
int n,m;
int deg[100];
int ans[100][2];

int main() {
    n=read(),m=read(); S.init(n);
    
    if (n==1) {
        if (m==0) printf("YES\n1\n1 1\n");
        else if (m==1) printf("YES\n0\n");
        else puts("NO");
        return 0;
    }
    
    for (re int i=1;i<=m;i++) {
        int x=read(),y=read();
        deg[x]++,deg[y]++;
        S.merge(x,y);
    }
    
    for (re int i=1;i<=n;i++)
        if (deg[i]>2) { puts("NO"); return 0; }
    
    int s=0;
    
    for (re int x=1;x<=n;x++)
        for (re int y=x;y<=n;y++)
            if (deg[x]<2&&deg[y]<2&&!S.judge(x,y)) {
                ans[++s][0]=x; ans[s][1]=y;
                deg[x]++,deg[y]++;
                S.merge(x,y);
            }
            
    if (s+m==n-1) {
        s++;
        for (re int i=1;i<=n;i++) {
            if (deg[i]<2) {
                deg[i]++;
                if (ans[s][0]) ans[s][1]=i;
                else ans[s][0]=i;
            }
        }
    }
    
    for (re int i=2;i<=n;i++)
        if (!S.judge(1,i)) { puts("NO"); return 0; }
    
    puts("YES"); printf("%d\n",s);
    for (re int i=1;i<=s;i++) printf("%d %d\n",ans[i][0],ans[i][1]);
    
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 12 PM

发表评论