个人学习记录，代码难免不尽人意。
今天做了做21年的浙大复试上机题，感觉还好，但是第一题没做出来······汗，我觉得是自己阅读理解的问题，题意没有弄清楚，题目本身还是很简单的。
7-1 Square Friends
For any given positive integer n, two positive integers A and B are called Square Friends if by attaching 3 digits to every one of the n consecutive numbers starting from A, we can obtain the squares of the n consecutive numbers starting from B.
For example, given n=3, A=73 and B=272 are Square Friends since 73984=2722, 74529=2732, and 75076=2742.
Now you are asked to find, for any given n, all the Square Friends within the range where A≤MaxA.
Input Specification:
Each input file contains one test case. Each case gives 2 positive integers: n (≤100) and MaxA (≤106 ), as specified in the problem description.
Output Specification:
Output all the Square Friends within the range where A≤MaxA. Each pair occupies a line in the format A B. If the solution is not unique, print in the non-decreasing order of A; and if there is still a tie, print in the increasing order of B with the same A. Print No Solution. if there is no solution.
Sample Input 1:
3 85
Sample Output 1:
73 272
78 281
82 288
85 293
Sample Input 2:
4 100
Sample Output 2:
No Solution.
#include <cmath>
#include <iostream>
using namespace std;
int n;
bool check (int A, int B) {
for (int i = 0; i < n; i++) {
if (B * B / 1000 != A) return false;
A++;
B++;
}
return true;
}
void test () {
int MaxA, i, j, flag = 0;
scanf("%d %d", &n, &MaxA);
for (i = 1; i <= MaxA; i++) {
int B1 = (int)sqrt(i * 1000);
int B2 = (int)sqrt((i+1) * 1000);
for (j = B1; j <= B2; j++) {
if (check(i, j)) {
flag = 1; // 有输出了
printf("%d %d\n", i, j);
};
}
}
if (flag == 0) {
printf("No Solution.");
return;
}
}
int main () {
test();
return 0;
}
第一题我直接空着了，哈哈，根据我刷题的经验，第一题才是出题人能整活的题，后面大题反而都很中规中矩。这道题我看了别人的解析才知道题意：对于n，A，B，使得B2去掉末三位数字等于A，(B+1)2去掉末三位数字等于A+1，以此类推，(B+n-1)2去掉末三位数字等于A+n-1，现在给定n和A的上限MaxA，求所有满足条件的A与B，按照A升序（第一判断标准）且B升序（第二判断标准）输出。如果无解，输出No Solution.。
7-2 One Way In, Two Ways Out
Consider a special queue which is a linear structure that allows insertions at one end, yet deletions at both ends. Your job is to check, for a given insertion sequence, if a deletion sequence is possible. For example, if we insert 1, 2, 3, 4, and 5 in order, then it is possible to obtain 1, 3, 2, 5, and 4 as an output, but impossible to obtain 5, 1, 3, 2, and 4.
Input Specification:
Each input file contains one test case. For each case, the first line gives 2 positive integers N and K (≤10), which are the number of insertions and the number of queries, respectively. Then N distinct numbers are given in the next line, as the insertion sequence. Finally K lines follow, each contains N inserted numbers as the deletion sequence to be checked.
All the numbers in a line are separated by spaces.
Output Specification:
For each deletion sequence, print in a line yes if it is indeed possible to be obtained, or no otherwise.
Sample Input:
5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2
Sample Output:
yes
no
yes
yes
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int INF=1000000000;
const int maxn=10010;
int array[maxn];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&array[i]);
}
for(int i=0;i<m;i++){
int queue[maxn]={INF};
int list[n];
for(int j=0;j<n;j++){
scanf("%d",&list[j]);
}
int left=0,right=0;
bool flag=true;int cnt=0;
int len=0;
for(int j=0;j<n;j++){
// for(int k=left;k<right;k++){
// cout << queue[k] << " ";
// }
// cout << endl;
while(list[j]!=queue[left]&&list[j]!=queue[right]&&cnt<=n-1)
{
if(left==right&&len==0){
queue[right]=array[cnt++];
len++;
}
else{
right++;
queue[right]=array[cnt++];
len++;
}
}
if(list[j]!=queue[left]&&list[j]!=queue[right]&&cnt==n){
flag=false;
break;
}
if(list[j]==queue[left]){
if(left!=right)
left++;
len--;
}
else if(list[j]==queue[right]){
if(left!=right)
right--;
len--;
}
}
if(flag) printf("yes\n");
else printf("no\n");
}
}
第二题当时也让我卡了一会才找到思路，本质就是创建一个如题干所示的队列，然后模拟插入和删除看看给的序列是否符合要求：先插入，看看队列两端是否等于序列对应的元素，如果是，删除，序列向后处理；如果不是，继续插入直到满足是或者全部插入结束，如果全部插入结束了还有序列元素没有对应，那么就是错误的。
我模拟的队列需要注意一点，左指针和右指针代表的是队头和队尾的下标，需要注意的是需要把当前队列中的元素个数保存下来，如果没有元素的话插入时右指针不需要移动，仅仅将个数+1。
7-3 Preorder Traversal
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the last number of the preorder traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 50,000), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the last number of the preorder traversal sequence of the corresponding binary tree.
Sample Input:
7
1 2 3 4 5 6 7
2 1 4 3 7 5 6
Sample Output:
5
#include<iostream>
#include<cstdio>
using namespace std;
int const maxn=50010;
struct node{
int data;
node* lchild;
node* rchild;
};
int post[maxn];
int in[maxn];
int pre[maxn];
node* newnode(int data){
node* root=new node;
root->data=data;
root->lchild=NULL;
root->rchild=NULL;
return root;
}
node* create(int postl,int postr,int inl,int inr){
if(postl>postr) return NULL;
int mid=post[postr];
int index;
for(int i=inl;i<=inr;i++){
if(in[i]==mid){
index=i;
break;
}
}
int leftnum=index-inl;
node* root=newnode(mid);
root->lchild=create(postl,postl+leftnum-1,inl,index-1);
root->rchild=create(postl+leftnum,postr-1,index+1,inr);
return root;
}
int cnt=0;
void dfs(node* root){
if(root==NULL) return;
pre[cnt++]=root->data;
dfs(root->lchild);
dfs(root->rchild);
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&post[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&in[i]);
}
node* root=create(0,n-1,0,n-1);
dfs(root);
printf("%d",pre[n-1]);
}
嗯，不知道该说什么了，还记得我说过第一题才是出题人喜欢整活的题目吗…………
7-4 Load Balancing
Load balancing (负载均衡) refers to efficiently distributing incoming network traffic across a group of backend servers. A load balancing algorithm distributes loads in a specific way.
If we can estimate the maximum incoming traffic load, here is an algorithm that works according to the following rule:
The incoming traffic load of size S will first be partitioned into two parts, and each part may be again partitioned into two parts, and so on.
Only one partition is made at a time.
At any time, the size of the smallest load must be strictly greater than half of the size of the largest load.
All the sizes are positive integers.
This partition process goes on until it is impossible to make any further partition.
For example, if S=7, then we can break it into 3+4 first, then continue as 4=2+2. The process stops at requiring three servers, holding loads 3, 2, and 2.
Your job is to decide the maximum number of backend servers required by this algorithm. Since such kind of partitions may not be unique, find the best solution – that is, the difference between the largest and the smallest sizes is minimized.
Input Specification:
Each input file contains one test case, which gives a positive integer S (2≤N≤200), the size of the incoming traffic load.
Output Specification:
For each case, print two numbers in a line, namely, M, the maximum number of backend servers required, and D, the minimum of the difference between the largest and the smallest sizes in a partition with M servers. The numbers in a line must be separated by one space, and there must be no extra space at the beginning or the end of the line.
Sample Input:
22
Sample Output:
4 1
Hint:
There are more than one way to partition the load. For example:
22
= 8 + 14
= 8 + 7 + 7
= 4 + 4 + 7 + 7
or
22
= 10 + 12
= 10 + 6 + 6
= 4 + 6 + 6 + 6
or
22
= 10 + 12
= 10 + 6 + 6
= 5 + 5 + 6 + 6
All requires 4 servers. The last partition has the smallest difference 6−5=1, hence 1 is printed out.
25分代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int const maxn=50010;
priority_queue<int,vector<int>,less<int> > q,temp;
vector<int> res;
const int INF=1000000000;
void dfs(){
// priority_queue<int,vector<int>,less<int> > op;
// op=q;
// while(!op.empty()){
// int num=op.top();
// op.pop();
// cout << num << " ";
// }
// cout << endl;
if(q.size()==1){
int n=q.top();
q.pop();
if(n%2==0){
int mid=n/2;
int i=1;
while((mid-i)*2>(mid+i)){
priority_queue<int,vector<int>,less<int> > temp1;
temp1=q;
q.push(mid-i);
q.push(mid+i);
dfs();
q=temp1;
i++;
}
}
else{
int i=0;
int left=n/2;
int right=(n+1)/2;
while((left-i)*2>right+i){
priority_queue<int,vector<int>,less<int> > temp1;
temp1=q;
q.push(left-i);
q.push(right+i);
dfs();
q=temp1;
i++;
}
}
}
else{
int now=q.top();
q.pop();
int max=q.top();
if(now%2==0){
int mid=now/2;
int i=0;
if(mid*2<=max){
q.push(now);
if(q.size()>res.size()){
res.clear();
temp=q;
while(!temp.empty()){
int num=temp.top();
temp.pop();
res.push_back(num);
}
}
else if(q.size()==res.size()){
temp=q;
int max=q.top();
int min=INF;
while(!temp.empty()){
int num=temp.top();
temp.pop();
if(min>num){
min=num;
}
}
int max1=res[0];
int min1=res[res.size()-1];
if(max-min<max1-min1){
temp=q;
res.clear();
while(!temp.empty()){
int num=temp.top();
temp.pop();
res.push_back(num);
}
}
}
return ;
}
while((mid-i)*2>(max)){
priority_queue<int,vector<int>,less<int> > temp1;
temp1=q;
q.push(mid-i);
q.push(mid+i);
dfs();
q=temp1;
i++;
}
}
else{
int i=0;
int left=now/2;
int right=(now+1)/2;
if(left*2<=max){
q.push(now);
if(q.size()>res.size()){
res.clear();
temp=q;
while(!temp.empty()){
int num=temp.top();
temp.pop();
res.push_back(num);
}
}
else if(q.size()==res.size()){
temp=q;
int max=q.top();
int min=INF;
while(!temp.empty()){
int num=temp.top();
temp.pop();
if(min>num){
min=num;
}
}
int max1=res[0];
int min1=res[res.size()-1];
if(max-min<max1-min1){
temp=q;
res.clear();
while(!temp.empty()){
int num=temp.top();
temp.pop();
res.push_back(num);
}
}
}
return ;
}
while((left-i)*2>max){
priority_queue<int,vector<int>,less<int> > temp1;
temp1=q;
q.push(left-i);
q.push(right+i);
dfs();
q=temp1;
i++;
}
}
}
}
int main(){
int n;
scanf("%d",&n);
q.push(n);
dfs();
// for(int i=0;i<res.size();i++){
// printf("%d ",res[i]);
// }
printf("%d %d",res.size(),res[0]-res[res.size()-1]);
}
用了优先队列来做的，有两个测试点显示段错误，一个显示答案错误，当时时间不够了就没再检查了（我先做的3,4题，此时1,2题都还没写呢！），如果读者有心可以帮我检查一下。
总的来说本次测试就是死在了第一题上，唉英文就是容易出现读不懂题的情况，这个只能说看运气了。
