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

week9——作业(模拟题练习)

程序员文章站 2024-03-17 21:30:22
...

C - 签到题 :

问题描述

题目简述

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

输入/输出格式

输入格式:
第一行包含一个整数 x (1 <= x <= 100) 表示公园中长椅的数目
第二行包含一个整数 y (1 <= y <= 1000) 表示有 y 个人来到公园
接下来 x 个整数 a_i (1<=a_i<=100),表示初始时公园长椅上坐着的人数
输出格式:
输出 mn 和 mx

样例

输入样例:
3
7
1
6
1
输出样例:
6 13

问题分析

解题思路

这个题的题意是:若干个长椅,每个长椅上预先有部分人。此时又有几个人来到公园,他们可以随便坐在这些椅子上,那么在这些人的不同的坐法中,其中的长椅上的最大人数的最大值和最小值是多少。思路是:最大值很好求,所有人都坐在原本人最多的长椅上即可。最小值的计算方法是:首先计算长椅上原来的人数总和和新加入人数的和。比较其与最大值*长椅数的大小。如果发现大,那么最大人数的最小值为原来的人数总和和新加入人数的和/长椅数向上取整。否则,最大人数仍然为原来的最大值。

参考代码
#include <iostream>

using namespace std;

int main()
{
	int max_num=0;
	int sum=0;
	int x,y;
	cin>>x>>y;
	for(int i=1;i<=x;i++)
	{
		int temp;
		cin>>temp;
		if(temp>max_num) max_num=temp;
		sum+=temp;
	}
	if(sum+y>max_num*x) 
	{
		if((sum+y)%x==0) cout<<(sum+y)/x<<" "<<max_num+y<<endl;
		else cout<<(sum+y)/x+1<<" "<<max_num+y<<endl;
	}
	else cout<<max_num<<" "<<max_num+y<<endl;
	return 0;
}

心得体会

这个题读题还是没读懂,一开始以为是原来的最大人数长椅上最多有多少人,最少有多少人,就一直WA。

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。请你告诉东东,全场人的排名

输入/输出格式

输入格式:
输入包含多组数据。每组输入开头一个整数 n (1 <= n <= 1e5),表明全场共多少人。
随后是 n 行,每行一个字符串 s1 和 s2 (1 <= |s1|,|s2| <= 10), s1 是对应人的名字,s2 是他手里的牌情况。
输出格式:
对于每组测试数据,输出 n 行,即这次全场人的排名。

样例

输入样例:
3
DongDong AAA109
ZJM 678910
Hrz 678910
输出样例:
Hrz
ZJM
DongDong

问题分析

解题思路

这个题是我在作业预览的时候提前写的。所以代码的组织根本没有考虑,闷着头直接写,导致main函数过长。言归正传,说思路。这个题应该是week6实验的一个变体。(详细信息)本质上也是判断牌型。但是这个题相较于上一个实验来说更加的复杂。因为涉及到一些字符串处理及排序的问题。所以,以下分三个方面介绍各问题的解决方法。1.字符串处理:其实不算太复杂,A,J,Q,K的处理直接去对应数据就可以。10的处理相对复杂一点,但是由于1是由A对应的,因此,1就成了10的输入标志,因此也不难。2.排序:题目中给出了明确的排序方案,这里不再赘述,综合来看,当牌的类型不同时直接可通过类型排序,相同时需要用到牌型的信息。进一步可以看到,第三种牌型使用的信息最多,有3个。2,4,5,6种都是两个,1,7只有一个。第8种直接比较了名字的字典序。由此可以确定存储的信息量及存储的信息类型。3.牌型判断及信息记录:这个也比较好办,首先记录5张牌是什么以及不同牌的数量及对应的张数,数量最多的牌的张数。并将牌按从大到小排序。这样足够判断这手牌属于什么牌型,再根据上述信息存储比较时所用信息即可。

参考代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

struct player
{
	string name;
	int tag;
	int msg[5];
	bool operator <(const player& p) const
	{
		if(tag==p.tag)
		{
			if(tag==1||tag==7)
			{
				if(msg[1]!=p.msg[1]) return msg[1]>p.msg[1];
				else return name<p.name;
			}
			else if(tag==2||tag==4||tag==5||tag==6)
			{
				if(msg[1]!=p.msg[1]) return msg[1]>p.msg[1];
				else if(msg[2]!=p.msg[2]) return msg[2]>p.msg[2];
				else return name<p.name;
			}
			else if(tag==3)
			{
				if(msg[1]!=p.msg[1]) return msg[1]>p.msg[1];
				else if(msg[2]!=p.msg[2]) return msg[2]>p.msg[2];
				else if(msg[3]!=p.msg[3]) return msg[3]>p.msg[3];
				else return name<p.name;
			}
			else if(tag==8)
			{
				return name<p.name;
			}
		}
		else return tag>p.tag;
	}
};

int n;
int card_num[14];
int max_card_num,diff_card_num,max_pos;
int cards[5];

int main()
{
	vector<player> v;
	scanf("%d",&n);
	v.clear();
	for(int i=1;i<=n;i++)
	{
		memset(card_num,0,sizeof(card_num));
		max_card_num=0;
		max_pos=0;
		diff_card_num=0;
		int count=0;
		player temp;
		string card;
		cin>>temp.name>>card;
		for(int j=0;j<card.length();)
		{
			if(card[j]=='1') 
			{
				card_num[10]++;
				j+=2;
				cards[count]=10;
				count++;
			}
			else if(card[j]=='2') 
			{
				card_num[2]++;
				j+=1;
				cards[count]=2;
				count++;
			}
			else if(card[j]=='3') 
			{
				card_num[3]++;
				j+=1;
				cards[count]=3;
				count++;
			}
			else if(card[j]=='4') 
			{
				card_num[4]++;
				j+=1;
				cards[count]=4;
				count++;
			}
			else if(card[j]=='5') 
			{
				card_num[5]++;
				j+=1;
				cards[count]=5;
				count++;
			}
			else if(card[j]=='6') 
			{
				card_num[6]++;
				j+=1;
				cards[count]=6;
				count++;
			}
			else if(card[j]=='7') 
			{
				card_num[7]++;
				j+=1;
				cards[count]=7;
				count++;
			}
			else if(card[j]=='8') 
			{
				card_num[8]++;
				j+=1;
				cards[count]=8;
				count++;
			}
			else if(card[j]=='9') 
			{
				card_num[9]++;
				j+=1;
				cards[count]=9;
				count++;
			}
			else if(card[j]=='A') 
			{
				card_num[1]++;
				j+=1;
				cards[count]=1;
				count++;
			}
			else if(card[j]=='J') 
			{
				card_num[11]++;
				j+=1;
				cards[count]=11;
				count++;
			}
			else if(card[j]=='Q') 
			{
				card_num[12]++;
				j+=1;
				cards[count]=12;
				count++;
			}
			else if(card[j]=='K') 
			{
				card_num[13]++;
				j+=1;
				cards[count]=13;
				count++;
			}
		}
		sort(cards,cards+5);
		/*for(int j=0;j<5;j++)
		{
			printf("%d ",cards[j]);
		}
		printf("\n");*/
		for(int j=1;j<=13;j++)
		{
			if(card_num[j]!=0)
			{
				if(card_num[j]>max_card_num) 
				{
					max_card_num=card_num[j];
					max_pos=j;
				}
				diff_card_num++;
			}
		}
		if(cards[0]==1&&cards[1]==10&&cards[2]==11&&cards[3]==12&&cards[4]==13)
		{
			temp.tag=8;
		}
		else if(cards[1]==cards[0]+1&&cards[2]==cards[0]+2&&cards[3]==cards[0]+3&&cards[4]==cards[0]+4)
		{
			temp.tag=7;
			temp.msg[1]=cards[4];
		}
		else if(max_card_num==4)
		{
			temp.tag=6;
			temp.msg[1]=max_pos;
			if(cards[0]!=max_pos) temp.msg[2]=cards[0];
			else temp.msg[2]=cards[4];
		}
		else if(max_card_num==3&&diff_card_num==2)
		{
			temp.tag=5;
			temp.msg[1]=max_pos;
			if(cards[0]!=max_pos) temp.msg[2]=cards[0];
			else temp.msg[2]=cards[4];
		}
		else if(max_card_num==3&&diff_card_num==3)
		{
			temp.tag=4;
			temp.msg[1]=max_pos;
			if(cards[0]==max_pos) temp.msg[2]=cards[3]+cards[4];
			else if(cards[1]==max_pos) temp.msg[2]=cards[0]+cards[4];
			else temp.msg[2]=cards[0]+cards[1];
		}
		else if(max_card_num==2&&diff_card_num==3)
		{
			temp.tag=3;
			if(cards[0]!=cards[1]) 
			{
				temp.msg[1]=cards[1];
				temp.msg[2]=cards[3];
				temp.msg[3]=cards[0];
			}
			else if(cards[3]!=cards[4])
			{
				temp.msg[1]=cards[0];
				temp.msg[2]=cards[2];
				temp.msg[3]=cards[4];
			}
			else
			{
				temp.msg[1]=cards[0];
				temp.msg[2]=cards[3];
				temp.msg[3]=cards[2];
			}
			if(temp.msg[1]<temp.msg[2])
			{
				int t=temp.msg[1];
				temp.msg[1]=temp.msg[2];
				temp.msg[2]=t;
			}
		}
		else if(max_card_num==2&&diff_card_num==4)
		{
			temp.tag=2;
			temp.msg[1]=max_pos;
			if(cards[0]==max_pos)
			{
				temp.msg[2]=cards[2]+cards[3]+cards[4];
			}
			else if(cards[1]==max_pos)
			{
				temp.msg[2]=cards[0]+cards[3]+cards[4];
			}
			else if(cards[2]==max_pos)
			{
				temp.msg[2]=cards[0]+cards[1]+cards[4];
			}
			else if(cards[3]==max_pos)
			{
				temp.msg[2]=cards[0]+cards[1]+cards[2];
			}
		}
		else 
		{
			temp.tag=1;
			temp.msg[1]=cards[0]+cards[1]+cards[2]+cards[3]+cards[4];
		}
		v.push_back(temp);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
	{
		cout<<v[i].name;
		if(i!=v.size()-1) cout<<endl;
	}
	return 0; 
}

心得体会

由于之前有做类似题的经验,所以这个题感觉做的还是很顺的,没有什么太大的障碍就解决了。

A - 咕咕东的目录管理器:

问题描述

题目简述

week9——作业(模拟题练习)

问题分析

解题思路

1.数据结构:题目上已经明确提示了,目录管理器就是维护一棵以根目录为根的树。很明显,这棵树的节点可能会有多个孩子,而且孩子的排列顺序是按照字典序从小向大排列的。那么在存储孩子节点的信息时,需要使用一种有序的结构,以便维护。因此可以使用vector或者是map存储,相较而言map本身即可维护有序性,且获取某一个孩子的时间复杂度较低,因此选择map作为存储孩子的数据结构。
2.命令:本题中要实现的命令共有7条,其中MKDIR,RM,CD要求可以UNDO。因此,在保存命令的时候需要保存命令的类型,同时对于上述三条命令还需要保存命令执行成功的目标。对于MKDIR和RM,需要保存的是新加入或者移除的节点信息,CD则需要保存原来的结点位置。将执行成功的指令存储在一个栈中,每次UNDO,取出栈顶的指令执行即可。
3.功能实现及对数据结构的扩充:
(1).SIZE要求返回当前结点的子树大小,最好的方法是在每个节点中存储子树的大小的信息。因此,在原来的数据结构中加入subtree变量,储存子树大小。同时在加入结点或者删除结点时,要维护从该结点到根结点路径上的结点的子树大小。因此,为了方便返回父节点,加入parent变量,存储当前结点父节点的指针。
(2).MKDIR在当前结点的孩子中,如果不存在与加入结点同名的结点,那么进行插入,并维护子树大小即可。否则插入失败。
(3).RM与MKDIR基本一致,但要注意的是,此删除只是将对应指针移除,并不真正删除结点的信息。
(4).CD。进入子节点或者返回父节点,进入子节点直接在孩子中寻找即可,返回父节点直接将当前位置改为对应节点的parent位置即可。
(5).LS。找当前结点的直接孩子。直接遍历当前结点的孩子结点即可。如果孩子数大于10,那么需要先遍历前五个,再遍历后五个。
(6).TREE。通过审题可以发现,该题目中,最多只能有5000条MKDIR或者RM指令,指令总数为1e5。因此,很有可能会出现以下几种情况:1.目录树非常大,此时不断增加结点数量,每增加一个询问TREE一次。2.目录树非常大,不增加结点,连续多次询问TREE。而输出时,子树大小小于10时,要求遍历,大于等于10时,要求输出前五个和后五个。因此,我们需要在子树大小大于等于10的时候进行前序和后序遍历。这样可以避免不必要的结点遍历。同时,针对多次询问的情况,可以为每一个结点增设一个是否被更新过的变量,同时将每个节点的10个孩子存储在每个节点中。这样,如果一个结点没有被更新过,它会自动输出以前查找的结果,不需要再进行遍历搜索。

参考代码
#include <bits/stdc++.h>

using namespace std;

string tmps;

struct dir
{
	string name;
	map<string,dir*> children;
	dir* parent;
	int subtreesize;
	vector<string> *tenchildren;
	bool updated;
	dir(string name,dir* parent)
	{
		this->name=name;
		this->parent=parent;
		this->subtreesize=1;
		tenchildren=new vector<string>;
	}
	dir* mkdir(string name)
	{
		if(children.find(name)!=children.end())
		    return nullptr;
		else
		{
			dir* new_dir=new dir(name,this);
			children[name]=new_dir;
			maintain(1);
			return new_dir;
		}
	}
	dir* rm(string name)
	{
	    auto it=children.find(name);
		if(it==children.end())
		    return nullptr;
		else
		{
			maintain(-1*it->second->subtreesize);
			children.erase(it);
			return it->second;
		}
	}
	dir* cd(string name)
	{
		if(name=="..")
		    return this->parent;
		else
		{
			return getchild(name);
		}
	}
	void sz()
	{
		printf("%d\n",this->subtreesize);
	}
	void ls()
	{
		int size=children.size();
		if(size==0) printf("EMPTY\n");
		else if(size<=10) 
		{
			for(auto &i:children) 
			    printf("%s\n",i.first.c_str());
		}
		else
		{
			auto it=children.begin();
			for(int i=0;i<5;i++,it++)
			    printf("%s\n",it->first.c_str());
			printf("...\n");
			it=children.end();
			for(int i=0;i<5;i++)
			    it--;
			for(int i=0;i<5;i++,it++)
			    printf("%s\n",it->first.c_str());
		}
	}
	void alltree(vector<string>* v)
	{
		//printf("in\n");
		v->push_back(name);
		for(auto &i:children)
		{
			i.second->alltree(v);
		}
	}
	void findfirst(int num,vector<string>* v)
	{
		v->push_back(name);
		if(--num==0) return;
		int n=children.size();
		auto it=children.begin();
		while(n--)
		{
			int temp=it->second->subtreesize;
			if(temp>=num)
			{
				it->second->findfirst(num,v);
				return ;
			}
			else
			{
				it->second->findfirst(num,v);
				num-=temp;
			}
			it++;
		}
	}
	void findlast(int num,vector<string>* v)
	{
		int n=children.size();
		auto it=children.end();
		while(n--)
		{
			it--;
			int temp=it->second->subtreesize;
			if(temp>=num)
			{
				it->second->findlast(num,v);
				return ;
			}
			else
			{
				it->second->findlast(num,v);
				num-=temp;
			}
		}
		v->push_back(name);
	}
	void tree()
	{
		//printf("subtreesize:%d\n",subtreesize);
		if(subtreesize==1) printf("EMPTY\n");
		else if(subtreesize<=10)
		{
			//printf("inn\n");
			if(this->updated==true)
			{
				tenchildren->clear();
				//printf("innn\n");
				alltree(tenchildren);
				this->updated=false;
			}
			for(int i=0;i<subtreesize;i++)
			{
				printf("%s\n",tenchildren->at(i).c_str());
			}
		}
		else
		{
			if(this->updated==true)
			{
				tenchildren->clear();
				findfirst(5,tenchildren);
				findlast(5,tenchildren);
				this->updated=false;
			}
			for(int i=0;i<5;i++)
			{
				printf("%s\n",tenchildren->at(i).c_str());
			}
			printf("...\n");
			for(int i=9;i>=5;i--)
			{
				printf("%s\n",tenchildren->at(i).c_str());
			}
		}
	}
	bool addchild(dir* d)
	{
		if(children.find(d->name)!=children.end())
	        return false;
	    else
	    {
	    	children[d->name]=d;
	    	maintain(d->subtreesize);
	    	return true;
		}
	}
	void maintain(int num)
	{
		updated=true;
		subtreesize+=num;
		if(parent!=nullptr)
		{
			parent->maintain(num);
		}
	}
	dir* getchild(string name)
	{
		if(children.find(name)==children.end())
		    return nullptr;
		else return children[name];
	}
};

struct command
{
	const string cmds[7]={"MKDIR","RM","CD","SZ","LS","TREE","UNDO"};
	int type;
	string arg;
	dir* tmpDir;
	command(string s)
	{
		for(int i=0;i<7;i++)
		{
			if(cmds[i]==s)
			{
				type=i;
				if(i<3) cin>>tmps;
				arg=tmps;
				return ;
			}
		}
	}
};

stack<command*> cmdlist;

void solve()
{
	while(!cmdlist.empty())
	{
		cmdlist.pop();
	}
	int n;
	cin>>n;
	dir* now=new dir("root",nullptr);
	for(int i=1;i<=n;i++)
	{
		cin>>tmps;
		command* cmd=new command(tmps);
		switch(cmd->type)
		{
			case 0:
				{
					cmd->tmpDir=now->mkdir(cmd->arg);
					if(cmd->tmpDir==nullptr) printf("ERR\n");
					else
					{
						printf("OK\n");
						cmdlist.push(cmd);
					}
				}break;
			case 1:
				{
					cmd->tmpDir=now->rm(cmd->arg);
					if(cmd->tmpDir==nullptr) printf("ERR\n");
					else
					{
						printf("OK\n");
						cmdlist.push(cmd);
					}
				}break;
			case 2:
				{
					dir* ch=now->cd(cmd->arg);
					if(ch==nullptr) printf("ERR\n");
					else
					{
						printf("OK\n");
						cmd->tmpDir=now;
						now=ch;
						cmdlist.push(cmd);
					}
				}break;
			case 3:
				{
					now->sz();
				}break;
		    case 4:
		    	{
		    		now->ls();
				}break;
			case 5:
				{
					now->tree();
				}break;
			case 6:
				{
					bool success=false;
					if(!success&&!cmdlist.empty())
					{
						cmd=cmdlist.top();
						cmdlist.pop();
						switch(cmd->type)
						{
							case 0:
								{
									if(now->rm(cmd->arg)!=nullptr)
									{
										success=true;
									}
								}break;
							case 1:
								{
									success=now->addchild(cmd->tmpDir);
								}break;
							case 2:
								{
									now=cmd->tmpDir;
									success=true;
								}break;
						}
					}
					printf(success?"OK\n":"ERR\n");
				}
		}
	}
}

int main()
{
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		solve();
		if(i!=t) printf("\n");
	}
	return 0;
}

心得体会

这次的代码其实很大程度上参考了上课时助教的思路。我自己也在作业预览的时候做了这个题。但是很不幸TLE。我的代码中使用的是向量存储孩子的信息,而且最主要的是在TREE的时候是从前遍历到最后,取前五个和最后五个输出。这样导致了TREE的耗时很大(即使加了update变量也无法通过)。通过助教的讲解和自己实际写代码,我感觉,做这种模拟题时,在一开始的时候思路一定要明确。再往下写每一步的时候,都要考虑清楚什么是最优的解决方案,并及时完善和扩充原来的设计。我觉得,我的写代码的习惯还有待提高