【HDU-5898】odd-even number【记忆化搜索】

【HDU-5898】odd-even number【记忆化搜索】

问题链接:https://vjudge.net/problem/HDU-5898

Solution:

看到这个问题自然会想到一个办法:搜索一下每个数就好。关键的问题就是,全部搜索会超时,这时注意到搜索过程中有大量重复过程,我们把那些搜索结果以及其对应的状态【五种状态:START开始,ENE (Even Number Even)偶数个偶数,ONE (Odd Number Even)奇数个偶数,ONO (Odd Number Odd)奇数个奇数,ENO (Even Number Odd)偶数个奇数】都存储下来就可以解决。

另外,搜索过程中用一些标识来说明当前这个数字是不是最高位、是不是该位的最大数字是有帮助的,这样就可以确定下一位进行枚举的时候的枚举范围。

另外还有个技巧是,题目要求寻找的是区间内的个数,但是这样很不方便搜索,那么我们把搜索的目标转移到小于等于某个数的所有符合题意的数的个数,这样只要用区间最大值搜一下个数减去区间最小值减一搜一下个数就好。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

enum {ENE ,ONE, ONO, ENO, START};
const int NIL = -1;
const int LIM = 20;
const int SIZE = 5;
int digit[LIM];
LL dp[LIM][SIZE];

inline bool isOdd(int x) { return x & 1; }

LL dfs(int crt, bool islead, bool hasLimit, int state) {
  if(crt == NIL) return (state == ONE || state == ENO) && !islead;
  if(!hasLimit && !islead && dp[crt][state] != NIL) return dp[crt][state];
  int upBound = hasLimit ? digit[crt] : 9;
  LL cnt = 0;
  for(int i = 0; i <= upBound; i++)
  {
    if(islead) {
            cnt += dfs(crt - 1,islead && !i,hasLimit && (i == upBound), isOdd(i) ? ONO : ONE);
    } else {
      if(state == ENO) cnt += dfs(crt - 1, false, hasLimit && (i == upBound), isOdd(i) ? ONO : ONE);
      if(state == ONO && isOdd(i)) cnt += dfs(crt - 1, false, hasLimit && (i == upBound), ENO);
      if(state == ONE) cnt += dfs(crt - 1, false, hasLimit && (i == upBound), isOdd(i) ? ONO : ENE);
      if(state == ENE && !isOdd(i)) cnt += dfs(crt - 1, false ,hasLimit && (i == upBound), ONE);
    }
  }
  if(!hasLimit && !islead) dp[crt][state] = cnt;
  return cnt;
}
LL getNum(LL x) {
    memset(dp, NIL, sizeof(dp));
  int crt = 0;
  while(x) {
    digit[crt++] = x % 10;
    x /= 10;
  }
  return dfs(crt - 1, true, true, START);
}

int main() {
    int t;
  scanf("%d",&t);
  for(int k = 1; k <= t; k++) {
    LL left, right;
    scanf("%lld%lld", &left, &right);
    printf("Case #%d: %lld\n", k, getNum(right) - getNum(left - 1));
  }
    return 0;
}

 

 

【HDU-5892】Resident Evil【2-D Binary Indexed Tree】

【HDU-5892】Resident Evil【2-D Binary Indexed Tree】

问题链接:https://vjudge.net/problem/HDU-5892

Solution:

类似于区域和的查询及更新,使用二维树状数组,但是这道题有点特殊,特殊之处在于:如果对区域内每个点都进行一次更新调用的话,会超时。注意到我们仅仅是在做异或运算,而树状数组的查询得到的相当于是一种“前缀和”,下面暂时以一维树状数组来理解:如果我们对一个左端点为奇数的区间中每个点进行更新,最后必然得到区间内奇数点更新奇数次,偶数点更新偶数次;反过来,如果左端点是偶数,则必然偶数点更新奇数次、奇数点更新偶数次【注意:这里所说的更新不是指树状数组下标奇偶的更新情况,而是指更新结束后的最终效果,由于树状数组的查询结果是前缀,所以每当一个点进行更新时,后面所有点的查询返回值都会进行更新,就出现了上面的结果】,由于我们在做异或运算,偶数次更新不需要做,所以只需要根据左端点的情况单独对奇数或偶数两种情况进行更新就好,即对于奇数、偶数分开维护树状数组。这时还有一件事需要处理,我们不能只根据左端点更新完就结束,还要根据右端点来做一个“补充”,详情是这样的:对于左端点是奇数的情况,如果右端点也是奇数,那么右端点后的所有数都具有奇数次更新,这时,对于奇数的树状数组,我们不需要做任何操作,因为根据左端点的更新已经更新了所有奇数树状数组的值了,但是对于偶数的树状数组,我们需要对右端点值加1的点进行一次更新;当右端点是偶数时,它之后的奇数都具有偶数次更新,也就是不应该异或,但是左端点在更新时都对它们做了异或,我们仍然需要对右端点值加1的点进行一次更新【左端点是偶数的情况也能够推出这个结论,这里省略】。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int LIM = 3010;
LL bit[2][2][LIM][LIM];
int n, m;

void update(int x, int y, LL diff) {
    for (int i = x; i <= n; i += i & (-i)) {
        for (int j = y; j <= n; j += j & (-j)) {
            bit[x & 1][y & 1][i][j] ^= diff;
        }
    }
}

LL query(int x, int y) {
    LL ret = 0;
    for (int i = x; i; i -= i & (-i)) {
        for (int j = y; j; j -= j & (-j)) {
            ret ^= bit[x & 1][y & 1][i][j];
        }
    }
    return ret;
}

int main(void) {
    char op[3];
    int lx, ly, rx, ry, cnt, a, b;
    LL tmp;
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%s%d%d%d%d", op, &lx, &ly, &rx, &ry);
        if (op[0] == 'Q') {
            tmp = query(rx, ry) ^ query(rx, ly - 1) ^ query(lx - 1, ry) ^ query(lx - 1, ly - 1);
            for (int i = 0; i < 50; i++)
                printf("%d ", (tmp >> i) & 1 ? 2 : 1);
            putchar('\n');
        } else {
            scanf("%d", &cnt);
            tmp = 0;
            while (cnt--) {
                scanf("%d%d", &a, &b);
                if (b & 1) tmp ^= 1ll << (a - 1);
            }
            update(lx, ly, tmp);
            update(rx + 1, ly, tmp);
            update(lx, ry + 1, tmp);
            update(rx + 1, ry + 1, tmp);
        }
    }
    return 0;
}