欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

程序设计【Week9】作业

程序员文章站 2022-06-28 17:45:52
...

A题

咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！
初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。
程序设计【Week9】作业

程序设计【Week9】作业
程序设计【Week9】作业

输入
输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 T （T <= 20）；
每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q （Q <= 1e5）；
每组测试数据的 2 ~ Q+1 行为具体的操作 （MKDIR、RM 操作总数不超过 5000）；
面对数据范围你要思考的是他们代表的 “命令” 执行的最大可接受复杂度，只有这样你才能知道你需要设计的是怎样复杂度的系统。

输出
每组测试数据的输出结果间需要输出一行空行。注意大小写敏感。
时空限制
Time limit 6000 ms
Memory limit 1048576 kB

样例输入
1
22
MKDIR dira
CD dirb
CD dira
MKDIR a
MKDIR b
MKDIR c
CD …
MKDIR dirb
CD dirb
MKDIR x
CD …
MKDIR dirc
CD dirc
MKDIR y
CD …
SZ
LS
TREE
RM dira
TREE
UNDO
TREE

样例输出
OK
ERR
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
9
dira
dirb
dirc
root
dira
a
b
c
dirb
x
dirc
y
OK
root
dirb
x
dirc
y
OK
root
dira
a
b
c
dirb
x
dirc
y

思路：
从整体来考虑，然后分每一个操作步骤来考虑。
MKDIR:即在当前节点创建一个节点，UNDO：逆过程，在这个位置删除节点，需要记录当前及节点和创建的点，undo要将加号的边删除
RM：因为UNDO操作，我们仅仅做的是剪掉两个点之间的边而不是完全将字数删掉，恢复的时候直接把这条边加回来
CD：要有一个变量now,记录当前所在位置，执行成功要从哪里到哪里
TREE（超难！）：缓存更新记忆化：存储答案并标记是否被更新过。

总结：
这个题真的好难好难好难，我的天，辛亏上课的时候听了思路要不然我真的GG。
其实像这种题最关键在于理解，然后把题目的描述转为熟悉的计算机思路，同时学会封装。

代码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

struct Directory
{
	string name;
	map<string, int>op;
	int pa, ch;
	vector<string> pre, back;
	bool tag;
}node[200000];

int now, index;
struct point
{
	string name;
	int now;
	int next;
};
vector<point> v;
void update(int id, int num)
{
	while (id != -1)
	{
		node[id].tag = 0;
		node[id].ch += num;
		id = node[id].pa;
	}
}
void MKDIR(string& s)
{
	if (node[now].op.count(s) == 1)
		cout << "ERR" << endl;
	else
	{
		node[now].op.insert(pair<string, int>(s, index));
		update(now, 1);
		node[index].name = s;
		node[index].pa = now;
		node[index].ch = 1;
		node[index].tag = 0;
		node[index].op.clear();
		node[index].pre.clear();
		node[index].back.clear();
		point p;
		p.name = "MKDIR", p.now = now, p.next = index;
		v.push_back(p);
		index++;
		cout << "OK" << endl;
		//cout<<";;;;";
	}
}
void RM(string& s)
{
	if (node[now].op.count(s) == 1)
	{
		int inOfS = node[now].op[s];
		node[now].op.erase(s);
		update(now, (-1) * node[inOfS].ch);
		//将操作放入undo的vector中
		point p;
		p.name = "RM", p.now = now, p.next = inOfS;
		v.push_back(p);
		cout << "OK" << endl;
	}
	else	cout << "ERR" << endl;
}
void CD(string& s)
{
	if (s == "..")
	{
		if (node[now].pa == -1)
			cout << "ERR" << endl;
		else
		{

			point p;
			p.name = "CD", p.now = now, p.next = node[now].pa;
			v.push_back(p);
			now = node[now].pa;
			cout << "OK" << endl;
		}
	}
	else
	{
		if (node[now].op.count(s) == 1)
		{

			point p;
			p.name = "CD", p.now = now, p.next = node[now].op[s];
			v.push_back(p);
			now = node[now].op[s];
			cout << "OK" << endl;
		}
		else cout << "ERR" << endl;
	}
}
void SZ()
{
	cout << node[now].ch << endl;
}
void LS()
{
	if (node[now].op.size() == 0)
		cout << "EMPTY" << endl;
	else if (node[now].op.size() >= 1 && node[now].op.size() <= 10)
	{
		for (map<string, int>::iterator it = node[now].op.begin(); it != node[now].op.end(); it++)
			cout << it->first << endl;
	}
	else {


		map<string, int>::iterator it = node[now].op.begin();
		for (int i = 1; i <= 5; i++)
		{
			cout << it->first << endl;
			it++;
		}
		cout << "..." << endl;

		it = node[now].op.end();
		for (int i = 1; i <= 5; i++)
			it--;
		for (int i = 1; i <= 5; i++)
		{
			cout << it->first << endl;
			it++;
		}
	}
}
void alltrack(int id, vector<string>& pre)
{
	pre.push_back(node[id].name);
	for (map<string, int>::iterator it = node[id].op.begin(); it != node[id].op.end(); it++)
		alltrack(it->second, pre);
}
void pretrack(int id, vector<string>& pre, int& num)
{
	pre.push_back(node[id].name);
	num--;
	if (num == 0)	return;
	for (map<string, int>::iterator it = node[id].op.begin(); it != node[id].op.end(); it++)
	{
		pretrack(it->second, pre, num);
		if (num == 0)	break;
	}
}
void bcktrack(int id, vector<string>& bck, int& num)	//遍历id子树,求出后五个 
{
	map<string, int>::iterator it = node[id].op.end();
	int n = node[id].op.size();
	for (int i = 0; i < n; i++)
	{
		it--;
		bcktrack(it->second, bck, num);
		if (num == 0)	return;
	}
	bck.push_back(node[id].name);
	num--;
}
void pushdown(int id)
{
	node[id].pre.clear();
	node[id].back.clear();
	if (node[id].ch <= 10)
		alltrack(id, node[id].pre);
	else
	{
		int num = 5;
		pretrack(id, node[id].pre, num);
		num = 5;
		bcktrack(id, node[id].back, num);
	}
	node[id].tag = 1;
}
void TREE()
{
	if (!node[now].tag)
		pushdown(now);
	if (node[now].ch == 1)
		cout << "EMPTY" << endl;
	else if (node[now].ch > 1 && node[now].ch <= 10)
	{
		for (int i = 0; i < node[now].pre.size(); i++)
			cout << node[now].pre[i] << endl;
	}
	else
	{
		for (int i = 0; i < 5; i++)
			cout << node[now].pre[i] << endl;
		cout << "..." << endl;
		for (int i = 4; i >= 0; i--)
			cout << node[now].back[i] << endl;
	}
}
void UNDO()
{
	if (v.size() == 0)
		cout << "ERR" << endl;
	else
	{
		point p = v[v.size() - 1];
		v.pop_back();
		cout << "OK" << endl;
		if (p.name == "MKDIR")	//要删除
		{
			update(p.now, (-1) * node[p.next].ch);
			node[p.now].op.erase(node[p.next].name);
		}
		else if (p.name == "RM")
		{
			update(p.now, node[p.next].ch);
			node[p.now].op[node[p.next].name] = p.next;
		}
		else
			now = p.now;
	}
}
void init()
{
	now = 0, index = 1;
	node[0].name = "root", node[0].pa = -1, node[0].ch = 1, node[0].tag = 0;
	node[0].pre.clear(), node[0].back.clear(), node[0].op.clear();
	v.clear();
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	for (int t1 = 0; t1 < t; t1++)
	{
		if (t1 != 0)
			cout << endl;
		int q;
		cin >> q;
		init();
		for (int q1 = 0; q1 < q; q1++)
		{
			string op;
			cin >> op;
			if (op == "MKDIR")
			{
				string s;
				cin >> s;
				MKDIR(s);
			}
			else if (op == "RM")
			{
				string s;
				cin >> s;
				RM(s);
			}
			else if (op == "CD")
			{
				string s;
				cin >> s;
				CD(s);
			}
			else if (op == "SZ")
				SZ();
			else if (op == "LS")
				LS();
			else if (op == "TREE")
				TREE();
			else if (op == "UNDO")
				UNDO();
		}
	}
}

B题

题意：
最近，东东沉迷于打牌。所以他找到 HRZ、ZJM 等人和他一起打牌。由于人数众多，东东稍微修改了亿下游戏规则：
o所有扑克牌只按数字来算大小，忽略花色。
o每张扑克牌的大小由一个值表示。A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K 分别指代 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13。
o每个玩家抽得 5 张扑克牌，组成一手牌！（每种扑克牌的张数是无限的，你不用担心，东东家里有无数副扑克牌）
理所当然地，一手牌是有不同类型，并且有大小之分的。
举个栗子，现在东东的 “一手牌”（记为 α），瑞神的 “一手牌”（记为 β），要么 α > β，要么 α < β，要么 α = β。
那么这两个 “一手牌”，如何进行比较大小呢？首先对于不同类型的一手牌，其值的大小即下面的标号；对于同类型的一手牌，根据组成这手牌的 5 张牌不同，其值不同。下面依次列举了这手牌的形成规则：
1.大牌：这手牌不符合下面任一个形成规则。如果 α 和 β 都是大牌，那么定义它们的大小为组成这手牌的 5 张牌的大小总和。
2.对子：5 张牌中有 2 张牌的值相等。如果 α 和 β 都是对子，比较这个 “对子” 的大小，如果 α 和 β 的 “对子” 大小相等，那么比较剩下 3 张牌的总和。
3.两对：5 张牌中有两个不同的对子。如果 α 和 β 都是两对，先比较双方较大的那个对子，如果相等，再比较双方较小的那个对子，如果还相等，只能比较 5 张牌中的最后那张牌组不成对子的牌。
4.三个：5 张牌中有 3 张牌的值相等。如果 α 和 β 都是 “三个”，比较这个 “三个” 的大小，如果 α 和 β 的 “三个” 大小相等，那么比较剩下 2 张牌的总和。
5.三带二：5 张牌中有 3 张牌的值相等，另外 2 张牌值也相等。如果 α 和 β 都是 “三带二”，先比较它们的 “三个” 的大小，如果相等，再比较 “对子” 的大小。
6.炸弹：5 张牌中有 4 张牌的值相等。如果 α 和 β 都是 “炸弹”，比较 “炸弹” 的大小，如果相等，比较剩下那张牌的大小。
7.顺子：5 张牌中形成 x, x+1, x+2, x+3, x+4。如果 α 和 β 都是 “顺子”，直接比较两个顺子的最大值。
8.龙顺：5 张牌分别为 10、J、Q、K、A。
作为一个称职的魔法师，东东得知了全场人手里 5 张牌的情况。他现在要输出一个排行榜。排行榜按照选手们的 “一手牌” 大小进行排序，如果两个选手的牌相等，那么人名字典序小的排在前面。
不料，此时一束宇宙射线扫过，为了躲避宇宙射线，东东慌乱中清空了他脑中的 Cache。请你告诉东东，全场人的排名

输入
输入包含多组数据。每组输入开头一个整数 n (1 <= n <= 1e5)，表明全场共多少人。
随后是 n 行，每行一个字符串 s1 和 s2 （1 <= |s1|,|s2| <= 10）， s1 是对应人的名字，s2 是他手里的牌情况。

输出
对于每组测试数据，输出 n 行，即这次全场人的排名。

样例输入
3
DongDong AAA109
ZJM 678910
Hrz 678910

样例输出
Hrz
ZJM
DongDong

代码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include<algorithm>
using namespace std;

int n;

struct paiyou
{
	string name;
	int p[5];
}pi[100010];

void change(int p[5], string s)
{
	int index = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] >= '2' && s[i] <= '9')//大于2小于9 
			p[index] = s[i] - '0';
		else if (s[i] == '1')
		{
			p[index] = 10;
			i++;
		}
		else if (s[i] == 'A')
		{
			p[index] = 1;
		}
		else if (s[i] == 'J')
		{
			p[index] = 11;
		}
		else if (s[i] == 'Q')
		{
			p[index] = 12;
		}
		else if (s[i] == 'K')
		{
			p[index] = 13;
		}
		index++;
	}
}

int revalue(int p[5], int a[5])
{
	if (p[0] == 1 && p[1] == 10 && p[2] == 11 && p[3] == 12 && p[4] == 13)//爆炸顺子 
	{
		return 8;
	}
	else if (p[1] == p[0] + 1 && p[2] == p[1] + 1 && p[3] == p[2] + 1 && p[4] == p[3] + 1)//顺子 
	{
		a[0] = p[4];
		return 7;
	}
	else if (p[0] == p[1] && p[1] == p[2] && p[2] == p[3])//41 
	{
		a[0] = p[0], a[1] = p[4];
		return 6;
	}
	else if (p[1] == p[2] && p[2] == p[3] && p[3] == p[4])//14
	{
		a[0] = p[1], a[1] = p[0];
		return 6;
	}
	else if (p[0] == p[1] && p[1] == p[2] && p[3] == p[4])//32
	{
		a[0] = p[0], a[1] = p[3];
		return 5;
	}
	else if (p[0] == p[1] && p[2] == p[3] && p[3] == p[4])//23
	{
		a[0] = p[2], a[1] = p[0];
		return 5;
	}
	else if (p[0] == p[1] && p[1] == p[2])//311 
	{
		a[0] = p[0], a[1] = p[3] + p[4];
		return 4;
	}
	else if (p[1] == p[2] && p[2] == p[3])//131 
	{
		a[0] = p[1], a[1] = p[0] + p[4];
		return 4;
	}
	else if (p[2] == p[3] && p[3] == p[4])//113 
	{
		a[0] = p[2], a[1] = p[0] + p[1];
		return 4;
	}
	else if (p[1] == p[2] && p[3] == p[4])//122 
	{
		if (p[1] > p[3])
			a[0] = p[1], a[1] = p[3], a[2] = p[0];
		else
			a[0] = p[3], a[1] = p[1], a[2] = p[0];
		return 3;
	}
	else if (p[0] == p[1] && p[2] == p[3])//221 
	{
		if (p[0] > p[2])
			a[0] = p[0], a[1] = p[2], a[2] = p[4];
		else
			a[0] = p[2], a[1] = p[0], a[2] = p[4];
		return 3;
	}
	else if (p[0] == p[1] && p[3] == p[4])//212
	{
		if (p[0] > p[3])
			a[0] = p[0], a[1] = p[3], a[2] = p[2];
		else
			a[0] = p[3], a[1] = p[0], a[2] = p[2];
		return 3;
	}
	else if (p[0] == p[1])//2111
	{
		a[0] = p[0], a[1] = p[2] + p[3] + p[4];
		return 2;
	}
	else if (p[1] == p[2])//1211
	{
		a[0] = p[1], a[1] = p[0] + p[3] + p[4];
		return 2;
	}
	else if (p[2] == p[3])//1121
	{
		a[0] = p[2], a[1] = p[0] + p[1] + p[4];
		return 2;
	}
	else if (p[3] == p[4])//1112
	{
		a[0] = p[3], a[1] = p[0] + p[1] + p[2];
		return 2;
	}
	else //啥也不是 
	{
		a[0] = p[0] + p[1] + p[2] + p[3] + p[4];
		return 1;
	}
}

bool cmp(paiyou& pai1, paiyou& pai2)
{
	int value1, value2;
	int a1[5], a2[5];
	value1 = revalue(pai1.p, a1);
	value2 = revalue(pai2.p, a2);
	//cout<<value1<<endl;
	//cout<<value2<<endl;
	if (value1 < value2) return true;
	else if (value1 > value2)  return false;
	else
	{
		if (value1 == 7 || value1 == 1)
		{
			if (a1[0] != a2[0])
				return a1[0] < a2[0];
		}
		else if (value1 == 6 || value1 == 5 || value1 == 4 || value1 == 2)
		{
			if (a1[0] != a2[0] || a1[1] != a2[1])
				return a1[0] == a2[0] ? a1[1] < a2[1] : a1[0] < a2[0];
		}
		else if (value1 == 3)	//两对 比较大对a[0]小对a[1]和剩余a[2] 
		{
			if (a1[0] < a2[0])	return true;
			else if (a1[0] > a2[0])	return false;
			else if (a1[1] < a2[1])	return true;
			else if (a1[1] > a2[1])	return false;
			else if (a1[2] < a2[2])	return true;
			else if (a1[2] > a2[2])	return false;
		}

		return pai1.name > pai2.name ? true : false;
	}
}

int main()
{
	while (~scanf("%d", &n))
	{
		for (int i = 0; i < n; i++)
		{
			int a[5];
			string s1, s2;
			cin >> s1 >> s2;
			pi[i].name = s1;
			change(pi[i].p, s2);
			int value = revalue(pi[i].p, a);
			//cout<<value<<" "<<a[0]<<endl;
			sort(pi[i].p, pi[i].p + 5);
		}
		sort(pi, pi + n, cmp);
		for (int i = n - 1; i >= 0; i--)
			cout << pi[i].name << endl;
	}
}

C题

题意：
SDUQD 旁边的滨海公园有 x 条长凳。第 i 个长凳上坐着 a_i 个人。这时候又有 y 个人将来到公园，他们将选择坐在某些公园中的长凳上，那么当这 y 个人坐下后，记k = 所有椅子上的人数的最大值，那么k可能的最大值mx和最小值mn分别是多少。

Input
第一行包含一个整数 x (1 <= x <= 100) 表示公园中长椅的数目
第二行包含一个整数 y (1 <= y <= 1000) 表示有 y 个人来到公园
接下来 x 个整数 a_i (1<=a_i<=100)，表示初始时公园长椅上坐着的人数

Output
输出 mn 和 mx

Input Example
3
7
1
6
1
Output Example
6 13

思路：
先将原来座椅排个序，令maxnum为序列最大值，则加入人以后的最大值为maxnum+b
最小值，先求所有人加到最大人数的椅子上的人数t，如果t>=maxnum,则最小值为maxnum，否则，最小值为（如果t%a==0)则最小值为t/a+maxnum,或者为t/a+maxnum+1.

代码：

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include<algorithm>
using namespace std;

int a, b, minas, maxn, maxnum;
int chair[110];
int main()
{
	cin >> a >> b;
	for (int i = 0; i < a; i++)
	{
		cin >> chair[i];
	}
	sort(chair, chair + a);
	maxnum = chair[a - 1];
	maxn = chair[a - 1] + b;
	int t = 0;
	for (int i = 0; i < a; i++)
	{
		t += chair[a - 1] - chair[i];
	}
	if (t >= b) minas = chair[a - 1];
	else
	{
		t = b - t;
		if (t % a == 0)  minas = maxnum + t / a;
		else
			minas = maxnum + t / a + 1;
	}
	cout << minas << " " << maxn << endl;
}
相关标签： 程序设计题

上一篇： http协议学习笔记

下一篇： 【java】Java编码字符集与字符集编码入门（一） 编码字符集的前世今生

推荐阅读