个人AC代码如下,都能动笔总的来说就是要细心,然后卡点时心态稳住:)
题目已加入教育商店https://pintia.cn/market/item/1336191275793412096
7-1 The Closest Fibonacci Number (20point(s))
#include<iostream>
using namespace std;
const int N=110;
int a[N];
int main(){
int n;
cin>>n;
a[0]=a[1]=1;
int maxn=N;
for(int i=2;i<N;i++){//斐波拉契打表
a[i]=a[i-1]+a[i-2];
if(a[i]>1e8){//不会超过1e8
maxn=i;
break;
}
}
for(int i=0;i<maxn;i++)
if(n>=a[i]&&n<=a[i+1]){
int x=a[i],y=a[i+1];
if(abs(x-n)<=abs(y-n))
printf("%d\n",x);
else printf("%d\n",y);
return 0;
}
return 0;
}
7-2 Subsequence in Substring (25point(s))
#include<iostream>
#include<cstring>
using namespace std;
int main(){
// freopen("1.txt","r",stdin);
string str,tar;
cin>>str>>tar;
int minlen=str.size()+1;
string ans;
for(int i=0;i+tar.size()<=str.size();i++){//双指针枚举左右端点
int j=i,pos=0;//pos用来记录匹配到目标串哪个位置
for(;j<=str.size()&&pos<tar.size();j++)
if(str[j]==tar[pos])
pos++;
if(pos==tar.size())//刚好匹配完
if(j-i<minlen){
minlen=j-i;
ans=str.substr(i,minlen);
}
}
cout<<ans<<endl;
return 0;
}
7-3 File Path (25point(s))
#include<iostream>
#include<cstring>
#include<unordered_set>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N=10000;
int p[N];
int n,k;
unordered_set<int> st;
unordered_map<int,int> mp;//空格数对应点
int main(){
// freopen("2.txt","r",stdin);
scanf("%d\n",&n);//千万要记得整行读入时要读掉上一行的回车
memset(p,-1,sizeof p);//存父节点初始化为-1
int kon1=0,num1=0;
for(int i=0;i<n;i++){//根据长度放到每一行中,相邻的层数少1的
string str;
getline(cin,str);
int num=stoi(str);//对应数
st.insert(num);
int kon=0;//当前空格数
while(str[kon]==' ') kon++;
if(kon!=0){//当前空格数变大则是上一个点的孩子结点
if(kon>kon1){
p[num]=num1;
}
else{
p[num]=p[mp[kon]];//当前空格数变小或者不变,父节点为上一个空格数相同的点的父节点
}
}
mp[kon]=num;//空格数相同的上一个存过的点
kon1=kon;//上一个点的空格数
num1=num;//上一个点的值
}
cin>>k;
while(k--){
int x;
cin>>x;
if(st.count(x)==0) printf("Error: %04d is not found.\n",x);
else{
vector<int> ans;
for(int i=x;i!=-1;i=p[i]) ans.push_back(i);
cout<<"0000";
for(int i=ans.size()-2;i>=0;i--)
printf("->%04d",ans[i]);
cout<<endl;
}
}
return 0;
}
7-4 Chemical Equation (30point(s))
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m,k;
int pro[N];
bool ori[N],vis[N];
int idx;//公式编号
string format[N];//字符串形式的公式,方便打印输出
vector<int> P[N];//生成产物对应公式编号
vector<int> O[N];//公式编号对应原料
bool dfs(int u,vector<string> &ans){
if(u==m){//找完了所有产物的公式
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<endl;
return true;
}
for(int i=0;i<P[pro[u]].size();i++){//遍历当前产物的所有方案
int x=P[pro[u]][i];//第u个产物的第i个方案
bool success=true;
for(int j=0;j<O[x].size();j++){//遍历当前方案的所有原料
int y=O[x][j];//第u个产物的第i个方案的第j个原料
if(ori[y]==false||vis[y]==true){//如果没有该种原料或者已经用过则不合法,应跳过
success=false;
break;
}
}
if(success==false) continue;
for(int j=0;j<O[x].size();j++)//合法方案记录为用过
vis[O[x][j]]=true;
ans.push_back(format[x]);//加入该方案
if(dfs(u+1,ans)) return true;//只要打印最先满足条件的方案
for(int j=0;j<O[P[pro[u]][i]].size();j++)//恢复现场
vis[O[P[pro[u]][i]][j]]=false;
ans.pop_back();
}
return false;
}
bool cmp(int a,int b){//对不同公式排序,原料小的公式放前面
for(int i=0;;i++)
if(O[a][i]!=O[b][i])//字典序比较,小的方案放前面
return O[a]<O[b];
}
int main(){
// freopen("3.txt","r",stdin);
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
ori[x]=true;//标记所有原料
}
cin>>m;
for(int i=0;i<m;i++){
cin>>pro[i];
if(ori[pro[i]]){//产物也是原料
if(pro[i]>=0&&pro[i]<=9)
format[idx]="0"+to_string(pro[i])+" -> "+"0"+to_string(pro[i]);
else
format[idx]=to_string(pro[i])+" -> "+to_string(pro[i]);
P[pro[i]].push_back(idx);
O[idx].push_back(pro[i]);
idx++;
}
}
cin>>k;
getchar();//读掉末尾换行,防止getline出错
while(k--){
string str;
getline(cin,str);
format[idx]=str;
int a=stoi(str.substr(str.size()-2));//取出公式产物
P[a].push_back(idx);
vector<int> temp;
temp.clear();
for(int i=0;i<str.size()-6;i+=5){
int b=stoi(str.substr(i,2));//取出公式原料
temp.push_back(b);
}
O[idx]=temp;
idx++;
}
for(int i=0;i<m;i++)//对所有产物的编号对应公式排序
sort(P[pro[i]].begin(),P[pro[i]].end(),cmp);
vector<string> ans;//存结果
dfs(0,ans);
return 0;
}
想做真题只能购买吗?
是的,购买就是3h模拟,参加当场考完之后也只能绑定看代码,不能再提交
膜拜大佬
我是菜🐶