第三题：1802. 有界数组中指定下标处的最大值
思路：最值，二分法，check。分类左右两侧与x的大小关系
class Solution { public: bool judge(int x, int n, int index, int maxSum) { long long sum = 0; if(x <= index+1) sum = sum + 1ll*(1+x)*x/2 + index+1-x; else sum += 1ll*(2*x-index)*(index+1)/2; if(x-1 <= n-1-index) sum += 1ll*x*(x-1)/2 + n-index-x; else sum = sum + 1ll*(2*x-n+index)*(n-1-index)/2; return sum <= maxSum; } int maxValue(int n, int index, int maxSum) { int l = 1, r = 1e9+1, ans; while(l <= r) { int mid = (l+r)>>1; if(judge(mid,n,index,maxSum)) { ans = mid; l = mid+1; } else { r = mid-1; } } return ans; } };
第四题：1803. 统计异或值在范围内的数对有多少
思路：异或值，字典树。查询与x异或值小于limit的个数。
class Solution { public: #define maxnode 32*20000+10 #define sigma 2 struct Trie { int ch[maxnode][sigma]; // int value[maxnode]; // 叶子节点的值 int cnt[maxnode]; // 经该节点的元素个数 int sz = 1; void init(){ memset(ch, 0 ,sizeof(ch)); memset(cnt, 0, sizeof(cnt)); } void insert(int x){ int u = 0; for(int i = 31; i >= 0; i--){ int c = (x>>i)&1; if(!ch[u][c]) ch[u][c] = sz++; u = ch[u][c]; cnt[u]++; } } // 查询与x异或，结果小于limit的数的个数 int query(int x, int limit){ int u = 0, res = 0; for(int i = 31; i >= 0; --i){ int a = (x>>i)&1, b = (limit>>i)&1; if(a == 0 && b == 0) u = ch[u][0]; if(a == 0 && b == 1) res += cnt[ch[u][0]], u = ch[u][1]; if(a == 1 && b == 0) u = ch[u][1]; if(a == 1 && b == 1) res += cnt[ch[u][1]], u = ch[u][0]; if(!u) break; } return res; } }trie; int countPairs(vector<int>& nums, int low, int high) { trie.init(); for(int num : nums) trie.insert(num); int n = nums.size(), ans = 0; for(int i = 0;i < n;i++) { // cout << trie.query(nums[i], high) << " " << trie.query(nums[i], low-1) << endl; ans = ans + trie.query(nums[i], high+1) - trie.query(nums[i], low); } return ans/2; // 一对算了两遍 } };