Cloud_Player's Notes
0%

模拟与暴力

发表于
本文字数： 5.1k 阅读时长 ≈ 5 分钟

b站视频链接：北京理工大学ACM冬季培训课程
课程刷题地址 2020BIT冬训-模拟与暴力
本篇博文为看视频学习时的记录与自己的一些总结

模拟 && 暴力

模拟（implementation）

释义

在自然界和日常生活中,许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。

通俗的讲：
  找不到更高效的做法时，题目怎么描述就让程序怎么运行

特点

思考量不大，但阅读量和代码量可以很大
可以很简单，也可以很复杂
形式多样：走迷宫，斗地主，打麻将，打三国杀，魔塔…

注意：弄清题意，建立模型，注意细节

例题

约瑟夫环

问题背景

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）

据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从。首先从一个人开始，越过 k-2 个人（因为第一个人已经被越过），并杀掉第 k 个人。接着，再越过 k-1 个人，并杀掉第 k 个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

问题描述

已知n个人（编号1、2、…n）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个又从1开始报数，数到m的那个人又出列；依次规律重复下去，直到圆桌周围的人全部出列。给定n、m，输出出列人员先后顺序和最后剩下的人。

实现

数组实现：
利用公式 (p+m-1)%n ，找出要输出数组的下标
其中 p 为开始报数的人的编号，n 为当前剩下的人数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Joseph(int n, int m)
{
    int a[100], k = 0, p = 0;
    for(int i = 0; i < n; i++)
        a[i] = i + 1;
    while(n > 1)
    {
        p = (p + m - 1) % n;
        cout << "第" << ++k << "个出圈的是：" << a[p] << endl;
        for(int j = p + 1; j < n; j++)
            a[j - 1] = a[j];
        n--;
        if(p == n) p = 0;
    }
    cout << "最后剩下的是：" << a[p] << endl;
}

avatar

Online judge HDU-1073

给定两个输入，分别表示用户的输出和正确的输出，你来模拟测评机，对两个输出进行比较
完全相同输出 “Accepted”
只有空格，tab，回车的不同，输出 “Presentation Error”
否则输出 “Wrong Answer”

Presentation Error
avatar

Wrong Answer
avatar

分析

直接模拟比较过程即可

先将输入的两组数据去掉 ‘\n’,’\t’ 和 ’ ’ ，得到新的两组数据，那么这两组数据如果不是完全匹配的，结果一定是 WA 。如果这两组匹配了，去掉 ‘\n’,’\t’ 和 ’ ’ 前的不完全匹配则是 PE 。如果去掉前的两组数据完全匹配，则是 AC 。

False Coin POJ-1029

给你n个硬币，k组称量结果。在这n个硬币中有一个是假的，它的重量跟其他的不一样（不知道大小），真硬币的重量都相同，每组第一个数字代表左右放置硬币的数量，后面则是硬币的编号，每组后面的符号则是称量结果。问能不能确定哪个是假币，如果不能输出0。

Sample Input
avatar

Sample Onput
avatar

分析

结果为等号两边一定是真硬币，结果为不等号肯定含有假硬币
所以对于所有的不等式，将轻硬币放在 lightCoins 里，将重硬币放在 heavyCoins 里
因为只有一个假硬币，且假硬币不会一会儿轻，一会儿重，所以最后假硬币出现在 lightCoins 或者 heavyCoins 的次数一定和不等号出现的次数相等
若恰有一个满足条件的疑似硬币，则输出

Lytchen loves JSON

本题来自：The 7-th BIT Campus Programming Contest for Junior Grade Group

很大的大模拟
你需要编写一个程序，这个程序以一个合法的JSON文件作为输入，然后响应一系列查询，每个查询均会要求查询在这个JSON文档所包含的对象图上的一个值。

有兴趣可以自行体验

暴力（brute force）

释义

暴力是什么？

暴力就是枚举，指的是从问题所有可能的解的集合中一一枚举各元素，用题目中给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。

特点

优点是算法简单，在局部地方使用枚举法，效果会十分的好
缺点是运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢，计算量容易过大，可能获得一个TLE
所以需要先计算时间复杂度，并对其进行优化
一般直接暴力是不行的，需要有一些小小的优化

时间复杂度

时间复杂度：估算算法需要执行的运算次数
题目通常有时间限制，一秒、两秒、五秒、十秒等
计算机一秒能够进行的运算次数约为 $1e8$ 次
一次运算：赋值、比较、加减乘除模等运算，虽然实际运算时间不一样，但都可以近似看做一次运算
时间复杂度表达为 $O(f(n))$，$f(n)$ 是运算次数，关于问题规模 $n$ 的函数

由于近似性，可以忽略常数和低次项
$f(n)=n^2+3n+ \log_{2}(n)+4$ 与 $f(n)=n^2+3n+ \log_{2}(n)+1$ 运算次数不同，但时间复杂度相同，都为 $O(n^2)$

简单的例子：

求下列程序的时间复杂度

1
2
3
4
for (int i = 0; i < n;)
{
    i++;
}

$O(n)$

1
2
3
4
for (int i = 1; i < n;)
{
    i *= 2;
}

$O(\log_{2}n)$

1
2
3
4
5
6
7
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < i;)
    {
        j++;
    }
}

$O(n^2)$

1
2
3
4
5
6
7
8
for (int i = 0; i < 2 * n;)
{
    i++;
}
for (int i = 0; i < 3 * m;)
{
    i++;
}

$O(n+m)$

例题

一个简单的例子

已知 $S_n=1+1/2+1/3+…+1/n$. 给出一个整数 $k(1\le k\le 15)$ 计算出一个最小的 $n$，使得 $S_n>k$.

分析：
$S_n$ 为无穷级数，不收敛，对于任意 $k$ 总能找到一个 $S_n>k$
写一个程序算一下发现 $S_{1835421}>15$，不用担心超时
所以直接暴力即可

代码：

1
2
3
4
5
6
7
8
9
int query(int k)
{
    double sum = 0;
    for (int i = 1; ; i++)
    {
        sum += 1.0 / i;
        if (sum > k) return i;
    }
}

如果每个用例有 $q(1\le q\le 100000)$ 次询问呢？
每次都重新算太费时间，预处理！

1
2
int ans[20];
for (int i = 1; i <= 15; i++)   ans[i] = query(i);

百钱买百鸡问题

有一个人有100块钱，打算买100只鸡
到市场一看，公鸡一只三元，母鸡一只五元，小鸡三只一元
试求用100元买100只鸡，各为多少才合适？输出所有方案

分析：

根据题意我们可以得到方程组：

$3X+5Y+Z/3=100$

$X+Y+Z=100$

问题转化为求不定方程的非负整数解

解法1：for for for 枚举x，y，z，然后check              $O(n^3)$
解法2：for for 枚举x，y，让 $z=100-x-y$ ，然后check方程一   $O(n^2)$
解法3：for 枚举x，把x看作已知，解出y，z              $O(n)$

解法3代码：

1
2
3
4
5
for (int x = 0; x <= 25; x++)   //注意x，y，z的取值范围
{
    if ((200 - 8 * x) % 14 == 0 && ( 1200 - 6 * x ) % 14 == 0)
    cout<<x<<" "<<(200 - 8 * x) / 14<<" "<<( 1200 - 6 * x ) / 14<<endl;
}

avatar

Division Uva-725

输入正整数 $n（2\le n\le 79$），按照从小到大的顺序输出所有形如 $abcde/fghij=n$ 的表达式，其中a~j恰好为数字0到9的一个排列（可以有前导0）
Sample Input：$62$
Sample Output：$79546/01283 = 62$  $94736/01528 = 62$

分析:

可不可以枚举0到9的所有排列？
一共需要 $10！=3628800$ 可以接受，但是没必要
只需枚举fghij就可以算出abcde，再判断是否所有数字都不相同即可（对于判重存在多种方法）
枚举次数减少到一万以内

点这里传送到大佬的题解

大佬提示的注意点：
可用sprintf完成数值到字符串的格式转换，注意string此时不可直接作为接受字符串，需用字符数组

大佬的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int N, num=0;
int main() {
    while (scanf("%d", &N) == 1 && N != 0) {
        if (num != 0) puts(""); num++; // 连续的测试用例间需有空行
        char buf[100]; string s; int cnt=0;
        for (int fj=1234; ; fj++) { // 枚举1234 - 98765
            sprintf(buf, "%05d%05d", fj*N, fj); // 分子，分母转为字符串
            s = buf;
            if (s.size() > 10) break; // 其中一个超过5位数
            unordered_set<char> _set(s.begin(), s.end()); // 判重
            if (_set.size() == 10) { // 刚好整除且无重复数字
                printf("%s / %s = %d\n", s.substr(0,5).c_str(), s.substr(5).c_str(), N);
                cnt ++;
            }
        }
        if (cnt == 0) printf("There are no solutions for %d.\n", N);
    }
    return 0;
}

Four Operations HDU-5938

给定一个全是数字的字符串（长度为 $5$ 到 $20$），按照顺序加入 $‘+’、‘-’、‘*’、‘/’$ 四个运算符
求最大的计算结果，有 $q$ 组询问$（1\le q\le 100000）$

Sample Input：12345
Sample Output：1

分析：

直接暴力会超时，约 $20^4$ 种情况
计算形式总是 $a+b-c*d/e$，我们希望a、b、e大一些，c和d小一些
给c和d各一位，给e一位或两位，a和b中的一个拿一位，另一个拿光
共枚举4种情况即可

白学串

本题也来自：The 7-th BIT Campus Programming Contest for Junior Grade Group

给定一个n个数的数字序列，每个数不超过 $1e9$ 有 $q$ 次询问，每次询问一个区间是否存在三个数可以组成一个三角形，输出YES或NO $（1\le q\le 100000）$

分析：

不难发现，一组数不能构成三角形的充要条件是排完序后的任意三个相邻的数构不成三角形
换句话说，要写出尽可能多的数就要让相邻的三个数刚好构不成三角形
不能构成三角形的极限情况，就是 斐波那契数列
$1，1，2，3，5，8，13，21…$
而斐波那契数列增长很快，约第40项就达到了 $1e9$ ，而题目给的数不超过 $1e9$
所以当区间长度超过40，直接输出YES，否则排序后判断或直接暴力