一、题意 每组数据给出a,b,c,d四个值。a,b,c为三个杯子的容量，其中初始时前两个杯子为空，最后一个装满了水。d为目标水量。要求你在这三个杯子之间相互倒水，每次倒水要么源杯倒空，要么把目标杯倒满，不能把水倒掉。求最少的总倒水量，使得最终至少有一个杯子的水量最接近d。输出这个最少的总倒水量以及最接近d的那个值。 二、解析 这是一道典型的隐式bfs题目。老规矩，找状态点！在本题中，状态先就是三个杯子的容量和总倒水量。为什么状态包括总倒水量呢？因为本题中最短路径中的最短指的是总倒水量最少，因此需要将其算入状态的维度之中，同时需要使用优先队列来使得每次先弹出到水量最小的点。这样的话vis数组难道...

一、题意 如果一个字符串包含两个相邻的重复子串，则称它为容易的串。输入k和L, 要求输出由前L个字母组成的、字典序第k小的困难的串。 二、解析 通过回溯法按字典序枚举字符串，每次枚举都对应这当前字符串的最后一个字符。因此判断是否是困难的串时，就可以只判断当前字符串的后缀有没有出现相邻的重复子串即可。这个原理就像是：八皇后问题中，只需要判断新皇后和之前的皇后有无冲突，而不需要判断以前的皇后是否相互冲突。 三、代码 #include <iostream> #include <string> using namespace std; int k, L, cnt; string...

一、题意 每组数据给一个n。要求你输出所有1...n的从1开始的排列，每个排列满足相邻两个（包括首尾两个）之和为素数。输出顺序按字典序。 二、解析 看到这题第一反应是枚举全排列，事实证明那样会超时。紫薯告诉我们，回溯法总是比生成-测试法快得多。因此我们考虑用回溯的思想。需要一个递归深度值idx表示当前递归到第几个数，然后还有一个值cur表示当前选择的值。需要一个判断素数得函数。 三、代码 #include <iostream> using namespace std; const int maxn = 16 + 5; int n, kase = 0, vis[maxn], ans[...

一、题意 有若干组数据。每组数据给一个8*8棋盘，棋盘上每个位置上有一个数字，要求你找出一个八皇后摆法，使得八皇后位置上的数字之和最大。输出这个最大值。 二、解析 经典的八皇后问题，做了一些小修改。但其实还是八皇后问题。枚举出所有摆法然后维护出最大值即可。 三、代码 #include <iostream> #include <cstring> #include <iomanip> using namespace std; const int n = 8; int k, a[n + 5][n + 5], ans, vis[3][n * 2 + 5]; void...

一、题意 输入正整数k，找到所有的正整数x>=y，使得 1/k = 1/x + 1/y。并打印出来。 二、解析 暴力枚举法。关键是缩小枚举范围。首先显然 k<x<=y，另一方面 y<=2k<=x。因此可以发现y的范围是（k, 2k]，因此选择枚举y，时间复杂度仅为O(n)。 三、代码 #include <iostream> #include <vector> using namespace std; struct xy { int x, y; xy(int x, int y) : x(x), y(y) {} }; int k; vector...

一、题意 有n个城市，m条道路，每条道路收费t元。之后m行每行两个点表示一条道路。要求你找到一条最短路径，使得该路径经过所有这m条道路。输出路径的收费之和。 二、解析 别以为这是一道最短路或并查集问题，实际上这是一道欧拉回路问题。那m条道路连接后，将会分成几个连通分量。每个连通分量需要统计其中奇数点的个数（通过一次dfs即可），然后先在这些连通分量内部加边来使之可以一笔画，然后再加边把所有连通分量连接起来。需要注意的点：  连通分量可能只有一个点 有些城市可能压根就不参与，因此需要一个need[maxn]进行标记。 m=0的情形  三、代码 #include <iostream> ...

一、题意 第一行一个n表示一棵树有n个结点。然后第二三行分别给出这棵树的bfs和dfs序列。（子节点中会先遍历编号小的）要求输出每个节点的子节点有哪些。 二、解析 这题比较难。最终做法是，使用栈来模拟dfs的过程。在输入dfs序列时，同时维护一个栈，当在树上递归时则往栈中加入该节点，当发生了回溯时，则需要从栈中排出结点。bfs序列实际上我们可以从中提取出结点的pos数组（即结点在层次遍历中的下标）。利用这个pos数组，在dfs发生递归时，除了第一层外，当前结点的pos应该大于上一结点的pos+1（这样才会是往下走的dfs，并且不是兄弟结点）；当发生回溯时，当前节点的pos应该小于等于上一结点的...

一、题意 输入kase组数据，每组包括一个字符串，表示一个天平，如 "[[3,7],6]"要求输出一个数，表示最少需要修改多少个数字使得天平平衡。 二、解析 逻辑思维题。实际上整个天平中，任意一个数字都能决定整个天平的所有数字（因为要使得天平平衡），这样一来，就可以计算所有叶子结点所最终确定出的平衡天平总重量，统计每一种重量的数量，数量中最大的那一个所对应的叶子节点就是我们不要变的，这样只需要修改剩下的叶子即可。 三、代码 #include <iostream> #include <string> #include <sstream> #include &l...

一、题意 有一个巡逻机器人要从一个n*m的网格的左上角走到右上角，网格中0为空地，1为障碍物。该机器人具备连续通过k个障碍物的能力，求最短路径长度。  二、解析 最短路径考虑bfs。同样需要确定bfs的“状态点”如何定义。考虑到该机器人穿障碍物的能力（在障碍物中也可以拐弯），因此需要把它该能力的剩余“能量点”（初始为k）作为状态之一。注意作为状态后vis将要变成3维。 三、代码 #include <iostream> #include <queue> #include <cstring> using namespace std; const int maxn...

一、题意 输入若干个括号序列，判断是否合法。注意可能输入空串，空串为合法。 二、解析 括号序列的判断，老栈题了。注意由于有空串输入，所以需要用getline()。 三、代码 #include <iostream> #include <string> #include <stack> using namespace std; int n; string str; int main() { cin >> n; cin.ignore(); while(n --) { getline(cin, str); stack<char> stk; f...

一、题意 给一个n个点m条边（2<=n<=100000, 1<=m<=200000）的无向图，每条边都涂有一种颜色。求从结点1到结点n的一条最短路径。在此前提下，使得经过边的颜色序列的字典序最小。打印出路径长度和颜色序列。 二、解析 最短路问题的考虑bfs。但是这道题目要打印出最短路径，如果用平常的父节点p数组的方法，没有办法保证按照颜色字典序。因此要考虑其他方法。这里的方法是使用两次bfs。第一次是从终点开始的逆向bfs，可以得到所有顶点到终点的距离数组rev_d[maxn]；然后再进行正向bfs，正向bfs时就要沿着rev_d逐一递减的方向遍历，然后在每一步选择颜色...

一、题意 给定一个n和一个m。n表示有n个数1...n；m表示有m对大小关系。接下来打印出m对(i, j) 表示 i < j；要求输出一个这n个数可能的从小到大的排列。 二、解析 显然是拓扑排序。拓扑排序可以通过dfs的方法，也可以通过队列的方法。我比较喜欢用队列，只需要维护一个Next数组存放每个点所指向的点集（就叫出度点好了），以及一个inNum数组记录每个点当前的入度大小。当一个点的入度为0时就可以放心的把该点放入队列，然后更新它的出度点的入度值。 三、代码 #include <iostream> #include <queue> #include <...

一、题意 给出一个比较复杂的道路。每个结点有通行方向的限定。输入起点、起点方向、终点，要求出最短路径并打印出路径。 二、解析 这是一道比较复杂的bfs题目。最主要是的要找清楚状态点是什么。在本题中，状态点是包含（x, y, dir）的3维点。因此在维护vis数组、父节点p数组、下一步方向的vec数组都需要是3维的。此外对于向右转、向左转等旋转操作，可以通过一个如代码中getNext()中实现的方法。然后关于打印路径，只要维护好了p数组，只要在最后写个while循环将p数组中的点链转存到vector中即可，然后就可以逆序打印出路径了。 三、代码 #include <iostream>...

一、题意 有若干组数据。每组数据第一行一个n和一个m.接下来是一个n行m列的油田，要你输出油田中有多少个@块（斜着联通也算）。 二、解析 简单的dfs题目。用vis[maxn][maxm]维护每个点是否走过，然后进行dfs。该题只是为了简单的复习一下dfs，没有啥难度。 三、代码 #include <iostream> #include <string> using namespace std; const int maxn = 100 + 5, maxm = 100 + 5; const int Fx[8][2] = {{1, 0}, {1, 1}, {0, 1}, ...