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

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

Solution:

```#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++)
{
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】

Solution:

```#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;
}
```