L2 天梯真题

L2-056 被n整除的n位数题目大意：给你一个n代表n位数字，再给你一个a,b, 让你找到一个n位数字在a 和 b 之间，n范围最大为15。思路：肯定不能直接用暴力，这道题应该用dfs，每次检查一下今加进来的数看看是否符合题目意思，如果可以就继续检查一下一位字母，直到位数达到n就停止，再看一下，这个值是否在a和b范围之间#includebits/stdc++.h #define int long long using namespace std; int n; int a,b; int flag; void dfs(int u,int sum) { if(u == n) { if(sum = a sum = b) { cout sum '\n'; flag = 1; } return ; } for(int i = 0; i = 9; i ++) { if(i == 0 u == 0) continue; int z = sum * 10 + i; if(z % (u + 1) != 0) continue; dfs(u + 1, z); } } signed main() { cin n a b; // a = max(a,(int)pow(10,n - 1)); // b = min(b,(int)pow(10,n) - 1); dfs(0,0); if(!flag) puts("No Solution"); return 0; }L2-055 胖达的山头题目大意：给了你n段熊猫的时间点，让你看一下一个时间点最多有几个大熊猫思路：先把时间点全部转换为秒就行，然后用前缀和和差分来处理就行#includebits/stdc++.h using namespace std; const int N = 1e5 + 10; int a[N]; int main() { int n; cin n; for(int i = 1; i = n; i ++) { int b,c,d,e,f,g; scanf("%d:%d:%d %d:%d:%d",b,c,d,e,f,g); int start = b * 3600 + c * 60 + d; int en = e * 3600 + f * 60 + g; a[start] += 1; a[en + 1] -=1; } int res = 0; for(int i = 1; i = 24 * 3600 - 1; i ++) { a[i] += a[i - 1]; res = max(res,a[i]); } cout res '\n'; return 0; }L2-054 三点共线思路：这道题因为y只能是0 1 2中的一个，然后3重循环 肯定会超时，想办法优化到2重循环.#includebits/stdc++.h using namespace std; const int N = 1e6 + 10; vectorintA,B; bool st[2 * N]; int main() { int n; cin n; for(int i = 1; i = n; i ++) { int x,y; cin x y; if(y == 0) A.push_back(x); else if(y == 1) B.push_back(x); else { st[x + N] = true; } } sort(A.begin(),A.end()); A.erase(unique(A.begin(),A.end()),A.end()); sort(B.begin(),B.end()); B.erase(unique(B.begin(),B.end()),B.end()); int flag = 1; for(auto is : B) { for(auto it :A) { int x = 2 * is - it; if(abs(x) N st[N + x]) { flag = 0; cout "[" it ", 0] [" is ", 1] [" x ", 2]" endl; } } } if(flag == 1) puts("-1"); }L2-053 算式拆解思路：这道考查的是 对栈的运用，这道题目还是比较好理解的，从左往右遍历，遇到不是 ')' 都存储起来，遇到')' 从栈里面输出，直到遇到'(' 停止输出，将输出的结果翻转一下输出。补充:可以再去找几道 前缀表达式 和 后缀表达式的题 练练#includebits/stdc++.h using namespace std; int main() { string s; cin s; stackcharst; for(int i = 0; i s.size(); i ++) { if(s[i] == ')') { string a =""; while(st.top() != '(') { a += st.top(); st.pop(); } st.pop(); reverse(a.begin(),a.end()); cout a '\n'; } else st.push(s[i]); } }L2-052 吉利矩阵题目大意：统计一下 满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？思路：直接用dfs肯定会超时 + 剪枝就可以了#includebits/stdc++.h using namespace std; int L,N; int res = 0; int heng[10],lie[10]; void dfs(int x,int y) { if(x == N + 1 y == 1) { for(int i = 1; i = N; i ++) if(heng[i] != L || lie[i] != L) return ; res ++; return ; } for(int i = 0; i = 9; i ++) { if(heng[x] + i L) continue; if(lie[y] + i L) continue; if(y == N heng[x] + i != L) continue; if(x == N lie[y] + i != L) continue; heng[x] += i; lie[y] += i; if(y N) dfs(x,y + 1); else dfs(x + 1,1); heng[x] -= i; lie[y] -= i; } } int main() { cin L N; dfs(1,1); cout res '\n'; }L2-051 满树的遍历思路：这个直接用邻接表存储 可以直接用vector数组来模拟邻接表，也可以直接用add那个，建立一个树之后 就开始了前序遍历就行了 不难#includebits/stdc++.h using namespace std; const int N = 1e5 + 10; vectorinta[N]; int root; void dfs(int u) { if(u == root) { cout u; } else cout " " u; for(auto it : a[u]) { dfs(it); } } int main() { int n; cin n; for(int i = 1; i = n; i ++) { int x; cin x; if(x == 0) root = i; else a[x].push_back(i); } int flag = 1; int res = 0; for(int i = 1; i =n;i ++) { res = max(res,(int)a[i].size()); } cout res; for(int i = 1; i = n; i ++) { if(a[i].size() a[i].size() != res) { flag = 0; break; } } if(flag) cout " yes" endl; else cout " no" endl; dfs(root); }L2-050 懂蛇语思路:就是把每一句话的首字母提取出来，然后提取出来的首字母对应着一句话一开始没用stringstream z (s)导致有一个样例格式错误#includebits/stdc++.h using namespace std; mapstring,vectorstringmp; int main() { int n; cin n; getchar(); for(int i = 1; i = n; i ++) { string s; getline(cin,s); string ss =""; ss += s[0]; for(int i = 0; i s.size() - 1; i ++) { if(s[i] == ' ' s[i + 1] != ' ') ss += s[i + 1]; } mp[ss].push_back(s); } int k; cin k; getchar(); for(int i = 1; i = k; i ++) { string s; getline(cin,s); string ss =""; ss += s[0]; for(int j = 0; j s.size() - 1; j ++) { if(s[j] == ' ' s[j + 1] != ' ') ss += s[j + 1]; } if(mp[ss].size() == 0) cout s; else { sort(mp[ss].begin(),mp[ss].end()); for(int j = 0; j mp[ss].size(); j ++) if(j == 0) cout mp[ss][j]; else cout "|"mp[ss][j]; } cout '\n'; } return 0; }用stringstream#includebits/stdc++.h using namespace std; mapstring,vectorstringmp; int main() { int n; cin n; getchar(); for(int i = 1; i = n; i ++) { string s; getline(cin,s); string ss =""; stringstream z (s); string a; while(z a) { ss += a[0]; } mp[ss].push_back(s); } int k; cin k; getchar(); for(int i = 1; i = k; i ++) { string s; getline(cin,s); string ss =""; stringstream z (s); string a; while(z a) { ss += a[0]; } if(mp[ss].size() == 0) cout s; else { sort(mp[ss].begin(),mp[ss].end()); for(int i = 0; i mp[ss].size(); i ++) if(i == 0) cout mp[ss][i]; else cout "|"mp[ss][i]; } cout '\n'; } return 0; }stringstream z (s)stirng a;while(z a){}L2-049 鱼与熊掌思路：简单的离谱，就是开一个set的数组，存储他拥有的物品，然后用find 看一下查找的那两个物品是否在这里面，就可以了#includebits/stdc++.h using namespace std; const int N = 1e5 + 10; int n,m; setinta[N]; int main() { cin n m; for(int i = 1; i = n; i ++) { int k; cin k; for(int j = 1; j = k; j ++) { int x; cin x; a[i].insert(x); } } int k; cin k; while(k --) { int l,r; cin l r; int res = 0; for(int i = 1; i = n; i ++) if(a[i].find(l) != a[i].end() a[i].find(r) != a[i].end()) res ++; cout res '\n'; } return 0; }L2-048 寻宝图思路：很简单的一个bfs题目，遍历每个岛屿 在遍历的过程中，把岛屿变为海洋就行了#includebits/stdc++.h using namespace std; const int N = 1e5 + 10; string a[N]; int res,dao; int n,m; int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0}; int flag; void dfs(int x,int y) { if(a[x][y] '1') flag = 1; a[x][y] = '0'; for(int i = 0; i 4; i ++) { int xx = x + dx[i], yy = y + dy[i]; if(xx = 0 xx n yy = 0 y m a[xx][yy] !='0') dfs(xx,yy); } } int main() { cin n m; for(int i = 0; i n; i ++) cin a[i]; for(int i = 0; i n; i ++) for(int j = 0; j m;j ++) if(a[i][j] != '0') { res ++; dfs(i,j); if(flag) dao ++; flag = 0; } cout res " " dao endl; return 0; }L2-047 锦标赛思路：初见这一道题感觉没思路，挺难的，然后参考别人代码，顿悟。#includebits/stdc++.h using namespace std; const int N = 1e6 + 10; int a[30][N]; int p[N]; bool dfs(int k,int j,int w) { if(k == 1) { if(w = a[k][j]) { p[2 * j] = w; p[2 * j - 1] = a[k][j]; return true; } else return false; } if(w a[k][j]) return false; if(dfs(k - 1,2 * j,w) dfs(k - 1,2 * j - 1,a[k][j])) return true; else if(dfs(k - 1,2 * j - 1,w) dfs(k - 1,2 * j,a[k][j])) return true; return false; } int main() { int n; cin n; for(int i = 1; i = n; i ++) for(int j = 1; j = pow(2,n - i); j ++) cin a[i][j]; int w; cin w; if(dfs(n,1,w)) { for(int i = 1; i = pow(2,n); i ++) if(i == 1) cout p[i]; else cout " " p[i]; } else { puts("No Solution"); } return 0; }这里先用数组将每一轮的败者存储起来然后就用递归，看看每一轮的胜者是不是=当前轮的败者，如果不是，就返回false，并用另外一个数组存储。dfs(k,j，w) k代表第几轮, j 代表第几个，w代表当前的胜者34 5 8 57 689首先dfs(3,1,9) 先让9胜者和第3轮第一个元素比较大小，如果符合，就有两种情况让9 和 7比 或者让9和6比 任何一个满足情况就行所以有了dfs(k - 1,2 * j,w) dfs(k -1 ,2 * j - 1,a[k][j])dfs(k - 1,2 * j,a[k][j] d