7-1 Square Friends (20 分)

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=272 ², 74529=273², and 75076=274².

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 (≤10⁶), 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 <iostream>
#include <cmath>
using namespace std;

int n, maxA;

bool check(int A, int B)
{
    
    for (int i = 0; i < n; i++)
    {
    
        if (B * B / 1000 != A)
            return false;
        A++;
        B++;
    }
    return true;
}

int main()
{
    
    bool flag = false;
    cin >> n >> maxA;
    for (int i = 1; i <= maxA; i++)
    {
    
        for (int j = sqrt(i * 1000); j <= sqrt((i + 1) * 1000); j++)
        {
    
            if (check(i, j))
            {
    
                flag = true;
                cout << i << " " << j << endl;
            }
        }
    }
    if (flag == false)
        cout << "No Solution." << endl;
    return 0;
}

7-2 One Way In, Two Ways Out (25 分)

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

自己加了一个测试样例方便你进一步测试：
Sample Input:

6 1
10 2 3 4 5 6
3 2 10 4 6 5

Sample Output:

yes

这题一看是双端队列，自己想歪了想了好久，以为是允许两端进一端出，一直不知道怎么写。后面才发现是一端进两端出，相对来说会简单很多，用数组模拟就好了。文末放了个允许两端进一端出的双端队列代码，有兴趣可以看看。

代码如下：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    
    int n, k, num;
    int deque[100005]; // 模拟双端队列
    queue<int> q;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
    
        cin >> num;
        q.push(num);
    }

    while (k--)
    {
    
        bool flag = true;
        int front = 1, rear = 0;
        queue<int> temp = q;
        for (int i = 0; i < n; i++)
        {
    
            cin >> num;
            while (!temp.empty()) // 这里temp写成q了，死循环不报错找了半天
            {
    
                if (deque[front] == num || deque[rear] == num) // 有可能前面的队列可以出元素符合序列
                    break;
                else // 两边都不满足，那么往双端队列里面插入数据
                {
    
                    int t = temp.front();
                    temp.pop();
                    deque[++rear] = t;
                    if (deque[rear] == num) // 既然前面出不了，只能后面有可能会出元素了
                        break;
                }
            }
            if (deque[front] == num)
                front++;
            else if (deque[rear] == num)
                rear--;
            else
                flag = false; // 不能break，因为必须把元素输入完毕
        }
        if (flag)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}

7-3 Preorder Traversal (25 分)

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>
using namespace std;

const int MAXN = 50005;
int n, pos = 0;
int pre[MAXN], in[MAXN], post[MAXN];

void getPre(int root, int left, int right)
{
    
    if (left > right)
        return;
    int i = left;
    while (i < right && in[i] != post[root])
        i++;
    pre[pos++] = post[root];
    getPre(root - (right - i + 1), left, i - 1);
    getPre(root - 1, i + 1, right);
}

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> post[i];
    for (int i = 0; i < n; i++)
        cin >> in[i];
    getPre(n - 1, 0, n - 1);
    cout << pre[n - 1] << endl;
    return 0;
}

7-4 Load Balancing (30 分)

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.

这道题确实算难的了吧，就看想不想得到DFS了，代码中注释比较详细，理解起来应该问题不大。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxS = -1, minDiff = 0x3f3f3f3f;
vector<int> arr;

void dfs()
{
    
    bool flag = false;
    sort(arr.begin(), arr.end());
    vector<int> temp = arr; // 备份arr
    int maxLoad = arr[arr.size() - 1];
    for (int i = 1; i <= maxLoad / 2; i++) // 每次都拆解最大的负载（否则会不满足第三个条件）
    {
    
        int load1 = i, load2; // load1、load2分别表示表示按照i、maxLoad-i拆解后的所有负载中的最小的负载、最大的负载
        // 其中数组中任何一个元素都是大于等于maxLoad/2的（条件要求了的），那么拆分之后i就是最小的，因此load1=i，load2就要看拆分后谁最大了
        if (arr.size() >= 2)
            load2 = max(maxLoad - i, arr[arr.size() - 2]);
        else
            load2 = maxLoad - i;

        if (load1 * 2 > load2) // 符合条件则可以继续dfs进行拆分
        {
    
            flag = true;
            arr.pop_back();
            arr.push_back(i);
            arr.push_back(maxLoad - i);
            dfs();
            arr = temp; // dfs返回之后恢复arr原本的数据
        }
    }

    if (flag == false) // 拆解到底了，就看谁分的更多，分的同样多就看谁分出来最大最小负载之差最小
    {
    
        int size = arr.size();
        if (size > maxS)
        {
    
            maxS = size;
            minDiff = arr.back() - arr.front();
        }
        else if (size == maxS)
            minDiff = min(minDiff, arr.back() - arr.front());
    }
}

int main()
{
    
    int s;
    cin >> s;
    arr.push_back(s);
    dfs();
    cout << maxS << " " << minDiff << endl;
    return 0;
}

两端进一端出的双端队列模拟

数据输入方式和7-2模式一样，样例1是自己做的，样例2截取于2022年王道数据结构考研辅导书双端队列部分，如有问题，欢迎指正

Sample Input 1:

5 5
10 2 3 4 5
5 2 10 3 4
5 10 2 4 3
5 2 3 10 4
5 10 2 3 4
10 3 2 4 5

Sample Output 1:

yes
no
no
yes
yes

Sample Input 2:

4 5
1 2 3 4
1 4 2 3
2 4 1 3
3 4 1 2
4 1 3 2
4 2 3 1

Sample Output 2:

yes
yes
yes
no
no

代码如下：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    
    int n, k, num;
    cin >> n >> k;
    vector<int> rec(10005), temp(10005), deque; // 模拟双端队列,允许两端进一端出
    for (int i = 0; i < n; i++)
        cin >> rec[i];

    while (k--)
    {
    
        int indexRec = 0, indexTemp = 0;
        deque.clear();
        map<int, int> pos;
        for (int i = 0; i < n; i++)
        {
    
            cin >> temp[i];
            pos[temp[i]] = i; // 记录位置
        }

        while (indexRec < n)
        {
    
            if (deque.empty()) // 空的时候就直接往里面插元素就好了
                deque.push_back(rec[indexRec++]);
            else
            {
    
                int curFront = pos[deque[0]];  // 队头在检查序列中的下标
                int next = pos[rec[indexRec]]; // 新元素在检查序列中的下标
                if (next < curFront)
                    deque.insert(deque.begin(), rec[indexRec++]); // 输出序列中在队头左边就放左边
                else
                    deque.push_back(rec[indexRec++]); // 输出序列中在队头右边就放右边
            }

            while (deque.front() == temp[indexTemp])
            {
    
                indexTemp++;
                deque.erase(deque.begin());
            }
        }

        if (indexTemp == n)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}