本文主要是介绍南京大学机试试题合集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
🍰🍰🍰hello宝子们,今天我们来练习南京大学的机试题目,这些题目的缺点就是太老了,都是18或19年的题,大家就练练手。加油!fighting!( •̀ ω •́ )✧
🍩1161 二叉树遍历
#include<bits/stdc++.h>
using namespace std;
string s;
int len;
typedef struct node{char data;struct node *lchild,*rchild;
}*bitree;bitree create(bitree &t){if(len>=s.size()) return NULL;char data=s[len];len++;if(data!='#'){t=(bitree)malloc(sizeof(bitree));t->data=data;t->lchild=NULL;t->rchild=NULL;t->lchild=create(t->lchild);t->rchild=create(t->rchild);}return t;
}
void inorder(bitree &t){if(t!=NULL){inorder(t->lchild);cout<<t->data<<" ";inorder(t->rchild);}
}
int main(){while(cin>>s){len=0;bitree t;bitree tree=create(t);inorder(tree);cout<<endl;}return 0;
}
🍩1692 Distinct Subsequences🍦
//摘自N诺用户:csYfZhang
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1005
#define MOD 1000000007
int main(){long long dp[MAX][MAX];//表示 T 前 i 字符串可以由 S 前 j 字符串组成的最多个数int n; cin>>n;while(n--){string s,t;cin>>s>>t;s=' '+s;t=' '+t;int l1=s.size(),l2=t.size();for(int i=1;i<l2;i++)for(int j=1;j<l1;j++) dp[i][j]=0;int lens=s.size(),lent=t.size();for(int i=0;i<lens;i++) dp[0][i]=1;for(int i=1;i<lent;i++){for(int j=i;j<lens;j++){if(t[i]==s[j])dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%MOD;//dp[i][j-1]类似于不选s[j]能凑成t[1...i]的个数,dp[i-1][j-1]则为选s[j]能凑成t[1...i]的个数else dp[i][j]=dp[i][j-1];//当 S[j] != T[i] , dp[i][j] = dp[i][j-1](不想等,只能不选s[j])}}cout<<dp[l2-1][l1-1]<<endl;}return 0;
}
🍩1690 Stepping Numbers🍦
//摘自N诺用户:Ashionial
#include <bits/stdc++.h>
using namespace std;
const long long N = 3e8 + 10;
int main()
{vector<long long> num={10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98};int n=num.size();queue<long long> q;for(int i=0;i<n;i++) q.push(num[i]);//预处理,直接求出来所有满足的数while(!q.empty()){long long cur=q.front();q.pop();if(cur>=N) break;int end=cur%10;//最后一位数if(end>=1){long long tmp=cur*10+end-1;num.push_back(tmp);q.push(tmp);}if(end<=8){long long tmp=cur*10+end+1;num.push_back(tmp);q.push(tmp);}}long long T;cin>>T;while(T--){long long l,r;cin>>l>>r;long long s=lower_bound(num.begin(),num.end(),l)-num.begin();//lower_bound找到区间第一个大于等于l的数的位置long long e=lower_bound(num.begin(),num.end(),r)-num.begin();cout<<e-s+(num[e]==r?1:0)<<endl;}return 0;
}
🍩1691 Nodes from the Root🍦
//摘自N诺用户:lianghl
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3fvoid solve(int n,int y,vector<vector<int>> edges){vector<vector<int>> g(n,vector<int>(n,-1));int r=-inf,l=inf;for(auto e:edges){int u=e[0],v=e[1],w=e[2];g[u][v]=w;r=max(r,w);l=min(l,w);}auto check=[&](int thr)->bool{int cnt=1;vector<int> q {0};vector<bool> vis(n);vis[0]=true;while(!q.empty()){vector<int> p(q);q.clear();for(auto x:p){for(int y=0;y<n;y++){if (!vis[y]&&g[x][y]>=thr) {cnt++;vis[y]=true;q.push_back(y);}}}}return cnt<=y;};auto bisect=[&](int i,int j){while(i<=j){int mid=(i+j)/2;if(!check(mid)) i=mid+1;else j=mid-1;}return i;}; cout<<bisect(l, r)<<endl;
}int main() {int T; cin>>T;while(T--){int n, y; cin >> n >> y;vector<vector<int>> edges(n-1);for(int i = 0; i < n-1; i++) {int u, v, w;cin >> u >> v >> w;edges[i] = {u, v, w};}solve(n, y, edges);}
}
🍩1895 子序列
#include<bits/stdc++.h>
using namespace std;
int main(){string a,b;int n,ans=0;string res;cin>>a>>n;int lena=a.size(),lenb;int dp[2005][2005]={0};while(n--){for(int i=0;i<2005;i++)for(int j=0;j<2005;j++)dp[i][j]=0;cin>>b;lenb=b.size();for(int i=1;i<=lena;i++){for(int j=1;j<=lenb;j++){if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}if(ans<dp[lena][lenb]){ans=dp[lena][lenb];res=b;}}cout<<res<<endl<<ans;return 0;
}
🍩1894 奶牛位置🍦
//摘自N诺用户:cccclr
//自己填的注释,有不懂的地方欢迎评论区留言
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N];//dp[i]记录到当前位置i需要花费的最少时间
int path[N];//path[i]记录从哪走到了i
int main(){memset(dp,0,sizeof(dp));memset(path,0,sizeof(path));int s,t;cin>>s>>t;vector<int> a;if(s>0){dp[s-1]=1;//从s到s-1要走1步path[s-1]=s;//从s走到了s-1}dp[s]=0;//从s到s不用走path[s]=-1;//-1表示到头了dp[s+1]=1;//从s到s+1要走1步path[s-1]=s;//从s走到了s-1for(int i=s+2;i<=t+1;i++){int pos=i/2;if(i%2==0){//可以从pos的位置经过一次*2到达if(dp[pos]<dp[i-1]){//这里在对比从pos位置*2花费时间更少还是从前一个位置后移一位花费时间更少dp[i]=dp[pos]+1;//通过一步*2从pos到达当前位置ipath[i]=pos;//从pos走到了iwhile(dp[i-1]>dp[i]+1){//这是松弛的步骤:就是说,这种情况下从当前位置i到前边一个位置用时比之前记录的方法更短dp[i-1]=dp[i]+1;path[i-1]=i;//从i走到了i-1}}else{//从前一个位置后移一位花费时间更少dp[i]=dp[i-1]+1;path[i]=i-1;//从i-1走到了i}}else{//不能通过*2到达,那么当前位置只能通过从前一个位置向后走一步到达dp[i]=dp[i-1]+1;//考虑从后一个位置向前走一步到达会报错path[i]=i-1;//从i-1走到了i}}cout<<dp[t]<<endl;//输出最少花费时间for(int i=t;path[i]!=-1;){//逆着回去找所有的路径a.push_back(i);i=path[i];}a.push_back(s);for(int i=a.size()-1;i>=0;i--){cout<<a[i];if(i>0) cout<<"->";}return 0;
}
创作不易,点个赞吧~感兴趣的宝子欢迎关注本专栏和我们一起学习机试内容哦~
宝子们学习辛苦啦,休息下,我们下部分再见!👋( •̀ ω •́ )✧ ~
大家还想看哪个学校的机试题目,评论区告诉我~~~
这篇关于南京大学机试试题合集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!