2021年CCCC天梯赛【部分题题解】

article/2025/7/2 0:54:20

天梯赛有三个level，第一个level基本就是语法题，第二个level是基础算法和STL库的一些应用。
第三个level就是一些难的算法。 L3的题都不是太会，有思路但是写不出来。

L1
- 人与神
- 两小时学完C语言
- 强迫症
- 降价提醒机器人
- 大笨钟的心情
- 吉老师的回归
- 天梯赛的善良
- 乘法口诀数列
L2
- 3464. 包装机【队 / 栈模拟】
- 病毒溯源【求树的最长字典序最小的链】
- 清点代码库【map计数 / 排序】
- 哲哲打游戏【模拟】

L1

人与神

在这里插入图片描述
https://www.acwing.com/problem/content/3459/

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{cout<<"To iterate is human, to recurse divine."<<endl;return 0;
}

两小时学完C语言

在这里插入图片描述
https://www.acwing.com/problem/content/3460/

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{int n,k,m; cin>>n>>k>>m;cout<<n-k*m<<endl;return 0;
}

强迫症

在这里插入图片描述
https://www.acwing.com/problem/content/3461/

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(void)
{string s; cin>>s;int year=stoi(s.substr(0,2));if(s.size()>4){cout<<s.substr(0,4)<<"-"<<s.substr(4)<<endl;return 0;}if(year<22){cout<<20<<s.substr(0,2)<<"-"<<s.substr(2);}else{cout<<19<<s.substr(0,2)<<"-"<<s.substr(2);}return 0;
}

降价提醒机器人

在这里插入图片描述
https://www.acwing.com/problem/content/3462/

#include<cstdio>
#include<iostream>
using namespace std;
int main(void)
{int n,m; cin>>n>>m;while(n--){double x; cin>>x;if(x<m) printf("On Sale! %.1lf\n",x);}return 0;
}

大笨钟的心情

在这里插入图片描述
https://www.acwing.com/problem/content/3463/

#include<cstdio>
#include<iostream>
using namespace std;
int a[25];
int main(void)
{for(int i=0;i<24;i++) cin>>a[i];int x;while(cin>>x,x>=0&&x<=23){cout<<a[x]<<" ";if(a[x]>50) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
}

吉老师的回归

在这里插入图片描述
https://www.acwing.com/problem/content/description/3464/

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(void)
{int n,m; cin>>n>>m;int cnt=0;string ans,s;bool flag=false;getline(cin,s);for(int i=0;i<n;i++){getline(cin,s);if(s.find("qiandao")!=-1||s.find("easy")!=-1) continue;cnt++;if(cnt==m+1){ans=s;flag=true;}}if(flag) cout<<ans<<endl;else cout<<"Wo AK le"<<endl;return 0;
}

天梯赛的善良

在这里插入图片描述
https://www.acwing.com/problem/content/3465/

#include<cstdio>
#include<iostream>
#include<set>
using namespace std;
int main(void)
{multiset<int>st;int n,x; cin>>n;for(int i=0;i<n;i++) cin>>x,st.insert(x);auto a=st.begin();auto b=--st.end();cout<<*a<<" "<<st.count(*a)<<endl;cout<<*b<<" "<<st.count(*b)<<endl;
}

乘法口诀数列

在这里插入图片描述
https://www.acwing.com/problem/content/3466/

#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
stack<int> st;
int a[1005];
int main(void)
{int n; cin>>a[1]>>a[2]>>n;int k=2;int i=1;while(k<=n){int temp=a[i]*a[i+1];i++;if(temp==0) st.push(0);//当前数就是0elsewhile(temp){st.push(temp%10),temp/=10;}while(st.size()){a[++k]=st.top();st.pop();}}for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;return 0;
}

简单写法:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int main(void)
{int a,b,n; cin>>a>>b>>n;string s; s+=to_string(a)+to_string(b);int i=0;while(s.size()<n){s+=to_string((s[i]-'0')*(s[i+1]-'0'));i++;}for(int i=0;i<n;i++)  cout<<s[i]<<" ";return 0;
}

L2

3464. 包装机【队 / 栈模拟】

在这里插入图片描述
https://www.acwing.com/problem/content/3467/

#include<cstdio>
#include<iostream>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,v;
queue<int>q[105];
stack<int>st;
vector<int>ve;//拿的
int main(void)
{cin>>n>>m>>v;for(int i=1;i<=n;i++){for(int j=0;j<m;j++){char c; cin>>c;q[i].push(c);}}int op;while(cin>>op,op!=-1){if(op==0){if(st.size()==0) continue;//空int t=st.top(); st.pop();ve.push_back(t);}else{if(q[op].size()==0) continue;if(st.size()==v)//满了{int t=st.top(); st.pop();ve.push_back(t);}int temp=q[op].front(); q[op].pop();st.push(temp);}}for(int i=0;i<ve.size();i++) printf("%c",ve[i]);return 0;
}

病毒溯源【求树的最长字典序最小的链】

在这里插入图片描述
https://www.acwing.com/problem/content/description/3468/

思路:

找到入度为零的点，次点是一个根结点。
遍历根节点找到字典序最小的且最长的链

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e4+10;
int h[N],e[N],ne[N],idx;
int son[N];
int st[N];
int n;void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int dfs(int u)
{int res=0;son[u]=-1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];int d=dfs(j);if(res<d) res=d,son[u]=j;//短else if(res==d) son[u]=min(son[u],j);//相等，选字典序小的}return res+1;
}
int main(void)
{memset(h,-1,sizeof h);cin>>n;for(int i=0;i<n;i++){int cnt; scanf("%d",&cnt);for(int j=0;j<cnt;j++){int x; scanf("%d",&x);add(i,x);st[x]=true;//记录入度}}int root=0;while(st[root]) root++; //找到根printf("%d\n",dfs(root));printf("%d",root);while(son[root]!=-1){root=son[root];printf(" %d",root);}return 0;
}

清点代码库【map计数 / 排序】

在这里插入图片描述
https://www.acwing.com/problem/content/3469/
TLE一个点代码:

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
using namespace std;
map< vector<int>,int>mp;
vector< vector<int> > ve;
bool cmp(vector<int> a,vector<int> b)
{if(mp[a]==mp[b]){return a<b; }return mp[a]>mp[b];
}
int main(void)
{int n,m; scanf("%d%d",&n,&m);for(int i=0;i<n;i++){vector<int> line;for(int j=0;j<m;j++){int x; scanf("%d",&x);line.push_back(x);}if(mp[line]==0){ve.push_back(line);}mp[line]++;}sort(ve.begin(),ve.end(),cmp);printf("%d\n",mp.size());for(int i=0;i<ve.size();i++){printf("%d ",mp[ve[i]]);for(int j=0;j<m;j++){printf("%d",ve[i][j]);if(j!=m-1) printf(" ");}puts("");}return 0;
}

优化后的代码:

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
using namespace std;
map< vector<int>,int>mp;
vector< vector<int> > ve;int main(void)
{int n,m; scanf("%d%d",&n,&m);for(int i=0;i<n;i++){vector<int> line(m+1,0);for(int j=1;j<=m;j++)//从1开始写{scanf("%d",&line[j]);}if(!mp[line]++)//没有出现过{ve.push_back(line);}}for(auto&line:ve){//将个数进入第0个位置line[0]=-mp[line];//加个负号，是将其好排序，这样递增序列也直接排好了}sort(ve.begin(),ve.end());printf("%d\n",ve.size());for(int i=0;i<ve.size();i++){printf("%d",-ve[i][0]);for(int j=1;j<=m;j++){printf(" %d",ve[i][j]);}puts("");}return 0;
}

哲哲打游戏【模拟】

在这里插入图片描述
https://www.acwing.com/problem/content/3470/

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
vector<int> choose[N];//选择
int read[N];//存档
int n,m;
int main(void)
{int st=1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x; cin>>x;for(int j=0;j<x;j++){int a; scanf("%d",&a);choose[i].push_back(a);}}while(m--){int op,k; scanf("%d%d",&op,&k);if(op==0){st=choose[st][k-1];}if(op==1){read[k]=st;printf("%d\n",st);}if(op==2){st=read[k];}}cout<<st<<endl;return 0;
}