题目B. 亚特兰蒂斯知识点二分bfs关键由于海水高度是随时间上升呈单调性可以用二分思路在h的范围即1到1e9上二分答案对check的高度bfs即可代码#include bits/stdc.h using namespace std; #define int long long #define endl \n int t; int n, m; vectorvectorint arr; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; int check(int a1, int b1, int a2, int b2, int x) { if(xarr[a1][b1]) return 0; if (x arr[a2][b2]) return 0; vectorvectorbool vis(n 5, vectorbool(m 5, 0)); queuepairint, int q; q.push( {a1, b1}); vis[ a1][ b1] 1; while (!q.empty()) { pairint, int now q.front(); q.pop(); for (int i 1; i 4; i) { int nx now.first dx[i - 1]; int ny now.second dy[i - 1]; if (nx 1 || nx n || ny 1 || ny m) continue; if (vis[ nx][ ny]) continue; //int h now.first 1; if (x arr[nx][ny]) continue; if (nx a2 ny b2) return 1; q.push( {nx, ny}); vis[ nx][ny] 1; } } return 0; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin t; while (t--) { cin n m; arr.assign(n 5, vectorint(m 5, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { cin arr[i][j]; } } int a1, a2, b1, b2; cin a1 b1 a2 b2; int l -1, r 1e91; while (l 1 ! r) { int mid (l r) / 2; if (check(a1, b1, a2, b2, mid)) l mid; else r mid; } cout l endl; //cout r1 endl; } return 0; }题目D. 银狼逛谷子店知识点贪心二分查找lis最长上升子序列由于个人代码时间问题还用了下离散化关键由于题目要求严格单调递增那么每次回头都不需要再算上一轮的因此可以直接跑m1次lis思路lis我们需要维护一个最长上升子序列由于是上升的对于当前位置的值x二分查找到第一个大于x的值替换并打上标记对于被替换的值删除标记可能我这里代码问题标记直接用map会爆掉所以选择用离散化数组若没有大于x的值则直接插入到末尾代码#include bits/stdc.h using namespace std; #define int long long #define endl \n const int N 1e510; int arr[N]; int t; vectorint lisan; vectorbool vis(N); //获取离散化下标 int get(int x) { return lower_bound(lisan.begin(), lisan.end(), x) - lisan.begin(); } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin t; while (t--) { vectorint v; lisan.clear(); int n, m; cin n m; for (int i 0; i n; i) vis[i] 0; for (int i 1; i n; i)cin arr[i]; //离散化代码 for (int i 1; i n; i) lisan.push_back(arr[i]); sort(lisan.begin(), lisan.end()); auto it unique(lisan.begin(), lisan.end()); lisan.erase(it, lisan.end()); // m; while (m--) { for (int i 1; i n; i) { if (vis[get(arr[i])]) continue; auto it lower_bound(v.begin(), v.end(), arr[i]); //if (ti v.end()) continue; if (it ! v.end() v[it - v.begin()] arr[i]) continue; //auto it upper_bound(v.begin(), v.end(), arr[i]); if (it v.end()) { v.push_back (arr[i]); vis[get(arr[i])] 1; } else { vis[get(v[it - v.begin()])] 0; v[it - v.begin()] arr[i]; vis[get(arr[i])] 1; } } } cout v.size() endl; } return 0; }题目G. gcd与lcm知识点质因数关键题目所给式子正常思路时间复杂度太高容易想到要化简但是化简的过程并不那么容易想到这里就直接附上原题解的证明过程了思路化简为乘积后遍历一遍就可以在复杂度O(n)的情况下完成了但要记录下前缀和sum1以及前面的所有两两数乘积之和sum2对于当前值ans加上当前值乘上sum2即可再更新sum1和sum2代码#include bits/stdc.h using namespace std; #define int long long #define endl \n const int N 2e510; const int m 1e97; int arr[N]; int brr[N]; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin n; int sum1 0; int sum2 0; int ans 0; for (int i 1; i n; i)cin arr[i]; for (int i n; i 1; i--) { ans (ans sum2 * arr[i]) % m; sum2 (sum2 sum1 * arr[i]) % m; sum1 (sum1 arr[i]) % m; // cout sum1 sum2 ans endl; } cout ans; return 0; }题目H. 银狼的多重背包知识点二进制拆分贪心关键根据题意可以先列举一些出来可以看出拆分的位置一定是二次幂才能保证cnt最大思路由于题目给了固定个数无法一次直接确定当前位置的数所以需要循环遍历每次只用当前位置向上的更高一次幂填充该位置按该贪心思路可以保证全部填满并且都是最优cnt对于总C不够时则直接加上代码#include bits/stdc.h using namespace std; #define int long long #define endl \n const int N 1e510; int t; int vis[30] {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072}; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin t; while (t--) { int n, C; cin n C; if (n 1) { cout C endl; continue; } vectorint ans(n 10); for (int i 0; i n 5; i) ans[i] 0; for (int i 1; i 18; i) { for (int j 1; j n; j) { if (vis[i] - ans[j] C) { C - (vis[i] - ans[j]); ans[j] vis[i]; //cout C; } else { ans[j] C; C 0; break; } } } for (int i 1; i n; i) { cout ans[i] ; } cout endl; } return 0; }题目J. 树上游戏知识点博弈递归关键对于任意一点由于博弈的存在只存在唯一输赢思路用一个win数组0和1记录输赢对于叶子节点必赢直接标为1从根节点遍历树递归时累加如果某一结点以下的win值和大于等于2说明该点也是必赢点则当前节点win值为1否则为0代码#include bits/stdc.h using namespace std; #define int long long #define endl \n const int N 2e510; vectorint v[N]; int t; int win[N]; int dfs(int x) { int sum 0; if (!v[x].size()) { win[x] 1; return 1; } for (int i 1; i v[x].size(); i) sum dfs(v[x][i - 1]); if (sum 2) { win[x] 1; return 1; } else { win[x] 0; return 0; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin t; while (t--) { int n; cin n; for (int i 1; i n; i) { v[i].clear(); win[i] 0; } //for(int i1;in;i) arr[i]0; for (int i 1; i n - 1; i) { int x, y; cin x y; v[x].push_back(y); } dfs(1); if (win[1]) cout mzk endl; else cout enana endl; } return 0; }题目K. 银狼的 mex 6知识点贪心二分思路该题不难看出答案是在具体一个范围的可以直接用二分但是难点在于贪心有许多注意点遍历时需要从高位往地位进行对于每个位置都有一个vis值该值代表了对于当前位置的值至少需要这么多个才能构造出满足条件的x值如果不够就先欠着等到再往下遍历时能还则还还不上再往下以此类推但是如果超出最大能欠的值则直接结束还超了则将多余的转化成0再利用注意check0和1时特判需求量很大时虽好提前退出代码#include bits/stdc.h using namespace std; #define int long long #define endl \n const int MAX 1e15; const int N 3e510; int arr[N]; int n; int sum 0; int brr[N]; int check(int x) { if (x 0 || x 1) return 1; int vis 0; for (int i 0; i x; i) brr[i] arr[i]; for (int i x; i n; i) brr[0] arr[i]; for (int i x - 1; i 0; i--) { if (vis MAX) return 0; if (brr[i] vis 1) { brr[i] - (vis 1); brr[0] brr[i]; } else { vis (vis 1 - brr[i]); if (i 0) return 0; } } return 1; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n; for (int i 0; i n ; i) { cin arr[i]; sum arr[i] ; } int l 0, r n log2(sum) 1; while (l 1 ! r) { int mid (l r) / 2; if (check(mid)) l mid; else r mid; } cout l endl; return 0; }