题目链接
一、填空题
-
如图所示，平面上有两条平行的线段，上面的线段有A0~A3 4个点，下面的线段有B0到B5 6个点，现在需要把所有的点都连接起来，有如下约束：
每个端点，都至少有一条到另一平行线上端点的连线；
连线之间不能有交叉（除了端点，线与线之间不能有连接的地方）；请问，总共有多少种连法？
答案：231
二、编程题
1. 访问权限
题目
JSON是一种可以用来保存配置的数据格式，其结构为树状。JSON中某个子节点的位置可以JSON路径的形式表示，JSON路径类似UNIX文件路径，以’/'分隔父子节点名。JSON路径中不会出现空格。
如下JSON值中
mem – daemons – findme
| |- waccd
|
|- apps – appd
findme子节点的JSON路径为： /mem/daemons/findme
appd子节点的JSON路径为：/mem/apps/appd
waccd子节点的JSON路径为：/mem/daemons/waccd
有一个列表用来描述各JSON子节点是否允许用户编辑。如下：
Y /mem/daemons/findme
N /mem/daemons
Y /mem
如果有设置用户对某个子节点的权限，则实际权限为该设定权限，否则继承其父节点的可访问性，对根节点的默认访问权限为N。
输入描述：
第一行为一个正整数N，表示接下来有N行数据(0 < N < 100)
第2行到第N+1行，为字符串Path，表示待检查访问权限的JSON路径。
第N+2行为一个正整数T，表示接下来有T行数据（0 < T < 1000）
接下来会有T行数据，格式为"权限 JSON路径"。
权限有两种取值：Y和N
JSON路径最大长度为256
输出描述：
输出“权限”，权限表示该节点的实际访问权限。
示例1
输入例子：
1
/mem/total
3
Y /mem/daemons/findme
N /mem/daemons
Y /mem
输出例子：
Y
思路——前缀树
将字符串 /mem/start拆分成 mem、start 两单词， 每个单词为一个前缀。
-
前缀树的属性：
- 当前文件夹是否有权限
- 当前文件夹是否是继承父目录的权限
- 当前文件夹的子目录
- 当前文件夹的名字
-
前缀树的操作：
- 插入
- 查询
- 更新所有文件夹的权限信息
-
主程序读入所有信息
- 将待查询的信息，先存在一个 vector 中
- 将其余信息用于构建前缀树
-
构建前缀树的过程
vector<string> str保存路径的名字信息（利用函数拆分字符串）- 检查
map中是否有str[i]这个文件夹的名字， 如果没有， 则创建一个文件夹，并赋予父目录的权限 node指向map[str[i]]这个节点
-
查询前缀树的过程：
- 逐个判断
path中的名字是否在前缀树出现 - 如果没有出现，则返回当前
node的权限
- 逐个判断
代码：
#include<iostream>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;class Trie {
public:bool hava_Authority = false; bool isInherient = true; // 当前节点的权限是不是继承父节点的unordered_map<string, Trie*> ls; // 孩子节点string name;Trie(bool au, string str) {hava_Authority = au; name = str;}Trie() {}void insert(bool au, vector<string> str) {if (str.empty()) { this->isInherient = false;this->hava_Authority = true;return;}Trie* node = this; // 当前节点(作为父节点)for (int i = 0; i < str.size(); i++) {// 在当前节点的孩子没有找到，说明目前没有该路径，需要新建节点if (node->ls.find(str[i]) == node->ls.end()) {Trie* tmp = new Trie(node->hava_Authority, str[i]); // 继承父节点的权限node->ls.insert(make_pair(str[i], tmp)); // umap 的插入语句}// 已经存在该路径，更新当前节点的下一个访问位置node = node->ls.find(str[i])->second;}// 遍历完 str，就可以更新最后一个节点的权限if (node->isInherient) node->hava_Authority = au; // 记录新的权限node->isInherient = false; // 由于最后一个节点肯定有自己的权限，所以标记为非继承}bool query(vector<string> str) {Trie* node = this;for (int i = 0; i < str.size(); i++) {// 如果在下一层找不到，说明当前层就是最终层if (node->ls.find(str[i]) == node->ls.end()) {break;}// 如果在孩子节点能找到下一层，就递归查询node = node->ls.find(str[i])->second;}// 返回当前层的权限return node->hava_Authority;}// 权限更新void update() {Trie* node = this;for (auto it = node->ls.begin(); it != node->ls.end(); it++) {if (it->second->isInherient) { // 是继承，此时权限是父节点的权限node->ls[it->first]->hava_Authority = node->hava_Authority;}node->ls[it->first]->update(); // 递归更新儿子}}
};vector<string> split(string str) {str += "/"; // 在末尾加上 '/' ，遇到最后一个字符也不需要特殊处理str = str.substr(1); // 跳过第一个 '/' 开始遍历vector<string> res;string tmp;for (int i = 0; i < str.size(); i++) {if (str[i] == '/') {if (tmp.size()) res.push_back(tmp);continue;}tmp += str[i];}return res;
}int main() {Trie* root = new Trie();int n;cin >> n;vector<vector<string>> query;while (n--) {string t;cin >> t;query.push_back(split(t));}cin >> n;string a, b;while (n--) {cin >> a >> b;if (a == "Y") {root->insert(true, split(b));}else {root->insert(false, split(b));}}// 插入结束后，对所有节点进行权限更新root->update();// 查询权限for (int i = 0; i < query.size(); i++) {if (root->query(query[i])) {cout << "Y\n";}else {cout << "N\n";}}return 0;
}
