2019兰州大学计算机科学与技术复试机试试题

from2016cxg · 发表于 2019-3-17 10:39

A. Given a sequence of numbers, find a sub-sequence of the numbers, whose summation is the largest.
For example, -2 11 -4 13 -2, the largest sub-sequence in summantion is 11 -4 13. We are required to output the value of the summation and the positions the sub-sequence begins and ends. So the programe's output comes as 20 2 4 Input format: 5

-2 11 -4 13 -2
output format:
20 2 4
Here is my code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std ;
const int M = 2 * 10000 + 10 ;
int p[M], q[M], A[M] ;
int main(){
int N ;
cin>>N ;
for( int i = 0 ; i<N; i++ ){
cin>>A[i] ;
}
p[0] = A[0] ;
q[0] = 0 ;
for( int i = 1 ; i<N ; i ++ ){
if( p[i-1] <= 0 ){
p[i] = A[i] ;
q[i] = i ;
}
else {
p[i] = p[i-1] + A[i] ;
q[i] = q[i-1] ;
}
}
int val = p[0], bg = q[0], ed = q[0] ;
for( int i = 0 ; i<N ; i++ ){
if( p[i] > val ){
val = p[i] ;
bg = q[i] ;
ed = i ;
}
}
cout<<val<<" "<< bg+ 1<<" "<<ed + 1<<endl;
return 0 ;
}
/* Test example
4
-2 11 -4 13
*/

复制代码

B: Given the frequency of every letter, use them to create a Haffman Tree and calculate the weighted path length. Output the weighted path length.
Input format:
8
19 21 2 3 6 7 10 32
output format:
261
Here is my code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std ;
// weighted routing length of HAFFMAN Tree
// 1. priority_queue to process constructing the tree
// 1. each time get the top 2 node to and merge them to a new one and push it into the heap
// 2. untill there is only one node left, for each new node, give a new tag and create a tree
// 2. traverse the tree and tag the leaf node by the level of its position
struct Node{
int val, pos ;
Node( int a , int b ): val( a ), pos( b){}
friend bool operator <( Node left, Node right){
if( left.val == right.val ) return left.pos > right.pos ;
return left.val > right.val ;
}
} ;
priority_queue< Node > pq ;
const int M = 2 * 10000 + 10 ;
vector<int> p[M] ;
int q[M] ;
int N , val , N1 ;
int target( int father, int level ){
if( father < N )
return q[father] * level ;
return target( p[father][0], level + 1 ) + target( p[father][1] , level + 1 ) ;
}
int main(){
cin>> N ;
N1 = N ;
for( int i = 0 ; i < N ; i++ ){
cin>>q[i] ;
pq.push( Node(q[i], i ) ) ;
}
while( pq.size() > 1 ){
Node tmp1 = pq.top() ; pq.pop() ;
Node tmp2 = pq.top() ; pq.pop() ;
pq.push( Node( tmp1.val + tmp2.val , N1 ++ ) ) ;
p[ N1-1 ].push_back( tmp1.pos ) ;
p[ N1-1 ].push_back( tmp2.pos ) ;
}
// N1-1 is the father node
cout<< target( N1-1, 0 ) <<endl;
return 0 ;
}
/*
Test example
8
19 21 2 3 6 7 10 32
*/

复制代码

C: Given a string, find the brackets that don't match, for example, )()(, the two brackets in the middle match but the two side, which are red as ) and ( don't have a half bracket to match. We replace ')' with letter '?' and '(' with letter '$'. For the other letters in the string, we replace them by blank space.
Input format:
)(ab)ab)ab(
Output format:
)(ab)ab)ab(
? ? $Here is my

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
#include<queue>
using namespace std ;
/*Bracket Matching
traverse the string,
for letter '(' , push it directly into the stack,
for letter ')' firstly, check whether the stack is empty,
otherwise, get the top letter, if the top letter is letter '(', pop it out,
if not, push ')' into the stack
*/
stack<int> stck ;
int main(){
string str, cpy ;
while( getline(cin, str) ){
cpy = str ;
int len = str.length() ;
for( int i = 0; i < len ; i++ ){
if( str[i] == '(')
stck.push( i ) ;
else if( str[i] == ')'){
if( stck.empty() )
stck.push( i ) ;
else{
if( str[ stck.top() ] == '(' )
stck.pop() ;
else
stck.push( i ) ;
}
}
}
while( !stck.empty()){
if( str[stck.top() ] == ')'){
cpy[stck.top()] = '?' ;
stck.pop() ;
}
else{
cpy[stck.top()] = '
;
stck.pop() ;
}
}
for( int i = 0 ; i<len ; i++ ){
if( ( cpy[i] == '?') ||( cpy[i] == '
) ){
}
else{
cpy[i] = ' ' ;
}
}
cout<<str<<endl;
cout<<cpy<<endl;
}
return 0 ;
}

复制代码

		自动登录	找回密码
密码			注册

[信息院] 2019兰州大学计算机科学与技术复试机试试题

NEW最新资料推荐

浏览过的版块