DFS & BFS Example

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

normal:
Connect https://vjudge.net/problem/CodeForces-1130C#author=XMIWmayIsWorld
大臣的旅费 http://www.dotcpp.com/oj/problem1438.html
Sum in the tree https://vjudge.net/problem/CodeForces-1098A

BFS
easy:
迷宫问题 https://vjudge.net/problem/POJ-3984
Red and Black https://vjudge.net/problem/POJ-1979#author=s19435631
学霸的迷宫 http://www.dotcpp.com/oj/problem1923.html

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;
vector<Edge> adjOfNode[NLIM];
int parent[NLIM];
int ns[NLIM];       /* Node Set */
int c[SLIM];
int adjOfSet[SLIM][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++;
        }
    }
    // init adjOfSet
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            adjOfSet[i][j] = INF;
        }
    }
    // load the adjacent list and matrix
    int u, v;
    Edge tmp;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> tmp.w;
        tmp.to = v;
        adjOfNode[u].push_back(tmp);
        tmp.to = u;
        adjOfNode[v].push_back(tmp);
        // cout << u << " " << v << " " << ns[u] << " " << ns[v] << " " << tmp.w << endl;
        adjOfSet[ns[u]][ns[v]] = mini(adjOfSet[ns[u]][ns[v]], tmp.w);
        adjOfSet[ns[v]][ns[u]] = mini(adjOfSet[ns[v]][ns[u]], tmp.w);
    }
    // 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) {
            adjOfSet[ns[crt]][ns[crt]] = 0;
        }
        while (crt <= c[i]) {
            for (int j = 0; j < adjOfNode[crt].size(); j++) {
                if (adjOfNode[crt][j].w == 0)
                    Union(crt, adjOfNode[crt][j].to);
            }
            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 << adjOfSet[i][j];
        //     }
        //     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++) {
                    adjOfSet[i][j] = mini(adjOfSet[i][j], adjOfSet[i][r] + adjOfSet[r][j]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (j) cout << " ";
                cout << (adjOfSet[i][j] == INF ? -1 : adjOfSet[i][j]);
            }
            cout << "\n";
        }
    } else {
        cout << "No\n";
    }
    return 0;
}

 

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

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

问题链接:https://vjudge.net/problem/CodeForces-816A

题目描述:

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:

这道题十分有趣。Karen认为在“回文时间”起床十分幸运,于是,程序要求,对于给出的她要睡觉的时间,找到这个时间距离最近的“回文(Palindrome)时间”间隔多少分钟。【解释:这题所谓“回文时间”,如05:50,它是回文的。而如05:23,它不是回文的,即两边数值是不对称的】

第一点:关于时间(年月日时)的处理十分常见,时间可以看成一种特殊的进制,在这里,我们可以注意到,分钟数是以60为进制的,每60分钟,就可以进位1到小时位上。反过来,1小时就相当于60分钟,那么我们可以把每一时刻都转化到唯一的分钟数上,如05:50就等于5 * 60 + 50 = 350分钟。

第二点:暴力(Brute Force)。暴力枚举在数据范围很小的情况下通常是一种很好的解决方案,这道题注意到时间的取值范围是00:00 ~ 23:59,按照“第一点”所提的方法,这里可以转化为24 * 60 + 0个不同的分钟数,直接尝试每个分钟数所对应的时间是否构成“回文时间”就好。

第三点:用栈判断回文。栈是一种很常用的数据结构,可以想象它是一个衣柜,每次我们只能把新的衣服放到最顶部,而取衣服的时候也只能从最顶部取。考虑时间05:50,我们先处理小时部分,即05,我们把个位的5先放入栈中,再把十位的0压入栈中,如下图。

接着,我们考虑分钟部分的50,我们依然先考虑它的个位(即0),我们将这个与上图栈顶的数比较,发现0 = 0,很好,二者一样;于是我们将这个栈顶的0扔掉,接着我们用十位(即5)比较现在的栈顶(刚刚栈顶的0扔出去了,于是现在的栈顶是5),发现5 = 5,很好,又一样,因此我们的任务完成了,发现这个就是“回文时间”。

我们发现,这里使用栈这种数据结构,为我们提供了逆序,因为我们知道,如果这个串是回文的,它的两边一定是对称的,那么我们如果把一边的顺序颠倒一下,二者就应该完全一样了,如果发现不一样,就说明不是回文。

#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的理解】

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

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

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://blog.csdn.net/qq_34374664/article/details/53466435

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

感谢大神们的分享。

另外,这个数列十分有趣,附上OEIS相关页面:

https://oeis.org/A034893

相关论文:https://cs.uwaterloo.ca/journals/JIS/VOL8/Doslic/doslic15.pdf

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

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

Solution:

对于查询1,我们可以发现,输出的其实就是L到R之间(包含L和R)所有数的lowbit之和,即\(\sum_{i = L}^Rlowbit(i)\)。但是我们不能去枚举这个数,因为枚举的平均复杂度是\(O(n)\),而这道题的n取值为1e18.我们采用前缀和的方法,因为我们可以\(O(logn)\)的时间复杂度求出从1到n之间的所有数lowbit之和,我们先考虑如果对于单个要求的lowbit,如何求出拥有这个lowbit的数在1到x中出现的次数,如果我们用x除以\(lowbit(i) = 2^k\),就可以知道x中有多少个不小于\(2^k\)的数,用它再减去x中有多少个不小于\(2^{k + 1}\)的个数,就得知了拥有lowbit(i)的数的个数,由于我们要求它们lowbit之和,求出每个拥有lowbit(i)的数的个数,再乘上lowbit(i)就可以了,于是我们的策略就是枚举lowbit(i)。【这道题时间卡很紧,这个查询尽量避免多余的移位、乘除、条件判断操作,否则会超时】

对于查询2,直接把平常树状数组更新操作的循环那里加一个计数,即可解决。

#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:

直接根据威佐夫博弈的定理,两堆数量之差乘上黄金分割比等于数量少的那堆的个数,先手必输,反之先手必胜。

求解黄金分割比使用公式\(\frac{\sqrt{5} – 1}{2}\),关于\(\sqrt{5}\)的求解,等价于求解函数\(f(x) = x^2 – 5\)与横坐标轴的正值交点的横坐标,显然\(\sqrt{5}\)就是上面所述问题的解,但是我们现在需要一个浮点数值,也就是一定精度下根号的浮点近似值,可以使用二分法(基于介值定理,我们知道如果在一个区间内有根,这个区间的左右端点函数值之积一定小于零),还可以使用牛顿迭代法,它的收敛速度会比二分法快,但是有时牛顿迭代法比二分法更容易出现不收敛的情况,不过对于当前函数是不存在这个问题的,因为我们确定要找的根在0到5的区间内,并且这个函数显然在这个区间内单调递增,因此选取初始值5可以确保函数值收敛到我们想要的位置上。

牛顿迭代法公式:\(x_n = x_{n – 1} – \frac{f(x_{n – 1})}{f'(x_{n – 1})}\)。

代码:

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");
        BigDecimal goldNum = sqrt5.add(BigDecimal.valueOf(1)).divide(BigDecimal.valueOf(2));
        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【带权并查集】

问题链接:https://vjudge.net/problem/POJ-1988

Solution:

叠箱子,一种想法是,使用双向链表,完全模拟这一过程,但是会超时,我们该用并查集解决。使用并查集的核心是,需要另外记录每个位置的高度,我们重新审视一下合并操作,将一个box A堆叠到另一个box B上,那么A的高度变成1,B的高度依旧是0;顺着这个思路,我们想尝试能否使用并查集记录某种值来解决,我们需要解决:

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

2.Union时如何更新这个值

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

首先,(1)可以被简单的设计出来,我们让一个点到其根节点的所有点上改值之和表示这个box下box的数量,这样显然也是可以通过路径压缩对路径上的这个值进行求和的,这样(3)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;
}

 

参考了:

https://www.youtube.com/watch?v=LfYiut7wYHI

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

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

Solution:

二分数量。按照下面的解决方案需要注意sum可能会爆掉,但是根据合法数据的s,是不会爆掉的,所以只要爆整数范围就认为当前试验的数量太多了,直接进入左区间。

每次需要排序,故复杂度O(nlognlogn).

代码:

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