2022年CCCC天梯赛题解

L1-1今天我要赢

原题链接

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);printf("I'm gonna win! Today!\n2022-04-23");return 0;
}

L1-2 种钻石

原题链接

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read(), v=read();put(n/v);return 0;
}

L1-3 谁能进图书馆

原题链接

算法标签模拟

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){int a=read(), b=read(), x=read(), y=read();if (x > y){if (y >= a)printf("%lld-Y %lld-Y\nhuan ying ru guan\n", x, y);else if (x >= b)printf("%lld-Y %lld-Y\nqing 1 zhao gu hao 2\n", x, y);else if (x >= a)printf("%lld-Y %lld-N\n1: huan ying ru guan\n", x, y);elseprintf("%lld-N %lld-N\nzhang da zai lai ba\n", x, y);}else{if (x >= a)printf("%lld-Y %lld-Y\nhuan ying ru guan\n", x, y);else if (y >= b)printf("%lld-Y %lld-Y\nqing 2 zhao gu hao 1\n", x, y);else if (y >= a)printf("%lld-N %lld-Y\n2: huan ying ru guan\n", x, y);elseprintf("%lld-N %lld-N\nzhang da zai lai ba\n", x, y);}return 0;
}

L1-4 拯救外星人

原题链接

算法标签递归

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
int ans=1ll;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
int jie(int c){if(c==0){return ans;}else{return c*jie(c-1);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int a=read(), b=read();printf("%lld", jie(a + b));return 0;
}

L1-4 试试手气

原题链接

算法标签模拟

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
int ans=1ll;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
int solve(int a, int b){if(a==6){return a-b;}else {int t=a;a=6;b--;while(b){// 过程重复数据处理if(a-t){b--;a--;}else{a--;}}// 最终重复数据处理if(a==t){a-=1;}return a;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int a=read(), b=read(), c=read(), d=read(), e=read(), f=read();int n=read();printf("%lld %lld %lld %lld %lld %lld", solve(a, n), solve(b, n), solve(c, n), solve(d, n), solve(e, n),solve(f, n));return 0;
}

L1-5 斯德哥尔摩火车上的题

原题链接

算法标签模拟字符串

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
int ans=1ll;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);string s, s1, s2, s3;cin>>s>>s2;rep(i, 1, s.size()){if((s[i]-'0')%2==(s[i-1]-'0')%2){s1+=max(s[i]-'0', s[i-1]-'0')+'0';}}rep(i, 1, s2.size()){if((s2[i]-'0')%2==(s2[i-1]-'0')%2){s3+=max(s2[i]-'0', s2[i-1]-'0')+'0';}}if(s1==s3){cout<<s1;}else{cout<<s1<<"\n"<<s3;}return 0;
}

L1-6 机工士姆斯塔迪奥

原题链接

Time Limit Exceeded代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
// bool a[10005][10005];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
set<pair<int, int>> sps;
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read(), m=read(), q=read();while(q--){int t=read(),c=read();if(t){rep(i, 1, n+1){sps.insert({i, c});}}else{rep(i, 1, m+1){sps.insert({c, i});}}}printf("%lld", n*m-sps.size());return 0;
}

Time Limit Exceeded原因
insert操作耗时

Memory Limit Exceeded代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
bool a[N][N];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read(), m=read(), q=read();memset(a, 0, sizeof a);while(q--){int t=read(),c=read();if(t){rep(i, 1, n+1){a[i][c]=1;}}else{rep(i, 1, m+1){a[c][i]=1;}}}int cnt=0;rep(i, 1, n+1){rep(j, 1, m+1){if(!(a[i][j])){++cnt;}}}printf("%lld", cnt);return 0;
}

Memory Limit Exceeded原因
开辟N*N二维数组超出内存限制

AC代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
// bool a[10005][10005];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
int n, m, Q;
bool row[N], col[N];
signed main()
{int n=read(), m=read(), Q=read();while (Q -- ){int t=read(), c=read();if (t) {col[c] = true;}else{row[c] = true;}}int res = 0;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )if (!row[i] && !col[j])res ++ ;printf("%lld\n",res);return 0;
}

由于二维空间内存不够可以，且本题两个维度上互不影响，因此将二维看为两个一维, 节约空间。

L1-7 静静的推荐

原题链接

算法标签贪心模拟

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
int arr[295];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read(), k=read(), s=read();int res=0;while(n--){int a=read(), b=read();if(a>=175){if(b>=s){res++;    }else{arr[a]++;}}}rep(i, 175, 291){res+=min(arr[i], k);}printf("%lld", res);return 0;
}

L2-1 插松枝

原题链接

思路

根据题目要求，盒子的优先级是要大于推进器的，所以遍历的时候要先考虑盒子里的松针，然后再考虑推进器
盒子看成一个栈，推进器看成一个队列。

算法标签

模拟队列堆栈

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
int arr[295];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read(), m=read(), k=read();queue<int> q;stack<int> stk;while(n--){int x=read();q.push(x);}while(q.size()||stk.size()){int cnt=0, last=101;while(cnt<k){if(stk.size()&&stk.top()<=last){printf("%lld", stk.top());last=stk.top();stk.pop();cnt++;}else if(q.size()){int t=q.front();if(t<=last){printf("%lld", t);last=t;q.pop();cnt++;}else if(stk.size()<m){stk.push(t);q.pop();}else{break;}}else{break;}}printf("\n");}return 0;
}

L2-2 老板的作息表

原题链接

算法标签模拟字符串处理

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
int arr[3600*24+5];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read();memset(arr, 0, sizeof arr);while(n--){int a, b, c, d, e, f;scanf("%lld:%lld:%lld - %lld:%lld:%lld", &a, &b, &c, &d, &e, &f);int g=a*3600+b*60+c;int h=d*3600+e*60+f-1;rep(i, g, h+1){arr[i]=1;}}int cnt=0;rep(i, 0, 3600*24-1){if(!arr[i]){int t=i;while(!(arr[i])&&i<3600*24-1){i++;}printf("%02lld:%02lld:%02lld - %02lld:%02lld:%02lld\n", t/3600, (t-(t/3600)*3600)/60, t-(t/3600)*3600-(t-(t/3600)*3600)/60*60,i/3600, (i-(i/3600)*3600)/60, i-(i/3600)*3600-(i-(i/3600)*3600)/60*60);}}return 0;
}

L2-3 龙龙送外卖

原题链接

思路

最短路程的距离为所有边往返减去无需往返的最远距离

算法标签贪心递归

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
// p存储每个点的父节点 d存储每个点距根节点距离
int p[N], d[N];
// sum 总和 mx所有点据根节点最远距离 
int sum, mx;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
// 计算u距离根节点距离
int dfs(int u){// 若当前点父节点为根节点或当前点已经算过 返回d[u] 无需重复计算if(p[u]==-1||d[u]>0){return d[u];}// 新增一条边sum++;//更新节点u据根节点距离为父节点距离根的距离+1d[u] = dfs(p[u])+1;return d[u];
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read(), m=read();rep(i, 1 , n+1){p[i]=read();}while(m--){int x=read();mx=max(mx, dfs(x));printf("%lld\n", sum*2-mx);}return 0;
}

L2-4 大众情人

原题链接

思路

采用Floyd计算两者之间距离，进行模拟

算法标签 Floyd

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 505, INF = 0x3f3f3f3f;
int d[N];
char sex[N];
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n=read();memset(sex, 0x3f, sizeof 0);rep(i, 1, n+1){d[i][j]=0;}rep(i, 1, n+1){char ch;scanf("%c", &ch);int k=read();sex[i]=ch;while(k--){int id=read(), dist=read();d[i][id]=dist;  }}rep(k, 1, n+1){rep(i, 1, n+1){rep(j, 1, n+1){d[i][j]=min(d[i][j], d[i][k]+d[k][j]);}}}for(auto c:string("FM")){int mn=INF;rep(i, 1, n+1){if(sex[i]==c)(int mx=0;rep(j, 1, n+1){if(sex[i]!=sex[j]){mx=max(mx, d[j][i]); }}}}rep(i, 1, n+1){if(sex[i]==c){int mx=0;rep(j, 1, n+1){if(sex[i]!=sex[j]){mx=max(mx, d[j][i]);}}if(mx==mn){printf("%lld", i);}}puts("");}  }return 0;
}

L3-1 千手观音

原题链接

思路

对于所给定的若干比较结果，由于需要按照从小到大顺序进行输出，因此可以将小于号当作有向边，参与比较的对象作为图中顶点，由于比较结果具有传递性，若A<B , B<C 则A<C 符合传递性，因次只需建立相邻比较结果的有向边，再进行拓扑排序即可。

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
int n;
unordered_map<string, int> d;
unordered_map<string, vector<string>> g;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
vector<string> get(string str){vector<string> res;string word;for (auto c: str){if (c == '.'){res.push_back(word);if(!d.count(word)){d[word]=0;}word = "";}else word += c;}res.push_back(word);if(!d.count(word)){d[word]=0;}return res;
}
// 拓扑排序
vector<string> topsort(){priority_queue<string, vector<string>, greater<string>> heap;for(auto& [k, v]:d){if(!v){heap.push(k);}}vector<string> res;while(heap.size()){auto t = heap.top();heap.pop();res.push_back(t);for(auto& u: g[t]){// 如果点u入度变为0， 将其插入优先队列中if(--d[u]==0){heap.push(u);}}}return res;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);char str[50];int n=read();scanf("%s", str);auto last = get(str);rep(i, 0, n){scanf("%s", str);auto cur = get(str);if(last.size() == cur.size()){rep(j, 0, cur.size()){if(last[j]!=cur[j]){// 建立由last[j]到cur[j]的边g[last[j]].push_back(cur[j]);// 更新cur[j]入度d[cur[j]]++;break;}}}last = cur;}auto res = topsort();printf("%s", res[0].c_str());rep(i, 1, res.size()){printf(".%s", res[i].c_str());}return 0;
}

L3-2 关于深度优先搜索和逆序对的题应该不会很难吧这件事

原题链接

思路

sum所有节点dfs取模结果 s1 子孙关系逆序对数 s2 非子孙关系的数对数
则答案为s1 * sum + s2 * sum % P * (P + 1) / 4) % P

算法标签 DFS 组合计数

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 300005, M = N * 2, P = 1e9 + 7;
int n, root;
// 存储邻接表
int h[N], e[M], ne[M], idx;
// 存储每个子树大小 树状数组维护从根到当前节点中每一个节点出现次数
int sz[N], tr[N];
// sum所有节点dfs取模结果 s1 子孙关系逆序对数 s2 非子孙关系的数对数
int sum = 1, s1, s2;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
void put(int x) {if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar(x%10^48);
}
int lowbit(int x){return x & -x;
}
// 位置x增加v
void update(int x, int v){for(int i = x; i < N; i += lowbit(i)){tr[i] +=v;}
}
// 1至x前缀和
int query(int x){int res = 0;for(int i = x; i; i -= lowbit(i)){res += tr[i];}return res;
}
void dfs(int u, int father){// 将当前点u加入树状数组, 即将u+1 u出现一次update(u, 1);// 更新s1s1 = (s1 + query(n) - query(u)) % P;sz[u] = 1;// cnt存储当前节点儿子数量int cnt = 0;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(j != father){// 计算当前节点子孙大小dfs(j, u);sz[u] += sz[j];cnt ++;}}rep(i, 1, cnt + 1){sum = sum * i % P;}s2 = (s2 + n - query(n) -sz[u] + 1)% P;update(u, -1);
}
// 添加边a->b
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read(), root = read();memset(h, -1, sizeof h);rep(i, 0, n - 1){int a = read(), b = read();add(a, b), add(b, a);}// dfs(root, -1);printf("%lld", (s1 * sum + s2 * sum % P * (P + 1) / 4) % P); return 0;
}

住由于测试网站为acwing, 上述代码未对结果进行格式化输出，若需进行格式化输出，则在输出处增加如下代码

bool is_first=true
if(is_first){is_first=false;
}else{printf(" ");
}
printf("%lld", res);

原创不易
转载请标明出处
如果对你有所帮助别忘啦点赞支持哈
在这里插入图片描述