目录管理器
题目：
咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！
初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。
现在咕咕东可以在命令行下执行以下表格中描述的命令：
命令 类型 实现 说明
MKDIR s 操作 在当前目录下创建一个子目录 s，s 是一个字符串 创建成功输出 “OK”；若当前目录下已有该子目录则输出 “ERR”
RM s 操作 在当前目录下删除子目录 s，s 是一个字符串 删除成功输出 “OK”；若当前目录下该子目录不存在则输出 “ERR”
CD s 操作 进入一个子目录 s，s 是一个字符串（执行后，当前目录可能会改变） 进入成功输出 “OK”；若当前目录下该子目录不存在则输出 “ERR”
特殊地，若 s 等于 “…” 则表示返回上级目录，同理，返回成功输出 “OK”，返回失败（当前目录已是根目录没有上级目录）则输出 “ERR”
SZ 询问 输出当前目录的大小 也即输出 1+当前目录的子目录数
LS 询问 输出多行表示当前目录的 “直接子目录” 名 若没有子目录，则输出 “EMPTY”；若子目录数属于 [1,10] 则全部输出；若子目录数大于 10，则输出前 5 个，再输出一行 “…”，输出后 5 个。
TREE 询问 输出多行表示以当前目录为根的子树的前序遍历结果 若没有后代目录，则输出 “EMPTY”；若后代目录数+1（当前目录）属于 [1,10] 则全部输出；若后代目录数+1（当前目录）大于 10，则输出前 5 个，再输出一行 “…”，输出后 5 个。若目录结构如上图，当前目录为 “root” 执行结果如下，
UNDO 特殊 撤销操作 撤销最近一个 “成功执行” 的操作（即MKDIR或RM或CD）的影响，撤销成功输出 “OK” 失败或者没有操作用于撤销则输出 “ERR”
输入
输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 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
思路：
根据题意将题目一步一步的进行分解，明白每个函数需要的值，返回的值，以及其所实现的作用。
首先，我们知道需要读入7中操作，而其中3中操作是需要加入另外一个字符串作为函数的参数值，故我们对于每个命令，定义一个command结构体，其中包括这7种命令，并且用type将其数字化，便于后面的判断。
同时，定义一个目录directory结构体，因为每次操作的对象（除undo外）都是目录，各种操作的实现过程可以在目录结构体中实现，而目录相当于一颗树结构，故加入parent以及children节点，因为parent有且只有一个，故无需查找，但child有多个，故可以利用map函数进行查找，复杂度为log级别，并且在tree操作时能够自行内部排序。
然后对于各种操作来说，如mkdir，我们需要维护新目录的父节点以及祖宗节点，将其大小进行变化，然后引入update
（为后面懒更新做准备），这些父节点都需要置updated为true，然后我们需要一个返回值，返回新创造的目录，然后存入一个vector 数组中，等到undo的时候，就取出数组中的最后一个节点，进行undo，然后为了方便起见，我们mkdir是返回，新增的目录，undo就只需要将新增的目录rm即可。同理rm返回删去的目录，undo时mkdir这个目录。但成都返回的是原来的目录，即未操作之前的目录，undo就只需进入目录即可。
对于tree操作，不进行记忆化，会超时，故用到上面的updated，然后按照前序遍历或者有必要时进行的后序遍历，将其输出即可。
代码：
#include<bits/stdc++.h>
using namespace std;
char tmps[20];
struct directory;
struct command
{
const string CMDNAMES[7]={"MKDIR","RM","CD","SZ","LS","TREE","UNDO"};
int type;
string arg;
command(string s)
{
for(int i=0;i<7;i++)
{
if(CMDNAMES[i]==s)
{
type=i;
if(i<3)
{
scanf("%s",tmps);
arg=tmps;
}
return;
}
}
}
directory* tmpDir;
};
struct directory{
string name;
map<string,directory*> children;
directory* parent;
int subtreesize;
vector<string> tendescendants;
bool updated;
directory(string name,directory* parent){
this->name=name;
this->parent=parent;
this->subtreesize=1;
}
public:
directory* getchild(string name)
{
auto it=children.find(name);
if(it==children.end())
return nullptr;
return it->second;
}
directory* mkdir(string name)
{
if(children.find(name)!=children.end())
return nullptr;
directory* ch=new directory(name,this);
children[name]=ch;
maintain(+1);
return ch;
}
directory* rm(string name)
{
auto it=children.find(name);
if(it==children.end())
return nullptr;
maintain(-1*it->second->subtreesize);
children.erase(it);
return it->second;
}
directory* cd(string name)
{
if(".."==name)
return this->parent;
return getchild(name);
}
void sz()
{
printf("%d\n",this->subtreesize);
}
void ls()
{
int sz=children.size();
if(sz==0) printf("EMPTY\n");
else if(sz<=10) for(auto &entry:children) printf("%s\n",entry.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 tree()
{
if(subtreesize==1) printf("EMPTY\n");
else if(subtreesize<=10){
if(this->updated){
tendescendants.clear();
treeall(tendescendants);
this->updated=false;
}
for(int i=0;i<subtreesize;i++) printf("%s\n",tendescendants.at(i).c_str());
}else{
if(this->updated){
tendescendants.clear();
treefirstsome(5,tendescendants);
treelastsome(5,tendescendants);
this->updated=false;
}
for(int i=0;i<5;i++) printf("%s\n",tendescendants.at(i).c_str());
printf("...\n");
for(int i=9;i>=5;i--) printf("%s\n",tendescendants.at(i).c_str());
}
}
bool addchild(directory* ch)
{
if(children.find(ch->name)!=children.end())
return false;
children[ch->name]=ch;
maintain(+ch->subtreesize);
return true;
}
void maintain(int delta)
{
updated=true;
subtreesize+=delta;
if(parent!=nullptr)
parent->maintain(delta);
}
private:
void treeall(vector<string>& bar)
{
bar.push_back(name);
for(auto &entry:children)
entry.second->treeall(bar);
}
void treefirstsome(int num,vector<string>& bar)
{
bar.push_back(name);
if(--num==0) return;
int n=children.size();
auto it=children.begin();
while(n--)
{
int sts=it->second->subtreesize;
if(sts>=num){
it->second->treefirstsome(num,bar);
return;
}
else{
it->second->treefirstsome(sts,bar);
num-=sts;
}
it++;
}
}
void treelastsome(int num,vector<string>& bar)
{
int n=children.size();
auto it=children.end();
while(n--)
{
it--;
int sts=it->second->subtreesize;
if(sts>=num)
{
it->second->treelastsome(num,bar);
return;
}else{
it->second->treelastsome(sts,bar);
num-=sts;
}
}
bar.push_back(name);
}
};
void solve()
{
int n;cin >>n;
directory* now=new directory("root",nullptr);
vector<command*> cmdlist;
while(n--)
{
scanf("%s",tmps);
command* cmd=new command(tmps);
switch(cmd->type){
case 0:case 1:
cmd->tmpDir=(cmd->type==0?now->mkdir(cmd->arg):now->rm(cmd->arg));
if(cmd->tmpDir==nullptr) printf("ERR\n");
else{
printf("OK\n");
cmdlist.push_back(cmd);
}
break;
case 2:
{
directory* ch=now->cd(cmd->arg);
if(ch==nullptr) printf("ERR\n");
else{
printf("OK\n");
cmd->tmpDir=now;
now=ch;
cmdlist.push_back(cmd);
}
}
break;
case 3:
now->sz();break;
case 4:
now->ls();break;
case 5:
now->tree();break;
case 6:
{
bool success=false;
while(!success&&!cmdlist.empty())
{
cmd=cmdlist.back();cmdlist.pop_back();
switch(cmd->type)
{
case 0:success=now->rm(cmd->tmpDir->name)!=nullptr;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;
while(t--)
{
solve();
}
return 0;
}
打牌
题目：
最近，东东沉迷于打牌。所以他找到 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 张牌不同，其值不同。下面依次列举了这手牌的形成规则：
大牌：这手牌不符合下面任一个形成规则。如果 α 和 β 都是大牌，那么定义它们的大小为组成这手牌的 5 张牌的大小总和。
对子：5 张牌中有 2 张牌的值相等。如果 α 和 β 都是对子，比较这个 “对子” 的大小，如果 α 和 β 的 “对子” 大小相等，那么比较剩下 3 张牌的总和。
两对：5 张牌中有两个不同的对子。如果 α 和 β 都是两对，先比较双方较大的那个对子，如果相等，再比较双方较小的那个对子，如果还相等，只能比较 5 张牌中的最后那张牌组不成对子的牌。
三个：5 张牌中有 3 张牌的值相等。如果 α 和 β 都是 “三个”，比较这个 “三个” 的大小，如果 α 和 β 的 “三个” 大小相等，那么比较剩下 2 张牌的总和。
三带二：5 张牌中有 3 张牌的值相等，另外 2 张牌值也相等。如果 α 和 β 都是 “三带二”，先比较它们的 “三个” 的大小，如果相等，再比较 “对子” 的大小。
炸弹：5 张牌中有 4 张牌的值相等。如果 α 和 β 都是 “炸弹”，比较 “炸弹” 的大小，如果相等，比较剩下那张牌的大小。
顺子：5 张牌中形成 x, x+1, x+2, x+3, x+4。如果 α 和 β 都是 “顺子”，直接比较两个顺子的最大值。
龙顺：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
思路：
首先我们得到的值为名字以及牌型，按照要求，先比较牌型大小，若牌型大小相等，的比较名字。
首先定义per结构体，里面包括每个人的名字，牌，以及牌转化为数字的数组。
然后利用一个vector 数组将数字存进去，若数字相同，则只存一个，然后考虑牌型，若为龙顺子，直接返回最大，然后依次从大牌到小牌进行判断，先排序，然后顺子只需遍历一次即可判断出来，然后对vector 数组内部的元素个数分类讨论，若只有2个，则炸弹或者三代二，3个则为3个加单以及两对，4个即为一对，5个即为散牌。
然后将牌的大小按照数字进行return，要保证两副牌的大小关系的正确性。
然后对名字进行判断，每个字母进行比较，若比较完都相同，则输出短的。
最终利用这样的关系cmp，进行sort即可。
代码：
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
struct per
{
char name[11];
char pai[11];
int pa[11];
}pe[100010];
int n,vis[20];
vector<int> s;
void clear()
{
memset(pe,0,sizeof(pe));
s.clear();
}
int cmpname(char n1[],char n2[])
{
int x=min(strlen(n1),strlen(n2));
for(int i=0;i<x;i++)
{
if(n1[i]<n2[i])
return 1;
if(n1[i]>n2[i])
return 0;
}
if(strlen(n1)<=strlen(n2))
return 1;
else
return 0;
}
int change(char c)
{
if(c>='2'&&c<='9')
return c-'0';
if(c=='A')
return 1;
if(c=='1')
return 10;
if(c=='J')
return 11;
if(c=='Q')
return 12;
if(c=='K')
return 13;
}
int get(int p[])
{
if(s.size()==2)
return 5;
if(s.size()==3)
return 3;
if(s.size()==4)
return 2;
if(s.size()==5)
return 1;
}
int find(int p[])
{
sort(p,p+5);
s.clear();
memset(vis,0,sizeof(vis));
for(int i=0;i<5;i++)
{
if(!vis[p[i]])
{
s.push_back(p[i]);
vis[p[i]]=1;
}
}
if(p[0]==1&&p[1]==10&&p[2]==11&&p[3]==12&&p[4]==13)
return 800000;
int flag=0;
for(int i=0;i<4;i++)
{
if(p[i+1]-p[i]!=1)
flag=1;
}
if(!flag)
return 700000+p[4];
flag=0;
if(get(p)==5)
{
for(int i=0;i<5;i++)
{
if(p[i]==s[0])
flag++;
}
if(flag==4)
return 600000+s[0]*100+s[1];
if(flag==1)
return 600000+s[0]+s[1]*100;
if(flag==2)
return 500000+s[0]+s[1]*100;
if(flag==3)
return 500000+s[0]*100+s[1];
}
flag=0;
int flagg=0;
int f=0;
if(get(p)==3)
{
for(int i=0;i<5;i++)
{
if(p[i]==s[0])
flag++;
if(p[i]==s[1])
flagg++;
}
if(flag+flagg==2)
return s[0]+s[1]+400000+s[2]*100;
else if(flag+flagg==3)
{
if(flag==2)
return 300000+s[2]*1000+s[0]*50+s[1];
else
return 300000+s[2]*1000+s[1]*50+s[0];
}
else if(flag+flagg==4)
{
if(flag==2)
f=3;
else
f=4;
}
if(f==3)
{
if(s[0]>s[1])
return 300000+s[0]*1000+s[1]*50+s[2];
else
return 300000+s[1]*1000+s[0]*50+s[2];
}
if(f==4)
{
if(flag==3)
return 400000+s[1]+s[2]+s[0]*100;
if(flag==1)
return 400000+s[1]*100+s[2]+s[0];
}
}
int a1=0,a2=0,a3=0;
if(get(p)==2)
{
for(int i=0;i<5;i++)
{
if(p[i]==s[0])
a1++;
if(p[i]==s[1])
a2++;
if(p[i]==s[2])
a3++;
}
if(a1+a2+a3==3)
return 200000+s[3]*100+s[0]+s[1]+s[2];
if(a1+a2+a3==4)
{
if(a1==2)
return 200000+s[0]*100+s[1]+s[2]+s[3];
if(a2==2)
return 200000+s[1]*100+s[0]+s[2]+s[3];
if(a3==2)
return 200000+s[2]*100+s[0]+s[1]+s[3];
}
}
f=0;
if(get(p)==1)
{
for(int i=0;i<5;i++)
{
f+=p[i];
}
return f;
}
}
int cmppai(per p1,per p2)
{
if(find(p1.pa)==find(p2.pa))
return cmpname(p1.name,p2.name);
else
return find(p1.pa)>find(p2.pa);
}
void solve()
{
for(int i=1;i<=n;i++)
{
int j=0;
for(int w=0;w<5;w++)
{
pe[i].pa[w]=change(pe[i].pai[j]);
if(pe[i].pai[j]=='1')
j++;
j++;
}
}
sort(pe+1,pe+n+1,cmppai);
for(int i=1;i<=n;i++)
{
printf("%s\n",pe[i].name);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
clear();
for(int i=1;i<=n;i++)
{
scanf("%s",&pe[i].name);
scanf("%s",&pe[i].pai);
}
solve();
}
}
长椅
题目：
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
样例解释
最初三张椅子的人数分别为 1 6 1
接下来来了7个人。
可能出现的情况为{1 6 8},{1,7,7},…,{8,6,1}
相对应的k分别为8,7,…,8
其中，状态{1,13,1}的k = 13，为mx
状态{4,6,5}和状态{5,6,4}的k = 6，为mn
思路：
人照着人最少的椅子坐，最终的到的结果即为最小值，新来的人全部做到人最多的椅子上，取最大值。
最小值是分类讨论，如果作完后，人数没有原来的最多人多，则输出原来的值，如果多于，则输出最多的。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int a[110];
int x,y;
int main()
{
cin >> x >> y;
for(int i=1;i<=x;i++)
{
cin >> a[i];
}
sort(a+1,a+x+1);
int sum=0;
for(int i=1;i<=x;i++)
{
sum+=a[i];
}
if(sum+y<=x*a[x])
cout << a[x] << " ";
else
cout << (sum+y-1)/x+1 << " ";
cout << a[x]+y;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
