A 巨型模擬，文件管理器

題目描述

咕咕東的雪梨電腦的操作系統(tǒng)在上個(gè)月受到宇宙射線的影響，時(shí)不時(shí)發(fā)生故障，他受不了了，想要寫一個(gè)高效易用零bug的操作系統(tǒng) —— 這工程量太大了，所以他定了一個(gè)小目標(biāo)，從實(shí)現(xiàn)一個(gè)目錄管理器開始。前些日子，東東的電腦終于因?yàn)檫^度收到宇宙射線的影響而宕機(jī)，無法寫代碼。他的好友TT正忙著在B站看貓片，另一位好友瑞神正忙著打守望先鋒?，F(xiàn)在只有你能幫助東東！

初始時(shí)，咕咕東的硬盤是空的，命令行的當(dāng)前目錄為根目錄 root。

目錄管理器可以理解為要維護(hù)一棵有根樹結(jié)構(gòu)，每個(gè)目錄的兒子必須保持字典序。

image.png

現(xiàn)在咕咕東可以在命令行下執(zhí)行以下表格中描述的命令：

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

思路：

是一個(gè)很復(fù)雜的模擬題（但學(xué)長上課給出了代碼所以其實(shí)是一個(gè)讀代碼的題目2333）
主體結(jié)構(gòu)是一個(gè)樹形結(jié)構(gòu)
``
struct Directory
{
string name;
map<string,Directory> children;//子目錄,用指針為了避免復(fù)制構(gòu)造造成的內(nèi)存浪費(fèi)
Directory parent;//父節(jié)點(diǎn),用于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操作。之后封裝這個(gè)字典樹，并模擬操作： 基本都在注釋里面寫了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" };
//樹形結(jié)構(gòu)
struct Directory
{
string name;//當(dāng)前目錄的名字
map<string, Directory>children;//用指針是避免復(fù)制構(gòu)造造成的內(nèi)存浪費(fèi)
Directory parent;//以備CD.. 返回上級目錄
int subtreeSize;//以備sz要輸出子樹大小
vector<string>* tenDescendants;//保存當(dāng)前節(jié)點(diǎn)的十個(gè)后代
bool updated;//記錄當(dāng)前節(jié)點(diǎn)的子孫有無變動，
Directory(string name, Directory* parent) {
this->name = name;
this->parent = parent;
this->subtreeSize = 1;
this->tenDescendants=new vector<string>;
}
public:
void maintain(int delta) {//向上維護(hù)子樹大小
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、在結(jié)構(gòu)體類寫各種具體的實(shí)現(xiàn)
Directory* getChild(string name) {
    //取子目錄并返回，不存在返回空指針
    auto it = children.find(name);
    if (it == children.end()) return nullptr;
    return it->second;
}
Directory* mkdir(string name) {
    //創(chuàng)建子目錄并返回，創(chuàng)建失敗返回空指針
    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) {
    //更新前序幾個(gè)
    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) {
    //更新后序幾個(gè)
    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;//命令的 參數(shù)
Command(string s) {//構(gòu)造函數(shù)
for(int i=0;i<7;i++)
if (CMDNAMES[i] == s) {
type = i;
//MKDIR、RM、CD的參數(shù)后續(xù)讀入
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;//新增加的數(shù)組存成功執(zhí)行的命令以備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執(zhí)行成功與否
        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;
}

``

東東學(xué)打牌

題面

最近，東東沉迷于打牌。所以他找到 HRZ、ZJM 等人和他一起打牌。由于人數(shù)眾多，東東稍微修改了億下游戲規(guī)則：

所有撲克牌只按數(shù)字來算大小，忽略花色。
每張撲克牌的大小由一個(gè)值表示。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。
每個(gè)玩家抽得 5 張撲克牌，組成一手牌?。糠N撲克牌的張數(shù)是無限的，你不用擔(dān)心，東東家里有無數(shù)副撲克牌）
理所當(dāng)然地，一手牌是有不同類型，并且有大小之分的。

舉個(gè)栗子，現(xiàn)在東東的 “一手牌”（記為 α），瑞神的 “一手牌”（記為 β），要么 α > β，要么 α < β，要么 α = β。

那么這兩個(gè) “一手牌”，如何進(jìn)行比較大小呢？首先對于不同類型的一手牌，其值的大小即下面的標(biāo)號；對于同類型的一手牌，根據(jù)組成這手牌的 5 張牌不同，其值不同。下面依次列舉了這手牌的形成規(guī)則：

大牌：這手牌不符合下面任一個(gè)形成規(guī)則。如果 α 和 β 都是大牌，那么定義它們的大小為組成這手牌的 5 張牌的大小總和。

對子：5 張牌中有 2 張牌的值相等。如果 α 和 β 都是對子，比較這個(gè) “對子” 的大小，如果 α 和 β 的 “對子” 大小相等，那么比較剩下 3 張牌的總和。

兩對：5 張牌中有兩個(gè)不同的對子。如果 α 和 β 都是兩對，先比較雙方較大的那個(gè)對子，如果相等，再比較雙方較小的那個(gè)對子，如果還相等，只能比較 5 張牌中的最后那張牌組不成對子的牌。

三個(gè)：5 張牌中有 3 張牌的值相等。如果 α 和 β 都是 “三個(gè)”，比較這個(gè) “三個(gè)” 的大小，如果 α 和 β 的 “三個(gè)” 大小相等，那么比較剩下 2 張牌的總和。

三帶二：5 張牌中有 3 張牌的值相等，另外 2 張牌值也相等。如果 α 和 β 都是 “三帶二”，先比較它們的 “三個(gè)” 的大小，如果相等，再比較 “對子” 的大小。

炸彈：5 張牌中有 4 張牌的值相等。如果 α 和 β 都是 “炸彈”，比較 “炸彈” 的大小，如果相等，比較剩下那張牌的大小。

順子：5 張牌中形成 x, x+1, x+2, x+3, x+4。如果 α 和 β 都是 “順子”，直接比較兩個(gè)順子的最大值。

龍順：5 張牌分別為 10、J、Q、K、A。

作為一個(gè)稱職的魔法師，東東得知了全場人手里 5 張牌的情況。他現(xiàn)在要輸出一個(gè)排行榜。排行榜按照選手們的 “一手牌” 大小進(jìn)行排序，如果兩個(gè)選手的牌相等，那么人名字典序小的排在前面。

不料，此時(shí)一束宇宙射線掃過，為了躲避宇宙射線，東東慌亂中清空了他腦中的 Cache。請你告訴東東，全場人的排名
輸入：
輸入包含多組數(shù)據(jù)。每組輸入開頭一個(gè)整數(shù) n (1 <= n <= 1e5)，表明全場共多少人。
隨后是 n 行，每行一個(gè)字符串 s1 和 s2 （1 <= |s1|,|s2| <= 10）， s1 是對應(yīng)人的名字，s2 是他手里的牌情況。

輸出：

對于每組測試數(shù)據(jù)，輸出 n 行，即這次全場人的排名。

樣例：

樣例輸入：

3
DongDong AAA109
ZJM 678910
Hrz 678910

樣例輸出：

Hrz
ZJM
DongDong

思路：

其實(shí)也是一個(gè)很簡單的模擬題，定義一個(gè)牌型的結(jié)構(gòu)體。先通過統(tǒng)計(jì)記錄每個(gè)人牌型的級別要寫一個(gè)多級的比較函數(shù)。
比較復(fù)雜的是同一個(gè)級別的牌可能會有很多的比較情況（比如對子先比對子再比其他的情況，所以我們還是得在牌型結(jié)構(gòu)體里面用一個(gè)數(shù)組去記錄該牌型的大小，比如，數(shù)組第一個(gè)位置放優(yōu)先比較的位置）
上代碼

#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 個(gè)長凳上坐著 a_i 個(gè)人。這時(shí)候又有 y 個(gè)人將來到公園，他們將選擇坐在某些公園中的長凳上，那么當(dāng)這 y 個(gè)人坐下后，記k = 所有椅子上的人數(shù)的最大值，那么k可能的最大值mx和最小值mn分別是多少。

輸入：

第一行包含一個(gè)整數(shù) x (1 <= x <= 100) 表示公園中長椅的數(shù)目
第二行包含一個(gè)整數(shù) y (1 <= y <= 1000) 表示有 y 個(gè)人來到公園
接下來 x 個(gè)整數(shù) a_i (1<=a_i<=100)，表示初始時(shí)公園長椅上坐著的人數(shù)

輸出：

輸出 mn 和 mx

樣例：

樣例輸入:

3
7
1
6
1

樣例輸出：

6 13

分析：
這題的重點(diǎn)，在于分散；
1.求最大值：很簡單，所有新人都做到原來坐的人最多的凳子上去
2.求最小值，重點(diǎn)就是分散，先試圖讓所有人坐其他凳子，使全部的凳子都和原來人最多的凳子上的人一樣多。如果無法做到，原來人最多的那個(gè)就是最小值。如果能做到，再看看是不是剩下人，再試圖分散。。直到人都坐滿了，最多的比最少的也只多一個(gè)人（或者都一樣）
代碼不難

#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;
}