week9——作业（模拟题练习）

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 - 咕咕东的目录管理器：

问题描述

题目简述

问题分析

解题思路

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变量也无法通过）。通过助教的讲解和自己实际写代码，我感觉，做这种模拟题时，在一开始的时候思路一定要明确。再往下写每一步的时候，都要考虑清楚什么是最优的解决方案，并及时完善和扩充原来的设计。我觉得，我的写代码的习惯还有待提高