## DFS & BFS Example

DFS
easy:
Oil Deposits https://vjudge.net/problem/HDU-1241#author=prayerhgq

normal:
Eight II https://vjudge.net/problem/HDU-3567

DFS

int dfs(int crt) {
// 进入状态前
if (/*如果已经记录了数据*/) // 返回存储了的数据（记忆化）

// 处理状态中
// 检查是不是答案
// 可行性检查、最优性检查等

// 离开状态后
// 寻找之后的状态
for (/*iterate every choice*/) {
if (/*可达性判断*/) {
/*vis等标记处理*/
// 进入相邻的状态
dfs(next_state);
/*无效标记还原（backtrack）*/
}
}
}


BFS

void bfs() {
queue<T> q;
q.push(/*构建初始队列*/);

while (!q.empty()) {
// 状态前，获得当前状态属性等操作
crt = q.front();
q.pop();

// 处理状态中
if (/*达到解*/) {
/*找到解后的操作*/
}

// 状态后，将相邻状态加入队列
for (/*枚举每一种相邻状态*/) {
if (/*可达性、最优性、有效性等的检测*/) {
/*更新标记*/
q.push(/*新状态*/);
}
}

}
}


## 【CodeForces-400D】Dima and Bacteria【Disjoint Set + Floyd Warshall Algorithm】

【CodeForces-400D】Dima and Bacteria【Disjoint Set + Floyd Warshall Algorithm】

#include <iostream>
#include <vector>

using namespace std;
typedef long long LL;
struct Edge {
int to, w;
};
const int NLIM = 1e5 + 10;
const int SLIM = 500 + 10;
const int INF = 0xfffffff;
int parent[NLIM];
int ns[NLIM];       /* Node Set */
int c[SLIM];

inline int mini(int a, int b) {return a < b ? a : b;}

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

void Union(int x, int y) {
int nx = Find(x);
int ny = Find(y);
if (nx != ny) parent[nx] = parent[ny];
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < k; i++) {
cin >> c[i];
if (i) c[i] += c[i - 1];
}
for (int i = 0; i < k; i++) {
int crt = i ? c[i - 1] + 1 : 1;
while (crt <= c[i]) {
// save each node belong to which set
ns[crt] = i;
// init parent array
parent[crt] = crt;
crt++;
}
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
}
}
int u, v;
Edge tmp;
for (int i = 0; i < m; i++) {
cin >> u >> v >> tmp.w;
tmp.to = v;
tmp.to = u;
// cout << u << " " << v << " " << ns[u] << " " << ns[v] << " " << tmp.w << endl;
}
// use union-find set to check validity
bool flag = true;
for (int i = 0; i < k; i++) {
int crt = i ? c[i - 1] + 1 : 1;
if (c[i] == crt) {
}
while (crt <= c[i]) {
for (int j = 0; j < adjOfNode[crt].size(); j++) {
}
crt++;
}
crt = i ? c[i - 1] + 1 : 1;
int pre = Find(crt++);
for (; crt <= c[i]; crt++) {
if (Find(crt) != pre) break;
}
if (crt <= c[i]) {
flag = false;
break;
}
}
if (flag) {
// for (int i = 0; i < k; i++) {
//     for (int j = 0; j < k; j++) {
//         if (j) cout << ' ';
//     }
//     cout << endl;
// }
cout << "Yes\n";
// run the FloydDP
for (int r = 0; r < k; r++) {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
}
}
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (j) cout << " ";
}
cout << "\n";
}
} else {
cout << "No\n";
}
return 0;
}


## 【CodeForces-816A】Karen and Morning【进制+暴力+栈】

【CodeForces-816A】Karen and Morning【进制+暴力+栈】

Karen is getting ready for a new school day!

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.

Input:

The first and only line of input contains a single string in the format hh:mm (00 ≤ hh  ≤ 2300 ≤  mm  ≤ 59).

Output:

Output a single integer on a line by itself, the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome.

Solution:

#include <stdio.h>

int stack[2];
int isPalindrome(int h, int m) {
int pos = 0;
int cx = 2;
while (cx--) {
stack[pos++] = h % 10;
h /= 10;
}
while(pos--) {
if (stack[pos] != m % 10) return 0;
m /= 10;
}
return 1;
}

int main(void) {
int h, m;
int lim = 24 * 60;
scanf("%d:%d", &h, &m);
for (int cnt = h * 60 + m; true; cnt++) {
if (cnt >= lim) cnt %= lim;
if (isPalindrome(cnt / 60, cnt % 60)) {
printf("%d\n", ((cnt - h * 60 - m) % lim + lim) % lim);
break;
}
}
return 0;
}


## 【HDU-3746】Cyclic Nacklace【KMP找序列循环节】

【HDU-3746】Cyclic Nacklace【KMP找序列循环节】

#include <iostream>
#include <string>

using namespace std;

const int LIM = 1e5 + 10;
int kmp[LIM];
string str;
void build() {
int k = 0;
kmp[0] = 0;
for (int i = 1; i < str.size(); i++) {
while (k > 0 && str[k] != str[i]) k = kmp[k - 1];
if (str[k] == str[i]) k++;
kmp[i] = k;
}
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
while (n--) {
cin >> str;
build();
int len = str.size();
int l = len - kmp[str.size() - 1];
if (l != len && !(len % l)) {
cout << 0 << "\n";
} else {
cout << l - kmp[str.size() - 1] % l << "\n";
}
}
return 0;
}


## 【HDU-1358】Period【KMP的理解】

【HDU-1358】Period【KMP的理解】

Solution:

#include <iostream>
#include <string>

using namespace std;
// abcabcabc
// | | | | |
// v v v v v
// abcabc
//    abcabc
// 可以绘制每个字符的匹配线
// 如果长度与最大匹配差值小于最大匹配长度，则说明
// 前缀的一部分后缀已经成为了后缀的一部分前缀
// 如果此差值可以整除长度，则说明这个串是由这个差值串
// 多次拼接而成
const int LIM = 1e6 + 10;
int kmp[LIM];
string str;
void build() {
int k = 0;
kmp[0] = 0;
for (int i = 1; i < str.size(); i++) {
while (k > 0 && str[k] != str[i]) k = kmp[k - 1];
if (str[k] == str[i]) k++;
kmp[i] = k;
}
}

void solution() {
build();
for (int i = 1; i < str.size(); i++) {
int len = i + 1 - kmp[i];
if (len != i + 1 && !((i + 1) % len))
cout << i + 1 << ' ' << (i + 1) / len << "\n";
}
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
for (int k = 1; cin >> n && n; k++) {
cout << "Test case #" << k << "\n";
cin >> str;
solution();
cout << "\n";
}
return 0;
}


## 【HDU-5976】Detachment【二分+模逆元（费马小定理+同余式解法）】

【HDU-5976】Detachment【二分+模逆元（费马小定理+同余式解法）】

#include <iostream>

using namespace std;

typedef long long LL;
const int SIZE = 5e4;
const int LIM = 1e5;
const LL MOD = 1e9 + 7;
const LL MOD2 = 1e9 + 5;
LL pre[SIZE];
LL fractorial[SIZE];
// modula reverse identity element
LL mr[SIZE];

LL fastPow(LL base, LL p) {
LL ret = 1;
while (p) {
if (p & 1) ret = ret * base % MOD;
p >>= 1;
if (p) base = base * base % MOD;
}
return ret;
}

int main(void) {
// init
// the index is the number of answer's segments
pre[2] = 0;
pre[3] = 4;
int maxn;
for (LL i = 4; pre[i - 1] <= 1e9; i++) {
pre[i] = pre[i - 1] + i + 1;
// cout << i << " : " << pre[i] << "\n";
maxn = i;
}
// build the fractorial numbers' array
fractorial[0] = fractorial[1] = 1;
for (LL i = 2; i < SIZE; i++) {
fractorial[i] = fractorial[i - 1] * i % MOD;
}
// build the modulo reverse identity elements' array
for (LL i = 1; i < SIZE; i++) {
mr[i] = fastPow(i, MOD2);
}
int t;
LL x;
// start to deal with input
scanf("%d", &t);
while (t--) {
scanf("%lld", &x);
if (x < 5) {
printf("%lld\n", x);
continue;
}
// offset is 5
x -= 5;
int l = 2, r = maxn;
while (l < r) {
int mid = (l + r) >> 1;
if (pre[mid] > x) r = mid;
else l = mid + 1;
}
if (pre[l] > x) l--;
x += 5;
LL diff = x - (l * (l + 3) / 2);
// printf("cnt : %d\n", l);
// printf("fractorial[%d]: %lld\n", l + 2, fractorial[l + 2]);
// printf("pre[%d]: %lld\n", l, pre[l]);
// printf("diff: %lld\n", diff);
if (diff > l) {
printf("%lld\n", fractorial[l + 3] * mr[2] % MOD * mr[2 * l + 3 - diff] % MOD);
} else {
printf("%lld\n", fractorial[l + 2] * mr[l + 2 - diff] % MOD);
}
}
}

https://www.cnblogs.com/hsd-/p/5325780.html

https://oeis.org/A034893

## 【HDU-5975】Aninteresting game【lowbit数列】

【HDU-5975】Aninteresting game【lowbit数列】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;

LL query1(LL x) {
LL ret = 0;
for (LL i = 1; i <= x; i <<= 1) {
ret += ((x / i) - (x / (i << 1))) * i;
}
return ret;
}

LL query2(LL x, LL n) {
LL ret = 0;
while (x <= n) {
x += x & (-x);
ret++;
}
return ret;
}

int main(void) {
LL n, q, l, r;
int op;
while (~scanf("%lld%lld", &n, &q)) {
while (q--) {
scanf("%d", &op);
if (op & 1) {
scanf("%lld%lld", &l, &r);
printf("%lld\n", query1(r) - query1(l - 1));
} else {
scanf("%lld", &l);
printf("%lld\n", query2(l, n));
}
}
}
return 0;
}

lowbit数列：https://oeis.org/A006519

lowbit数列前缀和：https://oeis.org/A006520

## 【HDU-5973】Game of Taking Stones【威佐夫博弈】

【HDU-5973】Game of Taking Stones【威佐夫博弈】

Solution:

import java.util.Scanner;
import java.math.BigDecimal;

public class Main {
private static final BigDecimal EPS = new BigDecimal("0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001");
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigDecimal sqrt5 = sqrtNewtownMethod("5");
while (in.hasNext()) {
BigDecimal a = in.nextBigDecimal();
BigDecimal b = in.nextBigDecimal();
if (a.compareTo(b) > 0) {
BigDecimal t = a;
a = b;
b = t;
}
BigDecimal c = b.subtract(a).multiply(goldNum);
if (c.setScale(0, BigDecimal.ROUND_FLOOR).compareTo(a) == 0)
System.out.println("0");
else
System.out.println("1");
}
}
private static BigDecimal sqrtNewtownMethod(String b) {
BigDecimal two = BigDecimal.valueOf(2);
BigDecimal num = new BigDecimal(b);
BigDecimal pre = new BigDecimal(b);
BigDecimal crt = new BigDecimal("0");
while (true) {
// System.out.println(pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre))));
crt = pre.subtract(pre.multiply(pre).subtract(num).divide(two.multiply(pre), 102, BigDecimal.ROUND_FLOOR));
if (crt.subtract(pre).abs().compareTo(EPS) < 0) break;
pre = crt;
}
return crt;
}
}


## 【POJ-1988】Cube Stacking【带权并查集】

【POJ-1988】Cube Stacking【带权并查集】

Solution:

1.这个记录的值如何与查询的值联系起来

2.Union时如何更新这个值

3.find时如何更新（传播）这个值【通常Union后，合并前的某个根节点下的子结点的这个值没有更新，所以需要考虑如何在find时进行正确的更新】

（2）如何Union，Union的时候，假设我们要将根A并到根B下方，显然需要将根A的这个值记录为根B下的结点数，对于根节点，我们可以使用负值表示根，那么这个负数具体是负几就可以用来记录这个树下有多少结点，这样合并的时候的值就正好可以设置成这个值的相反数。

#include <iostream>

using namespace std;

const int NIL = -1;
const int LIM = 30000;
struct Node {
int parent, dist;
};
Node disSet[LIM];

inline char myGetChar() {
char ret;
while ((ret = getchar()) == ' ' || ret == '\n' || ret == '\t');
return ret;
}

Node find(int x) {
Node ret;
if (disSet[x].parent < 0) {
ret.parent = x;
ret.dist = 0;
return ret;
}
ret = find(disSet[x].parent);
ret.dist += disSet[x].dist;
disSet[x] = ret;
return ret;
}

void Union(int x, int y) {
x = find(x).parent;
y = find(y).parent;
if (x == y) return;
disSet[x].dist = -disSet[y].parent;
disSet[y].parent += disSet[x].parent;
disSet[x].parent = y;
}

int main(void) {
int p, x, y;
char op;
scanf("%d", &p);
// init
for (int i = 0; i < LIM; i++) {
disSet[i].parent = NIL;
disSet[i].dist = 0;
}
while (p--) {
op = myGetChar();
if (op == 'M') {
scanf("%d%d", &x, &y);
Union(x, y);
} else {
scanf("%d", &x);
printf("%d\n", find(x).dist);
}
}
return 0;
}


## 【CodeForces-812C】Sagheer and Nubian Market【二分】

【CodeForces-812C】Sagheer and Nubian Market【二分】

Solution:

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
int w;
struct Node {
int val, id;
bool operator < (const Node & n) const {
return val + id * w < n.val + n.id * w;
}
};

const int LIM = 1e5 + 10;
Node dat[LIM];

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
LL s;
cin >> n >> s;
for (int i = 0; i < n; i++) {
cin >> dat[i].val;
dat[i].id = i + 1;
}
int l = 0, r = n;
int mid;
LL sum;
while (l + 1 < r) {
mid = (l + r) >> 1;
w = mid;
sort(dat, dat + n);
sum = 0;
for (int i = 0; i < mid && sum >= 0; i++)
sum += dat[i].val + dat[i].id * mid;
// cout << mid << ": " << sum << endl;
if (sum >= s || sum < 0) r = mid;
else l = mid;
}
w = l;
sort(dat, dat + n);
LL ansa = 0;
for (int i = 0; i < l; i++)
ansa += dat[i].val + dat[i].id * l;
w = r;
sort(dat, dat + n);
LL ansb = 0;
for (int i = 0; i < r; i++)
ansb += dat[i].val + dat[i].id * r;
if (ansb > s) cout << l << ' ' << ansa;
else cout << r << ' ' << ansb;
cout << '\n';
return 0;
}