本文主要是介绍Codeforces 400E Inna and Binary Logic(位运算+暴力)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Codeforces 400E Inna and Binary Logic
题目大意：给出n和m，表示有n个数，m次修改，然后给出n个数的值a1[i]，通过a1数组可以推断出a2数组，长的为a1的长度减一，接着a3、a4直到an（长度为1），ai[k] = ai-1[k] & ai-1[k+1].sun为所有数的和。每次修改有p和x两个值，表示将a1数组的第p个位置修改成x，输出修改后的sum。
解题思路：假设一开始计算好了sun，然后每一次修改的时候，x和t[p]，只要考虑二进制的每个位即可，如果（x&(1<<i)) == (t[p]&(1<<i))那么不变；如果（x&(1<<i)) = 1， (t[p]&(1<<i))=0，那么就要加上s；否则减掉s；s的计算方法：从p往左，连续的l个数t[j]&（1<<i) = 1，往右连续r个数t[j]&(1<<i) = 1，s = （l + r + l*r) * (1<<i)。因为如果出现有一个t[j]&(1<<i) = 0，那么在它后面有多少个t&(1<<i) = 1也没有用。解决完修改的部分，初始值计算就是个问题了，一开始用o（n^2)的方法超时了，很费解。初始值计算，对于每个位i，遍历一遍数组，计算各个连续的片t&（1<<i) = 1的个数c，s += （c*（c+1）*（1<<i)).
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>using namespace std;
typedef long long ll;
const int N = 1e5+5;
int n, m, t[N];
ll s;void find(int k, ll& l, ll& r, int x) {l = r = 0;for (int i = x-1; i; i--) {if ((t[i]&k) == 0) break;l++;}for (int i = x+1; i <= n; i++) {if ((t[i]&k) == 0) break;r++;}
}void solve (int p, int x, int y) {ll l, r;for (int i = 0; (1<<i) < N; i++) {int k = (1<<i);if ((x&k) == (y&k)) continue;find(k, l, r, p);ll u = (l * r + l + r + 1) * (ll)k;if (x&k) {s += u;} else {s -= u;}}
}void init () {s = 0;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) scanf("%d", &t[i]);for (int i = 0; (1<<i) < N; i++) {int k = (1<<i);ll c = 0;for (int j = 1; j <= n; j++) {if (t[j]&k) c++;else {if (c) s += (c*(c+1)*(ll)k/2);c = 0;}}if (c) s += (c*(c+1)*(ll)k/2);}
}int main () {init ();int p, x;for (int i = 0; i < m; i++) {scanf("%d %d", &p, &x);solve (p, x, t[p]);t[p] = x;cout << s << endl;}return 0;
}
这篇关于Codeforces 400E Inna and Binary Logic(位运算+暴力)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
