网站 做内容分发资格,鞍山制作公司网站的公司,北京房产网站大全,做网站的是什么职位E.Yurii Can Do Everything
官方题解 按照题解的意思#xff0c;由于满足此条件的数量不多#xff0c;因此可以挖掘某些信息进行暴力。
考虑一个good subarray#xff1a;[al,al1,…,ar−1,ar][a_l,a_{l1},\dots,a_{r-1},a_r][al,al1,…,ar−1,ar] 按照题目意思满…E.Yurii Can Do Everything
官方题解 按照题解的意思由于满足此条件的数量不多因此可以挖掘某些信息进行暴力。
考虑一个good subarray[al,al1,…,ar−1,ar][a_l,a_{l1},\dots,a_{r-1},a_r][al,al1,…,ar−1,ar] 按照题目意思满足al⊕ar∑il1r−1aia_l\oplus a_r\sum_{il1}^{r-1}a_ial⊕ar∑il1r−1ai如果设al,ara_l,a_ral,ar二进制表示中最高位是分别为kl,krk_l,k_rkl,kr那么一定有2max(kl,kr)1∑il1r−1ai2^{max(k_l,k_r)1}\sum_{il1}^{r-1}a_i2max(kl,kr)1∑il1r−1ai由此我们正序逆序分别处理一下在不满足上述条件的情况下提前跳出循环注意可能重复计算
由于我们逆序处理只需要每次把和与2kl12^{k_l1}2kl1比较即可因为逆序后如果最开始右端点满足题意同样会枚举到如果原来的2kl12^{k_l1}2kl1和2kr12^{k_r1}2kr1都大于和那么可能会重复计算
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeset
#includemap
#includecmath
#includestack
#includequeue
#includerandom
#includebitset
#includestring
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includeunordered_map
#includeunordered_set
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N200010;
mappii,intmp;
int n,a[N],res;
void solve(bool op)
{for(int i1;i2n;i){ll sa[i1];int k0;for(int j0;j29;j)if(a[i]j1) kj;if(!op){for(int ji2;jn;j){if(s(a[i]^a[j])) res,mp[{n-j1,n-i1}]1;sa[j];if(s(1k1)) break;}}else{for(int ji2;jn;j){if(s(a[i]^a[j])!mp.count({i,j})) res;sa[j];if(s(1k1)) break;}}}
}
int main()
{IO;int T1;//cinT;while(T--){cinn;for(int i1;in;i) cina[i];solve(0);reverse(a1,a1n);solve(1);coutres\n;}return 0;
}总结如果自己感觉满足题意的个数不多可以考虑挖掘某些信息进行暴力提前跳出循环从而满足时间复杂度
