链接
题意:给你n个数并且有q次查询,查询的时候输入数组n中的一个下标,要求输出整个数组除了输入的下标剩下的所有数的与、或、异或。
思路:用前缀和与后缀和把三种位运算的值存一下,然后直接将前缀的i-1和后缀i+1直接计算,还有种思路是模拟位运算,开数组存,也不会t,下面贴个俊大佬的代码。
①:
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+1000; int a[maxn]; int ans1[maxn],ans2[maxn],ans3[maxn],ans4[maxn],ans5[maxn],ans6[maxn]; int main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,i,j,d,q; while(cin>>n>>q){ for(i=1;i<=n;i++){ cin>>a[i]; } i=1; ans1[i]=ans2[i]=ans3[i]=a[i]; for(i=2;i<=n;i++){ ans1[i]=a[i]&ans1[i-1]; ans2[i]=a[i]|ans2[i-1]; ans3[i]=a[i]^ans3[i-1]; } i=n;ans4[i]=ans5[i]=ans6[i]=a[i]; for(i=n-1;i>=1;i--){ ans4[i]=a[i]&ans4[i+1]; ans5[i]=a[i]|ans5[i+1]; ans6[i]=a[i]^ans6[i+1]; } while(q--){ int need; cin>>need; i=need; if(need==1){ cout<<ans4[2]<<" "<<ans5[2]<<" "<<ans6[2]<<endl; } else if(need==n){ n--; cout<<ans1[n]<<" "<<ans2[n]<<" "<<ans3[n]<<endl; } else { cout<<(ans1[i-1]&ans4[i+1])<<" "<<(ans2[i-1]|ans5[i+1])<<" "<<(ans3[i-1]^ans6[i+1])<<endl; } } } }
②:
#include<bits/stdc++.h> using namespace std; using LL = long long; const int N = 1e5 + 5; int n, q, a[N]; int getTowPow(int b) { int res = 1; for (int i = 1; i <= b; ++i) { res *= 2; } return res; } int getDigit (vector<int> a) { int res = 0; for (int i = 0; i < a.size(); ++i) { if (a[i] == 1) res += getTowPow(i); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while (cin >> n >> q) { int bit[31] = {}; //1 count for (int i = 1; i <= n; i++) { cin >> a[i]; int t = a[i], k = 30; while (t) { bit[k--] += (t & 1); t >>= 1; } } while (q--) { int p; cin >> p; int t = a[p], k = 30; vector<int> ad, o, x; bool fg = 0; while (k) { int q = (t & 1); int w = bit[k--]; if (w == 1 && q == 1) ad.push_back(0); else if (w == 1 && q == 0) { ad.push_back(1); fg = 1; } else if (w > 1) { ad.push_back(1); fg = 1; } else if (w == 0) ad.push_back(0); t >>= 1; } if (fg == 0) ad.clear(); fg = 0; t = a[p]; k = 30; while (k) { int q = (t & 1); int w = bit[k--]; if (w == n) { o.push_back(1); fg = 1; } else if (w == n - 1 && q == 0) { o.push_back(1); fg = 1; } else o.push_back(0); t >>= 1; } if (fg == 0) o.clear(); fg = 0; t = a[p]; k = 30; while (k) { int q = (t & 1); int w = bit[k--]; //cout << w << '\n'; if (w % 2 == 1 && q == 1) x.push_back(0); else if (w % 2 == 1 && q == 0) { x.push_back(1); fg = 1; } else if (w % 2 == 0 && q == 1) { x.push_back(1); fg = 1; } else if (w % 2 == 0 && q == 0) x.push_back(0); t >>= 1; } if (fg == 0) x.clear(); cout << getDigit(o) << ' ' << getDigit(ad) << ' ' <<getDigit(x) << '\n'; } } return 0; }