NOIP真题题解（一）模拟

1. 侦探推理：

来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/251/B

• 算法知识点: 枚举，模拟，字符串处理
• 复杂度：O(7M^2P)

解题思路：

对于比较繁琐的模拟题，写代码的时候建议尽可能模块化。
依次枚举每个同学是否可能是凶手。最终结果有三种：
可能的凶手只有一个，输出凶手名字；
可能的凶手多于一个，输出"Cannot Determine"；
任何一个同学都不可能是凶手，输出"Impossible"；
在枚举每个同学是凶手的过程中，依次枚举今天是星期几，然后判断说谎的同学是否有可能有 n 个。

这里有两点需要注意：
每个同学需要始终如一，如果出现某个同学既说真话又说假话，那么当前枚举的情况不合法；
每个句子有三种情况：真话、假话、废话。最终只要 假话数量 ≤n≤ 假话数量 + 废话数量，那么说谎的同学就有可能有 n 个；

时间复杂度分析:

我们会依次枚举凶手、星期几以及句子，对于每个句子在判断是谁说的时会再循环一遍所有同学，所以总时间复杂度是 O(7M^2P)，其中 M 是总人数，P 是总句子数。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 110;
 
int n, m, P;
string sentence[N];
string name[N];
string weekday[7] = {
    "Today is Monday.",
    "Today is Tuesday.",
    "Today is Wednesday.",
    "Today is Thursday.",
    "Today is Friday.",
    "Today is Saturday.",
    "Today is Sunday."
};
int state[N];
 
int get_person(string str)
{
    for (int i = 0; i < m; i++)
        if (name[i] == str)
            return i;
    return -1;
}
 
pair <int, string> get(string str)
{
    int t = str.find(":");
    int person = get_person(str.substr(0, t));
    return make_pair(person, str.substr(t + 2));
}
 
int get_state(int bad_man, int day, int now, string line)
{
    if (line == "I am guilty.")
    {
        if (bad_man == now) return 0;
        return 1;
    }
    if (line == "I am not guilty.")
    {
        if (bad_man == now) return 1;
        return 0;
    }
    int t = line.find(" is guilty.");
    if (t != -1)
    {
        int p = get_person(line.substr(0, t));
        if (p == bad_man) return 0;
        return 1;
    }
    t = line.find(" is not guilty.");
    if (t != -1)
    {
        int p = get_person(line.substr(0, t));
        if (p != bad_man) return 0;
        return 1;
    }
 
    for (int i = 0; i < 7; i++)
        if (weekday[i] == line)
        {
            if (i == day) return 0;
            return 1;
        }
 
    return -1;
}
 
bool check(int bad_man, int day)
{
    memset(state, -1, sizeof state);
    for (int i = 0; i < P; i++)
    {
        pair <int, string> t = get(sentence[i]);
        int p = t.first;
        int s = get_state(bad_man, day, p, t.second);
 
        if (s == 0)
        {
            if (state[p] == 1) return false;
            state[p] = s;
        }
        else if (s == 1)
        {
            if (state[p] == 0) return false;
            state[p] = s;
        }
    }
 
    int fake = 0, other = 0;
    for (int i = 0; i < m; i++)
        if (state[i] == 1)
            fake++;
        else if (state[i] == -1)
        other++;
 
    if (fake <= n && fake + other >= n) return true;
    return false;
}
 
int main()
{
    cin >> m >> n >> P;
    for (int i = 0; i < m; i++) cin >> name[i];
    getline(cin, sentence[0]);
    for (int i = 0; i < P; i++) getline(cin, sentence[i]);
 
    int cnt = 0, p;
    for (int i = 0; i < m; i++)
    {
        bool flag = false;
        for (int j = 0; j < 7; j++)
            if (check(i, j))
            {
                flag = true;
                break;
            }
 
        if (flag)
        {
            cnt++;
            p = i;
        }
    }
 
    if (cnt == 1) cout << name[p] << endl;
    else if (cnt > 1) puts("Cannot Determine");
    else puts("Impossible");
 
    return 0;
}

2. 机器翻译

• 来源：NOIP2010提高组 https://ac.nowcoder.com/acm/contest/258/A
  算法知识点: 模拟，队列
  复杂度：O(N)

解题思路：

这道题是让我们实现一个先进先出的缓存机制。
数据的存储：
由于是先进先出，所以我们可以用循环队列来维护缓存中的所有单词，这里可以用C++STL中的queue。
用bool数组存储每个单词是否已经在队列中，这样就可以用 O(1) 的时间判断每个单词是否已在缓存中了。
从前往后依次处理文章中的每个单词，然后分情况处理：
如果 x 已在缓存中，不需要做其他处理；
如果 x 不在缓存中：
如果队列不满，将 x 插入队尾；
如果队列已满，将队头弹出，然后将 x 插入队尾；

时间复杂度分析:

依次对每个单词处理一遍，每次处理时只有常数次操作，所以总时间复杂度是 O(N)，其中 N 是单词个数。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; const int N = 1010;
 
int n, m;
bool st[N];
 
int main()
{
    cin >> m >> n;
 
    int res = 0;
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (!st[x])
        {
            res++;
            if (q.size() == m)
            {
                st[q.front()] = false;
                q.pop();
            }
            q.push(x);
            st[x] = true;
        }
    }
 
    cout << res << endl;
 
    return 0;
}

3. 神奇的幻方

• 来源：NOIP2015提高组 https://ac.nowcoder.com/acm/contest/263/D
  算法知识点: 模拟
  复杂度：O(n^2)

解题思路：

直接按照题目给出的填数步骤模拟一遍即可。

时间复杂度分析:

总共有 n2 个数，每个数只被填写一遍，所以总时间复杂度是 O(n^2)。

#include <iostream>
using namespace std; const int N = 40;
 
int a[N][N];
 
int main()
{
    int n;
    cin >> n;
 
    int x = 1, y = n / 2 + 1;
    for (int i = 1; i <= n *n; i++)
    {
        a[x][y] = i;
        if (x == 1 && y == n) x++;
        else if (x == 1) x = n, y++;
        else if (y == n) x--, y = 1;
        else if (a[x - 1][y + 1]) x++;
        else x--, y++;
    }
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            printf("%d ", a[i][j]);
        puts("");
    }
 
    return 0;
}

4. 时间复杂度

• 来源：NOIP2017提高组 https://ac.nowcoder.com/acm/contest/265/E
  算法知识点: 栈，模拟，字符串处理
  复杂度：O(TL^2)

解题思路：

循环的时间复杂度取决于最内层的计算次数，即嵌套最深的一层循环的计算次数。

循环的嵌套和括号序列的嵌套类似，所以我们可以借助栈来遍历整个代码序列。

当遇到FOR语句时，将该循环压入栈顶，当遇到END语句时，将栈顶的循环弹出。那么栈中从底到顶的序列就是当前循环从外到内嵌套的序列。

对于每层循环FOR i x y，我们先判断它的计算次数cmp：

x 是 n 时:
y 也是 n，那么循环次数是 O(1);
y 是正整数，由于 n 远大于100，且 x,y 在100以内，所以这个循环一次也不执行；
x 是正整数时：
y 是 n,那么会循环 O(n) 次；
y 是正整数，如果 x≤y，那么会循环 O(1)次，如果 x>y，那么一次也不执行；
然后判断整个循环嵌套序列的计算次数：

如果外层循环中的某一层执行次数是0或者当前循环的执行次数是0，那么当前这层的计算次数就是0；
否则当前这层的循环次数就是上一层循环的执行次数乘以前面判断出的循环次数 cmp；
语法错误有两种：

对于当前循环创建的变量，如果在栈中已经出现过，说明与外面的某一层循环的循环变量重名了，产生语法错误；
如果遍历过程中对空栈执行弹出操作，或者遍历结束后栈不为空，说明FOR语句与END语句不匹配，产生语法错误。
时

时间复杂度分析:

总共有 T 个测试数据，对于每个测试数据，每个循环会进栈一次，出栈一次，每次进栈之前会循环一遍栈中所有元素，判断是否存在变量重名的情况，所以总时间复杂度是 O(TL^2)。

#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;
 
typedef pair <char, int> PCI; const int N = 110;
 
int tt;
PCI stk[N]; // 栈中存储当前嵌套的所有循环
// first存储每一层的变量名
// second存储到当前这层总共的计算量，如果为-1，表示当前这层无法到达
 
int get_number(string str) // 将字符串转化成整数
{
    int res = 0;
    for (auto c: str) res = res * 10 + c - '0';
    return res;
}
 
int get_time(string str) // 提取出str中n的次数
{
    if (str == "O(1)") return 0;
    int t = str.find('^');
    string num = str.substr(t + 1);
    num.pop_back();
    return get_number(num);
}
 
bool has(char c) // 判断当前栈中是否已经存在变量c
{
    for (int i = 1; i <= tt; i++)
        if (stk[i].first == c)
            return true;
    return false;
}
 
int get_cmp(string x, string y) // 判断 for (int i = x; i <= y; i ++) 的循环次数是n的多少次方
{
    if (x == "n")
    {
        if (y == "n") return 0;
        return -1;
    }
 
    if (y == "n") return 1;
    int a = get_number(x), b = get_number(y);
    if (a <= b) return 0;
    return -1;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    while (T--)
    {
        int n;
        string str;
        cin >> n >> str;
        int tm = get_time(str);
 
        int max_cmp = 0;
        bool error = false;
        tt = 0;
        string line;
        getline(cin, line);
        for (int i = 0; i < n; i++)
        {
            getline(cin, line);
 
            if (!error)
            {
                if (line == "E")
                {
                    if (tt) tt--;
                    else error = true;
                }
                else
                {
                    stringstream sin(line);
                    string F, i, x, y;
                    sin >> F >> i >> x >> y;
 
                    if (has(i[0])) error = true;
                    else
                    {
                        int cmp = get_cmp(x, y);
                        if (!tt) stk[++tt] = {
                            i[0], cmp
                        };
                        else
                        {
                            int computation = -1; // -1表示当前这层无法到达
                            if (stk[tt].second >= 0 && cmp >= 0) computation = stk[tt].second + cmp;
                            stk[++tt] = {
                                i[0], computation
                            };
                        }
                        max_cmp = max(max_cmp, stk[tt].second);
                    }
                }
            }
        }
 
        if (tt) error = true;
 
        if (error) puts("ERR");
        else if (tm == max_cmp) puts("Yes");
        else puts("No");
    }
 
    return 0;
}