程序设计思维与实践 Week9 作业 (3/4/数据班)

程序设计思维与实践 Week9 作业 (3/4/数据班)

A - 咕咕东的目录管理器

问题分析

比较复杂的模拟题,理解目录管理是树状结构,就可以利用树有关的数据结构和方法进行目录管理了。

#include<iostream>
#include<map>
#include<vector>
using namespace std;
struct dir{
	string name;
	map<string,dir*> children;
	dir *parent;
	int size;
	bool update;
	vector<string> tendes;
	dir(string na,dir *p)
	{
		size=1;
		name=na;
		parent=p;
	}
public:
	dir* getchild(string mu)
	{
		map<string,dir*>::iterator it=children.find(mu);
		if(it==children.end())
			return NULL;
		else
			return it->second;
	}
	dir* mkdir(string mu)
	{
		if(children.find(mu)!=children.end())
			return NULL;
		dir *te=new dir(mu,this);
		children[mu]=te;
		maintain(1);
		return te;
	}
	dir* rm(string mu)
	{
		map<string,dir*>::iterator it=children.find(mu);
		if(it==children.end())
			return NULL;
		maintain(-1*it->second->size);
		children.erase(it);
		return it->second;
	}
	dir* cd(string mu)
	{
		if(mu=="..")
			return this->parent;
		return getchild(mu);
	}
	bool addchild(dir *ch)
	{
		if(children.find(ch->name)!=children.end())
			return false;
		children[ch->name]=ch;	
		maintain(+ch->size);
		return true;
	}
	void maintain(int s)
	{
		update=true;
		size+=s;
		if(parent!=NULL)
			parent->maintain(s);
	}
	void sz()
	{
		cout<<size<<endl; 
	}
	void ls()
	{
		int ss=children.size();
		if(ss==0)
			cout<<"EMPTY"<<endl;
		else if(ss<=10)
		{
			map<string,dir*>::iterator it=children.begin();
			while(it!=children.end())
			{
				cout<<it->first<<endl;
				it++;
			}
		}
		else
		{
			map<string,dir*>::iterator it=children.begin();
			for(int i=0;i<5;i++,it++)
				cout<<it->first<<endl;
			cout<<"..."<<endl;
			it=children.end();
			for(int i=0;i<5;i++) it--;
			for(int i=0;i<5;i++,it++)
				cout<<it->first<<endl;
		}
	}
	void tree()
	{
		if(size==1) cout<<"EMPTY"<<endl;
		else if(size<=10)
		{
			if(update)
			{
				tendes.clear();
				treeall(&tendes);
				update=false;
			}
			for(int i=0;i<size;i++)
				cout<<tendes[i]<<endl;
		}
		else
		{
			if(update)
			{
				tendes.clear();
				treef(5,&tendes);
				treel(5,&tendes);
				update=false;
			}
			for(int i=0;i<5;i++)
				cout<<tendes[i]<<endl;
			cout<<"..."<<endl;
			for(int i=9;i>=5;i--)
				cout<<tendes[i]<<endl;
		}
	}
private:
	void treeall(vector<string> *v)
	{
		v->push_back(name);
		map<string,dir*>::iterator it=children.begin();
		while(it!=children.end())
		{
			it->second->treeall(v);
			it++;
		}
	}
	void treef(int n,vector<string> *v)
	{
		v->push_back(name);
		if(--n==0) return;
		int nn=children.size();
		map<string,dir*>::iterator it=children.begin();
		while(nn--)
		{
			int ss=it->second->size;
			if(ss>=n)
			{
				it->second->treef(n,v);
				return;
			}
			else
			{
				it->second->treef(ss,v);
				n-=ss; 
			}
			it++;
		}
	}
	void treel(int n,vector<string> *v)
	{
		int nn=children.size();
		map<string,dir*>::iterator it=children.end();
		while(nn--)
		{
			it--;
			int ss=it->second->size;
			if(ss>=n)
			{
				it->second->treel(n,v);
				return;
			}
			else
			{
				it->second->treel(ss,v);
				n-=ss;
			}
			
		}
		v->push_back(name);
	}
};
char ming[30];
struct com{
	string commands[7]={"MKDIR","RM","CD","SZ","LS","TREE","UNDO"};
	int type;
	string can;
	dir* tdir;
	com(string tem)
	{
		for(int i=0;i<7;i++)
		{
			if(commands[i]==tem){
				type=i;
				if(i<3){
					cin>>ming;
					can=ming;
				}
				return;
			}
		}
	}
	
};
void solve()
{
	int Q;
	cin>>Q;
	dir *now=new dir("root",NULL); 
	vector<com*> comlist;
	for(int i=0;i<Q;i++)
	{
		cin>>ming;
		com *c=new com(ming);
		if(c->type==0)
		{
			c->tdir=now->mkdir(c->can);
			if(c->tdir==NULL)
				cout<<"ERR"<<endl;
			else
			{
				cout<<"OK"<<endl; 
				comlist.push_back(c);
			}
		} 	
		else if(c->type==1)
		{
			c->tdir=now->rm(c->can);
			if(c->tdir==NULL)
				cout<<"ERR"<<endl;
			else
			{
				cout<<"OK"<<endl; 
				comlist.push_back(c);
			}
		}
		else if(c->type==2)
		{
			dir *te=now->cd(c->can);
			if(te==NULL)
				cout<<"ERR"<<endl;
			else
			{
				cout<<"OK"<<endl;
				c->tdir=now;
				now=te;
				comlist.push_back(c);	
			}
		}
			
		else if(c->type==3)
			now->sz();
		else if(c->type==4)
			now->ls();
		else if(c->type==5)
			now->tree();
		else if(c->type==6)
		{
			bool su=false;
			while(!su&&!comlist.empty())
			{
				c=comlist.back();
				comlist.pop_back();
				if(c->type==0)
				{
					dir *temp=now->rm(c->can);
					if(temp!=NULL) su=true;
				}
				else if(c->type==1)
					su=now->addchild(c->tdir);
				else if(c->type==2)
				{
					now=c->tdir;
					su=true;
				}
			}
			if(su) cout<<"OK"<<endl;
			else cout<<"ERR"<<endl;
		}  
	}
}
int main()
{
	int T;
	cin>>T;
	for(int i=0;i<T;i++)
	{
		solve();
	}
	return 0;
} 

B - 东东学打牌

问题分析

这是计蒜客上的原题

用结构体储存玩家的信息,包括名称和五张手牌(整型)。根据规则判断即可。

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

int n;
struct player
{
	string name;
	int pai[5];
};
player node[100100];
void solve(int pai[5],string s)
{
	int size=s.size();
	int index=0;
	for(int i=0; i<size; i++)
	{
		if(s[i]>='2'&&s[i]<='9')
			pai[index]=s[i]-'0';
		else if(s[i]=='1')
		{
			pai[index]=10;
			i++;
		}
		else if(s[i]=='A')	pai[index]=1;
		else if(s[i]=='J')	pai[index]=11;
		else if(s[i]=='Q')	pai[index]=12;
		else if(s[i]=='K')	pai[index]=13;
		index++;
	}
}
int value(int p[5],int a[3])
{	 
	if(p[0]==1&&p[1]==10&&p[2]==11&&p[3]==12&&p[4]==13)
		return 8;
	else if(p[0]==p[1]-1&&p[1]==p[2]-1&&p[2]==p[3]-1&&p[3]==p[4]-1)	
	{
		a[0]=p[4];
		return 7;
	}
	else if(p[0]==p[1]&&p[1]==p[2]&&p[2]==p[3])
	{
		a[0]=p[0],a[1]=p[4];
		return 6;
	}
	else if(p[1]==p[2]&&p[2]==p[3]&&p[3]==p[4])
	{
		a[0]=p[1],a[1]=p[0];
		return 6;
	}
	else if(p[0]==p[1]&&p[1]==p[2]&&p[3]==p[4])
	{
		a[0]=p[0],a[1]=p[3];
		return 5;
	}
	else if(p[0]==p[1]&&p[2]==p[3]&&p[3]==p[4])
	{
		a[0]=p[2],a[1]=p[0];
		return 5;
	}
	else if(p[0]==p[1]&&p[1]==p[2])
	{
		a[0]=p[0],a[1]=p[3]+p[4];
		return 4;
	}
	else if(p[1]==p[2]&&p[2]==p[3])
	{
		a[0]=p[1],a[1]=p[0]+p[4];
		return 4;
	}
	else if(p[2]==p[3]&&p[3]==p[4])
	{
		a[0]=p[2],a[1]=p[0]+p[1];
		return 4;
	}
	else if(p[0]==p[1]&&p[2]==p[3])
	{
		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])
	{
		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[1]==p[2]&&p[3]==p[4])
	{
		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])
	{
		a[0]=p[0],a[1]=p[2]+p[3]+p[4];
		return 2;
	}
	else if(p[1]==p[2])
	{
		a[0]=p[1],a[1]=p[0]+p[3]+p[4];
		return 2;
	}
	else if(p[2]==p[3])
	{
		a[0]=p[2],a[1]=p[0]+p[1]+p[4];
		return 2;
	}
	else if(p[3]==p[4])
	{
		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(player &p1,player &p2)
{
	int value1,value2,a1[3],a2[3];
	value1=value(p1.pai,a1);
	value2=value(p2.pai,a2);
	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)
		{
			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 p1.name>p2.name ? true :false;
	}
}
int main()
{
	while(cin>>n)
	{
		for(int i=0; i<n; i++)
		{
			string s1,s2;
			cin>>s1>>s2;
			node[i].name=s1;
			solve(node[i].pai,s2);
			sort(node[i].pai,node[i].pai+5);
		}
		sort(node,node+n,cmp);
		for(int i=n-1;i>=0;i--)
			cout<<node[i].name<<endl;
	}
	return 0;
}

C - 签到题,独立思考哈

问题分析

这个题很巧妙,我把注释都写在代码里面了,代码有点长,思路还是很清楚的。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;//椅子的数目 
	
	int p;//新来的人数 
	int mx,mn;
	scanf("%d%d",&n,&p);
	int* chair=new int[n];//每个椅子上的人数 
	fill(chair,chair+n,0);
	int tmp=0;
	int sum=0;
	for(int i=0;i<n;++i){
		scanf("%d",&chair[i]);
		sum+=chair[i]; 
		tmp=tmp>chair[i]?tmp:chair[i];//原来人数最多的椅子上的人数 
	}
	int rst=sum-n*tmp+p;//新来的人补齐差距后,还剩的人数 
	if(rst<=0){//能补齐 
		mn=tmp;//原来的最大值就是最大值的最小值 
	}
	else{//还有多余的人 
		if(rst%n==0){
			mn=tmp+rst/n;
		}
		else{
			mn=tmp+rst/n+1;
		}
	}
	mx=tmp+p;//最大值,就是全部坐在人最多的椅子上 
	printf("%d %d",mn,mx);
	delete[]chair;
	return 0;
}

原文地址:https://www.cnblogs.com/master-cn/p/12898881.html