江南程序设计竞赛联盟暑期多校训练·第四场（个人补题B,D,G,H,J,K）
题目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; vector<vector<int>> 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(x>arr[a1][b1]) return 0; if (x > arr[a2][b2]) return 0; vector<vector<bool>> vis(n + 5, vector<bool>(m + 5, 0)); queue<pair<int, int>> q; q.push( {a1, b1}); vis[ a1][ b1] = 1; while (!q.empty()) { pair<int, 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, vector<int>(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 = 1e9+1; 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 << r+1<< endl; } return 0; }题目D. 银狼逛谷子店
知识点：
贪心+二分查找，lis（最长上升子序列），（由于个人代码时间问题，还用了下离散化）
关键：
由于题目要求严格单调递增，那么每次回头都不需要再算上一轮的，因此可以直接跑m+1次lis
思路：
lis：我们需要维护一个最长上升子序列，由于是上升的，对于当前位置的值x二分查找到第一个大于x的值，替换并打上标记，对于被替换的值删除标记（可能我这里代码问题，标记直接用map会爆掉，所以选择用离散化数组），若没有大于x的值，则直接插入到末尾
代码：
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int N = 1e5+10; int arr[N]; int t; vector<int> lisan; vector<bool> 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--) { vector<int> 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 = 2e5+10; const int m = 1e9+7; 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 = 1e5+10; 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; } vector<int> 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 = 2e5+10; vector<int> 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 i=1;i<=n;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 =3e5+10; 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; }