编程题
R7-1 目录树
在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。
输入格式:
输入首先给出正整数N（≤104），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：
- 路径和名称中的字符仅包括英文字母（区分大小写）；
- 符号“\”仅作为路径分隔符出现；
- 目录以符号“\”结束；
- 不存在重复的输入项目；
- 整个输入大小不超过2MB。
输出格式:
假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。
输入样例:
7 b c\ ab\cd a\bc ab\d a\d\a a\d\z\
输出样例:
root a d z a bc ab cd d c b
#include<cstdio> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<set> #include<map> #define MAXN 100010 using namespace std; struct node { string name; int isCata; // 目录文件标记 vector<node*> child; // 孩子指针 }; bool cmp(node* a, node* b) { if(a->isCata != b->isCata) return a->isCata > b->isCata; else return a->name < b->name; } void dfs(node* root,int level) { if(root == NULL) return ; // 先输出自己 for(int i = 0; i < level; ++i) printf(" "); printf("%s\n",root->name.c_str()) ; // 排序所有孩子 ： 目录在前，文件在后，字典升序 sort(root->child.begin(),root->child.end(),cmp); // 向下递归 for(int i = 0; i < root->child.size(); ++i) dfs(root->child[i],level+1); } int n; int main() { scanf("%d",&n); getchar(); // 建立根节点 node* root = new node; root->name = "root"; root->isCata = 1; string tmp,str; node* curRoot; for(int j = 0; j < n; ++j) { // 每一个新的路径，都将根设为 root curRoot = root; getline(cin,str); for(int i = 0; i <= str.size(); ++i) { if(str[i] == '\\') { // 情况 1. 是目录 ： 切换当前目录， // 在当前父目录中寻找，看是否存在 int flag = 0; for(int k = 0; k < curRoot->child.size(); ++k) { // 1.1 有该目录 if(curRoot->child[k]->name == tmp && curRoot->child[k]->isCata == 1) { // 则切换当前目录 curRoot = curRoot->child[k]; flag = 1; break; } } // 1.2 没有该目录则创建一个 if(!flag) { // 创建结点 node* newnode = new node; newnode->name = tmp; newnode->isCata = 1; // 加入父目录 curRoot->child.push_back(newnode) ; // 切换当前目录 curRoot = newnode; } // 单词清零 tmp.clear(); // 情况 2. 是文件 }else if(i == str.size()) { if(!tmp.empty()) { // 到达最后，而单词不空，说明是文件 // 将文件加入到父节点中 node* newnode = new node; newnode->name = tmp; newnode->isCata = 0; curRoot->child.push_back(newnode) ; } tmp.clear(); } else { // 情况 3. 累加单词字母 tmp += str[i]; } } } // 输出过程 dfs(root,0); return 0; }
R7-1 是否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
4 2 3 1 4 2 3 4 1 2 3 2 4 1 2 1 2 1 1 2 0
输出样例:
Yes No No
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct TreeNode *Tree; struct TreeNode{ ElementType Data; Tree Left; Tree Right; int flag; //判别一个序列，没被访问设为0，被访问设为1 }; typedef Tree BinTree; BinTree Create(int N); BinTree NewNode(int V); BinTree Insert(BinTree T,int V); int Judge(BinTree T,int N); int check(BinTree T,int V); void ResetT(BinTree T); void FreeTree(BinTree T); int main() { int N,L,i; BinTree T; scanf("%d",&N); while(N) { scanf("%d",&L); T = Create(N); for(i = 0; i < L;i++) { if(Judge(T,N)) printf("Yes\n"); else printf("No\n"); ResetT(T); /* 清除T中的标记flag*/ } FreeTree(T); /* 比较完一组就释放*/ scanf("%d",&N); } } void FreeTree(BinTree T) { if(T->Left) FreeTree(T->Left); if(T->Right) FreeTree(T->Right); free(T); } void ResetT(BinTree T) { if(T->Left) ResetT(T->Left); if(T->Right) ResetT(T->Right); T->flag = 0; } BinTree Create(int N) { BinTree T = NULL; int V,i; scanf("%d",&V); T = NewNode(V); for(i = 0;i < N-1;i++) { scanf("%d",&V); T = Insert(T,V); } return T; } BinTree NewNode(int V) { BinTree BT; BT = (BinTree)malloc(sizeof(struct TreeNode)); BT->Data = V; BT->Left = NULL; BT->Right = NULL; BT->flag = 0; return BT; } BinTree Insert(BinTree T,int V) { BinTree TNode; if(!T) T = NewNode(V); else{ if(T->Data < V) { T->Right = Insert(T->Right,V); } if(T->Data > V) { T->Left = Insert(T->Left,V); } } return T; } /*当发现序列中的某个数和T不一样，必须把序列后面的数都读完*/ int Judge(BinTree T,int N) { int i; int V; int flag = 0; /*flag:0 代表目前一致 flag:1 代表已经不一致 */ scanf("%d",&V); if(V!=T->Data) flag = 1; else T->flag = 1; for (i = 1; i < N;i++) { scanf("%d",&V); /* 若check为0，则return 0；之前出现的节点没有被访问过，出现新的节点，所以树不一致*/ if(!flag && !check(T,V)) flag = 1; } if(flag) return 0; else return 1; } int check(BinTree T,int V) { if(T->flag) { if(V > T->Data) return check(T->Right,V); if(V < T->Data) return check(T->Left,V); // 若相等，则说明之前已经出现过一个相同的数，则两个树不一致 if(V == T->Data) return 0; } else{ if(V == T->Data) { T->flag = 1; return 1; } else{ return 0; } } }
R7-2 二叉搜索树的结构
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）
给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。
输入格式：
输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：
A is the root，即"A是树的根"；A and B are siblings，即"A和B是兄弟结点"；A is the parent of B，即"A是B的双亲结点"；A is the left child of B，即"A是B的左孩子"；A is the right child of B，即"A是B的右孩子"；A and B are on the same level，即"A和B在同一层上"。
题目保证所有给定的整数都在整型范围内。
输出格式：
对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。
输入样例：
5 2 4 1 3 0 8 2 is the root 1 and 4 are siblings 3 and 0 are on the same level 2 is the parent of 4 3 is the left child of 4 1 is the right child of 2 4 and 0 are on the same level 100 is the right child of 3
输出样例：
Yes Yes Yes Yes Yes No No No
#include <iostream> #include <string> #include <string.h> #include <map> using namespace std; const int MAX = 1e7 + 10; int tree[MAX]; //二叉搜索树 int deepth[MAX]; //结点深度 int tem; map<int, int> num; //键值对应的结点编号 void creatTree(int x, int d) //建立二叉搜索树 { if (tree[x] == 0x3f3f3f3f) { tree[x] = tem; num.insert(make_pair(tem, x)); deepth[x] = d; } else { if (tem < tree[x]) creatTree(x * 2, d + 1); else creatTree(x * 2 + 1, d + 1); } return; } int main() { int n; cin >> n; memset(tree, 0x3f, sizeof(tree)); //将每个元素初始化为0x3f3f3f3f for (int i = 0; i < n; i++) { cin >> tem; creatTree(1, 1); } int k; cin >> k; while (k--) { string str; int a, b; cin >> a >> str; if (str == "and") { cin >> b >> str >> str; if (str == "siblings") { if (num.find(a) == num.end() || num.find(b) == num.end()) cout << "No" << endl; else if (num[a] / 2 == num[b] / 2) cout << "Yes" << endl; else cout << "No" << endl; } else { getline(cin, str); if (num.find(a) == num.end() || num.find(b) == num.end()) cout << "No" << endl; else if (deepth[num[a]] == deepth[num[b]]) cout << "Yes" << endl; else cout << "No" << endl; } } else { cin >> str >> str; if (str == "root") { if (num.find(a) == num.end()) cout << "No" << endl; else if (num[a] == 1) cout << "Yes" << endl; else cout << "No" << endl; } else if (str == "parent") { cin >> str >> b; if (num.find(a) == num.end() || num.find(b) == num.end()) cout << "No" << endl; else if (num[a] == num[b] / 2) cout << "Yes" << endl; else cout << "No" << endl; } else if (str == "left") { cin >> str >> str >> b; if (num.find(a) == num.end() || num.find(b) == num.end()) cout << "No" << endl; else if (num[b] * 2 == num[a]) cout << "Yes" << endl; else cout << "No" << endl; } else { cin >> str >> str >> b; if (num.find(a) == num.end() || num.find(b) == num.end()) cout << "No" << endl; else if (num[b] * 2 + 1 == num[a]) cout << "Yes" << endl; else cout << "No" << endl; } } } return 0; }
R7-3 平衡二叉树的根
将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。
输入格式:
输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。
输出格式:
在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。
输入样例1:
5 88 70 61 96 120
输出样例1:
70
输入样例2:
7 88 70 61 96 120 90 65
输出样例2:
88
#include <iostream> using namespace std; struct Node { int data; Node* lc; Node* rc; }; int height(Node* T) { return T == NULL ? 0 : max(height(T->lc), height(T->rc)) + 1; } Node* turn1(Node* T) { //单向右旋 Node* A = T->lc; T->lc = A->rc; A->rc = T; return A; } Node* turn2(Node* T) { //单向左旋 Node* A = T->rc; T->rc = A->lc; A->lc = T; return A; } Node* turn3(Node* T) { //先左旋后右旋 T->lc = turn2(T->lc); return turn1(T); } Node* turn4(Node* T) { //先右旋后左旋 T->rc = turn1(T->rc); return turn2(T); } Node* Insert(Node* T, int x) { if (!T) T = new Node({ x,NULL,NULL }); else if (x < T->data) { T->lc = Insert(T->lc, x); if (height(T->lc) - height(T->rc) == 2) T = (x < T->lc->data ? turn1(T) : turn3(T)); } else if (x > T->data) { T->rc = Insert(T->rc, x); if (height(T->lc) - height(T->rc) == -2) T = (x > T->rc->data ? turn2(T) : turn4(T)); } return T; } int main() { Node* Tree = NULL; int n, t; cin >> n; while (n--) { cin >> t; Tree = Insert(Tree, t); } cout << Tree->data << endl; return 0; }
R7-1 完全二叉搜索树
一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。
输入格式：
首先第一行给出一个正整数 N（≤1000），随后第二行给出 N 个不重复的非负整数。数字间以空格分隔，所有数字不超过 2000。
输出格式：
在一行中输出这棵树的层序遍历序列。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
10 1 2 3 4 5 6 7 8 9 0
输出样例：
6 3 8 1 5 7 9 0 2 4
#include <iostream> #include <algorithm> using namespace std; int in[1001]; int res[1001]; int n,len; void dfs(int i){ if(i>n) return; dfs(2*i); res[i] = in[++len]; dfs(2*i+1); } int main(){ cin >> n; for(int i = 1;i<=n;i++){ cin >> in[i]; } sort(in+1,in+1+n); dfs(1); for(int i = 1;i<=n;i++){ if(i==1) cout << res[i]; else cout << " " << res[i]; } return 0; }
R7-1 修理牧场
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。
但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
输入首先给出正整数N（≤104），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8 4 5 1 2 1 3 1 1
输出样例:
49
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx=1e18; const int N=1E6+100; const int p=1e4; const double eps =1e-8; priority_queue<int,vector<int>,greater<int>>pmin; int n,t,sum; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>t; pmin.push(t); } while(pmin.size()!=1) { int k1,k2; k1=pmin.top(); pmin.pop(); k2=pmin.top(); pmin.pop(); sum+=(k1+k2); pmin.push(k1+k2); } cout<<sum; }
R7-2 嘴强王者
在召唤师峡谷中，优秀的召唤师总是喜欢比较自己的战斗力强弱，而青铜召唤师也不甘示弱，他们比较嘴炮的强弱。由于他们的嘴炮水平总是不断变化，难以通过人工进行比较，因此请你帮他们开发一个算法，找出其中的嘴强王者。
输入格式:
第一行两个正整数n,m，表示有n个选手，m次操作（1≤n≤105,1≤m≤5000)。
第二行有n个整数，分别表示第i个选手的初始嘴炮值ai；选手的编号从1到n。
接下来有m行，每行三个正整数x,l,r;
当x=1时，这是一个询问操作，询问区间[l,r]里面嘴炮值最高的召唤师，即嘴强王者；
当x=0时，这是一个更新操作，表示选手l的嘴炮值更新为r。
题目保证在每个查询区间内，嘴强王者是唯一的。
输出格式:
对于每个询问操作，在一行里面输出里面的嘴强王者的编号及其嘴炮值，用用空格分隔，行末没有多余空格。
输入样例:
5 6 1 2 3 4 5 1 1 5 0 3 6 1 3 4 1 4 5 0 2 9 1 1 5
输出样例:
在这里给出相应的输出。例如：
5 5 3 6 5 5 2 9
#include<bits/stdc++.h> #include<math.h> using namespace std; int n, m; int v[18][1 << 17]; int h = 1; void build() { for (int i = 1; i <= h; i++) { int span = pow(2, i); for (int j = 1; j <= n; j += span) { v[i][j] = max(v[i - 1][j], v[i - 1][j + (span / 2)]); } } } int update(int index, int val, int ll, int rr) { int idx = log2(rr - ll + 1); int mid = (ll + rr) / 2; if (ll > index || rr < index) return v[idx][ll]; if (ll == rr) { if (ll == index) { v[0][index] = val; return val; } else return v[0][ll]; } // 更新最大值 return v[idx][ll] = max(update(index, val, ll, mid), update(index, val, mid + 1, rr)); } int find(int l, int r, int ll, int rr) { if (rr < l || ll > r) return 0; int idx = log2(rr - ll + 1); if (ll >= l && rr <= r) return v[idx][ll]; int mid = (ll + rr) / 2; return max(find(l, r, ll, mid), find(l, r, mid + 1, rr)); } int main() { cin >> n >> m; while (pow(2, h) < n) h++; map<int, set<int>> mp; // 用来记录下标的小技巧 for (int i = 1; i <= n; i++) { cin >> v[0][i]; mp[v[0][i]].insert(i); } build(); for (int i = 0; i < m; i++) { int x, l, r; cin >> x >> l >> r; if (x == 1) { int ans = find(l, r, 1, pow(2, h)); int idx = *mp[ans].lower_bound(l); // 二分快速查找当前的下标 cout << idx << " " << ans << endl; } else { mp[v[0][l]].erase(l); // 更新时删除原来的下标 mp[r].insert(l); // 添加新的下标 update(l, r, 1, pow(2, h)); } } return 0; }
R7-3 房屋分拆
厂长买了一整间房屋作为车间，现准备将整个房屋分成若干个车间。装修公司规定分拆房屋的价格等于被分拆房屋的面积。如想将面积为200的房间分拆为面积为80、70和50的三个车间，第一次将房屋分拆为面积120和80的两个房间，花费200，第二次将面积为120的房间分拆为面积为70和50的两个房间，花费120，总花费为320。如果采用另一种方案，第一次将面积200的房屋分拆为150和50，花费200，第二次将面积为150的房间分拆为80和70的房间，花费150，则总花费为350。显然第一种方案花费更少。请编写程序为厂长设计花费最少的分拆方案。
输入格式:
输入为两行，第一行为一个整数n，表示所需的车间数量。第二行为n个正整数，以空格间隔，给出每个车间需要的面积。n不超过100000，且保证最终结果小于231。
输出格式:
输出为一个整数，表示将整个房屋分拆为n个车间所需的最少花费。
输入样例:
8 1 1 1 1 2 3 4 5
输出样例:
49
#include<stdio.h> #include<stdlib.h> typedef struct Node * Heap; /*堆结构*/ struct Node { int * Data; int Size; }; typedef Heap MinHeap;/*最小堆*/ Heap CreateHeap(int n)//最小堆的创建 { MinHeap H=(MinHeap)malloc(sizeof(struct Node)); H->Data=(int *)malloc(2*(n+1)*sizeof(int)); H->Size=0;//初始化 H->Data[0]=0;/*最小堆的哨兵*/ return H; } void Insert(Heap H,int m)//建初堆 { int i; i=++H->Size; for(; H->Data[i/2]>m; i/=2) H->Data[i]=H->Data[i/2]; H->Data[i]=m; } int Del(Heap H)//重建小跟堆 { int parent,child; int min,x; min=H->Data[1]; x=H->Data[H->Size--];//用最后一个元素替代已经输出的堆顶元素 for(parent=1; parent*2<=H->Size ; parent=child) //沿较小的孩子向下筛选{ { child=parent*2; if((child!=H->Size)&&(H->Data[child]>H->Data[child+1])) child++; if(H->Data[child]>=x) break; else H->Data[parent]=H->Data[child]; } H->Data[parent]=x; return min; } int main() { int n,m,i,sum=0,a,b; scanf("%d",&n); Heap H=CreateHeap(n); for(i=1; i<=n; i++) { scanf("%d",&m); Insert(H,m);/*将所有元素入堆(H)*/ } while(H->Size!=1) { a=Del(H);//去掉最小值再重建堆 b=Del(H);//去掉次小值再重建堆 b=a+b; sum+=b;//不断累加求和 Insert(H,b); } printf("%d\n",sum); // system("pause"); return 0; }
R7-4 动态区间求和
输入样例:
3 2 1 2 3 1 2 0 2 1 3
输出样例:
6
#include <iostream> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int MAXN = 1e6 + 5; ll n, q, c[MAXN];//树状数组， 下标为某一个元素， 值为这个元素出现的次数 int lowbit(int x) { return x&(-x); } //update将第x个整数加上v void update(int x, int v) { for (int i = x; i <= n; i += lowbit(i)) { c[i] += v; } } //getSum返回前x个整数之和 ll getSum(int x) { ll sum = 0; for (int i = x; i > 0; i -= lowbit(i)) { sum += c[i]; } return sum; } int main() { cin >> n >> q; memset(c, 0, sizeof(c)); for (int i = 1; i <= n; i++) { int temp; cin >> temp; update(i, temp); } while (q--) { int a, b, c; cin >> a >> b >> c; if (a == 1) { update(b, c); } else if (a == 2) { cout << getSum(c) - getSum(b - 1) << endl; } } }
R7-1 哈夫曼编码
给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。
输入格式：
首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：
c[1] f[1] c[2] f[2] ... c[N] f[N]
其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：
c[i] code[i]
其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。
输出格式：
对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。
注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。
输入样例：
7 A 1 B 1 C 1 D 3 E 3 F 6 G 6 4 A 00000 B 00001 C 0001 D 001 E 01 F 10 G 11 A 01010 B 01011 C 0100 D 011 E 10 F 11 G 00 A 000 B 001 C 010 D 011 E 100 F 101 G 110 A 00000 B 00001 C 0001 D 001 E 00 F 10 G 11
输出样例：
Yes Yes No No
#include<iostream> #include<queue> #include<vector> #include<string> #include<map> using namespace std; int c[100],f[100],n,m; string code[100];//存储序列 char ch[100]; map<char,int> mp; bool check(int WPL){ int a,b,wpl = 0; for(int i = 0;i<n;++i){ for(int j = i+1;j<n;++j){ a = code[i].find(code[j]); //前缀判断，存在则返回第一个位置，否则返回最后一个位置 b = code[j].find(code[i]); if((a==0) || (b==0)){ return false; } } wpl+=mp[ch[i]]*code[i].length();//计算当前wpl } if(wpl==WPL) return true; else return false; } int main(){ cin>>n; priority_queue<int,vector<int>,greater<int> > pqu;//优先队列，排序 for(int i = 0;i<n;++i){ scanf(" %c %d",&c[i],&f[i]); pqu.push(f[i]); mp[c[i]] = f[i];//存储字母的权值 } int WPL= 0,tmp = 0; while(pqu.size()>1){//compute WPL tmp = pqu.top(); pqu.pop(); tmp+=pqu.top(); pqu.pop(); WPL+=tmp; pqu.push(tmp); } cin >> m; for(int i = 0;i<m;++i){ for(int j = 0;j<n;++j){ scanf(" %c",&ch[j]); cin >>code[j]; } if(check(WPL)) cout <<"Yes"<<endl; else cout <<"No"<<endl; } return 0; }
至此，树的编程题就结束了，在下一篇中我们将介绍散列表的相关知识点。
