欧 拉 路 径
因为这是个欧拉回路，所以你最后一定是到达了start(全为0的情况)才收集的最后一个边权，所以最后n-1位一定是n-1个0，只需要去掉最后n-1个0，循环利用到start(n-1个0)，就是答案。从最小的点，先遍历权值最小的边跑一边希尔霍尔策算法，收集每个点来的那条边的边权，倒叙收集的序列，把第一个边权-1改为start，得到就是最短长度（德布罗意序列）2.如果题目要求字典序最小，那就先将每个点的
·
前置知识
一笔画：就是不抬笔的走完所有的边
有向图
有向图：如果是欧拉回路从哪一点出发都可以回来；如果是欧拉路径的起点和终点都是唯一的
// 有向图中找到一个起点，去生成欧拉回路 或者 欧拉路径
public static int directedStart() {
int start = -1, end = -1;
for (int i = 1; i <= n; i++) {
int v = outDeg[i] - inDeg[i];
if (v < -1 || v > 1 || (v == 1 && start != -1) || (v == -1 && end != -1)) {
return -1;
}
if (v == 1) {
start = i;
}
if (v == -1) {
end = i;
}
}
if ((start == -1) ^ (end == -1)) {
return -1;
}
if (start != -1) {
return start;
}
for (int i = 1; i <= n; i++) {
if (outDeg[i] > 0) {
return i;
}
}
return -1;
}无向图
无向图：如果是回路中任意一个点都可以做起点；如果是路径那两个点都可以做起点或终点
public static int undirectedStart() {
int odd = 0;
for (int i = 1; i <= n; i++) {
if ((deg[i] & 1) == 1) {
odd++;
}
}
if (odd != 0 && odd != 2) {
return -1;
}
for (int i = 1; i <= n; i++) {
if (odd == 0 && deg[i] > 0) {
return i;
}
if (odd == 2 && (deg[i] & 1) == 1) {
return i;
}
}
return -1;
}
生成路径(有/无向图通用)
当前弧优化：通过跳过已确认无效的边，大幅减少 DFS 的冗余遍历。
图解：
还有没有遍历过的边就去遍历，把没有新的边的可走的点加入一个列表，最后列表逆序就是欧拉路径
同理，不回的路在中和在后都是能正确收集的
1.对于无向图，不能走一条边的逆边，所以在加边时将每个边的正反两条边设置同一个序号，防止回头
2.如果题目要求字典序最小，那就先将每个点的边集按照通往点的序号排序，先处理通往点的序号小的边，就会得到字典序最小的结果
题目1
// 有向图的欧拉路径，java版
// 图中有n个点，m条有向边，每条边给出两个端点
// 如果存在欧拉路径，输出字典序最小的结果，如果不存在打印No
// 1 <= n <= 10^5
// 1 <= m <= 2 * 10^5
// 测试链接 : https://www.luogu.com.cn/problem/P7771
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Code01_DirectedEuler1 {
public static class EdgeCmp implements Comparator<int[]> {
@Override
//将每个节点的边集放在一起，每个边集按照通往点的序号从大到小排序，因为链式前向星是头插法
public int compare(int[] e1, int[] e2) {
return e1[0] != e2[0] ? (e1[0] - e2[0]) : (e1[1] - e2[1]);
}
}
public static int MAXN = 100001;
public static int MAXM = 200002;
public static int n, m;
public static int[][] edgeArr = new int[MAXM][2];
public static int[] head = new int[MAXN];
public static int[] nxt = new int[MAXM];
public static int[] to = new int[MAXM];
public static int cntg;
public static int[] cur = new int[MAXN];//遍历到哪条边了
public static int[] outDeg = new int[MAXN];
public static int[] inDeg = new int[MAXN];
public static int[] path = new int[MAXM];
public static int cntp;
public static void addEdge(int u, int v) {
nxt[++cntg] = head[u];
to[cntg] = v;
head[u] = cntg;
}
public static void connect() {
Arrays.sort(edgeArr, 1, m + 1, new EdgeCmp());
for (int l = 1, r = 1; l <= m; l = ++r) {
while (r + 1 <= m && edgeArr[l][0] == edgeArr[r + 1][0]) {
r++;
}
for (int i = r, u, v; i >= l; i--) {
u = edgeArr[i][0];
v = edgeArr[i][1];
outDeg[u]++;
inDeg[v]++;
addEdge(u, v);
}
}
for (int i = 1; i <= n; i++) {
cur[i] = head[i];
}
}
// 有向图中找到一个起点，去生成欧拉回路 或者 欧拉路径
public static int directedStart() {
int start = -1, end = -1;
for (int i = 1; i <= n; i++) {
int v = outDeg[i] - inDeg[i];
if (v < -1 || v > 1 || (v == 1 && start != -1) || (v == -1 && end != -1)) {
return -1;
}
if (v == 1) {
start = i;
}
if (v == -1) {
end = i;
}
}
if ((start == -1) ^ (end == -1)) {
return -1;
}
if (start != -1) {
return start;
}
for (int i = 1; i <= n; i++) {
if (outDeg[i] > 0) {
return i;
}
}
return -1;
}
// Hierholzer算法递归版，java会爆栈，C++可以通过
public static void euler1(int u) {
for (int e = cur[u]; e > 0; e = cur[u]) {
cur[u] = nxt[e];
euler1(to[e]);
}
path[++cntp] = u;
}
// Hierholzer算法迭代版
public static int[] sta = new int[MAXM];
public static int top;
public static void euler2(int node) {
top = 0;
sta[++top] = node;
while (top > 0) {
int u = sta[top--];
int e = cur[u];
if (e != 0) {
cur[u] = nxt[e];
sta[++top] = u;
sta[++top] = to[e];
} else {
path[++cntp] = u;
}
}
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
n = in.nextInt();
m = in.nextInt();
for (int i = 1; i <= m; i++) {
edgeArr[i][0] = in.nextInt();
edgeArr[i][1] = in.nextInt();
}
connect();
int start = directedStart();
if (start == -1) {
out.println("No");
} else {
// euler1(start);
euler2(start);
if (cntp != m + 1) {
out.println("No");
} else {
for (int i = cntp; i >= 1; i--) {
out.print(path[i] + " ");
}
out.println();
}
}
out.flush();
out.close();
}
题目2
P2731 [USACO3.3] 骑马修栅栏 Riding the Fences - 洛谷
// 无向图的欧拉路径，java版
// 图中给定m条无向边，每条边给出两个端点
// 如果存在欧拉路径，输出字典序最小的结果，如果不存在打印No
// 节点编号的范围是[1, 500]，所有点不一定都出现，以给定的边为准
// 1 <= m <= 1024
// 测试链接 : https://www.luogu.com.cn/problem/P2731
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Code02_UndirectedEuler1 {
public static class EdgeCmp implements Comparator<int[]> {
@Override
public int compare(int[] e1, int[] e2) {
return e1[0] != e2[0] ? (e1[0] - e2[0]) : (e1[1] - e2[1]);
}
}
public static int MAXN = 501;
public static int MAXM = 2001;
public static int n = 500, m, k;
public static int[][] edgeArr = new int[MAXM << 1][3];
public static int[] head = new int[MAXN];
public static int[] nxt = new int[MAXM << 1];
public static int[] to = new int[MAXM << 1];
public static int[] eid = new int[MAXM << 1];
public static int cntg;
public static int[] cur = new int[MAXN];
public static int[] deg = new int[MAXN];
public static boolean[] vis = new boolean[MAXM];
public static int[] path = new int[MAXM];
public static int cntp;
public static void addEdge(int u, int v, int id) {
nxt[++cntg] = head[u];
to[cntg] = v;
eid[cntg] = id;
head[u] = cntg;
}
public static void connect() {
Arrays.sort(edgeArr, 1, k + 1, new EdgeCmp());
for (int l = 1, r = 1; l <= k; l = ++r) {
while (r + 1 <= k && edgeArr[l][0] == edgeArr[r + 1][0]) {
r++;
}
for (int i = r, u, v, id; i >= l; i--) {
u = edgeArr[i][0];
v = edgeArr[i][1];
id = edgeArr[i][2];
deg[u]++;
addEdge(u, v, id);
}
}
for (int i = 1; i <= n; i++) {
cur[i] = head[i];
}
}
// 无向图中找到一个起点，去生成欧拉回路 或者 欧拉路径
public static int undirectedStart() {
int odd = 0;
for (int i = 1; i <= n; i++) {
if ((deg[i] & 1) == 1) {
odd++;
}
}
if (odd != 0 && odd != 2) {
return -1;
}
for (int i = 1; i <= n; i++) {
if (odd == 0 && deg[i] > 0) {
return i;
}
if (odd == 2 && (deg[i] & 1) == 1) {
return i;
}
}
return -1;
}
// Hierholzer算法递归版
public static void euler1(int u) {
for (int e = cur[u]; e > 0; e = cur[u]) {
cur[u] = nxt[e];
if (!vis[eid[e]]) {
vis[eid[e]] = true;
euler1(to[e]);
}
}
path[++cntp] = u;
}
// Hierholzer算法迭代版
public static int[] sta = new int[MAXM];
public static int top;
public static void euler2(int node) {
top = 0;
sta[++top] = node;
while (top > 0) {
int u = sta[top--];
int e = cur[u];
if (e != 0) {
cur[u] = nxt[e];
if (!vis[eid[e]]) {
vis[eid[e]] = true;
sta[++top] = u;
sta[++top] = to[e];
} else {
sta[++top] = u;
}
} else {
path[++cntp] = u;
}
}
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
m = in.nextInt();
k = 0;
for (int i = 1, u, v; i <= m; i++) {
u = in.nextInt();
v = in.nextInt();
edgeArr[++k][0] = u;
edgeArr[k][1] = v;
edgeArr[k][2] = i;//加入序号，防止走回头路
edgeArr[++k][0] = v;
edgeArr[k][1] = u;
edgeArr[k][2] = i;//加入序号，防止走回头路
}
connect();
int start = undirectedStart();
if (start == -1) {
out.println("No");
} else {
// euler1(start);
euler2(start);
if (cntp != m + 1) {
out.println("No");
} else {
for (int i = cntp; i >= 1; i--) {
out.println(path[i]);
}
}
}
out.flush();
out.close();
}
题目3
2097. 合法重新排列数对 - 力扣*5.（LeetCode）
// 合法排列数对，java版
// 给定n个数对，每个数对(a, b)，其中 a != b，并且不存在相同的数对
// 希望所有数对形成首尾相接的样子，叫做合法排列，比如以下的数对
// [5,1] [4,5] [11,9] [9,4] 合法排列为 [11,9] [9,4] [4,5] [5,1]
// 注意每个数对必须使用且仅用1次，数据保证存在合法排列，返回任何一个都可以
// 1 <= n <= 10^5
// 0 <= 数字 <= 10^9
// 测试链接 : https://leetcode.cn/problems/valid-arrangement-of-pairs/
// 提交以下代码中的Solution类，可以通过所有测试用例
import java.util.Arrays;
public class Code03_Arrangement1 {
class Solution {
public static int MAXN = 200001;
public static int n, m;
public static int[][] pair;
public static int[] sortv = new int[MAXN];
public static int[] head = new int[MAXN];
public static int[] nxt = new int[MAXN];
public static int[] to = new int[MAXN];
public static int cntg;
public static int[] cur = new int[MAXN];
public static int[] outDeg = new int[MAXN];
public static int[] inDeg = new int[MAXN];
public static int[] path = new int[MAXN];
public static int cntp;
public static void addEdge(int u, int v) {
nxt[++cntg] = head[u];
to[cntg] = v;
head[u] = cntg;
}
public static int kth(int num) {
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >>> 1;
if (sortv[mid] >= num) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
public static void prepare() {
int len = 0;
for (int i = 0; i < m; i++) {
sortv[++len] = pair[i][0];
sortv[++len] = pair[i][1];
}
Arrays.sort(sortv, 1, len + 1);
n = 1;
for (int i = 2; i <= len; i++) {
if (sortv[n] != sortv[i]) {
sortv[++n] = sortv[i];
}
}
cntg = cntp = 0;
for (int i = 1; i <= n; i++) {
head[i] = outDeg[i] = inDeg[i] = 0;
}
}
public static void connect() {
for (int i = 0, u, v; i < m; i++) {
u = kth(pair[i][0]);
v = kth(pair[i][1]);
outDeg[u]++;
inDeg[v]++;
addEdge(u, v);
}
for (int i = 1; i <= n; i++) {
cur[i] = head[i];
}
}
public static int directedStart() {
int start = -1, end = -1;
for (int i = 1; i <= n; i++) {
int v = outDeg[i] - inDeg[i];
if (v < -1 || v > 1 || (v == 1 && start != -1) || (v == -1 && end != -1)) {
return -1;
}
if (v == 1) {
start = i;
}
if (v == -1) {
end = i;
}
}
if ((start == -1) ^ (end == -1)) {
return -1;
}
if (start != -1) {
return start;
}
for (int i = 1; i <= n; i++) {
if (outDeg[i] > 0) {
return i;
}
}
return -1;
}
public static void euler(int u) {
for (int e = cur[u]; e > 0; e = cur[u]) {
cur[u] = nxt[e];
euler(to[e]);
}
path[++cntp] = u;
}
public int[][] validArrangement(int[][] pairs) {
m = pairs.length;
pair = pairs;
prepare();
connect();
int start = directedStart();
if (start == -1) {
return null;
}
euler(start);
if (cntp != m + 1) {
return null;
}
int[][] ans = new int[m][2];
for (int i = 0, j = cntp; i < m; i++, j--) {
ans[i][0] = sortv[path[j]];
ans[i][1] = sortv[path[j - 1]];
}
return ans;
}
}
}题目4
将单词的首尾字母作为点，把边的边权设置为这个单词，收集边按照字典序从小到大排序，再加入边。然后跑一边希尔霍尔策算法(带着来到这个点的那一条边的边的权，最后path收集边权)
// 词链，java版
// 给定n个由小写字母组成的单词，想把所有单词串成一个词链
// 同时要求前一个单词的结尾字符 == 后一个单词的开头字符
// 比如词链，aloha.arachnid.dog.gopher.rat.tiger
// 需要使用每个输入的单词恰好一次，同一单词出现k次就要用k次
// 返回字典序最小的结果，注意 . 的字典序 < 小写字母的字典序
// 如果不存在合法词链，输出***
// 1 <= n <= 1000
// 测试链接 : https://www.luogu.com.cn/problem/P1127
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
public class Code04_WordChain1 {
public static class EdgeCmp implements Comparator<Integer> {
public int compare(Integer i, Integer j) {
if (a[i] != a[j]) {
return a[i] - a[j];
}
return str[i].compareTo(str[j]);
}
}
public static int MAXN = 27;
public static int MAXM = 1002;
public static int n = 26, m;
public static String[] str = new String[MAXM];
public static int[] a = new int[MAXM];
public static int[] b = new int[MAXM];
public static Integer[] eidArr = new Integer[MAXM];
public static int[] head = new int[MAXN];
public static int[] nxt = new int[MAXM];
public static int[] to = new int[MAXM];
public static String[] weight = new String[MAXM];
public static int cntg;
public static int[] cur = new int[MAXN];
public static int[] outDeg = new int[MAXN];
public static int[] inDeg = new int[MAXN];
public static String[] path = new String[MAXM];
public static int cntp;
public static void addEdge(int u, int v, String w) {
nxt[++cntg] = head[u];
to[cntg] = v;
weight[cntg] = w;
head[u] = cntg;
}
public static int startNode(String str) {
return str.charAt(0) - 'a' + 1;
}
public static int endNode(String str) {
return str.charAt(str.length() - 1) - 'a' + 1;
}
public static void connect() {
Arrays.sort(eidArr, 1, m + 1, new EdgeCmp());
for (int l = 1, r = 1; l <= m; l = ++r) {
while (r + 1 <= m && a[eidArr[l]] == a[eidArr[r + 1]]) {
r++;
}
for (int i = r, u, v; i >= l; i--) {
u = a[eidArr[i]];
v = b[eidArr[i]];
outDeg[u]++;
inDeg[v]++;
addEdge(u, v, str[eidArr[i]]);
}
}
for (int i = 1; i <= n; i++) {
cur[i] = head[i];
}
}
public static int directedStart() {
int start = -1, end = -1;
for (int i = 1; i <= n; i++) {
int v = outDeg[i] - inDeg[i];
if (v < -1 || v > 1 || (v == 1 && start != -1) || (v == -1 && end != -1)) {
return -1;
}
if (v == 1) {
start = i;
}
if (v == -1) {
end = i;
}
}
if ((start == -1) ^ (end == -1)) {
return -1;
}
if (start != -1) {
return start;
}
for (int i = 1; i <= n; i++) {
if (outDeg[i] > 0) {
return i;
}
}
return -1;
}
public static void euler(int u, String w) {
for (int e = cur[u]; e > 0; e = cur[u]) {
cur[u] = nxt[e];
euler(to[e], weight[e]);
}
path[++cntp] = w;
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
m = in.nextInt();
for (int i = 1; i <= m; i++) {
str[i] = in.nextString();
a[i] = startNode(str[i]);
b[i] = endNode(str[i]);
eidArr[i] = i;
}
connect();
int start = directedStart();
if (start == -1) {
out.println("***");
} else {
euler(start, "");
if (cntp != m + 1) {
out.println("***");
} else {
out.print(path[cntp - 1]);
for (int i = cntp - 2; i >= 1; i--) {
out.print("." + path[i]);
}
out.println();
}
}
out.flush();
out.close();
}
题目5
1.将字母作为节点建立无向图，走欧拉路径即可得到字符串
2.无向图中为了得到字典序最小的欧拉路径，从字典序最小的字母作为起点开始遍历，每次选择通往字典序最小的节点的边
// 无序字母对，java版
// 给定n个字母对，每个字母对有两个字母，字母只可能是A~Z、a~z
// 字母对内部不区分顺序，ab和ba是相同的，但是区分大小写，Ab和ab是不同的
// 题目不会给定重复的字母对，构造一个长度n+1的字符串，让每个字母对都出现
// 一个字母对的两个字母，在字符串中相邻出现即可，请输出字典序最小的方案
// 如果没有满足要求的方案，打印"No Solution"
// 1 <= n <= 1326
// 测试链接 : https://www.luogu.com.cn/problem/P1341
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code05_LetterPairs1 {
public static int MAXN = 53;
public static int MAXM = 2001;
public static int n = 52, m;
public static char[][] arr = new char[MAXM][2];
public static int[][] graph = new int[MAXN][MAXN];
public static int[] deg = new int[MAXN];
public static int[] cur = new int[MAXN];
public static int[] path = new int[MAXM];
public static int cntp;
public static int getInt(char c) {
return c <= 'Z' ? (c - 'A' + 1) : (c - 'a' + 27);
}
public static char getChar(int v) {
return (char) (v <= 26 ? ('A' + v - 1) : ('a' + v - 27));
}
public static void connect() {
for (int i = 1, u, v; i <= m; i++) {
u = getInt(arr[i][0]);
v = getInt(arr[i][1]);
graph[u][v]++;
graph[v][u]++;
deg[u]++;
deg[v]++;
}
for (int i = 1; i <= n; i++) {
cur[i] = 1;
}
}
public static int undirectedStart() {
int odd = 0;
for (int i = 1; i <= n; i++) {
if ((deg[i] & 1) == 1) {
odd++;
}
}
if (odd != 0 && odd != 2) {
return -1;
}
for (int i = 1; i <= n; i++) {
if (odd == 0 && deg[i] > 0) {
return i;
}
if (odd == 2 && (deg[i] & 1) == 1) {
return i;
}
}
return -1;
}
public static void euler(int u) {
for (int v = cur[u]; v <= n; v = cur[u]) {
cur[u]++;
if (graph[u][v] > 0) {
graph[u][v]--;
graph[v][u]--;
euler(v);
}
}
path[++cntp] = u;
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
m = in.nextInt();
for (int i = 1; i <= m; i++) {
arr[i][0] = in.nextChar();
arr[i][1] = in.nextChar();
}
connect();
int start = undirectedStart();
if (start == -1) {
out.println("No Solution");
} else {
euler(start);
if (cntp != m + 1) {
out.println("No Solution");
} else {
for (int i = cntp; i >= 1; i--) {
out.print(getChar(path[i]));
}
out.println();
}
}
out.flush();
out.close();
}
// 读写工具类
static class FastReader {
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
private final InputStream in;
FastReader(InputStream in) {
this.in = in;
}
private int readByte() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0)
return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = readByte();
} while (c <= ' ' && c != -1);
boolean neg = false;
if (c == '-') {
neg = true;
c = readByte();
}
int val = 0;
while (c > ' ' && c != -1) {
val = val * 10 + (c - '0');
c = readByte();
}
return neg ? -val : val;
}
char nextChar() throws IOException {
int c;
do {
c = readByte();
if (c == -1)
return 0;
} while (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')));
return (char) c;
}
}
}链式前向星建图
maxn=53
maxm=2002
edges=[]
head=[0]*maxn
nex=[0]*maxm
to=[0]*maxm
eid=[0]*maxm
vis=[False]*maxm
cntg=0
cur=[0]*maxn
de=[0]*maxn
path=[0]*maxm
cntp=0
def add(u,v,id):
global cntg
cntg+=1
eid[cntg]=id
nex[cntg]=head[u]
to[cntg]=v
head[u]=cntg
def get_index(c):
if c<='Z':
return ord(c)-ord('A')+1
else:
return 27+ord(c)-ord('a')
def get_chr(i):
if i<=26:
return chr(ord('A')+i-1)
else:
return chr(ord('a')+i-26-1)
def connect():
edges.sort(key=lambda x:(x[0],x[1]))
l,r=0,0
while l<m*2:
while r+1<m*2 and edges[l][0]==edges[r+1][0]:
r+=1
for i in range(r,l-1,-1):
u=get_index(edges[i][0])
v=get_index(edges[i][1])
de[u]+=1
add(u,v,edges[i][2])
l=r+1
for i in range(1,n+1):
cur[i]=head[i]
def get_node():
odd=0
for i in range(1,n+1):
if (de[i]&1)==1:
odd+=1
if odd!=0 and odd!=2:
return -1
for i in range(1,n+1):
if odd==0 and de[i]>0:
return i
if odd==2 and (de[i]&1)==1:
return i
return -1
def euler(i):
e=cur[i]
while e:
cur[i]=nex[e]
if not vis[eid[e]]:
vis[eid[e]] = True
euler(to[e])
e=cur[i]
global cntp
cntp+=1
path[cntp]=get_chr(i)
m=int(input())
n=52
for i in range(1,m+1):
rem=input()
edges.append([rem[0],rem[1],i])
edges.append([rem[1],rem[0],i])
connect()
start=get_node()
if start==-1:
print("No Solution")
else:
euler(start)
if cntp!=m+1:
print("No Solution")
else:
for i in range(cntp,0,-1):
print(path[i],end="")
题目6
1.首先一共有k^n种可能性，就有k^n个开头，所以最短的长度就是k^n+n-1(最后一个需要n-1长度结尾)
2.n位长度，就把每个点设置为n-1位长度的点，每个点有k条边，边权为0 - k-1
以三位二进制举例：
从最小的点，先遍历权值最小的边跑一边希尔霍尔策算法，收集每个点来的那条边的边权，倒叙收集的序列，把第一个边权-1改为start，得到就是最短长度（德布罗意序列）
注：每个点的出度入度差都为0，形成的图是一个欧拉回路
// 破解保险箱，java版
// 给定正数n，表示密码有n位，给定正数k，表示每一位可能的数字是[0..k-1]
// 密码有(k^n)个可能性，构造一个字符串，其中的连续子串包含所有可能的密码
// 先保证字符串的长度最短，作为加强要求，保证字典序尽量的小，返回字符串
// 1 <= n <= 4 1 <= k <= 10
// 测试链接 : https://leetcode.cn/problems/cracking-the-safe/
// 提交以下代码中的Solution类，可以通过所有测试用例
public class Code06_CrackingTheSafe1 {
class Solution {
public int MAXN = 5001;
public int n, k, m;
public int[] cur = new int[MAXN];
public int[] path = new int[MAXN];
public int cntp;
public int[][] sta = new int[MAXN][2];
public int u, e;
public int stacksize;
public void push(int u, int e) {
sta[stacksize][0] = u;
sta[stacksize][1] = e;
stacksize++;
}
public void pop() {
stacksize--;
u = sta[stacksize][0];
e = sta[stacksize][1];
}
public void prepare(int len, int num) {
n = len;
k = num;
m = 1;
for (int i = 1; i <= n - 1; i++) {
m *= k;
}
for (int i = 0; i < m; i++) {
cur[i] = 0;
}
cntp = 0;
}
// 递归版
public void euler1(int u, int e) {
while (cur[u] < k) {
int ne = cur[u]++;
euler1((u * k + ne) % m, ne);
}
path[++cntp] = e;
}
// 迭代版
public void euler2(int node, int edge) {
stacksize = 0;
push(node, edge);
while (stacksize > 0) {
pop();
if (cur[u] < k) {
int ne = cur[u]++;
push(u, e);
push((u * k + ne) % m, ne);
} else {
path[++cntp] = e;
}
}
}
public String crackSafe(int len, int num) {
prepare(len, num);
euler1(0, -1);
// euler2(0, -1);
StringBuilder str = new StringBuilder();
for (int i = 1; i <= n - 1; i++) {
str.append("0");
}
for (int i = cntp - 1; i >= 1; i--) {
str.append(path[i]);
}
return str.toString();
}
}
}题目7
// 所有可能的密码串，java版
// 给定正数n，表示密码有n位，每一位可能的数字是[0..9]
// 密码有(10^n)个可能性，构造一个字符串，其中的连续子串包含所有可能的密码
// 先保证字符串的长度最短，然后保证字典序尽量的小，返回这个字符串
// 1 <= n <= 6
// 测试链接 : http://poj.org/problem?id=1780
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code07_Password1 {
public static int MAXN = 1000002;
public static int n, k, m;
public static int[] cur = new int[MAXN];
public static int[] path = new int[MAXN];
public static int cntp;
public static int[][] sta = new int[MAXN][2];
public static int u, e;
public static int stacksize;
public static void push(int u, int e) {
sta[stacksize][0] = u;
sta[stacksize][1] = e;
stacksize++;
}
public static void pop() {
stacksize--;
u = sta[stacksize][0];
e = sta[stacksize][1];
}
public static void prepare(int len, int num) {
n = len;
k = num;
m = 1;
for (int i = 1; i <= n - 1; i++) {
m *= k;
}
for (int i = 0; i < m; i++) {
cur[i] = 0;
}
cntp = 0;
}
// 本题的递归深度很大，递归版会爆栈，java和C++都只有迭代版可以通过
public static void euler(int node, int edge) {
stacksize = 0;
push(node, edge);
while (stacksize > 0) {
pop();
if (cur[u] < k) {
int ne = cur[u]++;
push(u, e);
push((u * k + ne) % m, ne);
} else {
path[++cntp] = e;
}
}
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int len = in.nextInt();
int num = 10;
while (len != 0) {
prepare(len, num);
euler(0, -1);
for (int i = 1; i <= n - 1; i++) {
out.print("0");
}
for (int i = cntp - 1; i >= 1; i--) {
out.print(path[i]);
}
out.println();
len = in.nextInt();
}
out.flush();
out.close();
}
// 读写工具类
static class FastReader {
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
private final InputStream in;
FastReader(InputStream in) {
this.in = in;
}
private int readByte() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0)
return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = readByte();
} while (c <= ' ' && c != -1);
boolean neg = false;
if (c == '-') {
neg = true;
c = readByte();
}
int val = 0;
while (c > ' ' && c != -1) {
val = val * 10 + (c - '0');
c = readByte();
}
return neg ? -val : val;
}
}
}题目8
因为这是个欧拉回路，所以你最后一定是到达了start(全为0的情况)才收集的最后一个边权，所以最后n-1位一定是n-1个0，只需要去掉最后n-1个0，循环利用到start(n-1个0)，就是答案
// 太鼓达人，java版
// 给定一个正数n，所有长度为n的二进制状态一共有(2^n)个
// 构造一个字符串，字符串可以循环使用，其中的连续子串包含所有二进制状态
// 求出字符串的最小长度值，并且给出字典序最小的方案
// 比如n=3，字符串最小长度值为8，字典序最小的方案为00010111
// 注意到 000、001、010、101、011、111、110、100 都已包含
// 注意到 最后两个二进制状态 是字符串循环使用构造出来的
// 1 <= n <= 11
// 本题可以推广到k进制，代码就是按照推广来实现的
// 测试链接 : https://www.luogu.com.cn/problem/P10950
// 测试链接 : https://loj.ac/p/10110
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code08_Taiko1 {
public static int MAXN = 3001;
public static int n, k, m;
public static int[] cur = new int[MAXN];
public static int[] path = new int[MAXN];
public static int cntp;
public static void prepare(int len, int num) {
n = len;
k = num;
m = 1;
for (int i = 1; i <= n - 1; i++) {
m *= k;
}
for (int i = 0; i < m; i++) {
cur[i] = 0;
}
cntp = 0;
}
public static void euler(int u, int e) {
while (cur[u] < k) {
int ne = cur[u]++;
euler((u * k + ne) % m, ne);
}
path[++cntp] = e;
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int len = in.nextInt();
int num = 2;
prepare(len, num);
euler(0, -1);
out.print((m * k) + " ");
for (int i = 1; i <= n - 1; i++) {
out.print("0");
}
for (int i = cntp - 1; i >= n; i--) {
out.print(path[i]);
}
out.println();
out.flush();
out.close();
}
// 读写工具类
static class FastReader {
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
private final InputStream in;
FastReader(InputStream in) {
this.in = in;
}
private int readByte() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0)
return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = readByte();
} while (c <= ' ' && c != -1);
boolean neg = false;
if (c == '-') {
neg = true;
c = readByte();
}
int val = 0;
while (c > ' ' && c != -1) {
val = val * 10 + (c - '0');
c = readByte();
}
return neg ? -val : val;
}
}
}题目9
1.如果边的初始状态和最终状态相同，则删掉这条边；如果不一样，只需要一辆车走一遍即可
2.在跑每个连通区的欧拉回路时，把每个简单环求出
P3520 [POI 2011] SMI-Garbage - 洛谷
// 垃圾车，java版
// 一共有n个点，m条无向边，所有点不保证连通
// 每条边的属性为 u v s t : u和v是端点，s是初始状态，t是最终状态
// 状态的数值只有0和1两种，当一辆车通过一条无向边，那么状态会翻转
// 一辆车的路线中，可以指定一个起点，最终回到起点，沿途的其他点不能重复经过
// 所有的边都要达成最终状态，所以需要若干辆车来完成这个目标
// 如果存在方案，提供任何一种方案即可，首先打印需要几辆车
// 然后对每辆车，先打印通过的边数，再打印依次到达了哪些点
// 如果不存在方案，打印"NIE"
// 1 <= n <= 10^5 1 <= m <= 10^6
// 测试链接 : https://www.luogu.com.cn/problem/P3520
// 提交以下的code，提交时请把类名改成"Main"，可以通过所有测试用例
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Code09_GarbageTruck1 {
public static int MAXN = 100001;
public static int MAXM = 2000001;
public static int n, m;
public static int[] head = new int[MAXN];
public static int[] nxt = new int[MAXM];
public static int[] to = new int[MAXM];
public static int[] eid = new int[MAXM];
public static int cntg;
public static int[] deg = new int[MAXN];
public static int[] cur = new int[MAXN];
// 区分多个连通区
public static boolean[] visNode = new boolean[MAXN];
// 标记无向边是否已经使用
public static boolean[] visEdge = new boolean[MAXM];
//某个点是否已经在path里了
public static boolean[] inpath = new boolean[MAXN];
public static int[] path = new int[MAXM];
public static int cntp;
public static int[] ansArr = new int[MAXM];
public static int[] ansl = new int[MAXM];
public static int[] ansr = new int[MAXM];
public static int idx;
public static int cnta;
public static void addEdge(int u, int v, int id) {
nxt[++cntg] = head[u];
to[cntg] = v;
eid[cntg] = id;
head[u] = cntg;
}
public static void popCircle(int u) {
cnta++;
ansArr[++idx] = u;
ansl[cnta] = idx;
for (int pop = path[cntp--]; pop != u; pop = path[cntp--]) {
inpath[pop] = false;
ansArr[++idx] = pop;
}
inpath[u] = false;
ansArr[++idx] = u;
ansr[cnta] = idx;
}
public static void euler1(int u) {
visNode[u] = true;
for (int e = cur[u]; e > 0; e = cur[u]) {
cur[u] = nxt[e];
if (!visEdge[eid[e]]) {
visEdge[eid[e]] = true;
euler1(to[e]);
}
}
if (inpath[u]) {
popCircle(u);
}
inpath[u] = true;
path[++cntp] = u;
}
public static int[] sta = new int[MAXM];
public static int top;
public static void euler2(int node) {
top = 0;
sta[++top] = node;
while (top > 0) {
int u = sta[top--];
visNode[u] = true;
int e = cur[u];
if (e != 0) {
cur[u] = nxt[e];
if (!visEdge[eid[e]]) {
visEdge[eid[e]] = true;
sta[++top] = u;
sta[++top] = to[e];
} else {
sta[++top] = u;
}
} else {
if (inpath[u]) {
popCircle(u);
}
inpath[u] = true;
path[++cntp] = u;
}
}
}
public static void main(String[] args) throws Exception {
FastReader in = new FastReader(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
n = in.nextInt();
m = in.nextInt();
for (int i = 1, u, v, s, t; i <= m; i++) {
u = in.nextInt();
v = in.nextInt();
s = in.nextInt();
t = in.nextInt();
if (s != t) {
deg[u]++;
deg[v]++;
addEdge(u, v, i);
addEdge(v, u, i);
}
}
for (int i = 1; i <= n; i++) {
cur[i] = head[i];
}
boolean check = true;
for (int i = 1; i <= n; i++) {
if ((deg[i] & 1) == 1) {
check = false;
break;
}
}
if (!check) {
out.println("NIE");
} else {
for (int i = 1; i <= n; i++) {
if (!visNode[i]) {
// euler1(i);
euler2(i);
}
}
out.println(cnta);
for (int i = 1; i <= cnta; i++) {
out.print((ansr[i] - ansl[i]) + " ");
for (int j = ansl[i]; j <= ansr[i]; j++) {
out.print(ansArr[j] + " ");
}
out.println();
}
}
out.flush();
out.close();
}
// 读写工具类
static class FastReader {
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
private final InputStream in;
FastReader(InputStream in) {
this.in = in;
}
private int readByte() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0)
return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = readByte();
} while (c <= ' ' && c != -1);
boolean neg = false;
if (c == '-') {
neg = true;
c = readByte();
}
int val = 0;
while (c > ' ' && c != -1) {
val = val * 10 + (c - '0');
c = readByte();
}
return neg ? -val : val;
}
}
}
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
9
0- 0
已为社区贡献1条内容
所有评论(0)