0%

常州大学新生寒假训练Round 4题解

发表于 更新于 分类于 Disqus：
常州大学新生寒假训练Round 4题解

常州大学新生寒假训练Round 4题解

比赛地址：https://vjudge.net/contest/207674

迷路的白学姐

  1. 、”蜜蜂只能爬向右侧相邻的蜂房”准确来说，包含三个方向：正右方，右下方，右上方。
  2. 到 1 只有一条路（本身嘛），到 2 有一条路线（1 -> 2），到 3 有两条路线（1 ->3 或者 2 -> 3），到 4 有 3 条路线（到 2 的 1 条加上到 3 的 2 条），到 5 有 5 条路线（到 3 的 2 条加上到 4 的 3 条）……
  3. 以此类推，从原点到达各个蜂房的路线数分别为：
    蜂房号 1 2 3 4 5 6 7 8 9 ……
    路线数 1 1 2 3 5 8 13 21 34 ……
  4. 然后就可以发现，这就是一个斐波那契数列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n;
   long long c[100];
   c[0]=1;
   c[1]=1;
   c[2]=2;
   int a,b,j;
   while(cin>>n)
   {
     for(int i=0;i<n;i++)
     {
        cin>>a>>b;
        for(j=2;j<=b-a;j++)
        {
            c[j]=c[j-1]+c[j-2];
        }
        cout<<c[j-1]<<endl;
     }
   }
   return 0;
}

热爱公平的白学姐

既然要保持大家公平，就只能找出序列中的最大值，并将大家补全成最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int a[100+10];
int main()
{
    //freopen("C:\\Users\\Weicheng\\Desktop\\in.txt","r",stdin);
    int n,maxi=-1，ans=0;
    scanf("%d",&n);
    //找出最大值
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        maxi=max(maxi,a[i]);
    }
    //计算每个需要补多少
    for(int i=0;i<n;i++)
    {
        ans+=maxi-a[i];
    }
    printf("%d\n",ans);
    return 0;
}

白学姐的填字游戏

只有一种情况时就是在相邻两个连续1子串中只能含有一个0，只有一个连续1子串则整个串中不能含有0

我们就要计算总共1的个数，然后看看剩下的0的个数是不是刚好能隔开每一个1串

只要满足a1+a2+…+an=x-n+1即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,tmp,sum=0;
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++){
        cin>>tmp;
        sum+=tmp;
    }
    sum+=(n-1);
    if(sum==x)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

打工的白学姐

首先考虑不进行抛售时能卖出多少，就是存货量和购买量中的较小值，如果抛售就会增加存货量*2和购买量的最小值减之前那个值的销售数量，那么我们统计出如果进行抛售，每天的销售数量增量，取最大的f天，再加上每一天不抛售的销售量就是答案

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
#include <cstdio>
#include <algorithm>
using namespace std;
long long k[100001],l[100001];
long long add[100001];
int main()
{
    long long n,f,ans;
    scanf("%I64d%I64d",&n,&f);
    for(long long i=0;i<n;i++)
    {
        scanf("%I64d%I64d",&k[i],&l[i]);
        add[i]=min(2*k[i],l[i])-min(k[i],l[i]);
    }
    sort(add,add+n);
//这里的话就是把排序的数组倒序，也可以通过学习写sort里内嵌cmp来直接获得降序
    reverse(add,add+n);
    ans=0;
    for(long long i=0;i<n;i++)
        ans+=min(k[i],l[i]);
    for(long long i=0;i<f;i++)
        ans+=add[i];
    printf("%I64d\n",ans);
    return 0;
}

白学姐安排座位

题意
贪心做法，首先将每四个同一队伍的人安排到中间位置四人座（3，4，5，6），如果四人座有空余则将每个四人座分解为一个双人座和一个单人座。然后再将每两个同一队伍的人安排到所有的双人座，若双人座有空余则分解为一个单人座，最后看单人座能否将所有安排满，若可以，输出YES，否则输出NO

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
//感谢可爱的林锦雄学长提供的代码
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k,x;
    cin >> n >> k;
    int sum2 = n*2,sum4 = n;         //双人座和四人座数量
    int x1 = 0,x2 = 0,x3 = 0,x4 = 0; //每种组合的数量
    for(int i=1;i<=k;i++) {
        cin >> x;
        x4 += x/4;         //四人组合
        if(x%4==3) x3 ++;  //三人小组
        if(x%4==2) x2 ++;  //二人小组
        if(x%4==1) x1 ++;  //单身狗
    }
    while(sum4>0 && x4>0) {sum4--;x4--;} //三四人组合优先分配四连座
    while(sum4>0 && x3>0) {sum4--;x3--;}
    while(sum4>0 && x2>0) {sum4--;x2--;x1--;} //二人组合在分配四连座时可以带走一个单身狗
    while(sum4>0 && x1>0) {sum4--;x1--;sum2++;} //单身狗在分配四连座时产生一个空的双人座
    //华丽分割线：x1可能变负数，表示还能容纳的单身狗数量
    //下面同理，主要是四人座的优先分配思想，以达到尽量多地使用座位
    while(sum2>1 && x4>0) {sum2-=2;x4--;}
    while(sum2>1 && x3>0) {sum2-=2;x3--;}
    while(sum2>0 && x2>0) {sum2--;x2--;}
    while(sum2>0 && x1>0) {sum2--;x1--;}
    if(x2*2+x3*3+x4*4+x1<=0) //计算没有二人座和四人座情况下单身狗够不够座位
        cout << "YES" << endl;
    else if(x1<=0 && x2<=0 && x3<=0 && x4<=0) //全部人都得到座位
        cout << "YES" << endl;
    else cout << "NO" << endl;
    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
#include <bits/stdc++.h>
using namespace std;

int n, k;
int rest[5], cnt[5];

inline void init() {
    scanf("%d%d", &n, &k);
    rest[2] = n << 1, rest[4] = n;
    for(int i = 1, x; i <= k; i++) {
        scanf("%d", &x);
        while(x > 2) {
            if(rest[4])
                rest[4]--, x -= 4;
            else if(rest[2])
                rest[2]--, x -= 2;
            else {
                puts("NO");
                exit(0);
            }
        }
        if(x)
            cnt[x]++;
    }
}

inline void solve() {
    while(cnt[2]--) {
        if(rest[4])
            rest[4]--, rest[1]++;
        else if(rest[2])
            rest[2]--;
        else
            cnt[1] += 2;
    }
    puts((rest[4] * 2 + rest[2] + rest[1] >= cnt[1]) ? ("YES") : ("NO"));
}

int main() {
    init();
    solve();
    return 0;
}