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

## 【HDU-6192】Removing Mountains【扩展KMP+hash】

【HDU-6192】Removing Mountains【扩展KMP+hash】

Solution：

F题拆完墙，这道K题又要移山了。。。回到正题，问题要求输出最短周期以及改造的山个数。问题当然要一步一步解决，先从最特殊的情况入手，如果当前只有一座山，则最短周期必然使是1，由于题目都明确要求他非得移山了，那只有一座山，他若想移那就移吧，所以$$n = 1$$时，输出“1 1”。。。【个人觉得，这是这道题最坑的地方】接着，如果这座山已经存在周期了，那么只好把它们全部移除来破掉旧的周期，达到最小的周期，所以输出“1 n”。接着就是一般情况了，枚举每种周期，根据扩展kmp得到的最大相同前缀长度，尝试修改其失配的第一个位置（两种修改方法，为了方便表述，假设现在枚举到周期i，用扩展kmp打出的数组【我命名成了kmp[]】中kmp[i]就表示从字符i到字符串结尾的子串与原字符串的最大相同前缀长度，则说明字符串【我命名为str】的str[kmp[i]]与str[kmp[i] + i]失配，两种修改方法就是拿前者替换后者，或者后者替换前者），接着使用hash值来判是否相同（这道题字符集很小，hash值不用取模，只要进制素数取得足够大，就不会发生碰撞，直接用hash值判断就可以确定字符串相同，关于hash进行字符串匹配，可以阅读：Rabin-Karp Algorithm，需要留意的一点是，链接的这篇文章中hash值存在碰撞的可能，所以需要在hash值匹配后进行二次判断）。

#include <iostream>
#include <string>

using namespace std;

typedef unsigned long long LL;
const int LIM = 1e6 + 10;
const int BASE = 131;
string str;
int kmp[LIM], n;
LL carryNum[LIM];
LL prehash[LIM];

// use ch to replace the character pos at br(beReplace)
inline LL getHash(int l, int r, int br, char ch) {
return prehash[r] - (l > 0 ? prehash[l - 1] * carryNum[r - l + 1] : 0)
+ (l <= br && br <= r ? -str[br] * carryNum[r - br] + ch * carryNum[r - br] : 0);
}

void init() {
int i;
for (carryNum[0] = 1, prehash[0] = str[0], i = 1; i < n; i++) {
carryNum[i] = carryNum[i - 1] * BASE;
prehash[i] = prehash[i - 1] * BASE + str[i];
}
}

void exkmp() {
kmp[0] = n;
int i;
for (i = 1; i < n && str[i - 1] == str[i]; i++);
kmp[1] = i - 1;
int p0 = 1;
for (i = 2; i < n; i++) {
if (i + kmp[i - p0] >= p0 + kmp[p0]) {
int j = p0 + kmp[p0] - i;
if (j < 0) j = 0;
for (; j + i < n && str[j + i] == str[j]; j++);
kmp[i] = j;
p0 = i;
} else {
kmp[i] = kmp[i - p0];
}
}
}

int main(void) {
ios::sync_with_stdio(false);
while (cin >> n >> str) {
if (n == 1) {
cout << 1 << " " << 1 << endl;
continue;
}
init();
exkmp();
for (int i = 1; i < n; i++) {
int lca = kmp[i];
if (i + lca == n) {
cout << i << " " << n << endl;
break;
} else {
int k = 0;
if (getHash(0, n - 1 - i, lca, str[i + lca]) == getHash(i, n - 1, lca, str[i + lca]))
k++;
if (getHash(0, n - 1 - i, i + lca, str[lca]) == getHash(i, n - 1, i + lca, str[lca]))
k++;
if (k) {
cout << i << " " << k << endl;
break;
}
}
}
}
return 0;
}

https://blog.csdn.net/u012345506/article/details/80134756

## 【HDU-6191】Query on A Tree【Trie + DFS】

【HDU-6191】Query on A Tree【Trie + DFS】

Solution:

【注：[]内表示该结点的标号，:后面则是该结点的值】

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int SIZE = 29;
const int LIM = 1e5 + 10;
const int NIL = -1;
int role[LIM * (SIZE + 3)], trie[LIM * (SIZE + 3)][2], root[LIM], values[LIM], sz[LIM];
int trie_size, node_size;
int idx[LIM];

inline void init(int n) {
trie_size = node_size = 0;
memset(trie, 0, sizeof trie);
memset(role, 0, sizeof role);
memset(sz, 0, sizeof sz);
for (int i = 1; i <= n; i++)
}

void update(int &crt, int pre, int vpos, int d) {
crt = ++trie_size;
trie[crt][0] = trie[pre][0];
trie[crt][1] = trie[pre][1];
role[crt] = role[pre] + 1;
if (d == NIL) return;
int key = (values[vpos] >> d) & 1;
if (key) update(trie[crt][1], trie[pre][1], vpos, d - 1);
else update(trie[crt][0], trie[pre][0], vpos, d - 1);
}

void dfs(int crt) {
idx[crt] = ++node_size;
sz[crt] = 1;
update(root[idx[crt]], root[idx[crt] - 1], crt, SIZE);
for (int i = 0; i < adj[crt].size(); i++) {
}
}

int query(int lb, int rb, int x, int d, int res) {
if (d == NIL) return res;
int key = ((x >> d) & 1) ^ 1;
int isInRange = role[trie[rb][key]] - role[trie[lb][key]];
if (isInRange) return query(trie[lb][key], trie[rb][key], x, d - 1, res | (1 << d));
else return query(trie[lb][key ^ 1], trie[rb][key ^ 1], x, d - 1, res);
}

int main(void) {
int n, q;
while (~scanf("%d%d", &n, &q)) {
init(n);
for (int i = 1; i <= n; i++)
scanf("%d", values + i);
for (int i = 2; i <= n; i++) {
int p;
scanf("%d", &p);
}
dfs(1);
int u, x;
while (q--) {
scanf("%d%d", &u, &x);
printf("%d\n", query(root[idx[u] - 1], root[idx[u] + sz[u] - 1], x,  SIZE, 0));
}
}
}

https://www.cnblogs.com/Blackops/p/7493464.html

https://www.cnblogs.com/teble/p/8952322.html

https://blog.csdn.net/jinglinxiao/article/details/77803383

## 【HDU-6187】Destroy Walls【最大生成树】

【HDU-6187】Destroy Walls【最大生成树】

Solution:

#include <iostream>
#include <algorithm>
// #define DBG

using namespace std;

const int LIM = 1e5 + 10;
struct Edge{
int x, y, w;
bool operator < (const Edge &e) const { return w > e.w; }
} edges[LIM * 2];
int parent[LIM];

int find(int x) {
if (x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}

bool Union(int x, int y) {
int xpos = find(x);
int ypos = find(y);
if (xpos == ypos) {
return false;
} else {
parent[ypos] = parent[xpos];
return true;
}
}

int main(void) {
int n, m;
while (~scanf("%d%d", &n, &m)) {
int sum = 0, cnt = 0, rest = 0;
for (int i = 1; i <= n; i++) {
scanf("%*d%*d");
parent[i] = i;
}
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
sum += edges[i].w;
}
sort(edges, edges + m);
#ifdef DBG
printf("Sorting...Done!\n");
for (int i = 0; i < m; i++) {
printf("edges[%d]: x = %d, y = %d, w = %d\n", i, edges[i].x, edges[i].y, edges[i].w);
}
printf("Show the edges...Done!\n");
#endif
for (int i = 0; i < m; i++) {
if (Union(edges[i].x, edges[i].y)) cnt++, rest += edges[i].w;
#ifdef DBG
printf("now cnt = %d, rest = %d, sum = %d\n", cnt, rest, sum);
printf("The parent[]:\n");
for (int i = 1; i <= n; i++)
printf("\tparent[%d] : %d\n", i, parent[i]);
printf("Done...\n");
#endif
}
printf("%d %d\n", m - cnt, sum - rest);
}
return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int LIM = 1e5 + 10;
struct Edge{
int x, y, w;
bool operator < (const Edge &e) const { return w > e.w; }
} edges[LIM * 2];
int parent[LIM];

int find(int x) {
if (x != parent[x]) parent[x] = find(parent[x]);
return parent[x];
}

bool Union(int x, int y) {
int xpos = find(x);
int ypos = find(y);
if (xpos == ypos) {
return false;
} else {
parent[ypos] = parent[xpos];
return true;
}
}

int main(void) {
int n, m;
while (~scanf("%d%d", &n, &m)) {
int sum = 0, cnt = 0, rest = 0;
for (int i = 1; i <= n; i++) {
scanf("%*d%*d");
parent[i] = i;
}
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
sum += edges[i].w;
}
sort(edges, edges + m);
for (int i = 0; i < m; i++) {
if (Union(edges[i].x, edges[i].y)) cnt++, rest += edges[i].w;
}
printf("%d %d\n", m - cnt, sum - rest);
}
return 0;
}

## 【HDU-6189】Law of Commutation

【HDU-6189】Law of Commutation

Solution:

from math import pow
for a in range(1, 6):
for n in range(1, 5):
m = int(pow(2, n))
cnt = 0
for b in range(1, m + 1):
if int(pow(a, b)) % m == int(pow(b, a)) % m:
cnt = cnt + 1
# print("a = ", a, "b = ", b, ", pow(a, b) = ", pow(a, b), ", pow(b, a) = ", int(pow(b, a)))
print("a = ", a, ", n = ", n, ", m = ", m, ", ans = ", cnt)

a =  1 , n =  1 , m =  2 , ans =  1
a =  1 , n =  2 , m =  4 , ans =  1
a =  1 , n =  3 , m =  8 , ans =  1
a =  1 , n =  4 , m =  16 , ans =  1
a =  2 , n =  1 , m =  2 , ans =  1
a =  2 , n =  2 , m =  4 , ans =  2
a =  2 , n =  3 , m =  8 , ans =  3
a =  2 , n =  4 , m =  16 , ans =  5
a =  3 , n =  1 , m =  2 , ans =  1
a =  3 , n =  2 , m =  4 , ans =  1
a =  3 , n =  3 , m =  8 , ans =  1
a =  3 , n =  4 , m =  16 , ans =  1
a =  4 , n =  1 , m =  2 , ans =  1
a =  4 , n =  2 , m =  4 , ans =  2
a =  4 , n =  3 , m =  8 , ans =  4
a =  4 , n =  4 , m =  16 , ans =  8
a =  5 , n =  1 , m =  2 , ans =  1
a =  5 , n =  2 , m =  4 , ans =  1
a =  5 , n =  3 , m =  8 , ans =  1
a =  5 , n =  4 , m =  16 , ans =  1

$$a^b = (2k)^b = 2^bk^b$$,

$$b^a = 2^{at} y^a$$,

$$y = \frac{b}{2^{ceil(n / a)}}$$

AC代码如下：

#include <iostream>

using namespace std;

typedef long long LL;

LL pow(LL a, LL b, LL mod) {
LL ret = 1;
while (b) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}

LL pow(LL a, LL b) {
LL ret = 1;
while (b) {
if (b & 1) ret = ret * a;
a = a * a;
b >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
LL a, n;
while (cin >> n >> a) {
if (a & 1) {
cout << "1" << endl;
} else {
LL cnt = 0, m = 1 << n;
for (LL b = 1; b <= n; b++)
if (pow(a, b, m) == pow (b, a, m)) cnt++;
LL tmp = 1 << ((n + a - 1) / a);
cnt += m / tmp - n / tmp;
cout << cnt << endl;
}
}
return 0;
}

## 【HDU-6184】Counting Stars【三元环+set+hash+邻接表】

【HDU-6184】Counting Stars【三元环+set+hash+邻接表】

Solution:

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
// #define DBG

using namespace std;

const int LIM = 1e5 + 5;
typedef long long LL;
struct edge {
int x, y;
bool operator < (const edge &e) const { return x < e.x; }
} edges[LIM * 2];
vector<int> v[LIM];
set<LL> e;
int n, m;
LL ans;

/* 用来计算hash值，结合set，可以用来快速判断是否存在某条边 */
inline LL myHash(LL x, LL y) {
return x + y * (n + 1);
}

inline void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}

inline void init() {
for (int i = 1; i <= n; i++)
v[i].clear();
memset(edges, 0, sizeof edges);
e.clear();
ans = 0;
}

LL getSum(int x, int y) {
LL cnt = 0;
if (v[y].size() <= v[x].size()) {
for (vector<int>::iterator ite = v[y].begin(); ite != v[y].end(); ite++)
} else {
/* 对于y顶点的度大于x顶点度的情况，使用set配合hash值查询 */
for (vector<int>::iterator ite = v[x].begin(); ite != v[x].end(); ite++)
if (e.find(myHash(*ite, y)) != e.end()) cnt++;
}
#ifdef DBG
printf("Edge: (%d, %d) -> cnt: %d\n", x, y, cnt);
#endif
/* 如果一条边有cnt个三元环，根据组合数学，应当会有cnt * (cnt - 1) / 2个题设结构 */
/* 需要注意cnt * (cnt - 1)可能会超过int的取值范围 */
return cnt * (cnt - 1) / 2;
}

int main(void) {
while (~scanf("%d%d", &n, &m)) {
init();
for (int i = 0; i < m; i++) {
scanf("%d%d", &edges[i].x, &edges[i].y);
e.insert(myHash(edges[i].x, edges[i].y));
e.insert(myHash(edges[i].y, edges[i].x));
v[edges[i].x].push_back(edges[i].y);
v[edges[i].y].push_back(edges[i].x);
/* 如果输入的第二个顶点小于第一个顶点，进行交换，为了维护我们需要的顺序 */
if (edges[i].x > edges[i].y) swap(edges[i].x, edges[i].y);
}
/* 将边按照x进行排序，edges数组中的边将会变得有序 */
sort(edges, edges + m);
int pre = 0;
for (int i = 0; i < m; i++) {
if (edges[i].x != pre) {
pre = edges[i].x;
for (vector<int>::iterator ite = v[edges[i].x].begin(); ite != v[edges[i].x].end(); ite++)
}
#ifdef DBG
cout << "#################" << endl;
for (int i = 1; i <= n; i++) {
}
cout << "#################" << endl;
#endif
ans += getSum(edges[i].x, edges[i].y);
}
printf("%lld\n", ans);
}
return 0;
}

7 12
1 7
2 1
4 2
4 5
6 5
6 7
1 3
2 3
4 3
5 3
6 3
7 3

8 16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
5 6
7 8

2 1
1 2

5 6
1 2
2 3
3 1
1 4
1 5
5 4

7 11
1 3
1 2
2 3
3 4
2 4
5 4
5 2
6 4
6 5
6 7
7 5

5 5
1 3
3 4
4 5
5 1
3 5

6
30
0
0
4
1

## 【HDU-6235】Permutation

【HDU-6235】Permutation

Solution:

Special Judge，想出来如何构造后，会感叹竟然有这么简单的题，先在奇数位置上从1开始每次递增1排过去，奇数位置排完，接着排偶数位置，这样任意相间排列的数之差都是1，显然1是任何数的因数。

#include <iostream>

using namespace std;

int main(void) {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
int bound = (n + 1) / 2;
for (int i = 1; i <= bound; i++) {
if (i - 1) putchar(' ');
printf("%d", i);
putchar(' ');
if (i + bound <= n) printf("%d", i + bound);
}
putchar('\n');
}
return 0;
}

## 【HDU-6231】K-th Number【尺取法+二分】

【HDU-6231】K-th Number【尺取法+二分】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;

const int LIM = 1e5 + 10;
int arr[LIM];
int n, k;
LL m;

bool deter(int v) {
int num = 0, lp = 0;
LL cnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] >= v) num++;
if (num == k) {
cnt += n - i;
while (arr[lp] < v) {
lp++;
cnt += n - i;
}
num--;
lp++;
}
}
return cnt >= m;
}

int main(void) {
int t;
scanf("%d", &t);
while (t--) {
int l = 1, r = 0;
scanf("%d%d%lld", &n, &k, &m);
/* input the data */
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
if (arr[i] > r) r = arr[i];
}
r++;
while (l < r) {
int mid = (l + r) >> 1;
if (deter(mid)) l = mid + 1;
else r = mid;
}
printf("%d\n", l - 1);
}
return 0;
}

## 【HDU-5869】Different GCD Subarray Query

【HDU – 5869】Different GCD Subarray Query

【2016 ACM/ICPC Asia Regional Dalian Online】

【gcd+离线查询+树状数组】

Solution:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
// #define DBG
using namespace std;

const int LIM = 1e5 + 10;
const int MAXI = 1e6 + 10;
struct query {
int l, r, idx;
bool operator < (const query & q) const {
return r < q.r;
}
} qs[LIM];
int data[LIM];
int bit[LIM];
int vis[MAXI];
int ans[LIM];
int n;
vector<pair<int, int> > gcds[LIM];

inline int gcd(int a, int b) {
return a % b ? (gcd(b, a % b)) : b;
}

inline int lowbit(int x) {
return x & (-x);
}

void add(int pos, int diff) {
while (pos < n) {
bit[pos] += diff;
pos += lowbit(pos);
}
}

int getSum(int pos) {
int ret = 0;
while (pos) {
ret += bit[pos];
pos -= lowbit(pos);
}
return ret;
}

int main(void) {
int q;
while (~scanf("%d%d", &n, &q)) {
for (int i = 1; i <= n; i++) {
scanf("%d", data + i);
gcds[i].clear();
}
/* discretization */
for (int i = 1; i <= n; i++) {
int g = data[i], lp = i;
for (int j = 0; j < gcds[i - 1].size(); j++) {
int tmpg = gcd(g, gcds[i - 1][j].first);
if (g != tmpg) {
gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
g = tmpg;
lp = gcds[i - 1][j].second;
}
}
gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
}
/* input the query and sort them */
for (int i = 0; i < q; i++) {

scanf("%d%d", &qs[i].l, &qs[i].r);
qs[i].idx = i;
}
sort(qs, qs + q);
/* operation of the binary index tree */
memset(vis, 0, sizeof vis);
memset(bit, 0, sizeof bit);
int pos = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < gcds[i].size(); j++) {
int g = gcds[i][j].first;
int lp = gcds[i][j].second;
vis[g] = lp;
}
while (qs[pos].r == i) {
ans[qs[pos].idx] = getSum(qs[pos].r) - getSum(qs[pos].l - 1);
pos++;
}
#ifdef DBG
printf("-----------------\n");
for (int i = 1; i <= 5; i++)
printf("%d: %d\n", i, bit[i]);
#endif
}
for (int i = 0; i < q; i++) {
printf("%d\n", ans[i]);
}
}
return 0;
}