寒假集训5——二分

这三题我都超时了优化完可能会再上传。这些都不是AC代码请批判性查阅轻喷1.B2166 查找不重复元素出现的位置题目描述输入 n 个不超过 109 的严格递增的正整数组成的数列 a1​,a2​,…,an​然后进行 m 次询问。对于每次询问给出一个整数 q要求输出这个数字在序列中出现的下标。如果序列中不包含该数字请输出 −1 。注意下标从 1 开始。输入格式第一行包含两个正整数 n 和 m分别表示数列的长度和询问的次数。第二行包含 n 个正整数 a1​,a2​,…,an​。接下来 m 行每行包含一个正整数 q表示一次询问。输出格式输出共 m 行。对于每次询问如果数字 q 存在于数列中则输出它在数列中的下标如果不存在则输出 −1。输入输出样例输入 #1复制运行5 4 10 20 30 40 50 30 10 50 35输出 #1复制运行3 1 5 -1说明/提示对于所有测试点保证1≤n,m≤1061≤ai​,q≤109对于 1≤in保证 ai​ai1​。本题输入输出量较大请使用较快的 IO 方式。#includeiostream using namespace std; const int N 1e6 10; int arr[N]; int Find(int x, int arr[], int n) { int l 1; int r n; int m l (r - l) / 2; if (arr[l] x) return l; if (arr[r] x) return r; while (l r) { m l (r - l) / 2; if (arr[m] x) l m 1; else if (arr[m] x) r m - 1; else return m; } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m, q; cin n m; for (int i 1;i n;i) cin arr[i]; while (m--) { cin q; cout Find(q,arr,n) endl; } return 0; }2.B2167 查找最后一个出现的位置题目描述输入一个长度为 n 的非递减正整数数列 a1​,a2​,…,an​然后进行 m 次询问。对于每次询问给出一个整数 q要求输出这个数字在序列中最后一次出现的下标。如果序列中不包含该数字请输出 −1 。注意下标从 1 开始。输入格式第一行包含两个正整数 n 和 m分别表示数列的长度和询问的次数。第二行包含 n 个正整数 a1​,a2​,…,an​。接下来 m 行每行包含一个正整数 q表示一次询问。输出格式输出共 m 行。对于每次询问如果数字 q 存在于数列中则输出它在数列中最后一次出现的下标如果不存在则输出 −1。输入输出样例输入 #1复制运行8 5 2 3 5 5 5 8 9 9 5 2 9 6 8输出 #1复制运行5 1 8 -1 6说明/提示样例解释数列为 [2,3,5,5,5,8,9,9]。询问 5数字 5 最后一次出现在第 5 个位置。询问 2数字 2 最后一次出现在第 1 个位置。询问 9数字 9 最后一次出现在第 8 个位置。询问 6数列中不存在 6。询问 8数字 8 最后一次出现在第 6 个位置。数据范围对于所有测试点保证1≤n,m≤1061≤ai​,q≤109对于 1≤in保证 ai​≤ai1​。本题输入输出量较大请使用较快的 IO 方式。这题优化到这样已经是我想到的最优了真想不到别的办法了。主要是我觉得新的下标会覆盖旧的所以mp里面存的就是最新的下标而且这肯定比二分快也就只开了一个数组 。超时也不是内存超限证明就是快读快写的问题。然后我想过用scanf和printf优化还想过解除绑定优化然后还是不成功。#includestdio.h const long long N 1e9 10; int mp[N]; int main() { int n, m, q; scanf(%d%d,n,m); for (int i 1;i n;i) { int x; scanf(%d,x); //新的下标会覆盖旧的 mp[x] i; } while (m--) { scanf(%d,q); if (mp[q] 0) printf(%d\n,mp[q]); else printf(-1\n); } return 0; }3.P2249 【深基13.例1】查找题目描述输入 n 个不超过 109 的单调不减的就是后面的数字不小于前面的数字非负整数 a1​,a2​,…,an​然后进行 m 次询问。对于每次询问给出一个整数 q要求输出这个数字在序列中第一次出现的编号如果没有找到的话输出 −1 。输入格式第一行 2 个整数 n 和 m表示数字个数和询问次数。第二行 n 个整数表示这些待查询的数字。第三行 m 个整数表示询问这些数字的编号从 1 开始编号。输出格式输出一行m 个整数以空格隔开表示答案。输入输出样例输入 #1复制运行11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6输出 #1复制运行1 2 -1说明/提示数据保证1≤n≤1060≤ai​,q≤1091≤m≤105本题输入输出量较大请使用较快的 IO 方式。#includeiostream using namespace std; const int N1e610; int arr[N]; const int N19e8; int mp[N1*2]; int main() { int n,m,q; scanf(%d%d,n,m); for(int i1;in;i) scanf(%d,arr[i]); for(int in;i1;i--) mp[arr[i]]i; while(m--) { scanf(%d,q); if(mp[q]0) printf(%d ,mp[q]); else printf(-1 ); } return 0; }