最新文章

[CSP-S2 2019]树上的数 题解

[CSP-S2 2019]树上的数 题解

题目地址:洛谷:P5659 树上的数 – 洛谷 | 计算机科学教育新生态

题目描述

给定一个大小为 $n$ 的树,它共有 $n$ 个结点与 $n-1$ 条边,结点从 $1 \sim n$ 编号。初始时每个结点上都有一个 $1 \sim n$ 的数字,且每个 $1 \sim n$ 的数字都只在恰好一个结点上出现。

接下来你需要进行恰好 $n-1$ 次删边操作,每次操作你需要选一条未被删去的边,此时这条边所连接的两个结点上的数字将会交换,然后这条边将被删去。

$n-1$ 次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字 $1 \sim n$ 所在的结点编号依次排列,就得到一个结点编号的排列 $P_i$ ​。现在请你求出,在最优操作方案下能得到的字典序最小的 $P_i$ ​。

tree csps219 img1 - [CSP-S2 2019]树上的数 题解

如上图,蓝圈中的数字 $1 \sim 5$ 一开始分别在结点②、①、③、⑤、④。按照 (1)(4)(3)(2) 的顺序删去所有边,树变为下图。按数字顺序得到的结点编号排列为①③④②⑤,该排列是所有可能的结果中字典序最小的。

tree csps219 img2 - [CSP-S2 2019]树上的数 题解

题意简述

一棵 $n$ 个节点的树上每个节点有一个 $1 \sim n$ 中的数字,定义对边 $(u, v)$ 进行删边操作为删边且交换 $u, v$ 节点上的数字,定义 $P_i$ 为数字 $i$ 所在的节点编号,求使得 $P_i$ 字典序最小的删边顺序。仅输出字典序最小的 $P_i$ 。

输入输出格式

输入格式:

从文件 tree.in 中读入数据。

本题输入包含多组测试数据。

第一行一个正整数 $T$ ,表示数据组数。

对于每组测试数据:

第一行一个整数 $n$ ,表示树的大小。

第二行 $n$ 个整数,第 $i \ (1 \leq i \leq n)$ 个整数表示数字 $i$ 初始时所在的结点编号。

接下来 $n – 1$ 行每行两个整数 $x, y$ ,表示一条连接 $x$ 号结点与 $y$ 号结点的边。

输出格式:

输出到文件 tree.out 中。

对于每组测试数据,输出一行共 $n$ 个用空格隔开的整数,表示最优操作方案下所能得到的字典序最小的 $P_i$ 。

输入输出样例

样例 #1

输入样例#1:

4
5
2 1 3 5 4
1 3
1 4
2 4
4 5
5
3 4 2 1 5
1 2
2 3
3 4
4 5
5
1 2 5 3 4
1 2
1 3
1 4
1 5
10
1 2 3 4 5 7 8 9 10 6
1 2
1 3
1 4
1 5
5 6
6 7
7 8
8 9
9 10

输出样例#1:

1 3 4 2 5
1 3 5 2 4
2 3 1 4 5
2 3 4 5 6 1 7 8 9 10

数据范围

测试点编号$n \leq$特殊性质
$1 \sim 2$$10$
$3 \sim 4$$160$树的形态是一条链
$5 \sim 7$$2000$ 树的形态是一条链
$8 \sim 9$$160$存在度数为 $n-1$ 的结点
$10 \sim 12$$2000$ 存在度数为 $n-1$ 的结点
$13 \sim 16$$160$
$17 \sim 20$$2000$

题解

由于作者水平有限,本题解表述、逻辑可能存在不足之处,欢迎读者以自身理解提出改进意见。

参考资料:[CSP-S2019]树上的数 – 仰望星空,脚踏实地 – 洛谷博客

刚看到这个题目的时候,总是想发掘树链上的性质,处理点上的信息,这种惯性思维使我完全没有思路。事实上,这个题处理边上的信息更好。

菊花图

本题中,有 $25$ 分的菊花图部分分,在菊花图和链两个部分分中,菊花图事实上相对好思考一些,因此先考虑菊花图的情况。

假如我们已经得到了菊花图上删边的顺序为 $(1, u_1), (1, u_2), \dots, (1, u_m)$ ,则按顺序删边后,容易发现, $1$ 号点的数字移动至 $u_1$, $u_1$ 的数字移动至 $u_2$,……, $u_m$ 的数字移动至 $1$ 。

因此我们可以贪心地构造这个顺序,枚举数字 $1 \sim n$ ,每个数字贪心地选择删边顺序中的下一条边,该数字最后的位置就是该边对应的 $u_i$ 。

链的情况同样是 $25$ 分。

在链的情况中,分析边的关系是必要的。对于一个数字 $k$ 从初始位置 $u_1$ 移动至 $u_m$ ,在路径 $u_1, u_2, \dots, u_m$ 上有以下性质:

  • 对于起点 $u_1$ ,其出边 $(u_1, u_2)$ 一定是这一点先被删掉的边。
  • 对于终点 $u_m$ ,其入边 $(u_{m-1}, u_m)$ 一定是这一点后被删掉的边。
  • 对于中间点 $u_i$ ,其入边 $(u_{i-1}, u_i)$ 先于出边 $(u_i, u_{i+1})$ 被删。

因此对于每个点可以获得一个删边的顺序,左先于右或右先于左。仍然按 $1 \sim n$ 的顺序枚举数字,检查每个数字从初始位置向左向右能走到的点中的最小编号。不能走仅当该点已确定的顺序不满足当前需要的顺序。

一般情况

与链类似,对于一个数字 $k$ 从初始位置 $u_1$ 移动至 $u_m$ ,在路径 $u_1, u_2, \dots, u_m$ 上有以下性质:

  • 对于起点 $u_1$ ,其出边 $(u_1, u_2)$ 一定是这一点第一条被删掉的边。如果不是,则 $k$ 会被换到其他点上。
  • 对于终点 $u_m$ ,其入边 $(u_{m-1}, u_m)$ 一定是这一点最后一条被删掉的边。如果不是,则 $k$ 也会被换到其他点上。
  • 对于中间点 $u_i$ ,其入边 $(u_{i-1}, u_i)$ 先于出边 $(u_i, u_{i+1})$ 被删,且在该点的所有边里被删除的顺序是相邻的。如果不满足后一条性质,则在中间数字 $k$ 会被换到其他点上。

容易发现,这些限制都是应用在某一点的边中的,因此可以单独考虑每个点的情况。依然是 $1 \sim n$ 枚举每个数字,从这个数字的初始位置开始 DFS ,检查路径上的点是否可以作为中间点/终点即可。

这里是这个题的实现中最难的位置,即检查是否满足中间点/终点的条件。这里,我使用了链表+并查集的实现方法管理边的关系。用类似链表的结构存储某个点的边是否被应用了在某边之后/之前被删的限制,用并查集存储某个点的边的限制连成的链式结构,且用两个数组 beg 和 end 存储某个点的边中,被固定为第一条/最后一条被删的边。

对于一个点,它能作为终点的条件为:

  • 不是起点;
  • 入边必须能作为该点的最后一条被删的边;
  • 特殊情况:当该点度数为 $1$ 时第一条/最后一条被删的边为同一条。

对于一个点,它能作为中间点的条件为:

  • 入边之后不能有除出边之外的紧接着要删的边;
  • 出边之前不能有除入边之外的紧接着要删的边;
  • 将入边和出边的限制关系加入后,如果会使该点的第一条和最后一条被删的边加入了同一条关系链,则此时该点的边都在这条关系链中。

根据以上条件进行判断一个点是否能作为中间点/终点,寻找每个数字的最小编号终点,并在路径上应用出入边的限制即可。

由于细节众多,文字描述无法包括所有方面,可以参考代码中的注释来理解。

代码

UPD:被卡常了,开 O2 洛谷可过。

// Code by KSkun, 2019/11
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>
#include <utility>

typedef long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	LL res = 0, neg = 1; char c = fgc();
	for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
	for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while(!isgraph(c = fgc())) {}
	return c;
}

const int MAXN = 2005;

int T, n, ptn[MAXN], deg[MAXN], beg[MAXN], end[MAXN]; // 每个点的第一条/最后一条被删的边
std::vector<int> gra[MAXN];

struct UnionFindSet {
	int fa[MAXN];
	bool pre[MAXN], nxt[MAXN]; // 一条边有无前后关系
	void clear() {
		for (int i = 1; i <= n; i++) fa[i] = i;
		memset(pre, 0, sizeof(pre));
		memset(nxt, 0, sizeof(nxt));
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	void join(int x, int y) { 
		int fx = find(x), fy = find(y);
		fa[fy] = fx;
		nxt[x] = pre[y] = true;
	}
	bool sameset(int x, int y) {
		return find(x) == find(y);
	}
} ufs[MAXN];

int dfs(int u, int f) {
	int mn = n + 1;
	// 能作为终点的条件:不是起点;入边可以是最后删边;入边之后无必须删边;入边和最后删边不在一条关系链中(只剩一条链时除外)
	if (f != 0 && (end[u] == 0 || end[u] == f) && !ufs[u].nxt[f] && 
		!(beg[u] != 0 && deg[u] > 1 && ufs[u].sameset(f, beg[u]))) {
		mn = std::min(mn, u);
	}	
	for (int v : gra[u]) {
		if (v == f) continue;
		if (f == 0) {
			// 不能作为起点之后的点的条件:起点的最后删边不是这条;这条边之前有必须删的边;这条边与最后删边在同一条关系链中,且仍有未加入关系链中的边
			if (beg[u] != 0 && beg[u] != v) continue;
			if (ufs[u].pre[v]) continue;
			if (end[u] != 0 && deg[u] > 1 && ufs[u].sameset(v, end[u])) continue;
			mn = std::min(mn, dfs(v, u));
		} else {
			// 不能作为中间点的条件:入边是最后删边;出边是最先删边;入边和出边已在同一条关系链中;出边之前有必须删边;入边之后有必须删边;应用出入边关系后让最先删边和最后删边在同一条关系链中,且有其他边未在该关系链中
			if (f == end[u] || v == beg[u] || ufs[u].sameset(f, v)) continue;
			if (ufs[u].pre[v] || ufs[u].nxt[f]) continue;
			if (beg[u] != 0 && end[u] != 0 && deg[u] > 2 && 
				ufs[u].sameset(f, beg[u]) && ufs[u].sameset(v, end[u])) continue;
			mn = std::min(mn, dfs(v, u));
		}
	}
	return mn;
}

bool dfs2(int u, int f, int& tar) {
	if (u == tar) {
		end[u] = f; return true;
	}
	for (int v : gra[u]) {
		if (v == f) continue;
		if (dfs2(v, u, tar)) {
			if (f == 0) {
				beg[u] = v;
			} else {
				ufs[u].join(f, v);
				deg[u]--;
			}
			return true;
		}
	}
	return false;
}

int main() {
	T = readint();
	while (T--) {
		n = readint();

		// init
		memset(beg, 0, sizeof(beg));
		memset(end, 0, sizeof(end));
		memset(deg, 0, sizeof(deg));
		for (int i = 1; i <= n; i++) {
			gra[i].clear();
			ufs[i].clear();
		}
		
		// input
		for (int i = 1; i <= n; i++) ptn[i] = readint();
		for (int i = 1, x, y; i < n; i++) {
			x = readint(); y = readint();
			gra[x].push_back(y);
			gra[y].push_back(x);
			deg[x]++; deg[y]++; // deg 表示一个点的边关系构成的链的数量,初始为度数,之后每加入一个关系就对其减 1
		}

		// process
		for (int i = 1; i <= n; i++) {
			int mn = dfs(ptn[i], 0);
			dfs2(ptn[i], 0, mn);
			printf("%d ", mn);
		}
		putchar('\n');
	}
	return 0;
}
[CSP-S2 2019]格雷码 题解

[CSP-S2 2019]格雷码 题解

题目地址:洛谷:P5657 格雷码 – 洛谷 | 计算机科学教育新生态

题目描述

通常,人们习惯将所有 $n$ 位二进制串按照字典序排列,例如所有 $2$ 位二进制串按字典序从小到大排列为:$00$,$01$,$10$,$11$。

格雷码(Gray Code)是一种特殊的 $n$ 位二进制串排列法,它要求相邻的两个二进制串间恰好有一位不同,特别地,第一个串与最后一个串也算作相邻。

所有 $2$ 位二进制串按格雷码排列的一个例子为:$00$,$01$,$11$,$10$。

$n$ 位格雷码不止一种,下面给出其中一种格雷码的生成算法:

  1. $1$ 位格雷码由两个 $1$ 位二进制串组成,顺序为:$0$,$1$。
  2. $n + 1$ 位格雷码的前 $2^n$ 个二进制串,可以由依此算法生成的 $n$ 位格雷码(总共 $2^n$ 个 $n$ 位二进制串)按顺序排列,再在每个串前加一个前缀 $0$ 构成。
  3. $n + 1$ 位格雷码的后 $2^n$ 个二进制串,可以由依此算法生成的 $n$ 位格雷码(总共 $2^n$ 个 $n$ 位二进制串)按逆序排列,再在每个串前加一个前缀 $1$ 构成。

综上,$n + 1$ 位格雷码,由 $n$ 位格雷码的 $2^n$ 个二进制串按顺序排列再加前缀 $0$,和按逆序排列再加前缀 $1$ 构成,共 $2^{n+1}$ 个二进制串。另外,对于 $n$ 位格雷码中的 $2^n$ 个二进制串,我们按上述算法得到的排列顺序将它们从 $0 \sim 2^n – 1$ 编号。

按该算法,$2$ 位格雷码可以这样推出:

  1. 已知 $1$ 位格雷码为 $0$,$1$。
  2. 前两个格雷码为 $00$,$01$。后两个格雷码为 $11$,$10$。合并得到 $00$,$01$,$11$,$10$,编号依次为 $0 \sim 3$。

同理,$3$ 位格雷码可以这样推出:

  1. 已知 $2$ 位格雷码为:$00$,$01$,$11$,$10$。
  2. 前四个格雷码为:$000$,$001$,$011$,$010$。后四个格雷码为:$110$,$111$,$101$,$100$。合并得到:$000$,$001$,$011$,$010$,$110$,$111$,$101$,$100$,编号依次为 $0 \sim 7$。

现在给出 $n, k$,请你求出按上述算法生成的 $n$ 位格雷码中的 $k$ 号二进制串。

题意简述

按规则求出格雷码。

输入输出格式

输入格式:

从文件 code.in 中读入数据。

仅一行两个整数 $n, k$,意义见题目描述。

输出格式:

输出到文件 code.out 中。

仅一行一个 $n$ 位二进制串表示答案。

输入输出样例

输入样例#1:

2 3

输出样例#1:

10

输入样例#2:

3 5

输出样例#2:

111

数据范围

对于 $50\%$ 的数据:$n \leq 10$

对于 $80\%$ 的数据:$k \leq 5 \times 10^6$

对于 $95\%$ 的数据:$k \leq 2^{63}-1$

对于 $100\%$ 的数据:$1 \leq n \leq 64 , 0 \leq k < 2^n$

题解

要求出 $n$ 位格雷码,就需要求出 $n-1$ 位格雷码, $n-1$ 位格雷码又需要用 $n-2$ 位格雷码来求,这构成了一种适合递归解决的问题。因此,这里就使用递归解决这个问题。

接下来分析求出样例 $2$ 答案的过程:

code csps219 pic1 - [CSP-S2 2019]格雷码 题解

我们可以推得解决一般性问题的流程:

  1. 边界条件:当 $n=1$ 时, $k$ 值就是此时要求的的 $1$ 位格雷码;
  2. 判断当前 $k$ 属于前半段(正序)还是后半段(逆序),这决定了是否需要把下一层的递归 $k$ 值换算成正序的编号以及加的前缀是 $0$ 还是 $1$ ;
  3. 如果 $k < 2^{n-1}$ ,说明要求的格雷码是前半段的,对应 $n-1$ 位格雷码的编号 $k$ ,加前缀 $0$ ;
  4. 如果 $2^{n-1} \leq k \leq 2^n-1$ ,说明要求的格雷码是后半段的,对应 $n-1$ 位格雷码的编号 $2^n-1-k$ ,加前缀 $1$ 。

使用递归实现这一流程即可求出格雷码。

需要注意的是,本题的数据范围为 $n \leq 64$ ,需要用 unsigned long long ,否则会溢出导致 $95$ 分。

代码

// Code by KSkun, 2019/11
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <utility>

typedef unsigned long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	LL res = 0, neg = 1; char c = fgc();
	for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
	for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while(!isgraph(c = fgc())) {}
	return c;
}

LL n, k;
int ans[100];

void dfs(int pos, LL k) {
	if (pos == 1) {
		ans[pos] = k;
		return;
	}
	if (k < (1ull << (pos - 1))) {
		ans[pos] = 0;
		dfs(pos - 1, k);
	} else {
		ans[pos] = 1;
		dfs(pos - 1, (1ull << (pos - 1)) - k - 1 + (1ull << (pos - 1)));
	}
}

int main() {
	n = readint(); k = readint();
	dfs(n, k);
	for (int i = n; i >= 1; i--) {
		printf("%d", ans[i]);
	}
	return 0;
}
Web开发学习手记(三):MVC架构

Web开发学习手记(三):MVC架构

前言

在Web开发实践中,我尝试使用MVC架构进行了一次完整的后端开发。

这篇文章记录我对MVC架构的理解和实例。

MVC结构

MVC是指Model-View-Controller,即将一个项目中的数据、业务逻辑、展示三部分分开。在处理业务时,调用的顺序应当是View-Controller-Model。

Model

Model,即模型,是指数据模型。在Model里处理的事务包括数据的结构、存取、管理等,与数据库等的交互应当只在这个部分中出现。

Controller

Controller,即控制器,是指控制Model的控制器,也就是业务逻辑。在Controller里处理的事务包括业务的处理,处理用户的操作请求,使用、操作数据模型完成操作或进行响应。

View

View,即视图,是指展示给用户的部分。用户通过View与Controller交互。需要注意的是,View是广义的视图,它的形式不局限于HTML或应用GUI等。例如,在下面的用户系统实例中,View仅仅是将Handler绑定到Router上这个步骤。

实例:简单的用户系统

在这个实例中,需要实现一个支持用户注册、登录、使用JWT Token获得API权限的简单用户系统,使用JSON请求和响应,使用MongoDB作为数据库。

Model

用户的数据包括用户名和加密后的密码,在这里用一个struct管理。

在这里实现的函数有:

  • init():初始化Model。创建到MongoDB的session。
  • IsUserExists(name string):检查用户是否存在。
  • GetUserByName(name string):获取用户。这里连接到MongoDB进行查询。
  • AddUser(user User):添加用户。这里连接到MongoDB进行添加。

Controller

控制器实现了一个Handler函数BindAccount(context *gin.Context),在这个函数里进行两个业务操作的处理:

  • 注册:调用model.AddUser函数。
  • 登录:首先获取指定用户信息,比对密码。如果登陆成功,则生成一个JWT Token并响应给客户端。

View

将Controller实现的Handler函数绑定到Router上。

Middleware

除了注册登录接口之外还实现了一个API接口,用于验证API权限。验证权限使用了JWT Middleware。

在这里实现了一个函数ValidateJWT(context *gin.Context)用于验证客户端发来的JWT Token是否有效。如果无效,则在进入Handler之前就响应http.StatusUnauthorized