第九周作业
A - 咕咕东的目录管理器
问题描述
建造一个目录管理器，初始时硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。然后依次实现下列操作：
输出与输入
Input
输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 T （T <= 20）；
每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q （Q <= 1e5）；
每组测试数据的 2 ~ Q+1 行为具体的操作 （MKDIR、RM 操作总数不超过 5000）；
面对数据范围你要思考的是他们代表的 “命令” 执行的最大可接受复杂度，只有这样你才能知道你需要设计的是怎样复杂度的系统。
Output
每组测试数据的输出结果间需要输出一行空行。注意大小写敏感。
限制：
Time limit 6000 ms
Memory limit 1048576 kB
Example
input
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
output
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
解题思路
定于文件树的节点类dir
对于孩子节点的存储：
使用map<string,dir*>来存孩子节点，可以在O(logn)的复杂度内找到孩子节点。
使用vector< int > cmlist记录旧的操作命令
使用cmd[size]记录操作命令池，提高一点效率。
MKDIR s, 创建子目录操作：因为map可以按照key也就是string就行排序，那么直接向children数组中插入名字为s的目录即可，如果已存在同名子目录返回空指针。
RM s, 删除子目录操作：与插入操作基本一致，就是改为如果不存在目录名为s的子目录返回空指针。
CD s, 进入子目录操作：具体操作较为简单，就是要为撤销做准备，如果执行成功就将当前的目录存储到对应的cmlist数组中，然后再更新当前目录。
以上MKDIR,RM,CD都有UNDO操作，因此要记录下执行的这三种命令。
对于MKDIR，使用RM实现撤销
对于RM，使用addchild函数实现撤销，撤销操作时将dir*记录下来，可以比较方便的实现添加
对于CD，撤销时直接从cmlist数组取出对应的目录，然后更新now即可。
对于LS和SZ操作，实现比较简单。只要在MKDIR、RM、UNDO时维护一下子节点的数目即可。
TREE操作最复杂，分析TREE的复杂度，可以发现重复遍历的复杂度过大，而更新的次数反而比较少，引入一个懒更新，避免重复遍历（否则会超时），为此需要引入一个bool类型的updated来记录当前的目录是否已经遍历过以及一个vector< string>* tenDescendants来保存当前目录的十个后代。
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int Size = 1e5 + 10;
const string op[] = {"MKDIR", "RM", "CD", "SZ", "LS", "TREE", "UNDO"};
int cnt;
bool ff;
vector<int> cmdlist;
string tt;
class dir
{
public:
string name;
dir *parent;
int treesz;
vector<string> tenD;
bool update;
map<string, dir *> children;
dir(string name, dir *pp);
void maintain(int num);
dir *mkdir(string s);
dir *rm(string s);
dir *cd(string s);
void sz();
void ls();
void treeAll(vector<string> &bar);
void treef(int num, vector<string> &bar);
void treel(int num, vector<string> &bar);
bool addchild(dir *ch);
void tree();
};
dir::dir(string name, dir *pp)
{
this->name = name;
treesz = 1;
parent = pp;
}
void dir::maintain(int num)
{
this->update = true;
treesz += num;
if (parent != NULL)
parent->maintain(num);
}
dir *dir::mkdir(string s)
{
if (children.find(s) != children.end())
return NULL;
dir *newdir = new dir(s, this);
children[s] = newdir;
maintain(1);
return newdir;
}
dir *dir::rm(string s)
{
auto it = children.find(s);
if (it == children.end())
return NULL;
maintain(-1 * it->second->treesz);
dir *temp = it->second;
children.erase(it);
return temp;
}
dir *dir::cd(string s)
{
if (s == "..")
{
return parent;
}
else
{
map<string, dir *>::iterator it = children.find(s);
if (it == children.end())
return NULL;
else
return it->second;
}
}
void dir::sz()
{
printf("%d\n", treesz);
}
void dir::ls()
{
int sizeofch = children.size();
if (sizeofch == 0)
printf("EMPTY\n");
else if (sizeofch <= 10)
{
for (auto it = children.begin(); it != children.end(); it++)
{
cout << it->first << endl;
}
}
else
{
auto 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 dir::treeAll(vector<string> &bar)
{
bar.push_back(name);
for (auto it = children.begin(); it != children.end(); it++)
it->second->treeAll(bar);
}
void dir::treef(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->treesz;
if (sts >= num)
{
it->second->treef(num, bar);
return;
}
else
{
it->second->treef(sts, bar);
num -= sts;
}
it++;
}
}
void dir::treel(int num, vector<string> &bar)
{
int n = children.size();
auto it = children.end();
while (n--)
{
it--;
int sts = it->second->treesz;
if (sts >= num)
{
it->second->treel(num, bar);
return;
}
else
{
it->second->treel(sts, bar);
num -= sts;
}
}
bar.push_back(name);
}
void dir::tree()
{
if (treesz == 1)
printf("EMPTY\n");
else if (treesz <= 10)
{
if (update)
{
tenD.clear();
treeAll(tenD);
update = false;
}
for (auto it = tenD.begin(); it != tenD.end(); it++)
{
cout << *it << endl;
}
}
else
{
if (update)
{
tenD.clear();
treef(5, tenD);
treel(5, tenD);
update = false;
}
for (int i = 0; i < 5; i++)
cout << tenD[i] << endl;
cout << "..." << endl;
for (int i = 9; i >= 5; i--)
cout << tenD[i] << endl;
}
}
bool dir::addchild(dir *ch)
{
if (children.find(ch->name) != children.end())
{
return false;
}
children[ch->name] = ch;
maintain(ch->treesz);
return true;
}
struct Command
{
int type;
string arg;
dir *oldcmd;
void ini(string temp)
{
for (int i = 0; i < 7; i++)
{
if (temp == op[i])
{
type = i;
break;
}
}
if (type < 3)
{
cin >> arg;
}
return;
}
} Com[Size];
void solve()
{
dir *now = new dir("root", NULL);
int n;
cin >> n;
while (n--)
{
cin >> tt;
Com[++cnt].ini(tt);
switch (Com[cnt].type)
{
case 0:
Com[cnt].oldcmd = now->mkdir(Com[cnt].arg);
if (Com[cnt].oldcmd == NULL)
printf("ERR\n");
else
printf("OK\n"), cmdlist.push_back(cnt);
break;
case 1:
Com[cnt].oldcmd = now->rm(Com[cnt].arg);
if (Com[cnt].oldcmd == NULL)
{
printf("ERR\n");
}
else
{
printf("OK\n");
cmdlist.push_back(cnt);
}
break;
case 2:
{
dir *ch = now->cd(Com[cnt].arg);
if (ch == NULL)
printf("ERR\n");
else
{
printf("OK\n");
Com[cnt].oldcmd = now;
now = ch;
cmdlist.push_back(cnt);
}
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())
{
int n = cmdlist.back();
cmdlist.pop_back();
switch (Com[n].type)
{
case 0:
success = (now->rm(Com[n].arg) != NULL);
break;
case 1:
success = now->addchild(Com[n].oldcmd);
break;
case 2:
now = Com[n].oldcmd;
success = true;
break;
}
}
if (success)
printf("OK\n");
else
printf("ERR\n");
break;
}
}
}
}
int main()
{
int nu;
cin >> nu;
while (nu--)
{
if (ff)
cout << endl;
else
ff = 1;
cnt = -1;
cmdlist.clear();
solve();
}
return 0;
}
TB - 东东学打牌
问题描述
所有扑克牌只按数字来算大小，忽略花色。
每张扑克牌的大小由一个值表示。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。
根据这个输出这些玩家的排名。如果两个选手的牌相等，那么人名字典序小的排在前面。
输入包含多组数据。每组输入开头一个整数 n (1 <= n <= 1e5)，表明全场共多少人。
随后是 n 行，每行一个字符串 s1 和 s2 （1 <= |s1|,|s2| <= 10）， s1 是对应人的名字，s2 是他手里的牌情况。
思路
本题与原来的实现很相似。
根据输入读入字符后，将字符转换为int型存入。
对于每个牌型，首先进行排序，排序之后可以方便的判断牌型，然后按照优先级进行牌型判断即可。
对于相同牌型的大小比较，使用score记录一下。
代码
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
struct pa
{
string name;
int p[5];
int type;
int score;
void reset();
void set();
bool do7()
{
for (int i = 1; i < 4; i++)
{
if (p[i] != p[i + 1] - 1)
{
return false;
}
}
return true;
}
};
bool compare(const pa &a, const pa &b)
{
if (a.type == b.type)
{
if (a.score == b.score)
{
return (a.name < b.name);
}
return (a.score > b.score);
}
return (a.type > b.type);
}
void pa::reset()
{
cin >> name;
char c;
scanf("%c", &c);
for (int i = 0; i < 5; i++)
{
scanf("%c", &c);
if (c >= '2' && c <= '9')
{
p[i] = c - '0';
}
else if (c == 'K')
{
p[i] = 13;
}
else if (c == 'Q')
{
p[i] = 12;
}
else if (c == 'J')
{
p[i] = 11;
}
else if (c == 'A')
{
p[i] = 1;
}
else if (c == '1')
{
scanf("%c", &c);
p[i] = 10;
}
}
sort(p, p + 5);
}
void pa::set()
{
bool ff = do7();
if (ff && p[1] == 10 && p[0] == 1) //龙顺
{
type = 8;
}
else if (ff && p[0] + 1 == p[1]) //顺子
{
type = 7;
score = p[0];
}
else if (p[0] == p[3]) //炸弹
{
type = 6;
score = p[0] * 14 + p[4];
}
else if (p[1] == p[4]) //炸弹
{
type = 6;
score = p[4] * 14 + p[0];
}
else if (p[0] == p[2] && p[3] == p[4]) //三代二
{
type = 5;
score = p[0] * 14 + p[3];
}
else if (p[0] == p[1] && p[2] == p[4]) //三代二
{
type = 5;
score = p[3] * 14 + p[0];
}
else if (p[0] == p[2]) //三个
{
type = 4;
score = p[0] * 100 + p[3] + p[4];
}
else if (p[1] == p[3])
{
type = 4;
score = p[1] * 100 + p[0] + p[4];
}
else if (p[2] == p[4])
{
type = 4;
score = p[2] * 100 + p[1] + p[0];
}
else if (p[0] == p[1] && p[2] == p[3]) //两对
{
type = 3;
score = p[3] * 100 * 100 + p[1] * 100 + p[4];
}
else if (p[0] == p[1] && p[3] == p[4])
{
type = 3;
score = p[3] * 100 * 100 + p[1] * 100 + p[2];
}
else if (p[1] == p[2] && p[3] == p[4])
{
type = 3;
score = p[3] * 100 * 100 + p[1] * 100 + p[0];
}
else if (p[0] == p[1])
{
type = 2;
score = p[0] * 100 + p[2] + p[3] + p[4];
}
else if (p[1] == p[2])
{
type = 2;
score = p[1] * 100 + p[0] + p[3] + p[4];
}
else if (p[2] == p[3])
{
type = 2;
score = p[2] * 100 + p[0] + p[1] + p[4];
}
else if (p[3] == p[4])
{
type = 2;
score = p[3] * 100 + p[0] + p[1] + p[2];
}
else
{
type = 1;
score = 0;
for (int i = 0; i < 5; i++)
{
score = score + p[i];
}
}
}
pa x[100000 + 1024];
int main()
{
int t;
while (scanf("%d", &t) != EOF)
{
for (int i = 0; i < t; i++)
{
x[i].reset();
x[i].set();
}
sort(x, x + t, compare);
for (int i = 0; i < t; i++)
{
cout << x[i].name << endl;
}
}
}
TC - 签到题
题意
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
思路
首先，将现有的数组a进行排序，最大值无疑就是让y个人全部坐在目前人最多的那个长椅上，即mx=a[n-1]+y。
然后最小值就是要让每个长椅上的人尽可能地均匀，有两种情况：
（1）当y不足以分配给其他长椅使他们的数值都达到a[n-1]时，那么最小值就是a[n-1]；
（2）当y足以分配给其他长椅使他们的数值都达到a[n-1]时，先分配，即让所有的长椅的人数都达到k，然后剩下的人平均分给x个长椅，然后最多的那个即为mn.
最后依次输出mn和mx即可。
注意，当只有一个长椅时，应当特殊处理，防止除零。
代码
#include <iostream>
using namespace std;
int sum, n, y, l, ma;
int main()
{
cin >> n >> y;
for (int i = 0; i < n; i++)
{
cin >> l;
sum += l;
if (l > ma)
{
ma = l;
}
}
if (n == 1)
{
cout << ma + y << " " << ma + y << endl;
return 0;
}
int a = (y + sum - ma) / (n - 1);
int b = (y + sum - ma) % (n - 1);
if (b != 0)
{
a++;
}
if (a <= ma)
{
cout << ma << " ";
}
else
{
a = (y + sum) / n;
b = (y + sum) % n;
if (b != 0)
{
a++;
}
cout << a << " ";
}
cout << ma + y << endl;
return 0;
}