牛客网OJ题解--20210315

比较月亮大小

https://ac.nowcoder.com/acm/problem/15431

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC15431-比较月亮大小

题目链接

https://ac.nowcoder.com/acm/problem/15431

题目描述

点点是一名出色的狼人。众所周知，狼人只有在满月之夜才会变成狼。同时，月亮的大小随着时间变化，它的大小变化30天为一循环。它的变化情况(从第一天开始)为0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 然后又再一次循环。今年夏天点点很无聊，于是开始看月亮。由于点点很忙，所以他只选择一段连续的时间看月亮，并把月亮的大小记录了下来。现在，他告诉你他记录下东西，让你告诉他下一天(即点点记录下的最后一天的第二天)的月亮是比前一天(即点点记录下的最后一天)大还是小。

给你一个正整数n表示点点记录下的时间个数。下一行n个自然数表示点点记录下的月亮大小。一个字符串。如果下一天的比前一天的大则输出"UP"如果下一天的比前一天的小则输出"DOWN"。如果无法判断则输出"-1"

测试样例

样例1

输入

5
3 4 5 6 7

输出

UP

样例2

输入

8
12 13 14 15 14 13 12 11

输出

DOWN

样例3

输入

1
8

输出

-1

解题思路

实际上我们发现只要观察前两个天数就可以判断出天数的走向从而锁定起始天数的位置，然后加上n天就是我们要比较的那个天X，那X和起始天进行比较即可。但是要注意对于只有1天的情况要进行特判，如果是1天，那么只有0和15可以判断，其他情况都是无法判断。

解题代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int date[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2,
                1 };
        int n = sc.nextInt();
        if (n == 1) {
            // 一个情况的特判
            int a = sc.nextInt();
            // 如果刚好是0，那么下一天一定是1，直接输出UP
            if (a == 0)
                System.out.println("UP");
            // 如果是15，那么下一天一定是14，直接输出DOWN
            else if (a == 15)
                System.out.println("DOWN");
            else
                // 否则无法判断，返还-1
                System.out.println("-1");
        } else {
            int a[] = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
            }
            int index = 0;
            // 寻找匹配的段，实际上两个天就可以找到起始天了
            case1: for (int i = 0; i < 30; i++) {
                for (int j = 1; j <= 2; j++) {
                    if (a[j] == date[i] && a[j + 1] == date[i + 1]) {
                        index = i;
                        break case1;
                    }
                }
            }
            // 然后加上n天取模30（因为可能会到下一个30天了）
            // 就得到了需要的下一天
            // 根据大小判断即可，此时不可能再有无法判断的情况了
            if (date[index + n % 30] > a[n])
                System.out.println("UP");
            else
                System.out.println("DOWN");
        }
    }
}

NC16120-博弈论

题目链接

https://ac.nowcoder.com/acm/problem/16120

题目描述

铁子和顺溜在学习了博弈论的sg函数之后，解决了很多很多博弈题，现在他们遇到了一道难题。给出一个长度为 n 的数列，数列里的每个元素都是个位数，这个数列的每一个连续子数列都能生成。一个十进制数，对于子数列a[l~r]，这个十进制数的个位为a[r],十位为a[r - 1]，...，最高位为a[l]。现在铁子需要知道最小的不能被该数列的子数列生成的十进制非负整数是多少？第一行一个数字n。(1 ≤ n ≤ 1000)。第二行n个数字di。(0 ≤ di ≤ 9)。输出一个数字表示答案。

测试样例

样例1

输入

4
3 0 1 2

输出

样例2

输入

10
9 8 7 6 5 4 3 2 1 0

输出

解题思路

大水题，一开始读错题了以为是子序列，谁知道居然是子数列，那么就简单许多了，直接暴力打表即可。

解题代码

#include <bits/stdc++.h>
using namespace std;

bool v[1000009];
int a[100005];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        //存入数列
        cin >> a[i];
    }
    //枚举打表
    //初始位置从i开始
    for (int i = 1; i <= n; i++)
    {
        //子数列长度最大也就到6了，再长表示不出来了
        for (int l = 1; l <= 6; l++)
        {
            int ans = 0;
            //j最长只能到n和i+l-1的最小值，即可能j到不了n，如果超出n了那么就停止
            for (int j = i; j <= min(n, i + l - 1); j++)
            {
                ans = ans * 10 + a[j];
            }
            v[ans] = 1;
        }
    }
    for (int i = 0; i <= 1e6; i++)
    {
        //找道第一个表示不出来的数
        if (!v[i])
        {
            cout << i << endl;
            return 0;
        }
    }
}