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最新資料推薦