2021天梯总决赛题解
文章目录
L1-1 人与神 (5 分)
分析
输出题，直接输出即可
代码
php代码【狗头】
To iterate is human, to recurse divine.
L1-2 两小时学完C语言 (5 分)
分析
n为总字数，k是每分钟看的，m是看的时间，答案即为n-k*m
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k,m;
cin >> n >> k >> m;
cout << n - k * m << endl;
}
L1-3 强迫症 (10 分)
分析
用字符串if else即可
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
if(s.size() == 4){
if(((s[0] - '0') * 10 + s[1] - '0') < 22){
cout << 2 << 0 << s[0] << s[1] << "-" << s[2] << s[3];
}
else{
cout << 1 << 9 << s[0] << s[1] << "-" << s[2] << s[3];
}
}
else {
cout << s[0] <<s[1] << s[2] << s[3] << "-" << s[4] << s[5];
}
}
L1-4 降价提醒机器人 (10 分)
分析
每次比较，循环加if即可,注意数据类型是double。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
double m;
double p;
int main()
{
cin >> n >> m;
while(n--){
cin >> p;
if(p < m)
cout << "On Sale! " <<fixed << setprecision(1) << p << endl;
}
}
L1-5 大笨钟的心情 (15 分)
分析
同1-4，循环加if比较即可
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll moon[105];
int main()
{
for(ll i = 0;i < 24;i++){
cin >> moon[i];
}
ll num;
while(cin >> num && num < 24 && num >= 0){
if(moon[num] > 50){
cout << moon[num] <<" " <<"Yes" << endl;
}
else{
cout << moon[num] <<" " << "No" << endl;
}
}
}
L1-6 吉老师的回归 (15 分)
分析
读入使用getline函数，因为题目中存在空格，使用cin无法读入完全，同时记得在读入nm之后使用getchar()消除多余符号。
这里可以用到字符串的一个子串查找功能，格式为s.find(“xx”)==string::npos
如果不能找到，则find函数会返回真，反之如果找到了，则会返回假。
坑点：注意要把全部读入再判断，如果读入和循环在一起，有可能会导致无法读入完全，同时数据可能存在输入行数多于规定n的情况，建议使用for循环规定读入行数读入，而不是用while
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
string s[35];
int main()
{
cin >> n >> m;
getchar();
for(ll i = 0;i < n;i++){//保证数据完全读入
getline(cin,s[i]);
}
ll num = 0;
bool flag = 1;
for(ll i = 0;i < n;i++){
if(s[i].find("qiandao") == string::npos &&
s[i].find("easy") == string::npos){
num++;
}
if(num == m + 1){
cout << s[i];
flag = 0;
break;
}
}
if(flag)cout << "Wo AK le";
}
L1-7 天梯赛的善良 (20 分)
分析
给提供的数据排序，然后从前往后和从后往前分别遍历，来看最小值和最大值的数目。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10;
ll n,m;
ll a[N];
int main()
{
cin >> n;
for(ll i = 0;i < n;i++){
cin >> a[i];
}
sort(a,a + n);
ll minNum = 1;
for(ll i = 0;i < n;i++){
if(a[i] != a[i + 1])break;
minNum++;
}
ll maxNum = 1;
for(ll i = n - 1;i >= 0;i--){
if(a[i] != a[i - 1])break;
maxNum++;
}
cout << a[0] << " " << minNum << endl;
cout << a[n - 1] << " " << maxNum;
return 0;
}
L1-8 乘法口诀数列 (20 分)
分析
模拟题，使用动态数组，设定一个遍历下标值，每次进一个，然后将得到的乘积转化为字符串，按位录入字符串，这里使用了to_string函数，可以将数字转换为字符串。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>ans;
ll a,b,c,n;
int main()
{
ll num = 0;//设定的遍历下标值
cin >> a >> b >> n;
ans.push_back(a);
ans.push_back(b);
while(ans.size() < n){
c = ans[num] * ans[num + 1];
num++;
if(c / 10){
string tmp = to_string(c);//将c转换为字符串存储
for(ll i = 0;i < tmp.size();i++){
ans.push_back(tmp[i] - '0');
//存入数，故减去字符0
}
}
else
ans.push_back(c);
}
for(ll i = 0;i < n;i++){
if(i) cout << " ";
cout << ans[i];
}
cout << endl;
}
L2-1 包装机 (25 分)
分析
栈和队列的模拟，按照题意写就可以了，注意题目给定的特殊情况：1.框满了2.被选中轨道空，3.筐空
题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,m,s;
stack<char>box;//筐
queue<char>q[105];//轨道
queue<char>stream;//流水线
ll num;
string str;
cin >> n >> m >> s;
for(ll i = 1;i <= n;i++){
cin >> str;//用字符串读入
for(ll j = 0;j < str.size();j++){
q[i].push(str[j]);//按位存入轨道
}
}
while(cin >> num && num != -1){//输入操作，当碰到-1停止
if(num != 0 && q[num].size()){//注意轨道为空则不操作
if(box.size() == s){//筐满时
stream.push(box.top());
box.pop();
}
box.push(q[num].front());
q[num].pop();
}
else if(num == 0 && box.size()){//注意筐为空则不操作
stream.push(box.top());
box.pop();
}
}
while(stream.size()){
cout << stream.front();
stream.pop();
}
return 0;
}
L2-2 病毒溯源 (25 分)
分析
通过并查集来将病毒建成一颗树，注意不能更新路径，然后从0到n - 1遍历，来向上找，来寻找最长的变异链的长度，然后将所有长度为最长的变异链放入动态数组，排序最小的即是我们要找的变异链。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll int
const ll N = 1e4 + 10;
ll p[N];
ll a,k;
ll n;
ll maxn = -1;
vector<ll>ans[N];
ll find_root(ll x,ll val)
{
while(p[x] != x){
x = p[x];
val++;
}
return val;
}
stack<ll>box;
int main()
{
scanf("%d",&n);
for(ll i = 0;i < n;i++){
p[i] = i;
}
for(ll i = 0;i < n;i++){
scanf("%d",&k);
for(ll j = 0;j < k;j++){
scanf("%d",&a);
p[a] = i;
}
}
for(ll i = 0;i < n;i++){
ll tmp = find_root(i,1);
if(tmp > maxn){
maxn = tmp;
}
}
ll idx = 0;
for(ll i = 0;i < n;i++){
if(find_root(i,1) == maxn){
ll tmp = i;
while(p[tmp] != tmp){
box.push(tmp);
tmp = p[tmp];
}
box.push(tmp);
while(box.size()){
ans[idx].push_back(box.top());
box.pop();
}
idx++;
}
}
sort(ans, ans + idx - 1);
printf("%d\n",maxn);
for(ll i = 0;i < ans[0].size();i++){
if(i)printf(" ");
printf("%d",ans[0][i]);
}
return 0;
}
L2-3 清点代码库 (25 分)
分析
建议用vector数组存储输出，使用map映射来存储输出相同的组，当两组数目相同的，使用cmp函数逐个比较vector的大小。
注意：若考虑使用string存储输出的话，一个是数字有一位有两位，可能存在数字和空格比较，若解决了这个问题，也会有字符串的长度过长导致超时的问题，这题卡常，使用cincout的话需要关闭同步流。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
map<vector<ll>,ll>ma;
pair<vector<ll> ,ll>p[10005];
ll n,m;
bool cmp(pair<vector<ll> ,ll> x,pair<vector<ll> ,ll> y)
{
if(x.se == y.se){//如果两组数目相同
for(ll i = 0;i < x.fi.size();i++){//遍历输出
if(x.fi[i] != y.fi[i])//碰到输出不同的元素
return x.fi[i] < y.fi[i];//按元素大小从小到大排序
}
}
return x.se > y.se;//若数目不同，返回数目大的
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
vector<ll>tmp;//输入临时存储数组
ll num;
for(ll i = 0;i < n;i++){
tmp.clear();//将临时数组清空
for(ll j = 0;j < m;j++){
cin >> num;
tmp.push_back(num);
}
ma[tmp]++;//记录输出相同的数目
}
ll idx = 1;//pair的下表，pair的first元素存储输出的数组，second元素存储这样输出的有多少组
for(auto it = ma.begin();it != ma.end();it++,idx++){
//遍历map，将map中元素存入pair数组中
p[idx].fi = it->fi;
p[idx].se = it->se;
}
idx--;//最后idx多遍历一次，减去
sort(p + 1,p + idx + 1,cmp);//给pair数组排序，排序规则见cmp
cout << ma.size() << endl;
for(ll i = 1;i <= idx;i++){
cout << p[i].se;
for(ll j = 0;j < p[i].fi.size();j++){
cout << " " << p[i].fi[j];
}
if(i != idx)
cout << endl;
}
}
L2-4 哲哲打游戏 (25 分)
分析
模拟题，按照题意写就可以了，主要难度在于读题.
同样卡常，需要关闭同步流。
题目大意：哲哲通过每一个剧情点都能有一些能到达的剧情点，比如我当前在第一关，能到达2关3关和4关，则第一个输入即为3 2 3 4,第一个3为能到达的剧情点数量，之后进行m次操作，每次输入0，1，2对应输入种类，后面的j表示对应的操作位置
0：从当前剧情点做出了第j个选择，即选择了当前动态数组j - 1下标的存档(动态数组下标从0开始)
1：表示存档，用map存储，第j个点的second值就是当前位置，同时将当前存档的位置输出
2：读取存档，读取第j个存档，当当前状态更新成键值为j的map对应的值
代码
#include <bits/stdc++.h>
using namespace std;
#define se second
#define fi first
typedef long long ll;
const ll N = 1e5 + 10;
vector<ll> p[N];
ll st[105];
ll a;
map<ll,ll>ma;
ll num;
ll n,m;
int main()
{
ios::sync_with_stdio(false);//关闭同步流
cin >> n >> m;//n为剧情点个数，m为游戏操作
for(ll i = 1;i <= n;i++){
cin >> num;//num表示第i个剧情点能到的剧情点个数
for(ll j = 0;j < num;j++){
cin >> a;
p[i].push_back(a);
//将第i个剧情点能到达的剧情点存入第i个动态数组
}
}
ll ch;
ll now = 1;//当前在的剧情点
ll j;
while(m--){
cin >> ch >> j;
if(ch == 0){
now = p[now][j - 1];
}
else if(ch == 1){
ma[j] = now;
cout << now << endl;
}
else if(ch == 2){
now = ma[j];
}
}
cout << now;
return 0;
}
L3-2 还原文件 (30 分)
1.暴力骗26分做法
分析
暴力比较即可，多次遍历查找跟当前折点相同的碎片，直到找完为止。测试点2会超时。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll a[N];
ll n,m;
ll num;
ll k;
vector<ll>p[105];
int main()
{
ios::sync_with_stdio(false);
cin >> n;
for(ll i = 1;i <= n;i++){
cin >> a[i];
}
cin >> m;
for(ll i = 1;i <= m;i++){
cin >> k;
for(ll j = 0;j < k;j++){
cin >> num;
p[i].push_back(num);
}
}
ll idx = 1;
while(1){
if(idx == n)break;
for(ll i = 1;i <= m;i++){
bool flag = 1;
ll tmp = idx;
if(p[i][0] == a[idx]){
for(ll j = 0;j < p[i].size();j++,tmp++){
if(p[i][j] != a[tmp]){
flag = 0;
break;
}
}
tmp--;
if(flag)idx = tmp;
if(flag && idx != n)cout << i << " ";
else if(flag && idx == n)cout << i;
}
}
}
}
5817
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
