山东大学计算机科学与技术学院程序设计思维与实践作业 week9-复杂模拟题的普适性方法

2023-11-21 17:50
文章标签 技术 实践 方法 思维 作业 山东大学 程序设计 学院 模拟题 复杂 计算机科学 普适性 week9

本文主要是介绍山东大学计算机科学与技术学院程序设计思维与实践作业 week9-复杂模拟题的普适性方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

山东大学计算机科学与技术学院程序设计思维与实践作业
山大程序设计思维与实践作业
sdu程序设计思维与实践
山东大学程序设计思维实践作业H9
山大程序设计思维实践作业H9
山东大学程序设计思维与实践
week9-复杂模拟题的普适性方法

相关资料：GitHub

文章目录

    • A : 化学方程式
    • B : 带配额的文件系统

A : 化学方程式

题目描述
化学方程式，也称为化学反应方程式，是用化学式表示化学反应的式子。给出一组化学方程式，请你编写程序判断每个方程式是否配平（也就是方程式中等号左右两边的元素种类和对应的原子个数是否相同)。

本题给出的化学方程式由大小写字母、数字和符号（包括等号 =、加号 +、左圆括号 ( 和右圆括号 ))组成，不会出现其他字符（包括空白字符，如空格、制表符等)。化学方程式的格式与化学课本中的形式基本相同（化学式中表示元素原子个数的下标用正常文本，如 H
2
​
O 写成 H2O)，用自然语言描述如下:

化学方程式由左右两个表达式组成，中间用一个等号 = 连接，如 2H2+O2=2H2O；
表达式由若干部分组成，每部分由系数和化学式构成，部分之间用加号 + 连接,如 2H2+O2、2H2O；
系数是整数或空串，如为空串表示系数为 1；
整数由一个或多个数字构成；
化学式由若干部分组成，每部分由项和系数构成，部分之间直接连接，如 H2O、CO2、Ca(OH)2、Ba3(PO4)2；
项是元素或用左右圆括号括起来的化学式，如 H、Ca、(OH)、(PO4):
元素可以是一个大写字母，也可以是一个大写字母跟着一个小写字母，如 H、O、Ca。
用巴科斯范式(Backus-Naur form，BNF)给出的形式化定义如下：

::= “=”
::= | “+”
::= | “”
::= |
::= “0” | “1” | … | “9”
::= |
::= | “(” “)”
::= |
::= “A” | “B” | … | “Z”
::= “a” | “b” | … | “z”
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数n，表示输入的化学方程式个数。接下来 n 行，每行是一个符合定义的化学方程式。

输出格式
输出到标准输出。
输出共 n 行，每行是一个大写字母 Y 或 N，回答输入中相应的化学方程式是否配平。
在这里插入图片描述
测试样例
样例 1
输入:
11
H2+O2=H2O
2H2+O2=2H2O
H2+Cl2=2NaCl
H2+Cl2=2HCl
CH4+2O2=CO2+2H2O
CaCl2+2AgNO3=Ca(NO3)2+2AgCl
3Ba(OH)2+2H3PO4=6H2O+Ba3(PO4)2
3Ba(OH)2+2H3PO4=Ba3(PO4)2+6H2O
4Zn+10HNO3=4Zn(NO3)2+NH4NO3+3H2O
4Au+8NaCN+2H2O+O2=4Na(Au(CN)2)+4NaOH
Cu+As=Cs+Au
输出:
N
Y
N
Y
Y
Y
Y
Y
Y
Y
N

#include<bits/stdc++.h>
using namespace std;vector<string> split(string &s,char c)
{stringstream ss(s);string du;vector<string> re;while(getline(ss,du,c)){re.push_back(du);}return re;
}int duint(string &s,int &p)
{int re=0;while(p!=s.size()&&isdigit(s[p])){re=re*10+(s[p]-'0');p++;	}	if(re==0){return 1;}else{return re;}
} string duelement(string &s,int &p)
{string re;re+=s[p];p++;if(p!=s.size()&&islower(s[p])){re+=s[p];p++;}return re;
}void merge(map<string,int> &re,map<string,int> &current,int coef)
{for(auto &i:current){re[i.first]+=i.second*coef;}
}map<string,int> duformula(string &formula,int &p);map<string,int> duterm(string &term, int &p)
{if(term[p]=='('){p++;map<string,int> re=duformula(term,p);p++;return re;}else{string element=duelement(term,p);map<string,int> re;re[element]=1;return re;}
}map<string,int> duformula(string &formula,int &p)
{map<string,int> re;while(p!=formula.size()&&formula[p]!=')'){map<string,int> tmp=duterm(formula,p);int coef=duint(formula,p);merge(re,tmp,coef);}return re;
}map<string,int> parseexpr(string expr)
{map<string,int> re;vector<string> formulas=split(expr,'+');for(auto i:formulas){int p=0;int coef=duint(i,p);map<string,int> tmp=duformula(i,p);merge(re,tmp,coef);}return re;
}void solve()
{string equation;cin>>equation;vector<string> expr=split(equation,'=');if(parseexpr(expr[0])==parseexpr(expr[1])){cout<<"Y"<<endl;}else{cout<<"N"<<endl;	}
} int main()
{int t;cin>>t;while(t--){solve();}	
}

B : 带配额的文件系统

题目背景
小 H 同学发现，他维护的存储系统经常出现有人用机器学习的训练数据把空间占满的问题，十分苦恼。查找了一阵资料后，他想要在文件系统中开启配额限制，以便能够精确地限制大家在每个目录中最多能使用的空间。

文件系统概述
文件系统，是一种树形的文件组织和管理方式。在文件系统中，文件是指用名字标识的文件系统能够管理的基本对象，分为普通文件和目录文件两种，目录文件可以被简称为 目录。目录中有一种特殊的目录被叫做 根目录。

除了根目录外，其余的文件都有名字，称为文件名。合法的文件名是一个由若干数字（[0-9]）、大小写字母（[A-Za-z]）组成的非空字符串。普通文件中含有一定量的数据，占用存储空间；目录不占用存储空间。

文件和目录之间存在含于关系。上述概念满足下列性质：

  1. 有且仅有一个根目录；
  2. 对于除根目录以外的文件，都含于且恰好含于一个目录；
  3. 含于同一目录的文件，它们的文件名互不相同；
  4. 对于任意不是根目录的文件 f，若 f 不含于根目录，那么存在有限个目录 d1,d2,…,dn，使得 f 含于 d1，d1 含于 d2，…，dn 含于根目录。

结合性质 4 和性质 2 可知，性质 4 中描述的有限多个目录，即诸 di ，是唯一的。再结合性质 3，我们即可通过从根目录开始的一系列目录的序列，来唯一地指代一个文件。

我们记任意不是根目录且不含于根目录的文件 f 的文件名是 Nf，那么 f 的路径是：′/′+Ndn+′/′⋯+Nd1+′/′+Nf，其中符号 + 表示字符串的连接；对于含于根目录的文件 f，它的路径是：‘/’+Nf；根目录的路径是：‘/’。不符合上述规定的路径都是非法的。

例如：/A/B 是合法路径，但 /A//B、/A/、A/、A/B 都不是合法路径。
若文件 f 含于目录 d，我们也称 f 是 d 的孩子文件。d 是 f 的双亲目录。我们称文件 f 是目录 d 的后代文件，如果满足：(1) f 是 d 的孩子文件，或 (2) f 含于 d 的后代文件。

如图所示，该图中绘制的文件系统共有 8 个文件。其中，方形表示目录文件，圆形表示普通文件，它们之间的箭头表示含于关
系。在表示文件的形状上的文字是其文件名；各个形状的左上方标记了序号，以便叙述。
在该文件系统中，文件 5 含于文件 2，文件 5 是文件 2 的孩子文件，文件 5 也是文件 2 的后代文件。文件 8 是文件 2 的后代文件，但不是文件 2 的孩子文件。文件 8 的路径是 /D1/D1/F2。
在这里插入图片描述

配额概述
配额是指对文件系统中所含普通文件的总大小的限制。对于每个目录 d，都可以设定两个配额值：目录配额 和 后代配额。

我们称目录配额 LDd 是满足的，当且仅当 d 的孩子文件中，全部普通文件占用的存储空间之和不大于该配额值。我们称后代配额 LRd 是满足的，当且仅当 d 的后代文件中，全部普通文件占用的存储空间之和不大于该配额值。我们称文件系统的配额是满足的，当且仅当该文件系统中所有的配额都是满足的。

很显然，若文件系统中仅存在目录，不存在普通文件，那么该文件系统的配额一定是满足的。随着配额和文件的创建，某个操作会使文件系统的配额由满足变为不满足，这样的操作会被拒绝。例如：试图设定少于目前已有文件占用空间的配额值，或者试图创建超过配额值的文件。

题目描述
在本题中，假定初始状态下，文件系统仅包含根目录。你将会收到若干对文件系统的操作指令。对于每条指令，你需要判断该指令能否执行成功，对于能执行成功的指令，在成功执行该指令后，文件系统将会被相应地修改。对于不能执行成功的指令，文件系统将不会发生任何变化。你需要处理的指令如下：
创建普通文件
创建普通文件指令的格式如下：
C

创建普通文件的指令有两个参数，是空格分隔的字符串和一个正整数，分别表示需要创建的普通文件的路径和文件的大小。

对于该指令，若路径所指的文件已经存在，且也是普通文件的，则替换这个文件；若路径所指文件已经存在，但是目录文件的，则该指令不能执行成功。
当路径中的任何目录不存在时，应当尝试创建这些目录；若要创建的目录文件与已有的同一双亲目录下的孩子文件中的普通文件名称重复，则该指令不能执行成功。
另外，还需要确定在该指令的执行是否会使该文件系统的配额变为不满足，如果会发生这样的情况，则认为该指令不能执行成功，反之则认为该指令能执行成功。
移除文件

移除文件指令的格式如下：
R

移除文件的指令有一个参数，是字符串，表示要移除的文件的路径。
若该路径所指的文件不存在，则不进行任何操作。若该路径所指的文件是目录，则移除该目录及其所有后代文件。在上述过程中被移除的目录（如果有）上设置的配额值也被移除。
该指令始终认为能执行成功。
设置配额值
Q

设置配额值的指令有三个参数，是空格分隔的字符串和两个非负整数，分别表示需要设置配额值的目录的路径、目录配额和后代配额。
该指令表示对所指的目录文件，分别设置目录配额和后代配额。若路径所指的文件不存在，或者不是目录文件，则该指令执行不成功。
若在该目录上已经设置了配额，则将原配额值替换为指定的配额值。
特别地，若配额值为 0，则表示不对该项配额进行限制。若在应用新的配额值后，该文件系统配额变为不满足，那么该指令执行不成功。

输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 n，表示需要处理的指令条数。
输入接下来会有 n 行，每一行一个指令。指令的格式符合前述要求。
输入数据保证：对于所有指令，输入的路径是合法路径；对于创建普通文件和移除文件指令，输入的路径不指向根目录。

输出格式
输出到标准输出。
输出共有 n 行，表示相应的操作指令是否执行成功。若成功执行，则输出字母 Y；否则输出 N。
样例解释

样例 1
输入总共有 10 条指令。
其中前两条指令可以正常创建两个普通文件。
第三条指令试图创建 /A/B/1/3，但是 /A/B/1 已经存在，且不是目录，而是普通文件，不能再进一步创建孩子文件，因此执行不成功。
第四条指令试图创建 /A，但是 /A 已经存在，且是目录，因此执行不成功。
第五条指令试图删除 /A/B/1/3，由于该文件不存在，因此不对文件系统进行修改，但是仍然认为执行成功。
第六条指令试图在根目录增加后代配额限制，但此时，文件系统中的文件总大小是 2048，因此该限制无法生效，执行不成功。
第七条指令试图创建文件 /A/B/1，由于 /A/B/1 已经存在，且是普通文件，因此该指令实际效果是
将原有的该文件替换。此时文件总大小是 1124，因此第八条指令就可以执行成功了。
第九条指令递归删除了 /A/B 目录和它的所有后代文件。此时文件系统中已经没有普通文件，因此第十条命令可以执行成功。

样例 2
输入共有 9 条指令。
第一条指令试图为 /A/B 创建配额规则，然而该目录并不存在，因此执行不成功。
接下来的两条指令创建了两个普通文件。
再接下来的两条指令分别在目录 /A/B 和 /A/C 创建了两个配额规则。其中前者是目录配额，后者是后代配额。
接下来的两条指令，创建了两个文件。其中，/A/B/3 超出了在 /A/B 的目录配额，因此执行不成功；但 /A/B/D/3 不受目录配额限制，因此执行成功。
最后两条指令，创建了两个文件。虽然在 /A/C 没有目录配额限制，但是无论是 /A/C 下的孩子文件还是后代文件，都受到后代配额的限制，因此两条指令执行都不成功。
在这里插入图片描述

测试样例
样例 1
输入:
10
C /A/B/1 1024
C /A/B/2 1024
C /A/B/1/3 1024
C /A 1024
R /A/B/1/3
Q / 0 1500
C /A/B/1 100
Q / 0 1500
R /A/B
Q / 0 1
输出:
Y
Y
N
N
Y
N
Y
Y
Y
Y
样例 2
输入:
9
Q /A/B 1030 2060
C /A/B/1 1024
C /A/C/1 1024
Q /A/B 1024 0
Q /A/C 0 1024
C /A/B/3 1024
C /A/B/D/3 1024
C /A/C/4 1024
C /A/C/D/4 1024
输出:
N
Y
Y
Y
Y
N
Y
N
N

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
struct file{bool isDir;//是否为目录ll ld,lr;//目录配额,后代配额ll sd,sr;//目录已用配额,后代已用配额map<string,file> children;//子一级文件、目录ll fileSize;//文件大小file(){//构造函数isDir=true;ld=lr=inf;sd=sr=0;fileSize=0;}
};
file root;
vector<string> split(string &path){//根据c对s分割stringstream ss(path);string read;vector<string> res;while(getline(ss,read,'/')){//从ss中读取字符串到read，直至遇见cres.push_back(read);//将分割后的片段放入res}return res;
}
vector<file *> findFile(vector<string> &fileNames){vector<file *> res;res.push_back(&root);for(int i=1;i<fileNames.size();++i){if(res.back()->isDir==false){break;}//该文件在此不是目录，无法进行操作if(res.back()->children.count(fileNames[i])==0){break;}//在该目录下未找到指定文件/目录res.push_back(&res.back()->children[fileNames[i]]);//在该目录下找到了指定文件/目录，加入res}return res;
}
/*C <file path> <file size>
创建普通文件的指令有两个参数，是空格分隔的字符串和一个正整数，分别表示需
要创建的普通文件的路径和文件的大小。
对于该指令，若路径所指的文件已经存在，且也是普通文件的，则替换这个文件；
若路径所指文件已经存在，但是目录文件的，则该指令不能执行成功。
当路径中的任何目录不存在时，应当尝试创建这些目录；若要创建的目录文件与已
有的同一双亲目录下的孩子文件中的普通文件名称重复，则该指令不能执行成功。
另外，还需要确定在该指令的执行是否会使该文件系统的配额变为不满足，如果会
发生这样的情况，则认为该指令不能执行成功，反之则认为该指令能执行成功。
*/
bool create(){//创建文件string path;ll fileSize;cin>>path>>fileSize;vector<string> fileNames=split(path);//vector<file *> filePtrs=findFile(fileNames);//查找能找到的符合的路径ll inc;if(fileNames.size()==filePtrs.size()){//若路径所指的文件已经存在if(filePtrs.back()->isDir){return false;}//是目录文件,不能执行成功else{inc=fileSize-filePtrs.back()->fileSize;}//是普通文件,替换这个文件}else{//路径中的某些目录不存在//要创建的目录文件与已有的同一双亲目录下的孩子文件中的普通文件名称重复，则该指令不能执行成功if(!filePtrs.back()->isDir){return false;}else{inc=fileSize;}//尝试创建这些目录}//检查该指令的执行是否会使该文件系统的配额变为不满足//后代配额检查for(int i=0;i<filePtrs.size();++i){if(filePtrs[i]->sr+inc>filePtrs[i]->lr){return false;}}//目录配额检查int i=fileNames.size()-2;if(i<filePtrs.size()&&filePtrs[i]->sd+inc>filePtrs[i]->ld){return false;}//补齐路径for(int i=filePtrs.size();i<fileNames.size();++i){filePtrs.push_back(&filePtrs.back()->children[fileNames[i]]);}//创建的文件基本信息的写入filePtrs.back()->isDir=false;filePtrs.back()->fileSize=fileSize;//修改祖先的后代已用配额for(auto &i:filePtrs){i->sr+=inc;}//修改父亲的目录已用配额filePtrs.end()[-2]->sd+=inc;return true;
}
/*R <file path>
移除文件的指令有一个参数，是字符串，表示要移除的文件的路径。
若该路径所指的文件不存在，则不进行任何操作。若该路径所指的文件是目录，
则移除该目录及其所有后代文件。在上述过程中被移除的目录（如果有）上设置的
配额值也被移除。
该指令始终认为能执行成功
*/
bool remove(){string path;cin>>path;vector<string> fileNames=split(path);vector<file *> filePtrs=findFile(fileNames);if(filePtrs.size()!=fileNames.size()){return true;}//该路径所指的文件不存在if(filePtrs.back()->isDir){//该路径所指的文件是目录for(auto &i:filePtrs){//对路径上的祖先的后代已用配额修减去最后一级目录的后代已用配额i->sr-=filePtrs.back()->sr;}}else{//该路径所指的文件是普通文件for(auto &i:filePtrs){//对路径上的祖先的后代已用配额修减去普通文件的文件大小i->sr-=filePtrs.back()->sr;}filePtrs.end()[-2]->sd-=filePtrs.back()->fileSize;//被移除文件的父亲的目录已用配额减去普通文件的文件大小}filePtrs.end()[-2]->children.erase(fileNames.back());//移除文件return true;
}
/*Q <file path> <LD> <LR>
设置配额值的指令有三个参数，是空格分隔的字符串和两个非负整数，分别表示需
要设置配额值的目录的路径、目录配额和后代配额。
该指令表示对所指的目录文件，分别设置目录配额和后代配额。若路径所指的文件
不存在，或者不是目录文件，则该指令执行不成功。
若在该目录上已经设置了配额，则将原配额值替换为指定的配额值。
特别地，若配额值为 0，则表示不对该项配额进行限制。若在应用新的配额值后，
该文件系统配额变为不满足，那么该指令执行不成功。
*/
bool quota(){string path;long long ld,lr;cin>>path>>ld>>lr;//若配额值为 0，则表示不对该项配额进行限制ld=(ld==0)?inf:ld;lr=(lr==0)?inf:lr;vector<string> fileNames=split(path);vector<file *> filePtrs=findFile(fileNames);if(filePtrs.size()!=fileNames.size()){return false;}//没有该目录if(!filePtrs.back()->isDir){return false;}//不是一个目录文件//若在应用新的配额值后，该文件系统配额变为不满足，那么该指令执行不成功。
//if(filePtrs.back()->sd>ld||filePtrs.back()->sr>lr){return false;}//判断修改后该目录的sd、sr是否溢出//完成配额修改操作（配额更新）filePtrs.back()->ld=ld;filePtrs.back()->lr=lr;return true;
}
int main(){ios::sync_with_stdio(false);int n;cin>>n;while(n--){char op;cin>>op;bool res;switch(op){case 'C':{res=create();break;}case 'R':{res=remove();break;}case 'Q':{res=quota();break;}}if(res){cout<<"Y\n";}else{cout<<"N\n";}}return 0;
}

这篇关于山东大学计算机科学与技术学院程序设计思维与实践作业 week9-复杂模拟题的普适性方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/404015。

相关文章

C/C++错误信息处理的常见方法及函数

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,：本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例：2. strerror()示例：3. perror(
阅读更多...
CSS去除a标签的下划线的几种方法

CSS去除a标签的下划线的几种方法

《CSS去除a标签的下划线的几种方法》本文给大家分享在CSS中，去除a标签（超链接）的下划线的几种方法，本文给大家介绍的非常详细，感兴趣的朋友一起看看吧... 在 css 中，去除a标签（超链接）的下划线主要有以下几种方法：使用text-decoration属性通用选择器设置：使用a标签选择器，将tex
阅读更多...
C++变换迭代器使用方法小结

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析：transform_iterator1. transform_iterat
阅读更多...
C++中std::distance使用方法示例

C++中std::distance使用方法示例

《C++中std::distance使用方法示例》std::distance是C++标准库中的一个函数,用于计算两个迭代器之间的距离,本文主要介绍了C++中std::distance使用方法示例,具... 目录语法使用方式解释示例输出：其他说明：总结std::distance&n编程bsp;是 C++ 标准
阅读更多...
SpringBoot3实现Gzip压缩优化的技术指南

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N
阅读更多...
Linux换行符的使用方法详解

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将
阅读更多...
SpringBoot实现数据库读写分离的3种方法小结

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一：基于AbstractRoutingDataSource实现动态
阅读更多...
Java中的String.valueOf()和toString()方法区别小结

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法
阅读更多...
Java中List的contains()方法的使用小结

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论：List 的 contain
阅读更多...
Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2