# aass3

**Repository Path**: tianq02/aass3

## Basic Information

- **Project Name**: aass3
- **Description**: CHD 24 fall Advanced Algorithm Design and Analysis, Assignment 3
- **Primary Language**: C++
- **License**: AGPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-12-04
- **Last Updated**: 2024-12-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Assignment 3

> CHD 24 fall Advanced Algorithm Design and Analysis

## [3-1](https://gitee.com/tianq02/aass3/blob/master/p1.cpp)

### Description:

> 一辆虚拟汽车在加满油之后可以行驶 $n$ km。旅途中有 $k$ 个加油站。设计一个有效算法，使得沿途加油的次数最少。
> 终端输入正整数 $n$ 和 $k$，表示汽车加满油后可行驶 $n$ km，且旅途中有 $k$ 个加油站。
> 接下来输入 $k+1$ 个整数，表示第 $k$ 个加油站与第 $k-1$ 个加油站之间的距离。
> 第 $0$ 个加油站表示出发地，汽车已加满油。第 $k+1$ 个加油站表示目的地。

> After filling up the gas tank, a virtual car can travel a distance of $n$ km. There are $k$ gas stations along the
> journey. Design an efficient algorithm to minimize the number of refueling stops. The input includes positive
> integers $n$ and $k$, representing the car's range after a full tank ($n$ km), and the number of gas stations ($k$).
> Following that, input $k+1$ integers representing the distances between consecutive gas stations. The $0$th gas
> station
> represents the starting point with a full tank, and the $k+1$th gas station represents the destination.

### Solution:

贪心算法，设置状态集合map，每个状态<剩余燃油，加油次数>，对于每个输入的加油站间距，迭代状态集合

1. 初始化，插入状态 <油箱容积，0>
2. 创建新的状态集合newMap，存储迭代结果
3. 对于 剩余燃油<间距 的状态，开不到下一个加油站，移除
4. 创建新状态 <剩余燃油-间距，加油次数>， 表示在下一个加油站不加油
5. 创建新状态 <油箱容积，加油次数+1>， 表示在下一个加油站加油
6. 处理完所有状态，map=newMap
7. 到达终点，输出map中最小的加油次数

由于题干有歧义，此处作两种版本

1. 求最小加油次数 <div id="solution-1" />

   ```c++
   #include <iostream>
   #include <vector>
   #include <limits>
   #include <unordered_map>
   using namespace std;
   
   int main() {
   int n, k;  // n: fuel tank size, k: gas stations count
   vector<int> distances;
   
       cin >> n >> k;
       for (int i = 0; i < k; i++) {
           int tmp = 0;
           cin >> tmp;
           distances.emplace_back(tmp);
       }
   
       int minRefill = 0; // 0: in case there is on stations between
       unordered_map<int, int> map; // <GasRemain,RefillCount>
       map.emplace(n, 0);
   
       for (const int &ahead: distances) {
           unordered_map<int, int> newMap; // <GasRemain,RefillCount>
           minRefill = numeric_limits<int>::max();
           for (const auto &[remain, refill]: map) {
               if (remain < ahead) continue; // we can't reach next station
               if (refill < minRefill) minRefill = refill;
   
               if (int curRemain = remain - ahead;
                   !newMap.contains(curRemain) || refill < newMap[curRemain]) {
                   newMap[curRemain] = refill;
               }
               if (!newMap.contains(n) || refill + 1 < newMap[n])
                   newMap[n] = refill + 1;
           }
           map = newMap;
       }
   
       cout << minRefill << endl;
       return 0;
   }
   ```

2. 求加油次数最小时的加油站选择

   思想：将前面版本的加油次数换成一串加油站序号

   此处只给出一种可行的策略，如果需要给出所有策略可以将更新处改成拉链

   ```c++
   #include <iostream>
   #include <vector>
   #include <limits>
   #include <unordered_map>
   using namespace std;
   
   int main() {
       int n, k;
       vector<int> distances;  // distance[0] means road from station 0 (start) to station 1
   
       cin >> n >> k;
       for (int i = 0; i < k; i++){
           int tmp = 0;
           cin >> tmp;
           distances.emplace_back(tmp);
       }
       // plus version, basically changing from a single counting number to a vector of station ids
       int minRefill = numeric_limits<int>::max();  // count min Refill rather than updating whole vector, this should save some time
       unordered_map<int, vector<int>> map;  // <GasRemain, vector<StationId>>
       map.emplace(n, 0); // {GasRemain: n, RefillList: {}} note that 0 here means 0 for initial capacity
   
       for (int i=0; i<distances.size(); i++) {
           int ahead = distances[i];
           minRefill = numeric_limits<int>::max();
           unordered_map<int,vector<int>> newMap;
           for (const auto &[remain, refills]: map){
               if (remain < ahead) continue;
               if (refills.size() < minRefill) minRefill = refills.size();
               int newRemain = remain-ahead;
               if (!newMap.contains(newRemain) || refills.size() < newMap[newRemain].size()) {
                   newMap[newRemain] = refills;
               }
               if (!newMap.contains(n) || refills.size()+1 < newMap[n].size()) {
                   newMap[n] = refills;  // since we are using const reference, we can't append Station Id here
                   newMap[n].emplace_back(i+1); // skipping 0, since we are leaving 0 for 1, the refill happens at 1
               }
           }
           map.swap(newMap);
       }
   
       for (const auto &[remain, refills]: map){
           if (refills.size() > minRefill) continue;
           for (const int &id : refills)
               cout << id << " ";
           cout << endl;
           break;
       }
       return 0;
   }
   ```

## [3-2](https://gitee.com/tianq02/aass3/blob/master/p2.cpp)

### Description:

> 设 $x_1, x_2, \dots , x_n$ 是实直线上的 $n$ 个点。用固定长度的闭区间覆盖这 $n$ 个点，至少需要多少个
> 这样的固定长度闭区间?对于给定的实直线上的 $n$ 个点和闭区间的长度 $k$，设计解此问题的有效算法，计算覆盖点集的最少区间数。

> Let $x_1, x_2, \dots , x_n$ be $n$ points on the real line. To cover these $n$ points with fixed-length
> closed intervals, what is the minimum number of such fixed-length closed intervals needed?
> For a given set of $n$ points on the real line and a length $k$ of the closed intervals,
> design an efficient algorithm to solve this problem
> and calculate the minimum number of intervals required to cover the set of points.

### Solution

这道题和前面的很像，每个点相当于加油站，油箱容积相当于闭区间的长度，不同的是此处不再要求区间不中断：区间不必重叠

想象一支笔画线，从左到右依次经过各点$x_1, x_2, \dots , x_n$，在$x_i$处一定有墨迹。

在每个点处，都可以选择画线/不画线，该点处的状态表示为{剩余距离: 画线次数}

加入下一个点时，更新每一个状态：

1. 若剩余距离大于等于间距，可以不添加新的线段，加入新状态{剩余距离-间距: 画线次数}
2. ~~若剩余距离小于间距，当前线段无法到达下一点，有必要增加线段~~
3. 无论剩余距离是否足够，加入新状态{线段长度: 画线次数+1}，新增线段  
   这是由贪心算法的思想决定的，要查找所有可能的动作，将该状态更新为画线次数最少的一个

由此，求解该问题只需将[问题一：求最小加油次数](#solution-1)中的更新逻辑稍微修改，将加油的逻辑移到判定之前

实现中需要先将数组排序，因而此处的时间复杂度无法低于$O(n \log n)$

为了避免浮点数预处理的精度损失，剩余距离不妨换成终点位置

1. 终点位置在点之后，保留该状态{终点位置：画线次数}
2. 新增状态：{该点位置+线段长度：画线次数+1}

```c++
#include <iostream>
#include <vector>
#include <random>
#include <unordered_map>
#include <algorithm>
#include <ranges>
using namespace std;

int main() {
    int n; // point count
    double k; // (closed) interval length
    vector<double> points; // coordinates of each point

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        double tmp;
        cin >> tmp;
        points.emplace_back(tmp);
    }

    ranges::sort(points);
    unordered_map<double, int> map;
    map.emplace(points[0] + k, 1); // repeating the first point on init, this should have no effect

    for (const auto &pos: points) {
        unordered_map<double, int> newMap;
        for (const auto &[endPos, count]: map) {
            // start a new interval here, update interval count
            if (!newMap.contains(pos+k) || count + 1 < newMap[pos+k])
                newMap.emplace(pos+k, count + 1);
            // current interval can reach this point, keep this state unchanged
            if (endPos < pos) continue;
            newMap.emplace(endPos, count);
        }
        map.swap(newMap);
    }

    int minCount = numeric_limits<int>::max();
    for (const int &count: map | std::views::values) {
        minCount = min(minCount, count);
    }

    cout << minCount << endl;

    return 0;
}
```

## [3-3](https://gitee.com/tianq02/aass3/blob/master/p3.cpp)

### Description:

[AcWing_6059](https://www.acwing.com/problem/content/description/6062/)

> 【数列极差】问题描述：在黑板上写了 $N$ 个正整数组成的一个数列，进行如下操作：每一次擦去其中的两个数 $a$ 和 $b$，
> 然后在数列中加入一个数 $a*b+1$，如此下去直至黑板上剩下一个数，在所有按这种操作方式得到的所有数中，最大的 $\max$，
> 最小的为 $\min$，则该数列的极差定义为 $M = \max - \min$。试设计一个算法，计算 $M$。

> 【 Sequence Extreme Difference 】 Problem Description: A sequence composed of $N$ positive
> integers is written on the blackboard. The following operation is performed: erase two numbers $a$
> and $b$, then add a number $a*b+1$ to the sequence. Repeat this process until only one number remains
> on the blackboard. Among all the numbers obtained by this operation, let the maximum be $\max$ and
> the minimum be $\min$. The extreme difference $M$ of the sequence is defined as $M = \max - \min$.
> Design an algorithm to calculate $M$.

### Solution

分析问题：

1. 输入：有限个数的数列
2. 输出：可能算出来的最大和最小数值之间的差
3. 目标：确定两种选取方案，分别求得最大者和最小值

解法1：暴力搜索：[p3brute](https://gitee.com/tianq02/aass3/blob/master/p3brute.cpp)

- 时间复杂度 $O(n!^2)$
- 空间复杂度 $O(n!)$

很显然，这道题不能暴力求解，我们需要一点**注意到**

- 每次选取两个较小的数合并，最终结果最大
- 每次选取两个较大的数合并，最终结果最小

```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
int n = 0;
vector<int> numbers;

   cin >> n;
   for (int i = 0; i < n; i++) {
       int tmp;
       cin >> tmp;
       numbers.emplace_back(tmp);
   }

   // ideology
   // by merging smallest 2 each time, we get the biggest one
   // by merging greatest 2 each time, we get the smallest one
   // don't just take my words, try it on paper

   vector<int> maxNums = numbers, minNums = numbers;

   ranges::sort(maxNums);
   while (maxNums.size() > 1) {
       int newNum = maxNums[0] * maxNums[1] + 1;
       maxNums.erase(maxNums.begin(), maxNums.begin() + 2);
       // since our vector is already ordered, we don't need to sort again
       auto it = ranges::lower_bound(maxNums, newNum);
       maxNums.emplace(it, newNum);
   }

   ranges::sort(minNums, greater());
   while (minNums.size() > 1) {
       int newNum = minNums[0] * minNums[1] + 1;
       minNums.erase(minNums.begin(), minNums.begin()+2);
       // the product of two biggest numbers should still be biggest
       minNums.emplace(minNums.begin(), newNum);
   }

   cout << maxNums[0] - minNums[0] << endl;
}
```

## [3-4](https://gitee.com/tianq02/aass3/blob/master/p4.cpp)

### Description:

> 在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选
> 相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，
> 计算出将 n 堆石子合并成一堆的最小得分和最大得分。

> Around a circular playground, there are n piles of stones arranged. The task is to merge the stones
> into a single pile in a certain order. It is stipulated that only adjacent piles of stones can be selected
> at a time to merge into a new pile, and the number of stones in the new pile is recorded as the score
> for that merging operation. Please design an algorithm to calculate the minimum and maximum
> scores to merge n piles of stones into a single pile.

### Solution:

和p3很像，略微修改[p3brute](https://gitee.com/tianq02/aass3/blob/master/p3brute.cpp)即可得到本题的暴力解法[p4brute](https://gitee.com/tianq02/aass3/blob/master/p4brute.cpp)

它的时空复杂度非常糟糕，但可以给我们一些ground truth

我们**注意到**： 
 - 每次合并两个**最少**的堆，所得分数**最少**，
 - 每次合并两个**最多**的堆，所得分数**最高**

此处的实现基于[solution3](https://gitee.com/tianq02/aass3/blob/master/submit/solution3.cpp)，加入了一点点修改

```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n = 0;
    vector<int> numbers;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        numbers.push_back(tmp);
    }

    // ideology
    // by merging smallest 2 each time, we get the smallest score
    // by merging greatest 2 each time, we get the greatest score
    // don't just take my words, try it on paper

    vector<int> minNums = numbers, maxNums = numbers;
    int minScore=0, maxScore = 0;

    ranges::sort(minNums);
    while (minNums.size() > 1) {
        int newNum = minNums[0] + minNums[1];
        minScore += newNum;

        minNums.erase(minNums.begin(), minNums.begin() + 2);
        auto it = ranges::lower_bound(minNums, newNum);
        minNums.emplace(it, newNum);
    }

    ranges::sort(maxNums, greater());
    while (maxNums.size() > 1) {
        int newNum = maxNums[0] + maxNums[1];
        maxScore += newNum;
        
        maxNums.erase(maxNums.begin(), maxNums.begin()+2);
        // the product of two biggest numbers should still be biggest
        maxNums.emplace(maxNums.begin(), newNum);
    }

    cout << maxScore - minScore << endl;

}
```

## [3-5](https://gitee.com/tianq02/aass3/blob/master/p5.cpp)

> 我无法独立完成此题目，此处参考网上的题解

[turing.1357](https://acm.webturing.com/problem.php?id=1357)

### Description:

> 一个长、宽、高分别为 m, n, p 的长方体被分割成 $m*n*p$ 个小立方体。每个小立方体内有
> 一个整数，设计一个算法，计算出所给长方体的最大子长方体。子长方体的大小由它所含的
> 所有整数之和确定。

> A cuboid with dimensions length, width, and height of m, n, and p respectively, is divided into
> $m*n*p$ small cubes. Each small cube contains an integer. Design an algorithm to calculate the
> maximum sub-cuboid within the given cuboid. The size of the sub-cuboid is determined by the sum
> of all the integers it contains.

> 特别说明：整数**有正有负**，不是单纯求和

**输入样例**
```plaintext
3 3 3

0 -1 2
1 2 2
1 1 -2

-2 -1 -1
-3 3 -2
-2 -3 1

-2 3 3
0 1 3
2 1 -3
```

**输出样例**
```plaintext
14
```

### Solution:

这道题是典型的动态规划，要应用化归的思想

```c++
// 8601 最大长方体问题.cpp
//

#include <iostream>
using namespace std;

//长方体：m行,n列,p层
//[m+1,n+1,p+1]


int MaxSum(int n,int *a){
    int sum=0;
    int b=0;
    for(int i=1;i<=n;i++){
        if(b>0)b+=a[i];
        else b=a[i];
        if(sum<b)sum=b;
    }
    return sum;
}

int MaxSum2(int m,int n, int **a){
    int sum=0;
    int *b = new int[n+1];
    for(int i=1;i<=m;i++){
        for(int k=1;k<=n;k++){
            b[k]=0;
        }

        for(int j=i;j<=m;j++){
            for(int k=1;k<=n;k++){
                b[k] += a[j][k];
            }
            int max=MaxSum(n,b);
            if(max>sum)sum=max;
        }

    }
    free(b);
    return sum;
}

int MaxSum3(int m, int n, int p, int ***a){
    int sum=0;
    int **b = new int*[n+1];	//动态分配数组[m+1,n+1]
    for(int i=1;i<=n;i++){
        b[i]=new int[p+1];
    }

    for(int i=1;i<=m;i++){//从第1层开始的所有平面  第2层、第3层...

        for(int j=1;j<=n;j++){
            for(int k=1;k<=p;k++){
                b[j][k] =0;
            }
        }
        for(int t=i;t<=m;t++){//第1层，第1层到第2层，第1层到第3层...  即第i层开始到第t层

            for(int j=1;j<=n;j++){
                for(int k=1;k<=p;k++){
                    b[j][k] += a[t][j][k];  //3维压缩为2维,即相加
                }
            }
            int max = MaxSum2(n,p,b);  //粗心 把这2行代码放到for循环外面了
            if(max>sum)sum=max;     //粗心 把这2行代码放到for循环外面了
            //放里面才是正确的
        }



    }
    free(b);
    return sum;

}



int main()
{

    int m,n,p;
    cin>>m>>n>>p;
    int ***a = new int **[m+1];
    for(int i=0;i<m+1;i++){
        a[i] = new int *[n+1];
        for(int j=0;j<n+1;j++){
            a[i][j] = new int [p+1];
        }
    }

    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=p;k++){
                cin>>a[i][j][k];
            }
        }
    }
    cout<<MaxSum3(m,n,p,a)<<endl;

    free(a);
    return 0;
}
```

## [3-6](https://gitee.com/tianq02/aass3/blob/master/p6.cpp)

> 我无法独立完成此题目，此处参考了网上的题解

### Description:

> 关于整数的 2 元圈乘运算⊙定义为：（X⊙Y）=10 进制整数X 的各位数字之和\*10 进制整
> 数 Y 的最大数字+Y 的最小数字。例如，（9⊙30）=9\*3+0=27。
> 对于给定的 10 进制整数X 和 K，由 X 和⊙运算可以组成各种不同的表达式。试设计一
> 个算法，计算出由 X 和 ⊙ 运算组成的值为 K 的表达式最少需用多少个 ⊙ 运算。

> The binary circle multiplication operation ⊙ on integers is defined as follows: (X⊙Y) = the
> sum of the digits of the decimal integer X multiplied by the maximum digit of the decimal integer
> Y, plus the minimum digit of Y. For example, (9⊙30) = 9*3 + 0 = 27.
> For given decimal integers X and K, various expressions can be formed using X and the ⊙
> operation. Design an algorithm to calculate the minimum number of ⊙ operations needed to obtain
> an expression composed of X and the ⊙ operation with a value of K.

### Solution:

```c++
#include <algorithm>
#include <cstring>
#include <iostream>

#define i32 int
#define i64 long long
#define u128 unsigned long long
#define u32 unsigned int

using namespace std;
const i32 MAXN = (int) 5e2;
// const i64 M = 1e10;
const auto L = 0x3f;

i64 G[MAXN];
i64 X, K;

i64 f (i64 X, i64 Y) {//X@Y运算
    i64 numX = 0, mxY = 0, mnY = 10;
    while (X) {
        numX += X % 10;
        X /= 10;
    }
    while (Y != 0) {
        mxY = max (mxY, Y % 10);
        mnY = min (mnY, Y % 10);
        Y /= 10;
    }
    return numX * mxY + mnY;
}

i64 get_lim (i64 X, i64 K) {//获取上界
    auto num = 0;
    while (X) {
        X /= 10;
        num++;
    }
    i64 lim = max (num, 2) * 81 + 9;
    return max(lim, K);
}


int main () {
    memset (G, L, sizeof (G));
    cin >> X >> K;
    auto lim = get_lim (X, K);
    G[f (X, X)] = 1;
    G[X] = 0;

    if (X > K) {
        goto error;
    }


    for (auto i = X; i <= lim; ++i) {
        for (auto j = X; j <= lim; ++j) {
            if (G[i] < L && G[j] < L && G[f (i, j)] > G[i] + G[j] + 1) {//i@j到S的运算次数更少,则更新
                G[f (i, j)] = G[i] + G[j] + 1;
            }
        }
    }

    if (G[K] < L) {
        cout << G[K] << endl;
        // for (auto p = X; p <= K; ++p) {
        //     cout << p << ":" << G[p] << " ";
        // }
        // cout << endl;
    }
    else {
    error:
        cout << "error" << endl;
    }
    return 0;
}
```