[Offer收割]编程练习赛48-白红宇

[Offer收割]编程练习赛48

阅读量：6194 次

发布时间：2019-06-21

本文共 2754 字，大约阅读时间需要 9 分钟。

题目1 : 折线中点

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定平面上N个点P1, P2, ... PN，将他们按顺序连起来，形成一条折线。

请你求出这条折线的中点坐标。

输入

第一行包含一个整数N。 (2 <= N <= 100)

以下N行每行包含两个整数Xi, Yi代表Pi的坐标。(0 <= Xi, Yi <= 10000)

输出

输出折线段的中点坐标。坐标保留一位小数。

样例输入

3  0 0   30 30  40 20

样例输出

20.0 20.0

第一题还是稍微友好些的，需要知道折线中点怎么算，可以先算出线段的重点，然后去枚举每个点的位置

#include 
      
       using namespace std;struct T{    int x,y;} A[105];const double eps=1e-6;int main(){    int n;    cin>>n;    double x,y;    for(int i=0; i
       
        >A[i].x>>A[i].y;    double len=0;    for(int i=1; i
        
         =tt)len-=tt;        else        {            double t;            if(tt<=eps)t=0;            else t=len/tt;            a1=t*A[i].x+(1-t)*A[i-1].x;            a2=t*A[i].y+(1-t)*A[i-1].y;            break;        }    }    printf("%.1f %.1f",a1,a2);    return 0;}

题目2 : 最小先序遍历

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

有一棵包含N个节点的二叉树，节点编号是1~N。

现在我们知道它的中序遍历结果A1, A2, ... AN。

只有中序遍历显然不能确定一棵二叉树的形态，可能有很多棵不同的二叉树符合给定的中序遍历。

那么你能从中找出先序遍历结果字典序最小的二叉树吗？

设先序遍历结果是P1, P2, ... PN。字典序最小指首先P1应尽量小，其次P2尽量小，再次P3尽量小…… 以此类推。

输入

第一行包含一个整数N。 (1 <= N <= 100)

以下N行每行包含一个整数Ai。 (1 <= Ai <= N)

输出

输出N行，依次是P1, P2, ... PN。代表最小的先序遍历结果。

样例输入

5  5  4  1  3  2

样例输出

1  4  5  2  3

B题就是个构造，贪心构造做左子树和右子树，前序遍历的访问数序是NLR，中序遍历的访问顺序是LNR，所以找区间最小的，然后在分别构造左右子树就可以了

#include
      
       using namespace std;const int N=105;int a[N],b[N],n,c;void dfs(int l,int r){    int f=-1,mn=N;    for(int i=l; i<=r; i++)if(a[i]
       
        l)dfs(l,f-1);    if(f
        
         >n;    for(int i=0; i
         
          >a[i];    dfs(0,n-1);    for(int i=0; i

题目3 : 假期计划

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Ho未来有一个为期N天的假期，他计划在假期中看A部电影，刷B道编程题。

为了劳逸结合，他决定先拿出若干天看电影，再拿出若干天刷题，最后再留若干天看电影。(若干代指大于0)

每天要么看电影不刷题，要么刷题不看电影；不会既刷题又看电影。并且每天至少看一部电影，或者刷一道题。

现在小Ho要安排每天看哪些电影/刷哪些题目，以及按什么顺序看电影/刷题目。

注意A部电影两两不同并且B道题目也两两不同，请你计算小Ho一共有多少种不同的计划方案。由于结果可能非常大，你只需要输出答案对1000000009取模的结果。

只要某个事件(看电影或刷题)发生的日期不同或者在全部事件中的次序不同，就视为不同的方案。

输入

三个整数N, A和B。

对于30%的数据，N, A, B <= 10

对于60%的数据, 3 <= N <= 4000, 2 <= A <= 4000, 1 <= B <= 4000

对于100%的数据，3 <= N <= 100000, 2 <= A <= 100000, 1 <= B <= 100000, A + B >= N

输出

一个整数表示答案。

样例输入

4 2 2

样例输出

是个组合数学，可是我比较菜啊，当时没有推出来

#include
      
       using namespace std;typedef long long ll;const ll MD=1e9+9;ll A[200010],n,a,b,ans;ll la(ll a,ll b){    a%=MD;    ll ans=1;    while(b)    {        if(b&1)ans=ans*a%MD;        b>>=1;        a=a*a%MD;    }    return ans;}int main(){    cin>>n>>a>>b;    A[0]=1;    for(int i=1; i<=max(a,b); i++)        A[i]=A[i-1]*i%MD;    for(int i=2; i<=min(a,n-1); i++)        if(b>=n-i)            ans=(ans+(A[a]*A[b]%MD*A[a-1]%MD*la(A[a-i]*A[i-1],MD-2)%MD*A[b-1]%MD*la(A[b-n+i]*A[n-i-1],MD-2)%MD*(i-1)%MD))%MD;    cout<