杭州网站建设很 棒,大中小网站的区分,wordpress seo 百度,网站开发工程师证书有用吗题面
分析#xff1a;
赛时一直纠结于与运算前缀和不可逆#xff0c;导致没有思路#xff0c;但是发现行不通并没有及时思考别的解决办法导致一条路走到黑#xff0c;阻碍了自己的思维#xff0c;在今年的网络赛赛时也是一样#xff0c;行不通的时候就没心思去重新想其…题面
分析
赛时一直纠结于与运算前缀和不可逆导致没有思路但是发现行不通并没有及时思考别的解决办法导致一条路走到黑阻碍了自己的思维在今年的网络赛赛时也是一样行不通的时候就没心思去重新想其他方法这是大忌以后要改必须能够赛时不断发散自己思维思考多种解决办法还有就是赛时遇到一些自我感觉麻烦的做法就认为对的可能性不大就不再去想要大胆思考各种方法多尝试。 虽然与运算不可逆但是拆开他的每一位从前向后记录他的每一位的1的个数这样就可以进行前缀和计算了根据后来的查询只需要查询区间内的每一位的1的个数只要区间内每一个数的二进制表示下第 i i i位都是1那么区间的与运算之和的第 i i i位也就一定是1这样就可以求出区间与运算的和进而二分解决。
代码
#include bits/stdc.husing namespace std;
using ll long long;const int N 2e5 10;int a[N][32];
int n;
int L;
int k;bool check(int mid) {int cnt 0;for(int i 0; i 31; i ) {//cout a[mid][i] ;if(a[mid][i] - a[L - 1][i] mid - L 1) cnt | (1 i);}
// cout mid cnt endl;return cnt k;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin T;while(T --) {cin n;for(int i 1; i n; i ) {int x;cin x;for(int j 0; j 31; j ) {a[i][j] a[i - 1][j] (x j 1);}}int q;cin q;while(q --) {cin L k;int l L - 1;int r n;while(l r) {int mid l r 1 1;if(check(mid)) l mid;else r mid - 1;}if(l L || l n) cout -1 ;else cout l ;//cout endl;}cout \n;}
}
