比赛很不错都不是很难主要靠思维吧学东西多了喜欢把问题复杂化了反而看不懂题目的本质目录A 签到题L 签到题G hsq的群D hsq的神秘序列问题unordered_map查找配对元素位置会TN hsq的计组实验H 圣母的眼泪K hsq的子序列A 签到题桶排序#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long LL; typedef pairint,int PII; const int N200005 ; const int INF0x3f3f3f3f; int n; int a[10]; void solve() { cinn; int tp; for(int i1;in;i){ cintp; a[tp]; } int ansINF; for(int i0;i3;i){ if(ansa[i])ansa[i]; } coutans; } int main() { IOS int T1;//cinT; while(T--) solve(); return 0; }L 签到题#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x typedef long long LL; typedef pairint,int PII; const int N200005 ; const int INF0x3f3f3f3f; int n; int a[10]; void solve() { string s; cins; cout114514; } int main() { IOS int T1;//cinT; while(T--) solve(); return 0; }G hsq的群简单查询二分和哈希表都行#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n typedef long long LL; typedef pairint,int PII; const int N200005; const int INF0x3f3f3f3f; int n,m,q; void solve() { cinnmq; vectorunordered_setint st(m1); for(int j1;jm;j){ int k; cink; for(int t1;tk;t){ int x; cinx; st[j].insert(x); } } while(q--){ int a1,a2; cina1a2; int cnt0; for(int j1;jm;j){ if(st[j].count(a1) st[j].count(a2)) cnt; } coutcntendl; } } int main() { IOS int T1; cinT; while(T--) solve(); return 0; }D hsq的神秘序列思路查找一个序列中元素配对元素在另一个序列中的位置记录下来元素之间的顺序不能改变不能直接找有多少个配对元素新序列必须一一配对问题就转化成了以坐标为元素的最大上升子序列问题。问题unordered_map查找配对元素位置会T原因学了哈希其实比较好理解了unordered_map是给定的基数和模数如果出题故意卡哈希冲突就会变成链上的遍历O1就变成On了还有一个原因我们的插入值最大2^31很大超过负载因子*桶数量时unordered_map会重新分配更大的桶数量旧节点重新搬过去非常耗时。优化unordered_mapll, ll pos; pos.reserve(n * 2); // 提前申请足够多的桶避免多次扩容 pos.max_load_factor(0.7); // 把负载因子调低默认1.0降低冲突概率用空间换时间当然这题最好用二分查找lower_bound,O(logn)。unordered_map:动态插入查询二分静态查询优化2求最长上升子序列遍历元素upper_bound求第一个大于它的元素没有则上升数组序列边长有则替换但不影响最优序列长度值得好好想想最后数组大小就是答案#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false), cin.tie(0) #define endl \n #define ll long long int main() { IOS; int T; cin T; while (T--) { int n, m, k; cin n m k; ll full (1LL k) - 1; // 2^k - 1 vectorpairll, int a(n); // (值, 在A中的位置) for (int i 1; i n; i) { ll x; cin x; a[i - 1] {x, i}; } sort(a.begin(), a.end()); // 按值排序便于二分 vectorint pos; // 按B顺序收集匹配到的A位置 pos.reserve(m); for (int i 0; i m; i) { ll x; cin x; ll d full - x; // 需要的补值 if (d 0 || d full) continue; // 在排序后的a中二分查找d auto it lower_bound(a.begin(), a.end(), make_pair(d, -1)); if (it ! a.end() it-first d) { pos.push_back(it-second); // 记录A中的位置 } } if (pos.empty()) { cout 0 endl; continue; } // 对位置序列求 LIS最长上升子序列 vectorint lis; for (int p : pos) { auto it upper_bound(lis.begin(), lis.end(), p); if (it lis.end()) lis.push_back(p); else *it p; } cout lis.size() endl; } return 0; }N hsq的计组实验同样做麻烦了共4n个断点我们按分成四组每组转为十进制建立长度2n-1的环形数组谈论“120”个数情况若0个这一组没有断点可用ans0;若1个n-2个断点可用ans(n-2)若个数大于等于2个任意断点一定存在“120”(可惜比赛没想到这做麻烦了)ansn;#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define int long long void solve() { int n; string s,S; cinns; sss; S000100100000; int ans0; for(int j0;j4;j){ int num0; for(int ij;i4*n;i4){ string tps.substr(i,12); if(Stp) num; } if(num1){ ans(n-2); }else if(num1){ ansn; } } coutansendl; } signed main() { IOS int T1;cinT; while(T--) solve(); return 0; }H 圣母的眼泪问题的点1.动态维护中间值我做的时候是想的线段树应该是可以做的但是没必要题解给的是堆来实现但是看大二学长的multiset要更好。2.整体偏移我们可以设应该add存累加的值和懒标记类似。3.对称问题我们可知mid2*k-mid;我们先将add对称过去然后加上2k最后设置标记p记录mid最后的正负对称一次就翻转一次。#include bits/stdc.h using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl \n #define pb push_back #define dbg(x) std::cout#x:x #define int long long typedef pairint,int PII; const int N200005 ; const int INF0x3f3f3f3f; void solve() { int n,m; cinnm; multisetint L,R;//可重复的set //lambda表达式 auto add [](int x)-void { if(L.empty() || x *L.rbegin()){ L.insert(x); }else{ R.insert(x); } while(L.size() R.size() 1){ auto it prev(L.end()); R.insert(*it); L.erase(it); } while(R.size() L.size()){ auto it R.begin(); L.insert(*it); R.erase(it); } }; for(int i1;in;i){ int x; cinx; add(x); } //yp*xq; int p1,q0; auto work[](){ int a*L.rbegin(); int b; if(L.size()R.size()){ b*R.begin(); } else{ ba; } double resp*(ab)/2.0(double)q; printf(%.10lf\n,res); }; work(); while(m--){ int op,k; cinopk; if(op1){ add((k-q)/p); }else if(op2){ qk; }else{ p-p; q2*k-q; } work(); } } signed main() { IOS int T1;//cinT; while(T--) solve(); return 0; }K hsq的子序列我们可以将所有的1分为左右两部分左面全都是u右面全是t找我们的分界位置然后找多少对usst就行查找位置用三分