首页 > 代码库 > 九度OJ&北邮机试题题解(北邮2010网院)
九度OJ&北邮机试题题解(北邮2010网院)
题目一、九度OJ-1173:查找(水题随便搞)
ac.jobdu.com/problem.php?pid=1173
- 题目描述:
输入数组长度 n
输入数组 a[1...n]
输入查找个数m
输入查找数字b[1...m]
输出 YES or NO 查找有则YES 否则NO 。
- 输入:
输入有多组数据。
每组输入n,然后输入n个整数,再输入m,然后再输入m个整数(1<=m<=n<=100)。
- 输出:
如果在n个数组中输出YES否则输出NO。
- 样例输入:
5 1 5 2 4 3 3 2 5 6
- 样例输出:
YES YES NO
水题,随便搞,直接查询时间复杂度O(n),二分查询时间复杂度O(logn),但是数据无序,排序O(nlogn),看自己喜好吧。
AC代码:
<span style="font-size:18px;">/** *@xiaoran *太水 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int main() { int a[105],n,m,k; while(cin>>n){ for(int i=0;i<n;i++) cin>>a[i]; cin>>m; int x; for(int i=0;i<m;i++){ cin>>x; for(k=0;k<n;k++){ if(x==a[k]) break; } if(k==n) cout<<"NO"<<endl; else cout<<"YES"<<endl; } } return 0; } </span>
题目二、九度OJ-1174:查找第K小数
http://ac.jobdu.com/problem.php?pid=1174
- 题目描述:
查找一个数组的第K小的数,注意同样大小算一样大。
如 2 1 3 4 5 2 第三小数为3。
- 输入:
输入有多组数据。
每组输入n,然后输入n个整数(1<=n<=1000),再输入k。
- 输出:
输出第k小的整数。
- 样例输入:
6 2 1 3 5 2 2 3
- 样例输出:
3
题目是一个经典问题,有好多解释,这里让求不重复的第k小的值,排序+查询,a[i]!=a[i-1],k++。
AC代码:
<span style="font-size:18px;">/** *@xiaoran */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int a[1005]; int main() { int n,k; while(cin>>n){ for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); cin>>k; if(k==1){ cout<<a[0]<<endl; continue; } int j=1; for(int i=1;i<n;i++){ if(a[i]!=a[i-1]) ++j; if(j==k){ cout<<a[i]<<endl; break; } } } return 0; } </span>
题目三、九度OJ-1175:打牌
http://ac.jobdu.com/problem.php?pid=1175
- 题目描述:
牌只有1到9,手里拿着已经排好序的牌a,对方出牌b,用程序判断手中牌是否能够压过对方出牌。
规则:出牌牌型有5种
[1]一张 如4 则5...9可压过
[2]两张 如44 则55,66,77,...,99可压过
[3]三张 如444 规则如[2]
[4]四张 如4444 规则如[2]
[5]五张 牌型只有12345 23456 34567 45678 56789五个,后面的比前面的均大。
- 输入:
输入有多组数据。
每组输入两个字符串(字符串大小不超过100)a,b。a字符串代表手中牌,b字符串代表处的牌。
- 输出:
压过输出YES 否则NO。
- 样例输入:
12233445566677 33
- 样例输出:
YES
首先说一下自己刚开始的错误的思路,我刚开始以为是个查询问题,我的思路是记录所有的出牌的可能,对于当前出牌b,判断在a中是否有所有的出牌的选择,并大于b,最后终于找到反例,例如:a:11222334455667788;b:12345,显然是可以压上的。嘿嘿~,读者可能没有看懂,这里就给出错误程序了,直接来正确的代码了,首先记录每张牌的个数,很简单,看代码吧。
AC代码:
<span style="font-size:18px;">/** *@xiaoran *刚开始以为是查找问题,wa了n次 *其实只需要模拟判断即可 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int main() { string s,ss; while(cin>>s>>ss){ int len=ss.size(),len1=s.size(),ok=0; int a[10]={0}; if(len>5){ cout<<"NO"<<endl; continue; } for(int i=0;i<len1;i++){ a[s[i]-'0']++;//记录每张牌的次数 } if(len<5){ for(int i=ss[0]-'0'+1;i<=9;i++){//找比当前排大的排的个数,是否满足 if(a[i]>=len){ ok=1; break; } } } if(len==5){ for(int i=ss[0]-'0'+1;i<=5;i++){//找比当前排大的排的个数,是否满足 if(a[i]&&a[i+1]&&a[i+2]&&a[i+3]&&a[i+4]){ ok=1; break; } } } if(ok) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } </span>
题目四、九度OJ-1176:树查找
http://ac.jobdu.com/problem.php?pid=1176
- 题目描述:
有一棵树,输出某一深度的所有节点,有则输出这些节点,无则输出EMPTY。该树是完全二叉树。
- 输入:
输入有多组数据。
每组输入一个n(1<=n<=1000),然后将树中的这n个节点依次输入,再输入一个d代表深度。
- 输出:
输出该树中第d层得所有节点,节点间用空格隔开,最后一个节点后没有空格。
- 样例输入:
4 1 2 3 4 2
- 样例输出:
2 3
此题可以建树,也可以i不建树,这里给出不建树的方法,模拟下标和层的关系,看第i层的元素,他们的开始下标是
2^(i-1)~2^i-1,直接输出吧,注意最后一层就行了。
AC代码:
<span style="font-size:18px;">/** *@xiaoran *直接模拟树的层数和下标的关系进行输出 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int a[1010]; int main() { int n,k; while(cin>>n){ for(int i=1;i<=n;i++) cin>>a[i]; cin>>k; int b,i,j,ok; b=(int) (pow(2,k-1)+0.5); if(b>n) cout<<"EMPTY"<<endl; else{ ok=0; for(i=b,j=0;i<=n&&j<b;i++,j++){ if(ok==0){ cout<<a[i]; ok=1; }else{ cout<<" "<<a[i]; } } cout<<endl; } } return 0; } </span>
九度OJ&北邮机试题题解(北邮2010网院)