week 9
A 巨型模拟，文件管理器
题目描述
咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！
初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。
image.png
现在咕咕东可以在命令行下执行以下表格中描述的命令：
image.png
样例输入：
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
hint
思路：
是一个很复杂的模拟题（但学长上课给出了代码所以其实是一个读代码的题目2333）
主体结构是一个树形结构
``
struct Directory
{
string name;
map<string,Directory> children;//子目录,用指针为了避免复制构造造成的内存浪费
Directory parent;//父节点,用于cd ..
int subtreeSize;//用于sz
vector<string>* tenDescendants;
bool updated;
Directory(string _name,Directory* _parent)
{
this->name=_name;
this->parent=_parent;
this->subtreeSize=1;
this->updated=true;
this->tenDescendants=new vector<string>;
}
Directory* getChild(string &_name);
Directory* mkdir(string &_name);
Directory* rm(string &_name);
Directory* cd(string &_name);
Directory* addChild(Directory* ch);
void maintain(int delta);
void sz();
void ls();/
void tree();
void treeAll(vector<string>* tenBuffer);
void treeFirstFive(int num,vector<string>* tenBuffer);
void treeLastFive(int num,vector<string>* tenBuffer);
};
定义所有的ADT操作。之后封装这个字典树，并模拟操作： 基本都在注释里面写了orz
include<iostream>
include<cstdio>
include<algorithm>
include<map>
include<string>
include<vector>
using namespace std;
char tmps[20];//meaning->temp string
const string CMDNAMES[7] = { "MKDIR","RM","CD","SZ","LS","TREE","UNDO" };
//树形结构
struct Directory
{
string name;//当前目录的名字
map<string, Directory>children;//用指针是避免复制构造造成的内存浪费
Directory parent;//以备CD.. 返回上级目录
int subtreeSize;//以备sz要输出子树大小
vector<string>* tenDescendants;//保存当前节点的十个后代
bool updated;//记录当前节点的子孙有无变动，
Directory(string name, Directory* parent) {
this->name = name;
this->parent = parent;
this->subtreeSize = 1;
this->tenDescendants=new vector<string>;
}
public:
void maintain(int delta) {//向上维护子树大小
updated = true;
subtreeSize += delta;
if (parent != nullptr)parent->maintain(delta);
}
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());
}
}
//12、在结构体类写各种具体的实现
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);
}
bool addChild(Directory* ch) {
//加入子目录并判断成功与否
if (children.find(ch->name) != children.end())
return false;
children[ch->name] = ch;
maintain(+ch->subtreeSize);
return true;
}
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());
}
}
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);
}
};
//5、封装command
struct Command
{
int type;//命令的类型
string arg;//命令的 参数
Command(string s) {//构造函数
for(int i=0;i<7;i++)
if (CMDNAMES[i] == s) {
type = i;
//MKDIR、RM、CD的参数后续读入
if (i < 3) scanf("%s", tmps), arg = tmps;
return;
}
}
Directory* tmpDir;
};
void solve(){
int n; cin >> n;
Directory *now = new Directory("root", nullptr);
vector<Command*>cmdList;//新增加的数组存成功执行的命令以备undo
while (n--) {
scanf("%s", tmps);
Command* cmd = new Command(tmps);
Directory * ch;
switch (cmd->type)
{
case 0:case 1://MKDIR、RM
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://CD
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;
//解决undo
case 6://undo
bool success = false;//undo执行成功与否
while (!success && !cmdList.empty()) {
cmd = cmdList.back(); cmdList.pop_back();
switch (cmd->type)
{
case 0:success = now->rm(cmd->arg) != nullptr; break;
//UNDO RM
case 1:success = now->addChild(cmd->tmpDir); break;
//UNDO CD
case 2:now = cmd->tmpDir; success = true; break;
}
}
printf(success ? "OK\n" : "ERR\n");
}
}
cout<<endl;
}
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
思路：
其实也是一个很简单的模拟题，定义一个牌型的结构体。先通过统计记录每个人牌型的级别要写一个多级的比较函数。
比较复杂的是同一个级别的牌可能会有很多的比较情况（比如对子先比对子再比其他的情况，所以我们还是得在牌型结构体里面用一个数组去记录该牌型的大小，比如，数组第一个位置放优先比较的位置）
上代码
#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<cstring>
using namespace std;
struct pai2
{
int daxiao;
int num;
};
int max1(int &a, int &b)
{
if (a > b) return a;
else return b;
}
int min1(int &a, int &b)
{
if (a < b) return a;
else return b;
}
bool cmp1(pai2 &a, pai2 &b)
{
return a.num > b.num;
}
int jibie(string x, int *a, pai2 *sumnumber)
{
int i = 0;
int t = x.length();
int p = 0;
for (int i = 0; i < t; i++)
{
if (x[i] >= 50 && x[i] <= 57) a[p] = x[i] - 48, p++;
else if (x[i] == 'A') a[p] = 1, p++;
else if (x[i] == 'J') a[p] = 11, p++;
else if (x[i] == 'Q') a[p] = 12, p++;
else if (x[i] == 'K') a[p] = 13, p++;
else if (x[i] == '1') a[p] = 10, p++;
}
sort(a, a + 5);
bool shunzi = 1;
for (int k = 0; k < 5; k++) sumnumber[k].num = 1;
sumnumber[0].daxiao = a[0];
int w = 0;
for (int i = 0; i < 4; i++)
{
if ((a[i + 1] - 1) != a[i]) shunzi = 0;
if (a[i + 1] == a[i]) sumnumber[w].num++; else w++, sumnumber[w].daxiao = a[i + 1];
}
sort(sumnumber, sumnumber + 5, cmp1);
if (a[0] == 1)
{
bool yes = 1;
for (int i = 1; i < 5; i++) if (a[i] != 9 + i) yes = 0;
if (yes) return 8;
}
if (shunzi)
{
return 7;
}
else if (sumnumber[0].num == 4) return 6;
else if (sumnumber[0].num == 3)
{
if (sumnumber[1].num == 2) return 5;
else return 4;
}
else if (sumnumber[0].num == 2)
{
if (sumnumber[1].num == 2) return 3;
else return 2;
}
else return 1;
}
struct shoupai
{
string name;
string pai;
int paizu[5];
pai2 tongji[5];
int jibies;
};
bool cmp(shoupai &a, shoupai &b)
{
if (a.jibies != b.jibies) return a.jibies > b.jibies;
else {
if (a.jibies == 7) {
if (a.paizu[0] != b.paizu[0]) return a.paizu[0] > b.paizu[0];
}
else if (a.jibies == 6) {
if (a.tongji[0].daxiao != b.tongji[0].daxiao) return a.tongji[0].daxiao > b.tongji[0].daxiao;
else {
int k1 = 0, k2 = 0;
for (int i = 0; i < 5; i++) k1 += a.paizu[i], k2 += b.paizu[i];
if (k1 != k2) return k1 > k2;
}
}
else if (a.jibies == 5) {
if (a.tongji[0].daxiao != b.tongji[0].daxiao) return a.tongji[0].daxiao > b.tongji[0].daxiao;
else
{
if (a.tongji[1].daxiao != b.tongji[1].daxiao) return a.tongji[1].daxiao > b.tongji[1].daxiao;
}
}
else if (a.jibies == 4)
{
if (a.tongji[0].daxiao != b.tongji[0].daxiao) return a.tongji[0].daxiao > b.tongji[0].daxiao;
else {
int k1 = 0, k2 = 0;
for (int i = 0; i < 5; i++) k1 += a.paizu[i], k2 += b.paizu[i];
if (k1 != k2) return k1 > k2;
}
}
else if (a.jibies == 3)
{
int d1 = max1(a.tongji[0].daxiao, a.tongji[1].daxiao); int d2 = max1(b.tongji[0].daxiao, b.tongji[1].daxiao);
int c1 = min1(a.tongji[0].daxiao, a.tongji[1].daxiao); int c2 = min1(b.tongji[0].daxiao, b.tongji[1].daxiao);
if (d1 != d2) return d1 > d2;
else {
if (c1 != c2) return c1 > c2;
else
{
int k1 = 0, k2 = 0;
for (int i = 0; i < 5; i++) k1 += a.paizu[i], k2 += b.paizu[i];
if (k1 != k2) return k1 > k2;
}
}
}
else if (a.jibies == 2)
{
if (a.tongji[0].daxiao != b.tongji[0].daxiao) return a.tongji[0].daxiao > b.tongji[0].daxiao;
else {
int k1 = 0, k2 = 0;
for (int i = 0; i < 5; i++) k1 += a.paizu[i], k2 += b.paizu[i];
if (k1 != k2) return k1 > k2;
}
}
else if (a.jibies == 1)
{
int k1 = 0, k2 = 0;
for (int i = 0; i < 5; i++) k1 += a.paizu[i], k2 += b.paizu[i];
if (k1 != k2) return k1 > k2;
}
return a.name < b.name;
}
}
shoupai a[100005];
int main()
{
int n;
while (cin >> n)
{
for (int i = 0; i < n; i++)
{
cin >> a[i].name >> a[i].pai;
a[i].jibies = jibie(a[i].pai, a[i].paizu, a[i].tongji);
}
sort(a, a + n, cmp);
for (int i = 0; i < n; i++)
{
cout << a[i].name << endl;
}
}
return 0;
}
公园的长凳
题意：
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
分析：
这题的重点，在于分散；
1.求最大值：很简单，所有新人都做到原来坐的人最多的凳子上去
2.求最小值，重点就是分散，先试图让所有人坐其他凳子，使全部的凳子都和原来人最多的凳子上的人一样多。如果无法做到，原来人最多的那个就是最小值。如果能做到，再看看是不是剩下人，再试图分散。。直到人都坐满了，最多的比最少的也只多一个人（或者都一样）
代码不难
#include<iostream>
#include<algorithm>
using namespace std;
int a[100+10];
int main()
{
int pl;
int n;cin>>n;
int m;cin>>m;
int mx=0,mn,max;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>mx) mx=a[i];
}
max=mx;
max+=m;
int quel=0;
for(int i=1;i<=n;i++)
{
quel+=(mx-a[i]);
}
if(m<=quel)
{
mn=mx;
}
else{
m-=quel;
if(m%n==0) pl=m/n;
else pl=m/n+1;
mn=mx+pl;
}
cout<<mn<<" ";
cout<<max<<endl;
return 0;
}
