NOIP提高组 模拟

1.NOIP 2010 机器翻译

2.NOIP 2015 神奇的幻方

3.NOIP 2017 时间复杂度

4.NOIP 2003 侦探推理

<mark>要点</mark>

<mark>模拟题，其实没有什么算法可言，最重要的是把思路理清楚，把各种细节处理好。</mark>

<mark>1.NOIP 2010 机器翻译</mark>

<mark>题目描述</mark>
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 M−1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

<mark>输入描述:</mark>
输入共2 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数M 和N，代表内存容量和文章的长度。
第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

<mark>输出描述:</mark>
共1 行，包含一个整数，为软件需要查词典的次数。

<mark>输入</mark>
3 7
1 2 1 5 4 4 1

<mark>输出</mark>
5
<mark>说明</mark>
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
空：内存初始状态为空。
1． 1：查找单词1 并调入内存。
2． 1 2：查找单词2 并调入内存。
3． 1 2：在内存中找到单词1。
4． 1 2 5：查找单词5 并调入内存。
5． 2 5 4：查找单词4 并调入内存替代单词1。
6． 2 5 4：在内存中找到单词4。
7． 5 4 1：查找单词1 并调入内存替代单词2。
共计查了5次词典。

<mark>分析</mark>

1.单词在缓存中先进先出，
所以可以用队列进行模拟。
2.该题范围比较小，
所以可以用一个bool数组，
进行快速判断单词是否在缓存中存在。
3.枚举每一个单词：
如果单词已经在缓存中，则pass
否则，
缓存不满，则直接插入
缓存已满，弹出队尾

<mark>标程</mark>

#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;
}

<mark>2.NOIP 2015 神奇的幻方</mark>

<mark>题目描述</mark>
幻方是一种很神奇的 N*N 矩阵：它由数字 1,2,3,…N x N 构成，且每行、每列及两条对角线上的数字之和都相同。
当 N 为奇数时，我们可以通过下方法构建一个幻方：
首先将 1 写在第一行的中间。
之后，按如下方式从小到大依次填写每个数 K (K=2,3,…,N x N) :
1.若 (K-1) 在第一行但不在最后一列，则将 K 填在最后一行， (K-1) 所在列的右一列；
2.若 (K-1) 在最后一列但不在第一行，则将 K 填在第一列， (K-1) 所在行的上一行；
3.若 (K-1) 在第一行最后一列，则将 K 填在 (K-1) 的正下方；
4.若 (K-1) 既不在第一行，也最后一列，如果 (K-1) 的右上方还未填数，则将 K 填在 (K-1) 的右上方，否则将 L 填在 (K-1) 的正下方。

<mark>输入描述:</mark>
一个正整数 N ，即幻方的大小。

<mark>输出描述:</mark>
共 N 行 ，每行 N 个整数，即按上述方法构造出的 N x N 的幻方，相邻两个整数之间用单空格隔开。

<mark>输入</mark>
3

<mark>输出</mark>
8 1 6
3 5 7
4 9 2

<mark>分析</mark>

纯模拟。

<mark>标程</mark>

#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;
}

<mark>3.NOIP 2017 时间复杂度</mark>

<mark>题目描述</mark>
给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。 A++ 语言的循环结构如下：
F i x y
循环体
E
然后判断 i 和 y 的大小关系，若 i 小于等于 y 则进入循环，否则不进入。每次循环结束后i都会被修改成 i +1，一旦 i 大于 y 终止循环。 x 和 y 可以是正整数（x 和 y 的大小关系不定）或变量 n。n 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 100。 E表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。
注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 O 表示通常意义下 的概念。

<mark>输入描述:</mark>
输入文件第一行一个正整数 t，表示有 t(t≤ 10) 个程序需要计算时间复杂度。
每个程序我们只需抽取其中 F i x y和E即可计算时间复杂度。注意：循环结构允许嵌套。
接下来每个程序的第一行包含一个正整数 L 和一个字符串，L 代表程序行数，字符串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w) 表示复杂度为 nw，其中 w 是一个小于 100 的正整数（输入中不包含引号），输入保证复杂度只有 O(1) 和 O(n^w) 两种类型。
接下来 L 行代表程序中循环结构中的 F i x y 或者 E。 程序行若以 F 开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y，其中 i 是一个小写字母（保证不为 n ），表示新建的变量名，x 和 y 可能是正整数或 n ，已知若为正整数则一定小于 100。 程序行若以 E开头，则表示循环体结束。

<mark>输出描述:</mark>
输出文件共 t 行，对应输入的 t 个程序，每行输出Yes或No或者ERR，若程序实际复杂度与输入给出的复杂度一致则输出 Yes，不一致则输出No，若程序有语法错误（其中语法错误只有: ①F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出ERR。
注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出ERR。

<mark>输入</mark>
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

<mark>输出</mark>
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

<mark>说明</mark>
第一个程序 i 从1 到 1 是常数复杂度。
第二个程序 x 从 1 到 n 是 n 的一次方的复杂度。
第三个程序有一个 F 开启循环却没有E结束，语法错误。
第四个程序二重循环，n 的平方的复杂度。
第五个程序两个一重循环，n 的一次方的复杂度。
第六个程序第一重循环正常，但第二重循环开始即终止（因为 n 远大于 100，100 大于 4）。
第七个程序第一重循环无法进入，故为常数复杂度。
第八个程序第二重循环中的变量 x 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

<mark>分析</mark>

F i x y
//循环体
E

for(int i = x; i <= y; i++)
{
}

F i x y
F j a b
E
E

for(int i = x; i <= y; i++)
{
for(int j = a; j <= b; j++)
{
}
}

状态存储
用stack存储当前循环嵌套的结构
pair<char, int>
first -> 循环变量
second -> 时间复杂度是n的多少次方
算法流程
For i = x; i <= y; i++
(1)判断i在外层循环中是否存在
(2)求当前这层的计算量time
(3)将该语句压入栈中
End
(1)判断是否匹配

<mark>标程</mark>

#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，表示当前这层无法到达
intget_number(string str) // 将字符串转化成整数
{
    int res = 0;
    for (auto c: str) res = res * 10 + c - '0';
    return res;
}
intget_time(string str) // 提取出str中n的次数
{
    if (str == "O(1)") return0;
    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;
}
intget_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;
    inta = 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;
}

<mark>4.NOIP 2003 侦探推理</mark>

<mark>题目描述</mark>
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

证词中出现的其他话，都不列入逻辑推理的内容。

明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。

现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

<mark>输入描述</mark>
输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。
往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。

<mark>输出描述:</mark>
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。

<mark>输入</mark>
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??

<mark>输出</mark>
MIKE

<mark>分析</mark>

枚举，判断。

<mark>标程</mark>

#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;
}