牛客网国庆集训派对Day3题目 2018年

时间：2021-02-26 19:27:46

链接：https://www.nowcoder.com/acm/contest/203/D
来源：牛客网

Shopping
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

你要买n件物品，其中有一些是凳子。
商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。
你有m辆购物车，请最小化你的花费。

输入描述:

第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。
每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数a

i

,b

i

，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ a

i

 ≤ 10

5

, 0 ≤ b

i

 ≤ 1)。

输出描述:

每组数据输出一行一个实数表示最小花费，保留一位小数。
示例1

输入

复制

2

5 1

1 0

2 1

3 1

4 0

5 0

5 10

1 0

2 1

3 1

4 0

5 0

输出

复制

12.5

10.5
 #include<bits/stdc++.h>

 using namespace std;

 double a[],b[];

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

         int n,m;

         scanf("%d%d",&n,&m);

         for(int i=;i<n;i++)

         {

             scanf("%lf%lf",&a[i],&b[i]);

         }

         sort(a,a+n);

         int sum=;

         for(int i=;i<n;i++)

         {

             if(b[i]==)

             {

                 sum++;

             }

         }

         if(sum<=m)

         {

             for(int i=n-;i>=n-sum;i--)

             {

                 a[i]/=;

             }

         }

         else

         {

             for(int i=n-;i>=n-m;i--)

             {

                 a[i]/=;

             }

         }

         double ans=;

          for(int i=;i<n;i++)

          {

             // cout<<a[i]<<" ";

              ans+=a[i];

          }

          printf("%.1f\n",ans);

     }

     return ;

 }

链接：https://www.nowcoder.com/acm/contest/203/H
来源：牛客网

Travel
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

魔方国有n座城市，编号为牛客网国庆集训派对Day3题目 2018年。城市之间通过n-1条无向道路连接，形成一个树形结构。
澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。
澜澜想知道有多少种旅游方案满足条件，两个方案不同当且仅当存在某一次旅游游览了不同的城市。
澜澜不会数数，所以只好让你来帮他数方案。

输入描述:

第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。
每组数据第一行两个整数n,m

牛客网国庆集训派对Day3题目 2018年

，接下来n-1行每行两个整数a

i

,b

i

表示一条道路 (1≤ a

i

,b

i

≤ n)。

输出描述:

每组数据输出一行一个整数表示方案数对10

9

+7取模的结果。
示例1

输入

复制

2

3 1

1 2

1 3

3 2

1 2

1 3

输出

复制

1

4
思路：组合数C(n-1,m-1)*m！

代码：
 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn =  << ;

 const int mod = ;

 int t, n, m, ta, tb;

 ll c[maxn];

 ll qq(ll a, ll b, ll c)

 {

     ll ans = ;

     a = a % c;

     while (b>)

     {

         if (b %  == )

             ans = (ans * a) % c;

         b = b / ;

         a = (a * a) % c;

     }

     return ans;

 }

 ll C(ll n, ll m)

 {

     return c[n] * qq(c[m] * c[n - m] % mod, mod - , mod) % mod;

 }

 int main(void)

 {

     scanf("%d", &t);

      c[] = ;

     for (int i = ; i <= maxn; i++)

     {

         c[i] = c[i - ] * i%mod;

     }

     while (t--)

     {

         scanf("%d%d", &n, &m);

         for (int i = ; i < n - ; i++)

             scanf("%d%d",&ta,&tb);

         if (m == )

         {

             printf("1\n");

             continue;

         }

         ll ans = C(n - , m - );

         ans = (ans*c[m]) % mod;

         cout << ans << endl;

     }

     return ;

 }
























相关文章