二级网站免费建,打电话叫人做网站,网站添加icp备案号,企业简介宣传片视频个人学习记录#xff0c;代码难免不尽人意。 今天又斥资买了今年春季的真题一试#xff0c;呃#xff0c;感觉尽力了#xff0c;89分#xff0c;在当年排名23#xff0c;感觉还不错#xff0c;没有出现读不懂的题目和没有思路的情况#xff0c;扣的11分分别是第二题两个… 个人学习记录代码难免不尽人意。 今天又斥资买了今年春季的真题一试呃感觉尽力了89分在当年排名23感觉还不错没有出现读不懂的题目和没有思路的情况扣的11分分别是第二题两个测试点超时其实考试时已经有解决思路了只是时间到了没有提交上其中一个测试点超时我在考完试后五分钟解决了还有最后一个大题有一个测试点错误。这个我现在也想明白了忘记判断必须是“心型”了光是对称的不够必须满足叶子节点的高度是先增再减再增再减的当时忘了唉不过题目给的数据到是挺集中这个条件只有一个过不去
A-1 The Winner over Squares and Primes This is about a game of fighting all the squrare numbers and prime numbers.
At the very beginning, N people are sitting in N seats, and the seats are numbered from 1 to N, from left to right. Then for all the seats with their numbers being squares (such as 1, 4, 9, 16, …), those people sitting in must leave, and everyone else must shift toward left so that there is no empty seat between any of them. If there are more than one people left, the game continues, but instead of square numbers, this round will let everyone sitting in the prime seats leave, and then the rest of them will shift to fill the empty seats again.
The game continues with checking the square seats and prime seats alternatively, until there is only one winner left. You are supposed to tell the initial seat number for this winner.
Input Specification: Each input file contains one test case, in which a positive integer N (≤10 5 ) is given.
Output Specification: For each test case, print in a line the initial seat number for this winner.
Sample Input: 10 Sample Output: 6 Hint: Round 1: People sitting in square seats 1, 4, and 9 will leave. The initial seat numbers for the rest of them sitting from 1 to 7 are 2, 3, 5, 6, 7, 8, 10.
Round 2: People sitting in prime seats 2, 3, 5, and 7 will leave. The initial seat numbers for the rest of them sitting from 1 to 3 are 2, 6, 8.
Round 3: People sitting in square seat 1 will leave. The initial seat numbers for the rest of them sitting from 1 to 2 are 6, 8.
Round 4: People sitting in prime seat 2 will leave. The initial seat numbers for the final winner is 6.
#includeiostream
#includecstdio
#includevector
#includealgorithm
#includecmath
using namespace std;
vectorint res,temp;
const int maxn100100;//写成10010最后三个测试点过不去。
int hashtable[maxn]{0};
void getsquare(){int i1;while(i*imaxn){hashtable[i*i]1;i;}
}
bool isprime(int n){if(n1) return false;int mid(int)sqrt(1.0*n);for(int i2;imid;i){if(n%i0) return false;}return true;
}
int main(){int n;scanf(%d,n);for(int i1;in;i){res.push_back(i);}getsquare();while(res.size()1){for(int i0;ires.size();i){if(hashtable[i1]!1){temp.push_back(res[i]);}}res.clear();for(int i0;itemp.size();i){if(!isprime(i1)){res.push_back(temp[i]);}}temp.clear();}printf(%d\n,res[0]);} 很简单的一道题先求出平方数表然后判断即可。
A-2 LRU-K Least Recently Used (LRU) cache scheme is to remove the least recently used frame (the one hasn’t been used for the longest amount of time) when the cache is full and a new page is referenced which is not there in cache.
LRU-K is a variant of the LRU algorithm, where K represents the number of recent uses. LRU can be considered as LRU-1. Unlike LRU, the LRU-K requires the maintenance of two different queues (for historical access and cache). The data in the historical access queue is not moved to the cache queue until the data is hit K times.
For example, assuming that the length of both queues is 5, and the memory is initialized to be empty. LRU-2 is used to process the data sequence in order: 9567838959834756. The changes of the historical access queue and the cache queue are shown in the following table: Your job is to implement this LRU-K cache scheme.
Input Specification: Each input file contains one test case. For each case, the first line gives 3 positive integers: K (≤5), N (≤10 4 ) and M (≤10 5 ) which are the number of hits for cache, the size of the queues (assuming both queues have the same size) and the number of referenced page ID’s. Then M referenced page ID’s are given in the next line. A page ID is a number in the range [1,2×10 4 ]. All the numbers in a line are separated by a space.
Output Specification: For each test case, output in the first line the page ID’s in the historical access queue, and in the second line, those in the cache queue. The ID’s are ordered from front to rear of each queue. All the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line. In case that a queue is empty, output - in a line instead.
Sample Input 1: 2 5 17 9 5 6 7 8 3 8 9 5 9 8 3 4 7 5 6 9 Sample Output 1: 4 9 8 3 7 5 6 Sample Input 2: 3 5 10 9 5 6 7 8 3 8 9 5 9 Sample Output 2: 7 3 8 5 9
20分代码应该是
#includeiostream
#includecstdio
#includevector
#includealgorithm
#includecmath
#includeunordered_set
#includeset
using namespace std;
unordered_setint v1,v2;
const int maxn100100;
int list[maxn];
int hashtable[maxn]{0};int main(){int k,n,m;scanf(%d %d %d,k,n,m);for(int i0;im;i)
{scanf(%d,list[i]);
}for(int i0;im;i){unordered_setint::iterator it2v2.find(list[i]);if(it2!v2.end()){v2.erase(it2);v2.insert(list[i]);}else{unordered_setint::iterator it1v1.find(list[i]);if(it1v1.end()){if(v1.size()n){v1.insert(list[i]);}else{int cntv1.size();unordered_setint::iterator tempv1.begin();for(int i0;icnt-1;i){temp;}v1.erase(temp);v1.insert(list[i]);}}else{//hithashtable[list[i]];if(hashtable[list[i]]k-1){v1.erase(it1);if(v2.size()n){v2.insert(list[i]);}else{int cntv2.size();unordered_setint::iterator tempv2.begin();for(int i0;icnt-1;i){temp;}v2.erase(temp);v2.insert(list[i]);}}else{v1.erase(it1); v1.insert(list[i]);} }}//if(v1.empty()) printf(-\n);
// else{
// int cntv1.size();
// for(unordered_setint::iterator itv1.begin();it!v1.end();it){
// printf(%d,*it);
// cnt--;
// if(cnt0) printf( );
// else printf(\n);
// }
// }
// if(v2.empty()) printf(-);
// else{
// int cntv2.size();
// for(unordered_setint::iterator itv2.begin();it!v2.end();it){
// printf(%d,*it);
// cnt--;
// if(cnt0) printf( );
//
// }
// }
// printf(-----------------------------------------\n); }vectorint vec1,vec2; for(unordered_setint::reverse_iterator itv1.rbegin();it!v1.rend();it){vec1.push_back(*it);}for(unordered_setint::iterator itv2.begin();it!v2.end();it){
vec2.push_back(*it);}
if(v1.empty()) printf(-\n);
else{for(int ivec1.size()-1;i0;i--){printf(%d,vec1[i]);if(i!0)printf( );else printf(\n);}
}if(v2.empty()) printf(-);else{for(int ivec2.size()-1;i0;i--){printf(%d,vec2[i]);if(i!0)printf( );}}} 这道题不是很难想但是有两个测试点用vector来做一定会超时涉及太多的删除和移动因此我们遇到频繁删除和移动的题尽量用set或者map来做在我改了之后代码应该可以过除了最后一个测试点以外的点。
A-3 K Vertex Given a directed graph, a K-vertex is a vertex of which the out degree is larger than the indegree. For example, the vertices a and b in the figure are K-vertices. Your job is to list all the K-vertices in a given graph.
Input Specification: Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤200) and M, which are the number of vertices and the number of edges, respectively. Then M lines follow, each gives a directed edge v1, v2 in the format:
v1 v2 Here we assume that all the vertices are numbered from 0 to N−1. It is guaranteed that v1 is never the same as v2.
Finally a line of N strings is given, where the i-th string corresponds to the key of the i-th vertex (i0,⋯,N−1). Each string consists of no more than 2 lower-cased English letters.
Output Specification: Output the keys of all the K-vertices, each occupies a line, in alphabetical order. It is guaranteed that there is at least one output.
Sample Input: 4 5 0 1 2 1 3 1 2 0 3 2 c d b a Sample Output: a b
#includeiostream
#includecstdio
#includevector
#includealgorithm
#includecmathusing namespace std;
const int maxn210;
const int INF1000000000;
int G[maxn][maxn];
int indegree[maxn]{0};
int outdegree[maxn]{0};
vectorstring v;
int main(){for(int i0;imaxn;i){for(int j0;jmaxn;j){G[i][j]INF;}}int n,m;scanf(%d %d,n,m);for(int i0;im;i){int a,b;scanf(%d %d,a,b);G[a][b]1;indegree[b];outdegree[a];}for(int i0;in;i){string str;cin str;if(outdegree[i]indegree[i]){v.push_back(str);}}sort(v.begin(),v.end());for(int i0;iv.size();i){cout v[i];if(i!v.size()-1) cout endl;}
}
有些简单了…
A-4 Tree of Love If a binary tree has its left and right subtrees perfectly symmetric. And more, if from left to right, the depths of leaves are first in increasing (or non-decreasing) then decreasing (or non-increasing), then again increasing (or non-decreasing), and finally decreasing (or non-increasing) order, then the shape of this tree looks like a heart (as shown by the above figure), and hence is called “Tree of Love”.
Given the inorder and postorder traversal sequences of a binary tree, your job is to construct this tree and test if it is a tree of love, and output its outer contour外轮廓. “Outer contour” consists of nodes visited from the root, along the left most path to a leaf, then all the leaves from left to right, and finally back to the root along the right most path.
Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (100), which is the number of nodes in the tree. Then the next two lines each contains N positive keys as the inorder and postorder traversal sequences, respectively. All the keys are distinct integers no more than 10 3 . The numbers in a line are separated by spaces. It is guaranteed that a unique binary tree can be constructed from the input.
Output Specification: For each test case, if the tree is a tree of love, output Yes in the first line, or No if not. Then output the outer contour in the second line.
All the numbers in a line must be separated by 1 space, and there must be no extra space at the beginning or the end of the line.
Sample Input 1: 27 5 4 6 22 3 23 7 20 2 21 8 18 9 1 10 19 11 24 17 25 12 26 16 27 13 15 14 5 6 22 4 7 23 20 3 8 21 9 18 2 10 11 24 19 12 26 25 13 27 14 15 16 17 1 Sample Output 1: Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Sample Input 2: 11 4 8 10 2 5 1 6 3 9 11 7 10 8 4 5 2 6 11 9 7 3 1 Sample Output 2: No 1 2 4 10 5 6 11 7 3 Hint for Sample 2: The answer is No because the tree is not symmetric. It would be Yes if we swap 9 and 11 in the inorder sequence.
28分代码
#includeiostream
#includecstdio
#includevector
#includealgorithm
#includecmath
#includequeue
using namespace std;
const int maxn210;
int in[maxn];
int post[maxn];
vectorint v;
struct node{int data;node* lchild;node* rchild;
};
node* newnode(int data){node* rootnew node;root-datadata;root-lchildNULL;root-rchildNULL;return root;
}
node* create(int postl,int postr,int inl,int inr){if(postlpostr) return NULL;int midpost[postr];int index;for(int iinl;iinr;i){if(in[i]mid){indexi;break;}}int leftnumindex-inl;node* rootnewnode(mid);root-lchildcreate(postl,postlleftnum-1,inl,index-1);root-rchildcreate(postlleftnum,postr-1,index1,inr);return root;
}
bool bfs(node* left,node* right){queuenode* q1,q2;q1.push(left);q2.push(right);while(!q1.empty()!q2.empty()){node* lefttempq1.front();q1.pop();node* righttempq2.front();q2.pop();int tag10,tag20,tag30,tag40;if(lefttemp-lchild!NULL){q1.push(lefttemp-lchild);tag11; }if(lefttemp-rchild!NULL){q1.push(lefttemp-rchild);tag21; }//右子树应该先入右子树节点 if(righttemp-rchild!NULL){q2.push(righttemp-rchild);tag31; }if(righttemp-lchild!NULL){q2.push(righttemp-lchild);tag41; }if(tag1!tag3||tag2!tag4){
// cout lefttemp-dataendl;
// cout righttemp-dataendl;
// cout tag1tag3tag2tag4endl; return false;}}if(!q1.empty()||!q2.empty()){return false;} else return true;
}
void dfs(node* root){if(rootNULL) return;dfs(root-lchild);if(root-lchildNULLroot-rchildNULL){v.push_back(root-data);}dfs(root-rchild);
}
void getleft(node* root){if(rootNULL) return;if(!(root-lchildNULLroot-rchildNULL))v.push_back(root-data);getleft(root-lchild);
}
void getright(node* root){if(rootNULL) return;getright(root-rchild);if(!(root-lchildNULLroot-rchildNULL))v.push_back(root-data);
}
int main(){int n;scanf(%d,n);for(int i0;in;i){scanf(%d,in[i]);}for(int i0;in;i){scanf(%d,post[i]);}node* rootcreate(0,n-1,0,n-1);bool flag;if(root-lchildNULLroot-rchildNULL){//测试点2需要特判数量为1 printf(Yes\n);printf(%d,root-data);return 0;}if(root-lchildNULLroot-rchild!NULL||(root-rchildNULLroot-lchild!NULL)){flagfalse;}else flagbfs(root-lchild,root-rchild);if(!flag){printf(No\n);}else printf(Yes\n);getleft(root);dfs(root);getright(root);v.pop_back();//右边多加了一个根节点 for(int i0;iv.size();i){printf(%d,v[i]);if(i!v.size()-1) printf( );}}
这道题我忘记判断叶子节点的高度必须从左到右满足先增后减再增再减了如果想要补上的话应该用bfs更新每个节点的高度同时将所有叶子节点的高度存储在数组中查看是不是先增后减再增再减这个也好判断设置信标即可如果是再输出yes。
