机试重点题-2021/2023

2021

5：由二叉树前々序列和中々序列得到后々序列列

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 50010;
int n;
int a[N], b[N]; //前序，中序 
unordered_map<int, int> p;

void build(int al, int ar, int bl, int br)
{
    if(al > ar) return;
    int root = a[al];
    int k = p[root];
    //画图更直观 
    build(al + 1, ar - br + k, bl, k - 1); //左 
    build(ar -br + k + 1, ar, k + 1, br); //右 
    int ans = root; //访问根结点 
    cout << ans << " ";
}

int main()
{
    cin >> n;
    for(int i = 0; i<n; i++) cin >> a[i];
    for(int i = 0; i<n; i++)
    {
        cin >> b[i];
        p[b[i]] = i;
    }
    build(0, n-1, 0, n-1);
    
    return 0;
}

/*
5
3 9 20 15 7
9 3 15 20 7
output:9 15 7 20 3
*/

2023

A：单源最短路径问题（双权值）

HDU 3790：多目标最短路径

考察：单源最短路径（Dijkstra）

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1010;
int g_dist[N][N], g_cost[N][N];
int dist[N], cost[N];
bool st[N];
int n, m;
int s, e;

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    memset(cost, 0x3f, sizeof cost);

    dist[s] = 0;
    cost[s] = 0;
    for(int i = 0; i<n; i++) {
        int t = -1;
        for(int j = 1; j<=n; j++) {
            if(!st[j] &&(t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;

        for(int j = 1; j<=n; j++) {
            if(dist[j] > dist[t] + g_dist[t][j]) {
                dist[j] = dist[t] + g_dist[t][j];
                cost[j] = cost[t] + g_cost[t][j];
            }
            else if(dist[j] == dist[t] + g_dist[t][j]) {
                if(cost[j] > cost[t] + g_cost[t][j]) {
                    cost[j] = cost[t] + g_cost[t][j];
                }
            }
        }
    }
    return;
}

int main()
{
    memset(g_dist, 0x3f, sizeof g_dist);
    memset(g_cost, 0x3f, sizeof g_cost);

    cin >> n >> m;
    while(m--) {
        int a, b, d, w;
        cin >> a >> b >> d >> w;
        g_dist[a][b] = g_dist[b][a] = min(g_dist[a][b], d);
        g_cost[a][b] = g_cost[b][a] = min(g_cost[a][b], w);
    }

    cin >> s >> e;

    dijkstra();
    cout << dist[e] << " " << cost[e];

    return 0;
}

B：最长上升子序列之和

考察：动态规划

//最大上升子序列之和
#include <iostream>

using namespace std;

const int N = 1010;
int n;
int f[N];
int a[N];
int main()
{
    cin >> n;
    for(int i = 1; i<=n; i++)
        cin >> a[i]; //各自的数值

    for(int i = 1; i<=n; i++) {
        f[i] = a[i]; //f[i]:以a[i]为结尾的序列之和
        for(int j = 1; j<i; j++) {
            if(a[j] < a[i]) {
                f[i] = max(f[i], f[j]+a[i]);
            }
        }
    }

    int res = 0;
    for(int i = 1; i<=n; i++) {
        res = max(f[i], res);
    }
    cout << res;
    return 0;
}

C：调整大根堆

考察：堆排序

#include <iostream>

using namespace std;

const int N = 10010;
int h[N], size;
int cnt;
int n;

void up(int u)
{
    int t = u;
    int left = u * 2;
    int right = u * 2 + 1;
    if(left <= size && h[left] > h[t]) t = left;
    if(right <= size && h[right] > h[t]) t = right;
    
    if(t != u){
        swap(h[t], h[u]);
        cnt ++;
        up(t);
    }
}

void up_2(int u)
{
    while(u / 2 != 0 && h[u/2] < h[u])
    {
        swap(h[u/2], h[u]);
        cnt ++;
        u /= 2;
    }
}

//从n/2~1处不断向下调整 
void down(int u)
{
    int t = u;
    int left = 2 * u;
    int right = 2 * u + 1;
    
    if(left <=size && h[t] < h[left]) t = left;
    if(right <= size && h[t] < h[right]) t = right;
    
    if(t != u)
    {
        swap(h[t], h[u]);
        cnt ++;
        down(t);
    }
}

int main()
{
    cin >> n;
    size = n;
    
    for(int i = 1; i<=n; i++)
        cin >> h[i];
        
    for(int i = n/2; i>0; i--) down(i);
    
    for(int i = 1; i<=n; i++)
        cout << h[i] << " ";
    cout << endl;
    cout << "cnt = " << cnt << endl;
    
    
    return 0;
}
/*
8
53 17 78 9 45 65 87 32
7
6 1 5 9 8 4 7
output:
87 45 78 32 17 65 53 9
cnt = 5
9 8 7 1 6 4 5
cnt = 4
*/