SCNUOJ 2020 软院天梯赛选拔赛 + 蓝桥杯热身赛 题解

写在前面

本次比赛面向软件学院2017、2018、2019级学生，赛制为IOI赛制，时长3小时。

最终共有311名同学提交代码，共有302名同学获得有效分数。

最终前18名的同学（除去打星）入围2020软件学院团体程序设计天梯赛名单，其中最高分为183分，最低分为105分。

祝贺他们！

题目限制

ps:一般来说，64MB内存足以。

L1-1 建议改成：空 格 体（5）

Problem Description

LXY 在某大型知名同性交友网站上传了一个视频，但并没有想到有意思的标题。作为标题党的 LXY 想让博学多识的你给他想一个好标题。

结合 LXY 的视频内容，你自然想到了一个非常好的标题。为了将自己的标题告诉 LXY，你需要在评论区用建议空格体加入标题竞标。

建议空格体示例

Input

输入共一行，一个由大小写字母及数字组成的字符串（不超过 个字符），表示你想出的标题。

Output

输出一行，开头是"Proposed change to: "，后面是标题并将标题内的每个字符用空格隔开。

Simple Input

114514

Simple Output

Proposed change to: 1 1 4 5 1 4

Source

CGY

思路

读取字符串，按要求每一个字符前输出一个空格即可。

这道题部分人用JAVA和C语言多次调用strlen函数会导致代码TLE，因为C语言里strlen函数的时间复杂度为O(n)，Java的String类比较慢，推荐使用StringBuffer来处理。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    cout<<"Proposed change to:";
    for(int i = 0;i<str.size();++i) cout<<" "<<str[i];
    return 0;
}

L1-2 多边形（5）

Problem Description

Veggie最近疲于教小侄子写红黑树，连多边形的内角和都忘记怎么求了，想请作为数学小天才的你帮忙编程解决这个问题。

Input

输入在一行中给出一个整数，表示多边形的边数。

Output

在一行中对应输出n边形内角和的值x，格式为”Answer: x degree”（不含双引号）。

Simple Input

4

Simple Output

Answer: 360 degree

Source

LWH

思路

多边形内角和 = (边数 - 2) * 180

代码

#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    printf("Answer: %d degree", (n - 2) * 180);
    return 0;
}

L1-3 米斯达与数字4（10）

Problem Description

Guīdo Misuta是《JOJO的奇妙冒险：黄金之风》里面的人物，他对于数字4很是在意，他认为4是十分不吉利的数字。现在有一串数字，请问这串数字迫害米斯达的次数是多少？

迫害次数=数字4出现的次数+数字长度内4出现的次数。

//性感手枪警告

Input

输入一串数字，长度不超过200位

Output

数字4出现的次数和数字长度中4的次数的总和

Simple Input

1234

Simple Output

2

Hint

数字中出现4的次数为1，同时数字长度为4，因此总和为1+1=2

Source

LXY

思路

这道题分为两个部分来求解，一个是求这串数字中4的个数，另一个是这串数字位数（长度）中4的个数。
在这里，我们可以采用string字符串来读入，借助string.size()函数来快速得到这串数字的位数，然后将位数不断模10整除10来获得每一位的数字并统计其中4的个数。最后遍历这个字符串，判断字符为'4'的个数，两部分累加即为答案。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int n = str.size();
    int cnt = 0;
    while(n){
        if(n%10 == 4) cnt++;
        n/=10;
    }
    for(int i = 0;i<str.size();++i){
        if(str[i]=='4') cnt++;
    }
    cout<<cnt;
    return 0;
}

L1-4 打印（10）

Problem Description

真的是道简单打印题哈——给定一个整数数组，请打印其中位数为偶数且数值也为偶数的数字。

Input

第一行为一个整数，代表数组有N个整数。

接下来有N行，每行有一个整数

Output

若输入的的位数为偶数且数值也为偶数，则打印该行。

Simple Input1

3
12
2
13

Simple Output1

12

Simple Input2

2
-1
-12

Simple Output2

-12

Source

SLF

思路

方法一：用字符串处理，判断字符串位数是否为偶数（负号不算入内），再判断最后一个字符是否为偶数即可。

方法二：直接读入整数处理。

代码（方法一）

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    int n;
    cin>>n;
    while(n--){
        cin>>str;
        int num_len = str.size();
        if(str[0]=='-'){
            num_len--;
        }
        if(str[str.size()-1]%2==0 && num_len%2==0){
            cout<<str<<endl;
        }
    }
    return 0;
}

L1-5 寻找连座（15）

Problem Description

image.png

软件学院的LXY和CGY要去一起坐火车外出比赛。火车上有许多节车厢，每节车厢的每一排都有4个座位，且这4个座位被过道分成了两半。不幸的是，当LXY和CGY到了车上时，一些位子已经有人了。

但LXY和CGY是好基友，于是他们想要找一对连在一起的座位，以便于更好地打游戏(手动划掉)学习。一对连在一起的座位指得是，这两个座位在同一排且不被过道分割开。已知火车上每节车厢上的座位情况，请问能否找得到这样的一对连座？

Input

第一行为一个整数，代表火车总长度。

紧接着输入行，每行由五个字符组成，代表一排座位或者车厢分割线。

若是一排座位，第1、2、4、5个字符分别代表一排中的4个座位情况，字符'O'表示空座位，字符'X'表示座位上已经有人，即被占用。第3个字符为'|'，代表过道。

若是车厢分割线，则五个字符均为'-'。

数据保证每节车厢至少有一排座位。

Output

如果能够找到这样一组连座，请先输出一行字符串"Yes"（不输出引号），接下来一行，输出一个整数k，代表这组连座在第k车厢（车厢编号由1开始，从前往后编号递增）。

接下来输出火车的座位情况，将LXY和CGY坐的连座用"+"来表示。

若不能找到这样的连座，则输出一行字符串"No"（不输出引号）。

有多组座位符合要求时，将LXY和CGY安排在靠前的车厢，靠前的排，如果同一排还有两组可行解，选择将LXY和CGY排在左边。例如：

OO|OO                ++|OO

-----        ->      -----

OO|XX                OO|XX

Simple Input1

6
OO|OX
XO|XX
OX|OO
XX|OX
-----
OO|XX

Simple Output1

Yes
1
++|OX
XO|XX
OX|OO
XX|OX
-----
OO|XX

Simple Input2

6
XO|OX
XO|XX
OX|XO
XX|OX
-----
OX|XX

Simple Output2

No

Source

SLF

思路

字符串处理题。

遍历字符串数组，判断出LXY和CGY连座的位置，记录下来即可。

需要注意得是，车厢分割线代表着前一节车厢和后一节车厢的分割，可以联想火车/高铁的平面示意图。有些同学没有注意到这一点，导致Wrong Answer。

代码

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

string str[110];

int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;++i){
        cin>>str[i];
    }
    int cnt = 1;
    int ansi,ansj;
    int flag = false;
    for(int i = 0;i<n;++i){
        for(int j = 0;j<4;++j){
            if(str[i][j]=='-'){
                ++cnt;//统计当前车厢为第几车厢
                break;
            }
            if(str[i][j]=='O' && str[i][j+1]=='O'){
                flag = true;
                ansi = i,ansj = j;
                break;
            }
        }
        if(flag) break;
    }
    if(flag){
        cout<<"Yes"<<endl;
        cout<<cnt<<endl;
        for(int i = 0;i<n;++i){
            for(int j = 0;j<5;++j){
                if(i==ansi&&j==ansj){
                    cout<<"++";
                    ++j;
                    continue;
                }
                cout<<str[i][j];
            }
            cout<<endl;
        }
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

L1-6 Heroes never die（15）

Problem Description

image.png

OverWatch里的三个英雄有着上图的克制关系。

现在，我们需要写一个程序来自动选择英雄，以对抗对方选择的英雄。

选择规则如下：

1、当回合数是K的倍数时，选择一个相同的英雄。

2、当回合数是N的倍数时，选择一个”天使”英雄，并在接下来一行输出” Heroes never die”。

3、当回合数是K和N的倍数时，选择一个相同的英雄。

4、其他回合，选择一个克制对方英雄的英雄。

Ps：回合数从1开始

Input

首先第一行给出两个整数K、N（1≤K,N≤10），由空格隔开。随后每行给出一个对方选择的英雄：”Mccree”代表”麦克雷”，”Hanzo”代表”半藏”，”Genji”代表源氏。End代表输入结束，这一行不要做任何处理。

数据保证：回合数最多不超过

Output

参照题意的规则，每次选择一个英雄，单独输出一行。其中”Mercy”代表”天使”，选择”天使”时，接下来一行要接着输出”Heroes never die”。（所有输出均不带双引号）

Simple Input1

2 3
Mccree
Hanzo
Genji
Genji
Hanzo
Mccree
End

Simple Output1

Genji
Hanzo
Mercy
Heroes never die
Genji
Mccree
Mccree

Source

SLF

思路

判断每一回合是否为K或者N的倍数，然后按照题意要求输出即可。

代码

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

int main(){
    string Mccree = "Mccree",Hanzo = "Hanzo",Genji = "Genji";
    int n,k,cnt = 0;
    cin>>k>>n;
    while(true){
        cnt++;
        string str;
        cin>>str;
        if(str == "End") break;
        if(cnt%k==0){
            cout<<str;
        }else if(cnt%n==0){
            cout<<"Mercy"<<endl;
            cout<<"Heroes never die";
        }else{
            if(str == Mccree) cout<<Genji;
            else if(str == Hanzo) cout<<Mccree;
            else              cout<<Hanzo;
        }
        cout<<endl;
    }
    return 0;
}

L1-7 LXY的小机器人（20）

Problem Description

LXY上大三了，他选修了机器人技术这门课。期末的大作业是要写一段机器人的控制程序，完成某些功能。LXY可以对机器人发布WSAD四个指令，在二维平面上，指令分别表示：

W：机器人向上走一步（X,Y+1）

S：机器人向下走一步（X,Y-1）

A：机器人向左走一步（X-1,Y）

D：机器人向右走一步（X+1,Y）

LXY的程序会从头到尾循环的运行，LXY设定的每个指令会在1s内完成，现在LXY想知道经过一段时间后，机器人所处在的二维平面上的位置是多少。（LXY开始时已经将机器人放在(0,0)点）

Input

第一行输入一串由‘W’,‘S’，‘A’，‘D’组成的字符串，表示指令（指令长度不超过2000）
第二行输入一个数字N，表示LXY想知道经过N秒后机器人的位置（N<=2000000000）

Output

输出包括两个数字，表示经过N秒后机器人的坐标位置，分别为横坐标和纵坐标

Simple Input1

WSDDWSDAADW
12

Simple Output1

2 2

Source

LXY

思路

模拟题，但要注意数据范围，数据。

所以若直接暴力模拟，时间复杂度为O(N)，在一秒内无法完成。这里有许多同学没有注意到这一点，导致无法通过最后两个测试点。

然后我们可以分析可得，完成一次指令周期机器人相对位置变化是固定的，而指令周期len最长只有2000，时间复杂度O(len)是可以接受的。

于是我们可以先算出一个指令周期的相对位置，然后乘以（N/len）次，最后我们再模拟一次（N/len）的余数部分即可。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int x = 0,y = 0;
    for(int i = 0;i<str.size();++i){
        if(str[i]=='W') ++y;
        if(str[i]=='S') --y;
        if(str[i]=='A') --x;
        if(str[i]=='D') ++x;
    }
    int len;
    cin>>len;
    x *= (len/str.size());y *= (len/str.size());
    for(int i = 0;i<(len%str.size());++i){
        if(str[i]=='W') ++y;
        if(str[i]=='S') --y;
        if(str[i]=='A') --x;
        if(str[i]=='D') ++x;
    }
    cout<<x<<" "<<y;
    return 0;
}

L1-8 LXY的圆和矩形（20））

Problem Description

LXY上初中了，数学老师有一天留下了一个作业。已知圆上有N个点，给出每个点之间的弧长（为方便）输入，给出的弧长已经除了π，请问这些点一共能构成多少个不重复的矩形。

Input

输入第一行整数N（N<=100），第二行输入N个整数，表示相邻每两个点之间的弧长。

Output

输出N个点所构成的不重复的矩形个数

Simple Input1

8
1 2 2 3 1 1 3 3

Simple Output1

3

Hint

image.png

据说，直径所对的弦为半圆；

而且，直径所对的圆周角为直角；

那么问题来了，矩形有几个直角呢？

Source

LXY

思路

圆内一条直径对应的两个圆周角均为直角，一个矩形有四个直角，所以两条直径确定一个矩形。

我们计算出圆内的点能连成多少条直径，然后两两直径算一次即可得出矩形数量。

如果两个点连接的直线对应的弧长正好为总弧长的一半，则该直线为圆的直径。

ps:只要两个矩形四点任意一点不同就视为不同的矩形。这里有一些同学可能考虑复杂了。

代码

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
    int n,sum = 0,m = 0;
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        sum += a[i];
    }
    for(int i = 1;i<=n;++i){
        int t = a[i];
        for(int j = i+1;j<=n-1;++j){
            t += a[j];
            if(t*2 == sum){
                ++m;
                break;
            }
        }
    }
    int res = 0;
    for(int i = 1;i<=m;++i){
        res+=(i-1);
    }
    cout<<res;
    return 0;
}

L2-1 窃取密码（25）

Problem Description

LWH想要窃取ACM-ICPC系统的管理员密码，以提前查看今年World Final的题目。为此，他偷偷溜进管理员办公室，偷了一张纸，上面有一张清单，清单上有着个密码，密码均由小写的英文字母组成。管理员密码就在其中。
LWH回家后，开始准备对系统进行黑客攻击。为了破解系统，他不得不输入一个个密码进行尝试。不过幸运得是，他发现了这些密码具有等效性。

• 如果清单上两个密码a和b都包含同一个字母，则密码a等效于b

• 如果清单上两个密码a和b都等效于c，则a也等效于b

如果管理员密码与某个密码等效，则用户也可以使用等效的密码来登录系统。

例如，如果清单列表包含密码”a”, ”b”, ”ab”, ”d”，则”a”, ”b”, ”ab”彼此等效，但密码”d”不与清单列表中任何的密码等效。所以：

• 如果管理员的密码为”b”，那么您可以使用以下任何密码访问系统：”a”, ”b”, ”ab”。

• 如果管理员的密码为”d”,那么您只能使用”d”来访问系统。

清单列表中只有一个密码是测试系统的管理员密码。请帮助LWH计算能正确进入系统所需的最小密码数。请记住，LWH不知道清单列表中哪个密码是管理员的密码。

Input

第一行包含一个整数，代表列表清单中的密码数。

接下来n行，每行一个非空字符串代表密码，长度不超过50个字符。某些密码可能一样。

数据保证所有字符串总长度不超过，所有密码都由小写英文字母组成。

Output

输出一个整数，代表需要测试密码的最小数量，其中这些密码能够确保LWH进入系统。

Simple Input1

4
a
b
ab
d

Simple Output1

2

Hint

第一个样例LWH只需要测试两个密码即可，一个密码为”a”、”b”、”ab”中的任意一个，因为它们相互具有等效性，另一个密码为”d”，所以输出2。

Source

SLF

思路

题意要求算可以将给出的密码列表分成多少类，同一类内的密码相互等效。

我们可以用并查集来解决这个问题。

1、设置一个长度为26的整数数组，分别代表26个英文字母指向哪一个字符串。

2、遍历每一个字符串的每一个字符。

3、若该字符的数组尚未指向，这将该字符指向这个字符串。

4、若该字符的数组已指向，这将该字符串用并查集指向该字符已指向的字符串。

5、最后统计有多少个字符串指向自己即可。（在并查集中，每个字符串一开始均指向自己）

ps：如果写得并查集常数较大或者没有进行路径压缩，只能拿到60%的分数。暴力查找求解也可以通过部分的测试点，但是代码容易写错且分数不高。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int f[MAXN];
int find_father(int x){return f[x]==x?x:f[x]=find_father(f[x]);}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int flag[110];
    memset(flag,0,sizeof(flag));
    int n;
    cin>>n;
    for(int i = 1;i<=n;++i){
        f[i] = i;
        string str;
        cin>>str;
        for(int j = 0;j<str.size();++j){
            int t = str[j]-'a';
            if(!flag[t]){
                flag[t] = i;
            }
            else{
                int tx = find_father(flag[t]);
                int ty = find_father(i);
                if(tx!=ty){
                    f[tx] = ty;
                }
            }
        }
    }
    int res = 0;
    for(int i = 1;i<=n;++i){
        if(i==find_father(i))
            res++;
    }
    cout<<res;
    return 0;
}

L2-2 愧疚往事（25）

Problem Description

Veggie想起高中注册时帮了初中语文老师插队交学费，至今内心都因为那次插队感到无比愧疚。为了能够让这件愧疚往事成为教训，Veggie决定通过建立插队模型来体会那些被插队者的心情。在模型中，每个人都属于且仅属于一个朋友圈，圈内的人相互之间都是朋友。他们在排队时，会在队伍从后往前找熟人，如果找到了自己的朋友，就排在朋友后面，否则才会选择排到队伍最后。Veggie正在为找实习而忙碌，于是请你帮忙编程实现这个模型。

Input

输入第一行中给出两个整数N、M，其中朋友圈个数，是指令条数。

随后N行中，每行给出一个朋友圈的信息。首先是整数，表示这个朋友圈中的人数，接着是K个人员的编号(00000~99999)，中间用空格分开。

随后M行中，每一行给出一条模拟指令，指令有以下两种形式：

"IN x": 表示编号为x的人员进入队伍。

"OUT": 表示在队首的人离开队伍，此时我们需要输出该人员的编号。
（注意：指令不含双引号）

Output

按顺序输出离开队伍的人员编号，每个人的编号占一行。如果对空的队伍使用“OUT”指令，则输出”EMPTY”（不含双引号）。

Simple Input1

3 16
3 00001 00002 00003
3 11111 22222 33333
5 05030 05116 05103 05139 05044
IN 00001
IN 11111
IN 05030
IN 00002
IN 22222
OUT
OUT
OUT
OUT
OUT
IN 00003
IN 05103
IN 05139
IN 00001
OUT
OUT

Simple Output1

00001
00002
11111
22222
05030
00003
00001

Source

LWH

思路

队列模拟题。

为了处理方便，我们将每一个朋友圈编号，然后用Map<string,int>来映射每一个人对应的朋友圈编号。（不用Map，也可以用数组代替相应功能）

然后我们设置一个编号队列T，用来存放正在排队的朋友圈编号。

最后我们给每一个朋友圈都再单独设置一个队列Q。

然后开始模拟：

当一个人x想入队时，我们先判断x所在的朋友圈队列Q是否为空。

• 若为空证明总队列中没有x的朋友，所以将x入队到Q中，同时将x所对应的朋友圈编号i入队到编号队列T中。

• 若不为空证明总队列中有x的朋友，所以将x入队到Q中即可。

当遇到出队命令时,我们先判断编号队列T的队首元素i,然后将i对应的队列Q的队首出队.然后判断Q是否为空,是则将队列T队首元素i进行出队处理.

要注意处理遇到出队命令时，需要判断队列是否为空，否则会造成Runtime Error。

所有入队/出队操作的时间复杂度都是O(lg(K*N))。

有许多同学直接暴力模拟题意，而没有考虑到数据范围和算法的时间复杂度，造成Time Limit。

这道题对Java选手不太友好，因为Java读入和自带的数据结构库比较慢，算法正确的前提下可能会导致后面几个点TLE。

代码

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
using namespace std;
const int maxn = 1e5+10;
queue<int> q_id;
queue<int> q_member[1005];
int mapping[maxn], isInQueue[1005];
int n, m, k, t;
string str;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &t);
            mapping[t] = i;
        }
    }

    while (m--) {
        cin >> str;
        if (str == "IN") {
            scanf("%d", &t);
            if (!isInQueue[mapping[t]]) {
                isInQueue[mapping[t]] = 1;
                q_id.push(mapping[t]);
            }
            q_member[mapping[t]].push(t);
        } else {
            if (q_id.empty()) {
                printf("EMPTY\n");
                continue ;
            }
            int id = q_id.front();
            printf("%05d\n", q_member[id].front());
            q_member[id].pop();
            if (q_member[id].empty()) {
                q_id.pop();
                isInQueue[id] = 0;
            }
        }
    }
    return 0;
}

L2-3 关心员工（25）

Problem Description

SLF是G市某集团的总裁，他认为能一起打拼的员工都是好兄弟，因此他十分关心公司各个层次员工的生活水平。在公司中，每位员工都有且只有一名直属上司（SLF除外），而上司有可能有多个下属员工，于是各级员工之间就有了层次之分。为了更好地给员工补贴，SLF会定期统计各层次员工的平均收入。由于SLF忙于处理集团事务，于是想请你帮忙编程解决这个问题。

Input

输入第一行中给出一个整数，即整个公司的总人数，每个员工从1到N编号，总裁SLF的编号为1。随后N行，第i行给出编号为i的员工的相关信息，格式如下：

其中K是一个整数，表示该员工直接下属员工的个数，是直接下属员工的编号，Salary是一个正数，表示该员工的收入。

Output

在一行中对应输出公司的层次数m，随后m行中输出各层次员工的平均工资，格式为”Level i: ”（不含双引号）,其中表示第i层员工的平均工资，需要保留两位小数。

Simple Input1

7
2 2 3 100
3 4 5 6 2
1 7 3
0 4
0 5
0 6
0 7

Simple Output1

3
Level 1: 100.00
Level 2: 2.50
Level 3: 5.50

Source

LWH

思路

对多叉树进行层序遍历，计算每一层员工的平均和有多少层，最后输出即可。

这里有个注意的点是：题目中的工资Salary是正数，而不是整数，所以输入的变量要设置为浮点数。

这个点许多同学没有注意到从而造成Wrong Answer，真是令人可惜。这也表明了同学们读题能力稍显薄弱，有待加强啊。

//你要问题意为什么这么坑？没办法，天梯赛的真题就有这样坑人的。(手动滑稽)

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 1e5 + 10;
vector<int> tree[maxn];
double num[maxn], salary;
int n, m, root, t;

void bfs(int root) {
    //pre_level表示当前层数，node_num表示本层的节点数
    int pre_level = 1, node_num = 0;
    //本层的平均值
    double avg = 0;
    vector<double> ans;
    queue<pair<int, int> > q;
    q.push(make_pair(root, 1));
    while (!q.empty()) {
        int node = q.front().first;
        int level = q.front().second;
        q.pop();
        //当去到新的一层就统计上一层的数据
        if (level != pre_level) {
            ans.push_back(avg / node_num);
            node_num = 0;
            avg = 0;
            pre_level = level;
        }
        //数量和工资的累计
        node_num++;
        avg += num[node];
        //将所有的子节点放入队列中
        for (int i = 0; i < tree[node].size(); i++) {
            q.push(make_pair(tree[node][i], level + 1));

        }
    }
    //由于最后一层无法再到达新的一层，所以要单独计算
    ans.push_back(avg / node_num);

    //输出结果
    printf("%d\n", pre_level);
    for (int i = 0; i < ans.size(); i++) {
        printf("Level %d: %.2f\n", i + 1, ans[i]);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> t;
            tree[i].push_back(t);
        }
        cin >> salary;
        num[i] = salary;
    }
    bfs(1);
    return 0;
}

L2-4 奇怪的需求增加了.jpg（25）

Problem Description

自从复工以来，CGY 一直在接一些奇怪的需求，需求多到做都做不完（他急了，他急了）。由于 CGY 是单核单线程处理器（Intel 赛扬 B720），所以他每次只能同时做一个需求。现在 CGY 手上堆了 个需求，每个需求都需要一段时间完成，如果他在一定时间内没有完成某个需求，那么这个需求就会被他的师兄忆兔之心拿过去做，这样忆兔之心就有可能抓到 CGY 把之前赶需求的时间都用来打雀魂（而且还上不了雀圣）的把柄。为了防止被发现，CGY 需要完成尽可能多的需求，那你能帮帮他吗？

9c551c53ca.png

Input

第一行是一个整数 。

接下来 行每行两个整数 和 ，描述了一个需求：完成这个需求需要 小时，如果在 小时之内还没有完成（如果刚好在 时刻完成也算完成，踩点不算迟到嘛），这个需求就被捞走了。（数据保证 ）

Output

输出一个整数 ，表示最多可以完成 个需求。

Simple Input1

4
100 200
200 1300
1000 1250
2000 3200

Simple Output1

3

Source

CGY

思路

堆+贪心。

我们可以先按照进行升序排序，然后遍历这些需求。遍历的同时维护一个nowtime（代表现在的时刻），如果当前需求能够被满足，就将这个需求加入到优先队列PQ（其中PQ是的大根堆）。如果当前需求不能被满足，则判断当前需求能否替换掉PQ顶端的需求，可以的话就替换，另外需要注意替换后nowtime可能会发生变化。这样替换并不会造成错误，因为我们已经对需求进行排序，所以替换对PQ中的其他需求不会产生冲突。

代码

#include <bits/stdc++.h>

using namespace std;

int n;
pair<long long, long long> needs[150010];
priority_queue<long long> pq;
int ans;
long long last;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> needs[i].second >> needs[i].first;
    }
    sort(needs, needs + n);
    for (int i = 0; i < n; ++i) {
        if (last + needs[i].second <= needs[i].first) {
            ++ans;
            last += needs[i].second;
            pq.push(needs[i].second);
        } else if (!pq.empty() && needs[i].second < pq.top()) {
            last += needs[i].second - pq.top();
            pq.pop();
            pq.push(needs[i].second);
        }
    }
    cout << ans << endl;

    return 0;
}

L3-1 《还债啦！动物森友会》（30）

Problem Description

Dr.Su 每天辛苦工作，缺乏休息时间，只能深夜在梦里玩动物之森聊以慰藉。在梦里，带资本家狸吉还是那个狸吉，西施惠还是那个西施惠，该还的贷款还是要还。于是，Dr.Su 给梦里的这个版本起名叫《还债啦！动物森友会》。

在《还债啦！动物森友会》里，赚钱的唯一方法是——从地上收集树枝卖钱（这才是真正的里数挑战）。这次的无人岛是一个 的长方形岛屿（难道哪一次不是吗？），第 行 列的格子内可以收集到 个树枝。Dr.Su 只会向上下左右四个方向走，并且不能离开这座无人岛（离开了狸吉会把你绑回来继续打工的），每当他走到一个格子，就会花费一个单位的时间将格子内的树枝全部收集完。众所周知，这是一个神（keng）奇（die）的岛屿，所以当 Dr.Su 收集完并离开某一格子后，该格子会重新刷新出原来所有的树枝。

Dr.Su 建的房子（房子所在的格子没有树枝）在第 行 列，他从这里出发，花费 单位的时间收集树枝，且 单位时间过后他恰好回到自己的房子，请问他最多能采集多少树枝？

（什么？你问 Dr.Su 这么聪明为什么不自己算？有动森玩谁还做题啊！）

微信图片_20200328141305.jpg

Input

第一行共五个正整数，分别是行数 、列数 、房子位置 、 和时间 ，保证 是偶数。

接下来 行每行 个非负整数 ，表示对应位置树枝的数量。且保证 。

Output

一个整数，表示 Dr.Su 能采集到的最多的树枝数。

Simple Input1

2 2 1 1 2
0 1
2 1

Simple Output1

2

Simple Input2

2 2 1 1 4
0 5
5 10

Simple Output2

20

Simple Input3

3 3 2 2 6
5 1 0
1 0 3
1 3 3

Simple Output3

15

Source

CGY

思路

登顶题。

首先，Dr.Su的路径可以视作原路返回。因为路径采摘树枝数sum = 去时采摘的树枝数x + 回时采摘的树枝数y，如果x是最优的x，那么想要sum最大，那么y必定 = x。所以我们可以将时间K/2，只需要算x，最后答案 = x*2。

所以我们可以进行搜索处理，但由于时间K最大有1e9，所以会超时。

其次，我们分析可得，如果K/2 ＞ n*m，那么Dr.Su会在最后一定会转圈圈，而且圈的周长等于2，也就说Dr

.Su会在两个格子之间反复横跳。因为我们可以假设如果圈的周长 = n，那么这n个格子里面一定可以选出两个格子使得这两个格子的树枝数/2 ＞= n个格子的树枝数/n。

所以如果K/2 ＞ n*m，那么我们只用对全部格子记忆化搜索n*m次即可。

代码一

#include <bits/stdc++.h>

using namespace std;

#define INF 0x7f7f7f7f

long long n;
long long m;
long long a;
long long b;
long long k;
long long c[110][110];
long long dp[110][110][2];
long long ans;
long long dx[4] = {-1, 0, 1, 0};
long long dy[4] = {0, 1, 0, -1};
long long step;
int tag = 0;

bool check(int x, int y) {
    return !(x < 1 || y < 1 || x > n || y > m);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> a >> b >> k;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c[i][j];
            dp[i][j][0] = dp[i][j][1] = -INF;
        }
    }
    k /= 2;
    step = min(k, n * m);
    dp[a][b][0] = 0;
    for (int i = 1; i <= step; ++i) {
        tag ^= 1;
        for (int row = 1; row <= n; ++row) {
            for (int col = 1; col <= m; ++col) {
                long long maxp = -INF;
                long long maxc = -INF;
                for (int dir = 0; dir < 4; ++dir) {
                    int newx = row + dx[dir];
                    int newy = col + dy[dir];
                    if (check(newx, newy)) {
                        maxp = max(maxp, dp[newx][newy][1 ^ tag]);
                        maxc = max(maxc, c[newx][newy]);
                    }
                }
                if (maxp != -INF) {
                    dp[row][col][tag] = maxp + c[row][col];
                    ans = max(ans, dp[row][col][tag] * 2 - c[row][col] + (maxc + c[row][col]) * (k - i));
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

代码二（ZLM大师37ms的代码orz）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

const int dir_x[] = {0, 0, -1, 1};
const int dir_y[] = {-1, 1, 0, 0};
const int MAXN = 101;

long long dp[MAXN][MAXN], ss[MAXN][MAXN];
int s[MAXN][MAXN], step[MAXN][MAXN];

int main() {
    int n, m, a, b, k;
    memset(dp, 0xFF, sizeof(dp));
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &k);
    k >>= 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", s[i] + j);
    memset(ss, 0, sizeof(ss));
    for (int x = 1; x <= n; ++x)
        for (int y = 1; y <= m; ++y) {
            for (int i = 0; i < 4; ++i) {
                int xx = x + dir_x[i];
                int yy = y + dir_y[i];
                if (!xx || xx > n || !yy || yy > m) continue;
                ss[x][y] = std::max(ss[x][y], (long long)s[x][y] + s[xx][yy]);
            }
        }
    long long ans = 0;
    std::queue< std::pair< int, int > > q;
    q.push(std::make_pair(a, b));
    dp[a][b] = 0;
    step[a][b] = 0;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (step[x][y] > k) break;
        long long left = k - step[x][y];
        left *= ss[x][y];
        ans = std::max(ans, (dp[x][y] << 1) + left - s[x][y]);
        for (int i = 0; i < 4; ++i) {
            int xx = x + dir_x[i];
            int yy = y + dir_y[i];
            if (!xx || xx > n || !yy || yy > m) continue;
            long long tmp = dp[x][y] + s[xx][yy];
            if (dp[xx][yy] == -1 || dp[xx][yy] + ((step[x][y] + 1 - step[xx][yy]) >> 1) * ss[xx][yy] < tmp) {
                dp[xx][yy] = tmp;
                step[xx][yy] = step[x][y] + 1;
                q.push(std::make_pair(xx, yy));
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

总结

这次比赛的前10名榜单每隔几分钟就会发生变化，竞争非常激烈。

这套题目的Lv1难度相对较低，所以主要拉开差距的题目在于Lv2数据结构方面的题目，这也和天梯赛现场赛题目的难度分布相同。如果同学们感觉做Lv2数据结构的题目稍显吃力，表明数据结构这方面有待加强。

无论结果如何，尽了自己最大的努力便是成功。没有入围队伍名单的同学不用气馁，好好准备接下来的蓝桥杯等赛事吧~