Codeforces Round #790 (Div. 4) A-H
Codeforces Round #790 (Div. 4) A-H
A
题目
https://codeforces.com/contest/1676/problem/A
题解
思路
知识点：模拟。
照着模拟（细节加0防炸char，虽然这里没用）。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h> using namespace std; int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ string s; cin>>s; if(0+s[0]+s[1]+s[2] == 0+s[3]+s[4]+s[5]) cout<<YES<<'\n'; else cout<<NO<<'\n'; } return 0; } B
题目
https://codeforces.com/contest/1676/problem/B
题解
思路
知识点：贪心。
所有数减去最小的加在一起就行。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h> using namespace std; int a[57]; int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; int ans = 0,mincnt = 1e8; for(int i = 0;i<n;i++){ cin>>a[i]; mincnt = min(mincnt,a[i]); ans += a[i]; } ans -= n * mincnt; cout<<ans<<'\n'; } return 0; } C
题目
https://codeforces.com/contest/1676/problem/C
题解
思路
知识点：暴力。
（看错题浪费20分钟写成求全部字符串变成一样的最小次数。。。）
直接暴力求最小值就行。
时间复杂度 \(O(n^2m)\)
空间复杂度 \(O(nm)\)
代码
#include <bits/stdc++.h> using namespace std; string s[57]; int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; for(int i = 0;i<n;i++) cin>>s[i]; int ans = ~(1<<31); for(int i = 0;i<n;i++){ for(int j = i+1;j<n;j++){ int sum = 0; for(int k = 0;k<m;k++){ sum += abs(s[i][k] - s[j][k]); } ans = min(ans,sum); } } cout<<ans<<'\n'; } return 0; } D
题目
https://codeforces.com/problemset/problem/1676/D
题解
思路
知识点：暴力。
暴力枚举最大值，注意边界。
时间复杂度 \(O(n^2m)\)
空间复杂度 \(O(nm)\)
代码
#include <bits/stdc++.h> using namespace std; int a[207][207]; int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; for(int i = 0;i<n;i++) for(int j = 0;j<m;j++) cin>>a[i][j]; int ans = 0; for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ int sum = 0; for(int k = 0;k<n;k++){ if(0<= j-(i-k) && j-(i-k) <m)sum += a[k][j-(i-k)]; if(0<= j+(i-k) && j+(i-k) <m && j+(i-k) != j-(i-k))sum += a[k][j+(i-k)]; } ans = max(ans,sum); } } cout<<ans<<'\n'; } return 0; } E
题目
https://codeforces.com/problemset/problem/1676/E
题解
思路
知识点：前缀和，二分查找，贪心。
每次都选最大的即可最少消耗到达目标 \(x\) ，考虑预处理从大到小的前缀和，二分查找第一个大于等于 \(x\) 的和的下标即可。
注意 \(lower\_bound\) 和 \(upper\_bound\) 函数的用法，前者查找大于等于的第一个下标，后者查找大于的第一个下标。并且只可查找“升序”序列，当然这个升序可以自定义，比如用 \(greater\) 把大于定义成升序，即可查找从大到小的序列。
时间复杂度 \(O(nlogn)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h> using namespace std; int a[150007]; bool cmp(int a,int b){ return a>b; } int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n,q; cin>>n>>q; for(int i = 1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n,cmp); for(int i = 1;i<=n;i++) a[i] += a[i-1]; while(q--){ int x; cin>>x; int ans = lower_bound(a+1,a+1+n,x) - a; cout<<(ans<=n?ans:-1)<<'\n'; } } return 0; } F
题目
https://codeforces.com/problemset/problem/1676/F
题解
思路
方法1：
知识点：贪心，双指针，模拟。
遍历排序后的数组 \(a\) ，记录相同数字个数 \(sum\)，如果 \(sum \geq k\) ，则说明这个数字合法，记入临时右值 \(r\) 中，并重置 $sum = 1 $ ，即记录了下一段第一个数字的一次 。
直到某个数字 \(a[i-1]\) 的 \(sum<k\) 或者与后一个数字 \(a[i]\) 差大于 \(1\) ，即 \(a[i] - a[i-1] > 1\) ，说明 \(a[i-1]\) 这个数字在目前段中是最后一个可能合法数字。此时有两种情况，如果 \(sum \geq k\) 则说明数字 \(a[i-1]\) 是合法的更新右值 \(r\) ，否则不合法。之后更新答案，并更新左值为 \(a[i]\) 以及 \(sum = 1\)，即新段开始。
遍历结束就可以得到答案。注意初始化方便判断无解。
小细节，如果直接遍历，最后一段合法段可能没法判断，在循环外额外加个判断太丑，可以在末尾加一个不合法的数，循环范围调大一个数字，这样就可以用最后一个不合法数字中断遍历进行判断，而且不合法数字不会参与判断。
时间复杂度 \(O(nlogn)\)
空间复杂度 \(O(n)\)
方法2：
知识点：贪心，离散化，双指针，模拟。
用 \(map\) 做数字和次数的映射，可以将区间压缩到数字一个点，再进行遍历即可。思路一样，不合法次数的数字直接跳过，合法数字直接更新右值为这个数字，若这个数字与上一个区间的右值差大于 \(1\) 则更新左值为此数字。每次都更新答案可以少在循环外加一个判断去判断最后一段。
时间复杂度 \(O(nlogn)\)
空间复杂度 \(O(n)\)
两种方法，前者写起来麻烦但常数小，后者写起来方便但常数大容易被卡。
代码
方法1：
///直接遍历，非常快 #include <bits/stdc++.h> using namespace std; int a[200007]; int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n,k; cin>>n>>k; for(int i = 0;i<n;i++){ cin>>a[i]; } sort(a,a+n); a[n] = a[n-1] + 2;///小细节，防止最后一段不判断，在后面加个新段就行 int lans = 1,rans = 0,l = a[0],r = 0,sum = 1; ///lans最大区间的左值，rans最大区间的右值，l左值，r右值，sum计数 for(int i = 1;i<=n;i++){///这里需要到n，因为后面有个用来终止的段，不怕越界 if(a[i] == a[i-1]) sum++; else{ if(sum<k || a[i] - a[i-1] > 1){///此段终止 if(sum>=k) r = a[i-1];///若合法，则更新最大右值 if(rans - lans < r - l) rans = r,lans = l;///更新答案 l = a[i];///更新左值 } else{///还可以继续增加 r = a[i-1];///更新最大右值 } sum = 1;///重置计数 } } if(!rans) cout<<-1<<'\n'; else cout<<lans<<' '<<rans<<'\n'; } return 0; } 方法2：
///map，好写但常数大 #include <bits/stdc++.h> using namespace std; int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ map<int,int> cnt; int n,k; cin>>n>>k; for(int i = 0;i<n;i++){ int tmp; cin>>tmp; cnt[tmp]++; } int lans = 0,rans = -1;///保证r-l的合法也能更新，同时rans能用来判断无解 int l = 0,r = -1;///r保证第一段合法开始l就会被更新，于是l随意 for(auto [i,j]:cnt){///c++17才有这个用法。。。不然老老实实单变量 if(j < k) continue; if(i - r > 1) l = i; r = i; if(rans - lans < r - l){///每次都更新就可以避免最后一段没判断 rans = r; lans = l; } } if(!~rans) cout<<-1<<'\n'; else cout<<lans<<' '<<rans<<'\n'; } return 0; } G
题目
https://codeforces.com/problemset/problem/1676/G
题解
思路
方法1：
知识点：DFS，图论，DP。
用图的方式存树，可以构建一个双向的树，方便从根搜索孩子。
深搜，自上而下搜索子树，自底向上累加子树颜色和，先搜索子树后累加实现。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n^2)\)
方法2：
知识点：拓扑排序，图论，DP。
用父亲表示法建树，同时建立节点度的数组。
拓扑排序，自度为0的节点（叶子节点，无子树）开始向上层搜索，进行累加颜色和，一个节点度变为0证明子树颜色和完毕，可以把其放入队列，向其父节点遍历。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
感觉方法1的常数比方法2小。
代码
方法1：
///深搜，自底向上累加子树颜色和，先搜后加实现 #include <bits/stdc++.h> using namespace std; int c[4007]; vector<int> g[4007]; void dfs(int u,int fa){ for(int i = 0;i<g[u].size();i++){ if(g[u][i] == fa) continue;///不能以下犯上233 dfs(g[u][i],u);///先把子树的颜色数解决 c[u] += c[g[u][i]];///当前节点的为根的子树颜色数等于自己颜色加所有孩子子树的颜色数 } } int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; for(int i = 1;i<=n;i++) g[i].clear(),c[i] = 0; for(int i = 2;i<=n;i++){ int fa; cin>>fa; g[i].push_back(fa); g[fa].push_back(i); } for(int i = 1;i<=n;i++){ char col; cin>>col; if(col == 'W') c[i] = 1; else if(col == 'B') c[i] = -1;///黑色-1，白色1，平衡子树总和为0 } dfs(1,-1); int ans = 0; for(int i = 1;i<=n;i++){ ans += c[i] == 0; } cout<<ans<<'\n'; } return 0; } 方法2：
///拓扑排序，自底向上累加子树颜色和，先度为0（叶子）的节点向上累加实现 #include <bits/stdc++.h> using namespace std; int c[4007],deg[4007]; int fa[4007]; void toposort(int n){ queue<int> q; for(int i = 1;i<=n;i++){ if(!deg[i]) q.push(i); } while(!q.empty()){ int cur = q.front(); q.pop(); c[fa[cur]] += c[cur]; deg[fa[cur]]--; if(!deg[fa[cur]]) q.push(fa[cur]); } } int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; for(int i = 1;i<=n;i++) deg[i] = c[i] = 0; for(int i = 2;i<=n;i++){ cin>>fa[i]; deg[fa[i]]++; } for(int i = 1;i<=n;i++){ char col; cin>>col; if(col == 'W') c[i] = 1; else if(col == 'B') c[i] = -1;///黑色-1，白色1，平衡子树总和为0 } toposort(n); int ans = 0; for(int i = 1;i<=n;i++){ ans += c[i] == 0; } cout<<ans<<'\n'; } return 0; } H
题目
https://codeforces.com/problemset/problem/1676/H1
https://codeforces.com/problemset/problem/1676/H2
题解
思路
方法1：
知识点：分治，归并排序。
通过肉眼观察法得到最大交点数实际上就是逆序数变种，区别就是等于的也要算，用归并排序改一下即可。
时间复杂度 \(O(nlogn)\)
空间复杂度 \(O(n)\)
方法2：
知识点：树状数组。
这块还不会，改天再学，先贴大佬代码。
时间复杂度 \(O(?)\)
空间复杂度 \(O(?)\)
代码
方法1：
///归并排序 #include <bits/stdc++.h> using namespace std; long long cnt = 0; int a[200000+7],b[200000+7]; void merge_sort(int l,int r){ if(l >= r) return;///必须>=，因为mid+1可能会大于 int mid = (l+r)/2; merge_sort(l,mid); merge_sort(mid+1,r); int i = l,j = mid+1,k = l; while(i<=mid && j<=r){ if(a[i]<a[j])///改了这里 b[k++] = a[i++]; else b[k++] = a[j++],cnt+=mid-i+1;///表示从i到mid的数字都大于a[j]都要算一遍 } while(i<=mid) b[k++] = a[i++]; while(j<=r) b[k++] = a[j++]; memcpy(a+l,b+l,(r-l+1)*sizeof(int)); } int main(){ std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; for(int i = 0;i<n;i++) cin>>a[i]; cnt = 0; merge_sort(0,n-1); cout<<cnt<<'\n'; } return 0; } 方法2：
///树状数组 #include <bits/stdc++.h> using namespace std; template <typename T> struct Fenwick{ const int n; vector<T> a; Fenwick(int n):n(n),a(n){} void add(int x,T v) { for (int i = x+1;i<=n;i += i&-i){ a[i-1] += v; } } T sum(int x) { T ans = 0; for (int i = x;i>0;i -= i&-i){ ans += a[i-1]; } return ans; } T rangeSum(int l,int r){ return sum(r) - sum(l); } }; void solve(){ int n; cin >> n; vector<int> a(n); for (int i = 0;i<n;i++) { cin>>a[i]; a[i]--; } Fenwick<int> fen(n); long long ans = 0; for (int i = n-1;i>=0;i--) { ans += fen.sum(a[i]+1); fen.add(a[i],1); } cout<<ans<<\n; } int main(){ std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int t; cin>>t; while(t--){ solve(); } return 0; }