程序员经验分享-hwhale

程序设计思维与实践 Week9 作业

2023-05-16

A - 咕咕东的目录管理器

题意

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

解题思路

  1. 首先我们要确定如何存储目录以及子目录，因为题目要求子目录必须要保持字典序，所以我们选用map来存储一个目录的所有子目录。
  2. MKDIR：直接在当前目录的map里插入新的目录即可。
  3. RM：是MKDIR的逆操作，将要删除的目录从当前目录中擦除即可。
  4. CD：将当前目录改为新目录
  5. SZ：每一次都遍历子目录会超时，所以我们可以对每一个目录增加sz来表示该目录的子节点数，这时，就需要在MKDIR和RM时向上更新sz直到root
  6. LS：直接判断并按顺序输出map的元素即可。
  7. TREE：与SZ类似，每一次都遍历的话会超时，所以我们可以存储一下答案，并标记一下是否被更新过。若进行了MKDIR和RM，则标记置空。
  8. UNDO：我们可以用一个vector存储执行过的指令，然后执行其逆操作即可。（在RM时我们不需要删除对应目录的所有信息，只需删去关系，以便恢复）

代码

#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
map<string, int> cases = {
	{"MKDIR", 0}, {"RM", 1}, {"CD", 2},
	{"SZ", 3}, {"LS", 4},{"TREE", 5},{"UNDO", 6}
};
struct command{	//记录
	int code;	//操作编号
	int op1;	//记录操作时的当前目录
	int op2;	//记录mkdir、rm、cd的操作数
	command(int a, int b, int c): code(a), op1(b), op2(c){}
};
vector<command> cmd;//记录mkdir、rm、cd指令方便undo
int now;//记录当前所在目录的下标
struct Directory
{
	string name;
	map<string, int> mp;
	int fa, sz;
	vector<string> pre,bck;
	bool tag;
}node[100005];
int node_i;
void update(int id, int num){
	while(id != -1){
		node[id].tag = 0;
		node[id].sz += num;
		id = node[id].fa;
	}
}
void mkdir(string &str){
	if(node[now].mp.count(str)){
		cout << "ERR\n";
		return;
	}
	cout << "OK\n";
	update(now, 1);
	node[now].mp.insert(pair<string, int>(str, node_i));
	node[node_i].name = str;
	node[node_i].fa = now;
	node[node_i].sz = 1;
	node[node_i].pre.clear();
	node[node_i].bck.clear();
	node[node_i].mp.clear();
	node[node_i].tag = 0;
	command temp(0, now, node_i++);
	cmd.push_back(temp);
}
void rm(string &str){
	if(!node[now].mp.count(str)){
		cout << "ERR\n";
		return;
	}
	cout << "OK\n";
	int temps = node[now].mp[str];
	node[now].mp.erase(str);
	update(now, -node[temps].sz);
	command temp(1, now, temps);
	cmd.push_back(temp);
}
void cd(string &str){
	if(str == ".."){
		if(now == 0)
			cout << "ERR\n";
		else{
			int tmpn = now;
			now = node[now].fa;
			cout << "OK\n";
			command temp(2, tmpn, now);
			cmd.push_back(temp);
		}
	}else{
		if(node[now].mp.count(str)){
			int tmpn = now;
			now = node[now].mp[str];
			cout << "OK\n";
			command temp(2, tmpn, now);
			cmd.push_back(temp);
		}else
			cout << "ERR\n";
	}
}
void ls(){
	int t = node[now].mp.size();
	if(t == 0)
		cout << "EMPTY\n";
	else if(t >= 1 && t <= 10)
		for(auto cur = node[now].mp.begin(); cur != node[now].mp.end(); cur++)
			cout << cur->first << endl;
	else{
		auto cur = node[now].mp.begin();
		for(int i = 0; i < 5; i++){
			cout << cur->first << endl;
			cur++;
		}
		cout << "...\n";
		cur = node[now].mp.end();
		for(int i = 0; i < 5; i++) cur--;
		for(int i = 0; i < 5; i++){
			cout << cur->first << endl;
			cur++;
		}
	}
}
void undo(){
	if(!cmd.size()){
		cout << "ERR\n";
		return;
	}
	cout << "OK\n";
	command c = cmd[cmd.size()-1];
	cmd.pop_back();
	switch(c.code){
	case 0:
		update(c.op1, -node[c.op2].sz);
		node[c.op1].mp.erase(node[c.op2].name);
		break;
	case 1:
		update(c.op1, node[c.op2].sz);
		node[c.op1].mp[node[c.op2].name] = c.op2;
	case 2:
		now = c.op1;
	}
}
void pretrack(int id, int& t){
	node[now].pre.push_back(node[id].name);
	if(t-- == 0) return;
	for(auto cur = node[id].mp.begin(); cur != node[id].mp.end(); cur++){
		pretrack(cur->second, t);
		if(t == 0) break;
	}
}
void pretrack(){
	int t;
	if(node[now].sz > 10) t = 5;
	else t = node[now].sz;
	pretrack(now, t);
}
void bcktrack(int id, int& t){
	auto cur = node[id].mp.end();
	int SIZE = node[id].mp.size();
	for(int i = 0; i < SIZE; i++){
		cur--;
		bcktrack(cur->second, t);
		if(t == 0) return;
	}
	node[now].bck.push_back(node[id].name);
	t--;
}
void pushdown(){
	node[now].pre.clear();
	node[now].bck.clear();
	pretrack();
	if(node[now].sz > 10) {
		int t = 5;
		bcktrack(now, t);
	}
	else node[now].bck = node[now].pre;
	node[now].tag = 1;
}
void tree(){
	if(!node[now].tag) pushdown();
	if(node[now].sz == 1) cout << "EMPTY\n";
	else if(node[now].sz > 1 && node[now].sz <= 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 << "...\n";
		for(int i = 4; i >= 0; i--) cout <<node[now].bck[i] << endl;
	}
}
int main(){
	int T;
	cin >> T;
	while(T--){
		cmd.clear();
		node_i = 1;
		now = 0;
		node[0].name = "root";
		node[0].fa = -1;
		node[0].sz = 1;
		node[0].tag = 0;
		node[0].pre.clear();
		node[0].bck.clear();
		node[0].mp.clear();
		int Q;
		cin >> Q;
		while(Q--){
			string cmmd;
			cin >> cmmd;
			switch(cases[cmmd]){
			case 0:{
				string str;
				cin >> str;
				mkdir(str);
				break;
			}
			case 1:{
				string str;
				cin >> str;
				rm(str);
				break;
			}
			case 2:{
				string str;
				cin >> str;
				cd(str);
				break;
			}
			case 3:{
				cout << node[now].sz << endl;
				break;
			}
			case 4:{
				ls();
				break;
			}
			case 5:{
				tree();
				break;
			}
			case 6:{
				undo();
				break;
			}
			}
		}
		cout << "\n";
	}
	return 0;
}

B - 东东学打牌

题意

最近，东东沉迷于打牌。所以他找到 HRZ、ZJM 等人和他一起打牌。由于人数众多，东东稍微修改了亿下游戏规则：

  • 所有扑克牌只按数字来算大小，忽略花色。
  • 每张扑克牌的大小由一个值表示。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。
  • 每个玩家抽得 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。请你告诉东东，全场人的排名

解题思路

一道操作较多但都比较简单的模拟题，和这道题较为类似。
首先读入每位玩家的姓名和牌，将牌转换成int数组存储，之后计算i张相同牌的数量为cnt[i]，并将牌面存入对应的cnt1[i]中，之后就能较为方便的判断牌属于哪个牌型。

代码

#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct player{
	string name;
	int card[6];
	int cnt[6];//cnt[i]表示有几个i张牌相同
	vector<int> cnt1[6];//cnt1[i]表示i张牌相同的牌面
	int point;
	void count(){
		memset(cnt, 0, sizeof(cnt));
		for(int i = 0; i < 6; i++)
			cnt1[i].clear();
		int last = card[0];
		int k = 1;
		for(int i = 1; i < 5; i++){
			if(card[i] == last)
				k++;
			else{
				cnt[k]++;
				cnt1[k].push_back(last);
				k = 1;
				last = card[i];
			}
		}
		cnt[k]++;
		cnt1[k].push_back(last);
	}
	void cal(){
		count();
		if(card[0] == 1 && card[1] == 10 && card[2] == 11 && card[3] == 12 && card[4] == 13)
			point = 8; 
		else if(card[1] == card[0] + 1 && card[2] == card[1] + 1 && card[3] == card[2] + 1 && card[4] == card[3] + 1)
			point = 7;
		else if(cnt[4] == 1)
			point = 6;
		else if(cnt[3] == 1 && cnt[2] == 1)
			point = 5;
		else if(cnt[3] == 1)
			point = 4;
		else if(cnt[2] == 2)
			point = 3;
		else if(cnt[2] == 1)
			point = 2;
		else 
			point = 1;
	}
}p[100005];
map<char, int>mp{{'K', 13}, {'Q', 12}, {'J', 11}, {'A', 1}, {'2', 2}, {'3', 3}, {'4', 4}, {'5', 5}, {'6', 6}, {'7', 7}, {'8', 8}, {'9', 9}};
bool cmp(player &a, player &b){
	if(a.point != b.point)
		return a.point > b.point;
	else{
		int sum1 = 0, sum2 = 0;
		for(int i = 0; i < a.cnt1[1].size(); i++){
			sum1 += a.cnt1[1][i];
			sum2 += b.cnt1[1][i];
		}
		if(a.point == 8)
			return a.name < b.name;
		else if(a.point == 7){
			if(a.card[2] != b.card[2])
				return a.card[2] > b.card[2];
			else
				return a.name < b.name;
		}else if(a.point == 6){
			if(a.card[2] != b.card[2])
				return a.card[1] > b.card[1];
			else if(a.cnt1[1][0] != b.cnt1[1][0])
				return a.cnt1[1][0] > b.cnt1[1][0];
			else
				return a.name < b.name;
		}
		else if(a.point == 5){
			if(a.card[2] != b.card[2])
				return a.card[2] > b.card[2];
			else{
				if(a.cnt1[2][0] != b.cnt1[2][0])
					return a.cnt1[2][0] > b.cnt1[2][0];
				else
					return a.name < b.name;	
			}
		}else if(a.point == 4){
			if(a.card[2] != b.card[2])
				return a.card[2] > b.card[2];
			else{
				if(sum1 != sum2)
					return sum1 > sum2;
				else
					return a.name < b.name;
			}
		}else if(a.point == 3){
			if(a.card[3] != b.card[3])
				return a.card[3] > b.card[3];
			else if(a.card[1] != b.card[1])
				return a.card[1] > b.card[1];
			else if(a.cnt1[1][0] != b.cnt1[1][0])
				return a.cnt1[1][0] > b.cnt1[1][0];
			else 
				return a.name < b.name;
		}else if(a.point == 2){
			if(a.cnt1[2][0] != b.cnt1[2][0])
				return a.cnt1[2][0] > b.cnt1[2][0];
			else if(sum1 != sum2)
				return sum1 > sum2;
			else 
				return a.name < b.name;
		}else{
			if(sum1 != sum2)
				return sum1 > sum2;
			else 
				return a.name < b.name;
		}
	}
}
int main()
{
	int n;
	while(cin >> n){
		for(int i = 0; i < n; i++){
			string str;
			cin >> p[i].name >> str;
			int k = 0;
			for(int j = 0; j < str.length(); j++){
				if(str[j] == '1'){
					p[i].card[k++] = 10;
					j++;
				}else
					p[i].card[k++] = mp[str[j]];
			}
			sort(p[i].card, p[i].card + 5);
			p[i].cal();
		}
		sort(p, p + n, cmp);
		for(int i = 0; i < n; i++)
			cout << p[i].name << endl;
	}
    return 0;
}

C - 签到题

题意

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

解题思路

  • 因为没有规定一个凳子能坐多少人，mx的值很容易想到，y个人全部都坐到原来人数最多的凳子上即可，所以我们在读入每个凳子上人数的时候比较记录最大值，最后 m x = y + m a x ( a i ) mx = y + max(a_i) mx=y+max(ai​)
  • mn的取值分为两种情况：
    1. 当 s u m ( a i ) + y ≤ x ⋅ m a x ( a i ) sum(a_i)+y \leq x \cdot max(a_i) sum(ai​)+y≤x⋅max(ai​)时，我们可以把y个人分配到人数最多的长凳之外的长凳上，如果优先从人数少的长凳开始分配，则最后人数最多的长凳上的人数依然为 m a x ( a i ) max(a_i) max(ai​).
    2. 当 s u m ( a i ) + y > x ⋅ m a x ( a i ) sum(a_i)+y > x \cdot max(a_i) sum(ai​)+y>x⋅max(ai​)时，我们将所有人平均分配到x个长凳上，平均值即为mn(这里要注意如果 s u m ( a i ) + y sum(a_i)+y sum(ai​)+y不能被x整除，得到的结果要+1)

代码

#include <iostream>
using namespace std;
int main()
{
    int x, y;
    cin >> x >> y;
    int maxx = 0;
    int sum = 0;
    for (int i = 0; i < x; i++) {
        int temp;
        cin >> temp;
        if (temp > maxx)
            maxx = temp;
        sum += temp;
    }
    if (sum + y > maxx * x) {
        if ((sum + y) % x == 0)
            cout << (sum + y) / x;
        else
            cout << (sum + y) / x + 1;
    } else
        cout << maxx;
    cout << ' ';
    cout << maxx + y;
    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

程序设计思维与实践 Week9 作业 的相关文章

随机推荐

  • 以太坊学习一：密码学

    密码学作为区块链最基础的的技术之一 xff0c 这些知识既包括对信息的转换 加解密 xff0c 以及校验过程 xff0c 也包括以太坊地址和交易Hash xff0c 交易信息RLP编码 基于椭圆曲线公私钥签名 区块Merkle树交易 Has

  • VMware安装Debian完成后启动黑屏仅有一个光标

    问题 xff1a vmware安装Debian完成 xff0c 启动时出现黑屏现象 xff0c 仅有一个光标 问题原因 xff1a 安装步骤有误 解决方案 重新安装镜像 xff0c 安装过程中记得 将GRUB 启动引导器安装至您的主驱动器

  • mybatis resultType为map 字段为null不返回

    框架 springboot框架 xff0c 分为两种情况 xff1a 一种情况为部分字段为null xff0c 一种情况是全部字段均为null 部分字段为null 返回的数据格式形如 这种情况下 xff0c 只会返回 post code p

  • mysql在update语句中使用分页查询limit [offset，] rows

    在update语句中 limit 前几条是没问题的 xff0c 形如下面的写法 span class token keyword update span temp dj purchase span class token keyword s

  • 认识常见中间件-redis(一)

    Redis 是一种基于内存的数据库 xff0c 对数据的读写操作都是在内存中完成 xff0c 因此读写速度非常快 xff0c 常用于缓存 xff0c 消息队列 分布式锁等场景 Redis 提供了多种数据类型来支持不同的业务场景 xff0c

  • 线程池源码分析

    ThreadPoolExecutor的参数解释 public class ThreadPoolExecutor extends AbstractExecutorService public ThreadPoolExecutor int co

  • Ubuntu 18.04开机报错无法启动

    在虚拟机中启动Ubuntu时 xff0c 显示类似如下界面 原因 xff1a 硬盘空间不足 xff0c 所以无法启动系统了 解决方案 xff1a 1 启动系统 xff0c 在该界面单击按键shift xff08 如果是虚拟机 xff0c 要

  • win10+Xming+VSCode接远程服务器使用图形化界面（GUI）

    Xming安装 官网下载 Download下载安装下载完毕 xff0c 点开安装包 xff0c 直接按默认设置一路点击next完成安装 进入Xming的安装文件夹 xff0c 默认是 C Program Files x86 Xming xf

  • Python 判断文件是否存在，存在则删除

    span class token comment filepath为文件路径 span span class token keyword import span os span class token comment 判断文件是否存在 sp

  • arm下QT环境搭建

    第一次接触QT xff0c 发现每个人搭建环境问题都不一样 xff0c 我把我的问题和步骤写下 xff0c 以供参考 xff01 1 选择环境 xff0c QT需要安装Xwindows环境的操作系统 xff0c 开始我使用操作系统是没有图形

  • 计算机网络-聊天室的设计与实现

    计算机网络实践 一 实践设计的目的和意义二 实践设计的内容和要求三 设计用设备仪器四 实践设计的相关技术五 项目设计与实践1 设计思路2 模块描述3 运行结果 六 结束语源码与详细过程 一 实践设计的目的和意义 在互联网如此发达的今天 xf

  • python-下载某短视频平台视频（高清无水印）

    python 下载某短视频平台音视频 xff08 高清无水印 xff09 前言1 获取视频 url2 发送请求3 数据解析4 本地保存5 完整代码 前言 1 Cookie中文名称为小型文本文件 xff0c 指某些网站为了辨别用户身份而储存在

  • Java中的Reflection（反射）、暴力反射

    文章目录 1 反射 Reflection 的概念1 1 反射的出现背景1 2 反射概述1 3 Java反射机制研究及应用1 4 反射相关的主要API1 5 反射的优缺点 2 Class类并获取Class实例2 1 理解Class2 1 1

  • JVM（类的加载与ClassLoader、双亲委派机制）

    文章目录 1 类的生命周期2 类的加载过程3 类加载器 xff08 classloader 3 1 类加载器的作用3 2 类加载器的分类 JDK8 3 3 双亲委派机制3 3 1 双亲委派机制优势 3 4 查看某个类的类加载器对象3 5 使

  • Java中的反射（通过反射获取类的结构、invoke方法、获取注解）

    文章目录 1 创建运行时类的对象2 获取运行时类的完整结构2 1 相关API2 2 获取所有的属性及相关细节2 3 获取所有的方法及相关细节2 4 获取其他结构 构造器 父类 接口 包 注解等 2 5 获取泛型父类信息2 6 获取内部类或外

  • JDK的版本迭代（JDK9 - JDK20）

    文章目录 1 发布特点2 名词解释Oracle JDK和Open JDKJEPLTS 3 各版本支持时间路线图4 各版本介绍jdk 9jdk 10jdk 11jdk 12jdk 13jdk 14jdk 15jdk 16jdk 17jdk 1

  • 如何对第三方相同请求进行筛选过滤

    文章目录 问题背景处理思路注意事项代码实现 问题背景 公司内部多个系统共用一套用户体系库 xff0c 对外 钉钉 我们是两个客户身份 这里是根据系统来的 xff0c 例如当第三方服务向我们发起用户同步请求 xff1a 是一个更新用户操作 x

  • 域控制器部署组策略，立即下发强制更新，显示“远程过程调用被取消”，错误代码 8007071a；以及RPC服务器不可用，800706ba【解决方案】

    域控制器部署组策略 xff0c 立即下发强制更新 xff0c 显示 远程过程调用被取消 xff0c 错误代码 8007071a 首先放一张故障截图 报错过程解决方法 首先放一张故障截图 报错过程 在公司的域环境 xff0c 通过域控制器设置

  • windows下通过远程桌面访问linux图形界面

    一 安装epel库 epel库安装之前无法使用yum install xrdp命令安装xrdp 命令 xff1a yum install epel span class token operator span release 之后会自动匹配

  • 程序设计思维与实践 Week9 作业

    A 咕咕东的目录管理器 题意 解题思路 首先我们要确定如何存储目录以及子目录 xff0c 因为题目要求子目录必须要保持字典序 xff0c 所以我们选用map来存储一个目录的所有子目录 MKDIR xff1a 直接在当前目录的map里插入新的

热门标签