ACM ICPC 2008–2009, NEERC, Problem F Fenwick Tree(找规律，打表) Codeforces Gym 100623F

- 日理万妓 2022-06-11 05:17 113阅读 0赞

![Center][]

![Center 1][]

![Center 2][]

题意：给你一个长度为n的数组，每次操作可以改变一个数，要求用最少的操作次数将该数组变成一个self-fenwick数组，并输出该self-fenwick数组。

self-fenwick数组：如果存在一个数组，将其转化成其对应的树状数组后，与原数组一模一样，则称该数组为self-fenwick数组。

思路：

题目里给了我们将一个数组转化为对应的树状数组的规律

b\[1\] = a\[1\]  
b\[2\] = a\[1\] + a\[2\]  
b\[3\] = a\[3\]  
b\[4\] = a\[1\] + a\[2\] + a\[3\] + a\[4\]  
b\[5\] = a\[5\]  
b\[6\] = a\[5\] + a\[6\]

如果一个数组是self-fenwick数组，那么a\[i\]=b\[i\]，所以当i为奇数的时候，这个规律对我们没有任何用，但是当i为偶数的时候，我们可以得到该数组某几个数的和为0，例如当i=4的时候，我们可以得到a\[1\]+a\[2\]+a\[3\]=0，而题目里给出了这个规律的公式，所以我们可以确定是哪几个数的和为0。那么我们只需把当i为偶数的时候a\[i\]的值赋给b\[i\](因为当i为偶数的时候，b\[i\]的取值可以任意，没有影响),然后再根据之前的规律就可以把b\[i-1\]求出来(例如a\[1\]+a\[2\]+a\[3\]=0，那么a\[3\]=-a\[1\]-a\[2\])，i从2到N循环一遍，b数组就是a数组对应的答案。如果N是奇数，最后一个数是不需要改变的，要特判一下，AC代码如下。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL h[MAXN];
    LL l[MAXN];
    LL two[40];
    LL a[MAXN];
    LL b[MAXN];
    LL N;
    
    void init()//根据题目所提供的公式打表
    {
    	two[0] = 1;
    	for (int i = 1; i <= 30; i++)
    	{
    		two[i] = two[i - 1] * 2;
    	}
    	for (int i = 1; i < MAXN; i++)
    	{
    		for (int j = 30; j >= 0; j--)
    		{
    			if(i%two[j]==0)
    			{
    				h[i] =j;
    				break;
    			}
    		}
    	}
    	for (int i = 1; i < MAXN; i++)
    	{
    		l[i] = two[h[i]];
    	}
    }
    
    void solve()
    {
    	LL t;
    	b[0] = 0;
    	for (int i = 2; i <= N+1; i+=2)//因为i每次+2，所以i要循环到N+1来判断N为奇数的情况
    	{
    		if (i == N + 1)//判断N为奇数的情况
    		{
    			b[i - 1] = a[i - 1];
    			continue;
    		}
    		t = 0;
    		b[i] = a[i];
    		for (int j = i - l[i] + 1; j <= i - 1; j++)
    		{
    			if (j == i - 1)
    				continue;
    			t += b[j];
    		}
    		b[i - 1] = -t;
    	}
    }
    
    int main()
    {
    	freopen("fenwick.in", "r", stdin);
    	freopen("fenwick.out", "w", stdout);
    	init();
    	while (scanf("%lld",&N)!=EOF)
    	{
    		memset(a, 0, sizeof(a));
    		memset(b, 0, sizeof(b));
    		for (int i = 1; i <= N; i++)
    		{
     			scanf("%lld", &a[i]);
    		}
    		solve();
    		printf("%lld", b[1]);
    		for (int i = 2; i <= N; i++)
    		{
    			printf(" %lld", b[i]);
    		}
    		printf("\n");
    	}
    }

[Center]: /images/20220611/72a576d0997e456c916b98506dc83220.png
[Center 1]: /images/20220611/dd1e5d2b9858492dacb5f48d6ff599bb.png
[Center 2]: /images/20220611/527933a3c65d4e599e30d62ee8c382ea.png