EOJ Test Round #3 Solution

ultmaster edited 7 年前

拿分很容易。拿高分很难。结果。。。好惨啊。。。

A. 天气猜猜看

为了满足条件，我们只要碰到 UP 加 0.1，碰到 DOWN 减 0.1 就可以了？

抱歉，这种方法只能拿 70。考虑这样的情况：起始温度是 25.0，接下来有 1 个 UP 和 300 个 DOWN。那么，显然，为了应对这 300 个 DOWN，我们刚开始的 1 个 UP 要提得尽可能的高：即提到 30。推及一般情况，就是如果一连串的 UP 后面紧跟一个 DOWN，那么最后一个 UP 要输出 30.0；如果一连串的 DOWN 后面紧跟 UP，那么要输出 0.0。这样实际上已经做完了。具体实现可能要读入后一天的天气后再决定前一天的温度。

for (int i = 0; i < n; ++i) {
    cin >> self; // for C++, use scanf("%s", self) for C
    if (i > 0 && self != last) {
        if (last == "UP") ans[i-1] = 30;
        else if (last == "DOWN") ans[i-1] = 0;
        start = ans[i-1];
    }
    if (self == "UP")
        start += 0.1;
    else start -= 0.1;
    ans[i] = start;
    last = self;
}

B. 寻找图书馆

70 分解法

枚举每个图书馆，计算当前城市与该图书馆之间的距离，然后取最小值。
下面给出每一次询问时的关键代码。

int ans = 120000; // 一个很大的数
for (int i = 0; i < m; ++i)
    ans = min(ans, abs(x[i] - qr));
printf("%d\n", ans);

100 分解法

对图书馆的位置 (x_i) 进行排序，对于每一次询问 (qr)，在 (x) 中二分查找，计算该城市与最近的两个城市之间的距离的最小值。

下面给出二分部分的代码：

x[m++] = -1000000; //读完图书馆位置后加一个边界，防止输出答案时r-1越界

// 使用 qsort/sort 排序（略）

int l = 0, r = m - 1; //二分
while (l < r) {
    int mid = (l + r) / 2;
    if (x[mid] < qr) l = mid + 1;
    else r = mid;
}
printf("%d\n", min(abs(x[r - 1] - qr), abs(x[r] - qr)));

C. 很大很大的数

最简单的方法就是对 (n) 反复地减，然后再进行反复地验证。这种做法就可以轻松地拿到 70 分以上。

int check(ll x) {
    int res = 0;
    while (x) {
        int i = x % 10;
        if (i == 0 || i == 1)
            res++;
        x /= 10;
    }
    return res;
}
while (check(n) != x) n--;

要是想要 AC，则要用到搜索的技巧。首先从高往低枚举长度，然后进行逐位枚举，一边枚举一边记录 0 和 1 的个数，同时还要记录是否达到了搜索数的边界。感兴趣的同学可以看一下 Python 的实现（不想看的同学可以手动折叠，因为 70 分也是很高的分数。。。另外，比赛时好像不能交 Python。。。。）：

def solve(n, x):
    ans = dfs(str(n), x, 0, True, 0, '')
    if ans is None:
        length = len(str(n)) - 1
        while length > 0:
            ans = dfs('9' * length, x, 0, False, 0, '')
            if ans is not None:
                break
            length -= 1
    return int(ans)

def dfs(s, x, u, lim, siz, cur):
    # Limit is True means it is still limited
    # print(cur)
    if siz > x:
        return None
    if len(s) - u < x - siz:
        return None
    if u == len(s):
        if siz == x:
            # print(x, u, lim, siz)
            return ''
        return None
    start = int(s[u]) if lim else 9
    ed = 0 if u == 0 else -1
    for i in range(start, ed, -1):
        # print(u, i)
        append = 1 if 0 <= i <= 1 else 0
        if i != start or not lim:
            new_ans = dfs(s, x, u + 1, False, siz + append, cur + str(i))
            if new_ans is not None:
                return str(i) + new_ans
        else:
            new_ans = dfs(s, x, u + 1, True, siz + append, cur + str(i))
            if new_ans is not None:
                return str(i) + new_ans
    return None

D. 相似的句子

这道题如果没想到排序就真的不好做了。不过还是有 20% 的分可以拿的？QAQ

实际上就是把字符串全部读进来，排序一下（随便你怎么排，正着排也行倒着排也行），然后比较两个句子排序之后的结果是否相等。

别忘了全部转成小写。

int judge() {
    if (k1 != k2) return 0;
    for (int i = 0; i < k1; ++i)
        if (s1[i] != s2[i]) return 0;    // use strcmp for C
    return 1;
}

sort(s1, s1 + k1);    // use qsort for C
sort(s2, s2 + k2);
printf("Case %d: %s\n", kase, judge() ? "YES" : "NO");

0 0