NxgSept26 – ACM 集训 #1

Problem #1

TSOJ P1508
定义：对于整数序列A，若整数a∈A，且出现的次数最多，则称a是A的最高频率元素。
现在，给定一个包含L个整数的序列A，并且存在一个整数X，它出现的次数大于L/2，因此X是最高频率元素，且唯一。请找出元素X。

Solution #1 模拟 时间O(L), 空间O(max{A})

一维数组，整数大小作为下标，模拟计数，求最大值。

代码略

Solution #2 时间O(L), 空间 O(1)

两个整数模拟栈的操作。对于极限情况，出现次数最多的数 出现次数为floor(L/2)+1，则用floor(L/2)个不同元素消去后，栈内还存在一个数，此数即为出现次数最多的数。

Note 1: 此题（TSOJ P1508）为最简单的形式，此题还可以有更多变式。

因为用此方法时，只需比较两数是否相等，所以也可以使用字符串来进行处理。这样可以处理出现大整数的情况。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    string t, s;
    int c;
    for(int n; cin >> n;) {
        c = 0;
        s = t = "";
        for(int i = 0; i < n ; i++) {
            cin >> t;
            if(t != s) {
                if(s == "") {
                    s = t;
                    c = 1;
                } else {
                    if(c == 1) {
                        c = 0;
                        s = "";
                    } else {
                        c--;
                    }
                }
            } else {
                c++;
            }
        }
        cout << s << endl;
    }
    return 0;
}

 

Problem #2

TSOJ P1162
某火车站铁轨铺设如图，有 n 节车厢自 A 方向进入车站，按进站方向编号为 1 ~ n。现对其进行编组，编组过程可借助中转站 Station，其中 Station 可停靠任意多车厢，由于 Station 末端封顶，故驶入 Station 的车辆必须按相反方向驶出。对每个车厢，一旦自 A 进入 Station，就不能再驶入 A；且一旦自 Station 驶入 B，再不能返回 Station。给定 n 值，请判断某个车厢编组是否可能。

Solution #1 栈模拟

略

Solution #2 空间复杂度O(n) 时间复杂度 O(nlogn)

因为 进站可视为单调上升的栈，所以当 x 出栈时，所有比x大的已入栈元素一定已经出栈。

所以 所有比最后一个已入栈元素大的元素一定没有入栈

所以 当 子序列中的最小元素m已经出栈时，出栈序列中m左边的所有元素均比m右边的所有元素小

所以 在子序列 a 中，

a[i] = m, i = max{a[1..i]} (*)

可根据（*）式进行递归。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110000;

int a[N];

bool exec(int l, int r, int m) {
    if(r - l < 2) return true;
    int v = -1;
    for(int i = l; i <= r; i++) {
        v = max(a[i], v);
        if(a[i] == m) {
            if(v - m  != i - l) {
                return false;
            } else {
                return exec(l, i - 1, m + 1) && exec(i + 1, r, v + 1);
            }
        }
    }
}

int main() {
    for(int n; cin >> n;) {
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        cout << (exec(1, n, 1) ? "Yes" : "No") << endl;
    }
    return 0;
}

 

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.