1:数组元素的目标和
首先是暴力做法:
暴力做法就是遍历两个数组，如果相加为x，那么就输出这个i和j
然后介绍的是双指针算法
1. #include<iostream> 2. using namespace std; 3. const int N=100010; 4. int a[N],b[N],n,m,x; 5. 6. int main(void) 7. { 8. scanf("%d %d %d",&n,&m,&x); 9. for(int i=0;i<n;i++) scanf("%d",&a[i]); 10. for(int i=0;i<m;i++) scanf("%d",&b[i]); 11. 12. for(int i=0,j=m-1;i<n;i++) 13. { 14. while(a[i]+b[j]>x) j--; 15. if(a[i]+b[j]==x) 16. { 17. printf("%d %d\n",i,j); 18. } 19. } 20. return 0; 21. }
也可以使用二分查找来解题：依次遍历a数组，然后通过a数组当前的值来反解出来符合条件的值，然后在b数组中看是否可以找到
1. #include<iostream> 2. using namespace std; 3. const int N=100010; 4. int a[N],b[N],n,m,x; 5. 6. int main(void) 7. { 8. scanf("%d %d %d",&n,&m,&x); 9. for(int i=0;i<n;i++) scanf("%d",&a[i]); 10. for(int i=0;i<m;i++) scanf("%d",&b[i]); 11. 12. for(int i=0;i<n;i++) 13. { 14. int y=x-a[i]; 15. int l=0,r=m-1; 16. while(l<=r) 17. { 18. int mid=l+r>>1; 19. if(b[mid]==y) 20. { 21. printf("%d %d",i,mid); 22. return 0; 23. }else if(b[mid]<y) 24. { 25. l=mid+1; 26. }else 27. { 28. r=mid-1; 29. } 30. } 31. } 32. return 0; 33. }
2.区间和
1. #include<iostream> 2. #include<algorithm> 3. #include<vector> 4. using namespace std; 5. const int N = 1000010; 6. typedef pair<int, int>PII; 7. vector<PII>query, add;//询问区间还有需要增加的 8. vector<int>alls; 9. int a[N], s[N];//s[N]为前缀和 10. int n, m, l, r, c, x; 11. 12. int find(int x) 13. { 14. int l = 0, r = alls.size() - 1; 15. while (l < r) 16. { 17. int mid = l + r >> 1; 18. if (alls[mid] >= x) 19. { 20. r = mid; 21. } 22. else 23. { 24. l = mid + 1; 25. } 26. } 27. return l + 1; 28. } 29. 30. int main(void) 31. { 32. scanf("%d %d", &n, &m); 33. for (int i = 0; i < n; i++) 34. { 35. scanf("%d %d", &x, &c); 36. add.push_back({ x,c }); 37. alls.push_back(x); 38. } 39. for (int i = 0; i < m; i++) 40. { 41. scanf("%d %d", &l, &r); 42. query.push_back({ l,r }); 43. alls.push_back(l); 44. alls.push_back(r); 45. } 46. //对所有的区间进行排序，然后进行去重，离散化 47. sort(alls.begin(), alls.end()); 48. alls.erase(unique(alls.begin(), alls.end()), alls.end()); 49. for (auto tmp : add) 50. { 51. int x = find(tmp.first); 52. a[x] += tmp.second; 53. } 54. //求前缀和 55. for (int i = 1; i <= alls.size(); i++) 56. { 57. s[i] = s[i - 1] + a[i]; 58. } 59. //求区间和 60. for (auto tmp : query) 61. { 62. int l = find(tmp.first), r = find(tmp.second); 63. printf("%d\n", s[r] - s[l - 1]); 64. } 65. return 0; 66. }
3.双链表
首先我们约定链表头是0，尾是1，这里说的都是下标
所以先对链表进行初始化
然后是插入操作：
删除操作就很简单了：
1. r[l[k]] = r[k]; 2. l[r[k]] = l[k];
1. #include<iostream> 2. using namespace std; 3. int m; 4. const int N = 100010; 5. int e[N], r[N], l[N], idx; 6. 7. void init() 8. { 9. r[0] = 1; 10. l[1] = 0; 11. idx = 2; 12. } 13. 14. void add(int k, int x) 15. { 16. e[idx] = x; 17. r[idx] = r[k]; 18. l[idx] = k; 19. l[r[k]] = idx; 20. r[k] = idx; 21. idx++; 22. } 23. 24. void move(int k) 25. { 26. r[l[k]] = r[k]; 27. l[r[k]] = l[k]; 28. } 29. 30. int main(void) 31. { 32. cin >> m; 33. init(); 34. while (m--) 35. { 36. string op; 37. cin >> op; 38. int k, x; 39. if (op == "R") 40. { 41. cin >> x; 42. add(l[1], x); 43. } 44. else if (op == "L") 45. { 46. cin >> x; 47. add(0, x); 48. } 49. else if (op == "D") 50. { 51. cin >> k; 52. move(k + 1); 53. } 54. else if (op == "IL") 55. { 56. cin >> k >> x; 57. add(l[k + 1], x); 58. } 59. else { 60. cin >> k >> x; 61. add(k + 1, x); 62. } 63. } 64. for (int i = r[0]; i != 1; i = r[i]) 65. { 66. cout << e[i] << " "; 67. } 68. return 0; 69. }
4：单调栈
暴力解法：从当前位置依次往前遍历，看是否有满足条件的数，有就输出，没有就输出-1
当我们遍历了前面的数，可以利用已知信息来减少遍历次数
思路：
1. #include<iostream> 2. using namespace std; 3. const int N=100010; 4. int stk[N],m,x,tt; 5. 6. int main(void) 7. { 8. scanf("%d",&m); 9. while(m--) 10. { 11. scanf("%d",&x); 12. while(stk[tt]>=x&&tt) 13. { 14. tt--; 15. } 16. if(tt) printf("%d ",stk[tt]); 17. else printf("-1 "); 18. stk[++tt]=x; 19. } 20. return 0; 21. }
