这些题大部分是练二分答案。问题 C: 哈希查找1提交:6| 解决:1| 时间限制:1.00s| 内存限制:128MB视频: 无[提交] [状态]题目描述题目描述有一个数据字典里面存有n个不同数字(n100000)以哈希函数为f(x)x1存在数据字典中。小明现在接到一个任务这项任务看起来非常简单——给定m个数字分别查询这m个数字是否出现在字典之中但是考虑到你是个优秀的程序员如果查询的数存在表中你不仅要告诉小明数据存在还得贴心的告诉小明他查询的数的在数据字典中的下标下标从2开始到n1。若查询的数不存在则返回-1输入第一行包含两个整数n m分别代表字典中数字的个数和要查询的数字的个数。接着n个数代表字典中存在的n个数字。1a[i]100000最后m行表示要查询的数字输出输出m行如果某个数字存在则输出下标否则输出-1输入输出样例样例输入 #19 3 1 2 3 4 5 6 7 8 9 3 7 0样例输出 #14 8 -1这题我用vector显示运行错误也不知道为什么所以就用map了。#includeiostream #includevector #includealgorithm #includeunordered_map using namespace std; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n, q; cin n q; vectorinta(n); unordered_mapint, intmp; for (int i 0;i n;i) { cin a[i]; mp[a[i]] a[i] 1; } while (q--) { int x; cin x; if (mp.find(x) mp.end()) cout -1 \n; else cout mp[x] \n; } return 0; }问题 D: 哈希查找2提交:7| 解决:5| 时间限制:1.00s| 内存限制:128MB视频: 无[提交] [视频] [状态]题目描述根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)Key%p,将关键字映射到长度为p的哈希表中用线性探测法解决冲突。重复关键字放在hash表中的同一位置。输入输入数据第一行为两个正整数N(N 1000)和p(p 为大于等于 N的最小素数)N是关键字总数p是hash表长度第2行给出N个正整数关键字数字间以空格间隔。输出输出每个关键字在hash表中的位置以空格间隔。注意最后一个数字后面不要有空格。输入输出样例样例输入 #15 5 24 39 61 15 39样例输出 #14 0 1 2 0提示第二组样例输入5 521 21 21 21 21输出1 1 1 1 1#includeiostream #includevector #includealgorithm #includeunordered_map #define int long long using namespace std; //这题用vector不行要用unordered_map可能是因为数据范围太大了。 signed main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n, p; cin n p; vectorinta(n); unordered_mapint, intmp;//mol cnt_mol unordered_mapint, intpos;//a[i] mol for (int i 0;i n;i) { cin a[i]; pos[a[i]] -1;//初始化为不可能取得的数-1 } for (int i 0;i n;i) { if (pos[a[i]] ! -1)//如果之前处理过相同的数直接沿用跳过 continue; int mol a[i] % p; //如果冲突即mol这个位置之前被用过了也就是cnt_mol!0就顺延往后找 while (mp[mol] ! 0) { mol; mol % p; } mp[mol];//计数 pos[a[i]] mol; } for (int i 0;i n;i) cout pos[a[i]] ; return 0; }问题 G: C 语言习题 折半查找提交:20| 解决:5| 时间限制:1.00s| 内存限制:128MB视频: 无[提交] [状态]题目描述有 nnn 个数n≤1000000n \le 1000000n≤1000000这 nnn 个数已按从大到小顺序存放在一个数组中然后有 TTT 次查询每次输入一个数要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出0。输入第一行数组元素的个数 nnn。第二行 nnn 个数组元素的值。第三行输入查询次数 TTTT≤100000T \le 100000T≤100000。往下有 TTT 行每行输入一个需要查询的数字。输出查找的值在数组中的位置。输入输出样例样例输入 #1复制10 10 9 8 7 6 5 4 3 2 1 2 9 5样例输出 #1复制2 6提示注意数组空间为 100000010000001000000 和 100000100000100000。tips使用scanf和printf会更快哦这题二分我试了好几趟都超时只能用map了。#includeiostream #includevector #includeunordered_map using namespace std; const int N 1e9; unordered_mapint, intmp; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n; cin n; vectorinta(n); for (int i 0;i n;i) { cin a[i]; } //倒序存储不然后面的下标会覆盖前面的 for (int i n - 1;i 0;i--) { mp[a[i]] i 1;//记得1 } int q; cin q; while (q--) { int x; cin x; cout mp[x] \n; } return 0; }问题 I: 在线翻译提交:4| 解决:3| 时间限制:1.00s| 内存限制:128MB视频: 无[提交] [状态]题目描述你最近从滑铁卢搬到了另一个大城市这里的人们说着一种难以理解的外语。幸运的是你带着一本词典它可以帮助你与这里的人们沟通。输入输入包含不多于 100001000010000 条词条接着空一行然后是待翻译的短文包含不多于 100000100000100000 个外语单词。每一个词条占一行包含英语单词和对应的外语单词两者之间用空格隔开。短文中每个外语单词占 111 行。输人保证没有重复的外语单词且每个单词都由不多于 101010 个的小写字母组成。输出输出是翻译成英文的短文每个英文单词占一行。如果有词典中没有出现的外语单词则该单词应该被翻译成eh。输入输出样例样例输入 #1复制dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay样例输出 #1复制cat eh loops#includeiostream #includestring #includemap using namespace std; int main() { string s; mapstring, stringmp; while (getline(cin, s) s ! ) { int i 0; string a; while (s[i] ! ) { a.push_back(s[i]); i; } i; int n s.size(); string b; while (i ! n) { b.push_back(s[i]); i; } mp[b] a; } while (cins) { if (mp.find(s) ! mp.end())//注意这一行 cout mp[s] \n; else cout eh\n; } return 0; }问题 J: 查找最接近的元素提交:15| 解决:6| 时间限制:1.00s| 内存限制:128MB视频: 无[提交] [视频] [状态]题目描述在一个非降序列中查找与给定值最接近的元素。输入第一行包含一个整数 nnn为非降序列长度。1≤n≤1000001 \le n \le 1000001≤n≤100000。第二行包含 nnn 个整数为非降序列各元素。所有元素的大小均在 0−10000000000 - 10000000000−1000000000 之间。第三行包含一个整数 mmm为要询问的给定值个数。1≤m≤100001 \le m \le 100001≤m≤10000。接下来 mmm 行每行一个整数为要询问最接近元素的给定值。所有给定值的大小均在 0−10000000000 - 10000000000−1000000000 之间。输出mmm 行每行一个整数为最接近相应给定值的元素值保持输入顺序。若有多个值满足条件输出最小的一个。输入输出样例样例输入 #1复制3 2 5 8 2 10 5样例输出 #1复制8 5这题也错了好多次。#includeiostream #includevector #includealgorithm #includecmath using namespace std; int solve(vectorinta, int x) { int n a.size(); //处理边界 if (x a[0]) return a[0]; if (x a[n - 1]) return a[n - 1]; int l 0; int r n - 1; int m l (r - l) / 2; //二分主体 while (l r a[l]x a[r]x) { m l (r - l) / 2; //一定要卡退出条件不然会死循环 if (l m || r m || l r) break; if (a[m] x) r m; else if (a[m] x) l m; else return a[m]; } int ret a[l]; int mindt 0x3f3f3f;//最小差距 int dt abs(a[l] - x); //这里用倒序循环得到的就是最小的数 //这个循环右端点记得包含l //虽然前面用了a[l],但是循环的时候如果右端点不到l,还是会被覆盖 for (int i r;i l;i--) { dt abs(a[i] - x); if (dt mindt) { mindt dt; ret a[i]; } } return ret; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n; cin n; vectorinta(n); for (int i 0;i n;i) cin a[i]; sort(a.begin(), a.end()); int q; cin q; while (q--) { int x; cin x; cout solve(a, x) \n; } return 0; }问题 K: 和为给定数提交:15| 解决:5| 时间限制:1.00s| 内存限制:128MB视频: 无[提交] [视频] [状态]题目描述给出若干个整数询问其中是否有一对数的和等于给定的数。输入共三行 第一行是整数 nnn (0n≤100000)(0 \lt n \le 100000)(0n≤100000)表示有 nnn 个整数。第二行是 nnn 个整数。整数的范围是在 000 到 10810^8108 之间。第三行是一个整数 mmm (0≤m≤230)(0 \le m \le 2^{30})(0≤m≤230)表示需要得到的和。输出若存在和为 mmm 的数对输出两个整数小的在前大的在后中间用单个空格隔开。若有多个数对满足条件选择数对中较小的数更小的。若找不到符合要求的数对输出一行No。每个整数最多使用一次可能会出现相同的整数输入输出样例样例输入 #1复制4 2 5 1 4 6样例输出 #1复制1 5这题数据范围要卡到ull然后记得排序还要看是不是一个数重复用了两次。#includeiostream #includevector #includeunordered_map #includealgorithm //这题我开到了ull #define int unsigned long long using namespace std; signed main() { int n; cin n; vectorinta(n); unordered_mapint, intmp; for (int i 0;i n;i) { cin a[i]; mp[a[i]];//记录a[i]的个数 } int target; cin target; //先排序保证得到的答案是小的 sort(a.begin(), a.end()); for (int i 0;i n;i) { //如果是同一个数个数也只有一个不满足条件 if (a[i] target - a[i] mp[a[i]] 1) continue; //如果两个数都存在直接输出然后结束程序 if (mp[a[i]] 0 mp[target - a[i]] 0) { cout a[i] target - a[i]; return 0; } } //没有答案就输出No cout No; return 0; }问题 N: 快速找到和为零的四个数提交:11| 解决:2| 时间限制:2.00s| 内存限制:128MB视频: 无[提交] [视频] [状态]题目描述定义求和问题如下给定 444 组整数 A,B,C,DA, B, C, DA,B,C,D找到有多少四元组 (a,b,c,d)∈A×B×C×D(a, b, c, d) \in A \times B \times C \times D(a,b,c,d)∈A×B×C×D, 满足条件 abcd0a b c d 0abcd0。此问题中假设 A,B,C,DA, B, C, DA,B,C,D 具有相同的大小 nnn。输入输入包含多组测试数据。每组测试数据的第一行包含一个整数 nnn表示 A,B,C,DA, B, C, DA,B,C,D 的元素个数n≤1000n \leq 1000n≤1000。接下来 nnn 行每行 444 个整数分别属于 A,B,C,DA, B, C, DA,B,C,D每个整数的大小在 [−228,228]\left[ -228,228 \right][−228,228] 之间。输出对于每组测试数据输出满足条件的四元组的个数。输入输出样例样例输入 #1复制6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45样例输出 #1复制5这题暴力写四层循环会超时所以要用哈希表预处理两数之和。#includeiostream #includevector #includeunordered_map #define int long long using namespace std; signed main() { int n; cin n; vectorinta(n); vectorintb(n); vectorintc(n); vectorintd(n); for (int i 0;i n;i) { cin a[i] b[i] c[i] d[i]; } unordered_mapint, intmp; //用哈希表预处理a[i]b[j]的和出现的次数 for (int i 0;i n;i) { for (int j 0;j n;j) mp[a[i] b[j]]; } int cnt 0; for (int i 0;i n;i) { for (int j 0;j n;j) { //从哈希表找到目标值 //并加上匹配次数 cnt mp[-c[i] - d[j]]; } } cout cnt; return 0; }