题目描述
Abathur采集了一系列Primal Zerg 的基因样本,这些基因构成了一个完整的进化链。为了方便,我们用A0,A1…An-1 这n 个正整数描述它们。 一个基因Ax 可以进化为序列中在它之后的基因Ay。这个进化的复杂度,等于Ax | Ax+1…| Ay的值,其中| 是二进制或运算。 Abathur 认为复杂度小于M 的进化的被认为是温和的。它希望计算出温和的进化的对数。
思路
将全部数转化为二进制数进行操作,详见代码
#include
#include
#include
using namespace std;
#define maxn 200001
#define maxm 41
#define fill(x, y) memset(x, y, sizeof(x))
int a[maxn][maxm];
int f[maxm];
bool check()
{
for (int k = maxm - 1; k >= 1; k--)
{
if (a[0][k] == 1 && f[k] == 0) return 1;
if (a[0][k] == 0 && f[k] > 0) return 0;
}
}
int main()
{
freopen("evolve.in", "r", stdin);
freopen("evolve.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
int l = 0;
while (m > 0)
{
int x = m % 2;
a[0][++l] = x;
m /= 2;
}
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
int l = 0;
while (x > 0)
{
int y = x % 2;
a[i][++l] = y;
x /= 2;
}
}
long long ans = 0;
for (int i = 1; i <= maxm; i++)
f[i] = a[1][i];
int i = 1, j = 1;
do
{
while (check())
{
j++;
for (int k = 1; k < maxm; k++) f[k] += a[j][k];
if (j > n) break;
}
if (j <= n) for (int k = 1; k < maxm; k++) f[k] -= a[j][k];
j--;
ans += j - i;
for (int k = 1; k < maxm; k++) f[k] -= a[i][k];
i++;
}
while (i != n);
printf("%lld\n", ans);
}
]]>
Comments NOTHING