ACDaily 7

本文最后更新于：2 个月前

枚举、模拟问题

这类问题通常没有一个非常契合的算法作为计算模板，但通常数据量是有过精心设计的。

我们可以通过以下问题来看一看。

1.连续区间段

没有思路时，从暴力做法入手

整体复杂度由每一步的复杂度进行组合后确定

一般可以通过一半的小数字样例

遍历复杂度为O(n)，排序算法复杂度为nlogn

当多重循环内包含大于等于10句话，就属于长代码了。

形成暴力做法的思考闭环后，有想法可以对算法进行优化

逆向思考，什么样的区间满足连号区间，可以发现连号区间等价于区间里最大数-最小数=区间端点差值。有了这样的思路我们就可以进行如下的设计：

先枚举区间左端点，再枚举区间右端点，根据以上思考对方案进行判别。

题目描述

在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。

输入格式

第一行是一个正整数 N，表示排列的规模。

第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。

输出格式

输出一个整数，表示不同连号区间的数目。

数据范围

1 ≤ N ≤ 10000,
1 ≤ Pi ≤ N

样例

输入样例1:

4
3 2 4 1

样例1解释:

第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]

输出样例1:

7

输入样例2:

5
3 4 2 5 1

样例2解释:

第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

输出样例2:

9

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, INF = 1000000000;
int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        int maxv = -INF, minv = INF;
        for(int j = i; j <= n; j++)
        {
            maxv = max(maxv, a[j]);
            minv = min(minv, a[j]);
            if(maxv-minv == j-i) res++;
        }
    }

    cout << res << endl;
    return 0;
}

2.递增三元组

题目描述

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：

1 ≤ i,j,k ≤ N
Ai < Bj < Ck

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1 ≤ N ≤ 10^5,
0 ≤ Ai,Bi,Ci ≤ 10^5

输入样例

3
1 1 1
2 2 2
3 3 3

输出样例

27

题解

  1. 首先，我们可以选择一个处理的起点，我们要求满足条件的组合数，考虑到A、C都由B限制，并且观察到数据量为10亿，无法做多重循环，所以我们能且仅能遍历一个数组B。
  2. 由于A、B、C中数的比较为相对关系，而数的范围是从0开始的，为了避免特判，我们可以使每个数+1而不改变相对关系
  3. 要时刻考虑计算的每个环节，在本题中方案数可能超过int范围，所以我们将计数器变量定义为LL类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
```
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;
int a[N], b[N], c[N];
int sa[N], sc[N];
typedef long long LL;

int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) cin >> a[i], a[i]++;
    for(int i = 0; i < n; i++) cin >> b[i], b[i]++;
    for(int i = 0; i < n; i++) cin >> c[i], c[i]++;
    
    for(int i = 0; i < n; i++) sa[a[i]]++, sc[c[i]]++;
    for(int i = 1; i <= N; i++) sa[i] += sa[i-1], sc[i] += sc[i-1];
    
    LL res = 0;
    for(int i = 0; i < n; i++)
    {
        res += (LL)(sa[b[i]-1])*(sc[N]-sc[b[i]]);
    }
    
    cout << res << endl;
    return 0;
}
```

3.特别数的和

题目描述

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示满足条件的数的和。

数据范围

1≤n≤10000

样例

输入样例：
40
输出样例：
574

题解

本题的关键在于数位的切分，懂得如何利用循环将一个数每一位切下来就可以简单地处理掉这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
```
#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        int last, val = i;
        while(val)
        {
            last = val % 10;
            if(last == 2 || last == 0 || last == 1 || last == 9)
            {
                res += i;
                break;
            }
            val /= 10;
        }
    }
    cout << res << endl;
    return 0;
}
```

4.错误票据

题目描述

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的ID号。

全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。

因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。

你的任务是通过编程，找出断号的ID和重号的ID。

假设断号不可能发生在最大和最小号。

输入格式

第一行包含整数 N，表示后面共有 N 行数据。

接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。

输出格式

要求程序输出1行，含两个整数 m,n，用空格分隔。

其中，m表示断号ID， n 表示重号ID。

数据范围

1≤N≤100

样例

blablabla

题解

本题地难点在于数据的读取，剩下的，就是一个简单的模拟了，本题的数据量也不是很大。

  1. 在使用getline读取信息时，如果在之前有使用cin读入数据，就要对getline做一次初始化处理，因为cin后会默认将一个空格放在流中，也就是说我们首先要将这个无意义的操作排除。
  2. geline每次可以读取一行信息，只有按下回车才会结束一次读取，它有两个参数，一个是外部输入流cin，一个是空字符串对象line。在使用getline后本次读取的全部信息都会被存储在对象中。
  3. 我们可以使用stringstream类中的ssin读取方法，它能够赋予字符串流的特性。即stringstream ssin(line)，进行这样的定义之后，我们就可以使用line >> a[i]以空格作为区分将line中的数据一个个输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
```
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N];

int main()
{
    int k, cnt = 0;
    string line;
    cin >> k;
    
    getline(cin, line);
    while(k--)
    {
        getline(cin, line);
        stringstream ssin(line);
        while(ssin >> a[cnt]) cnt++;
    }
    
    sort(a, a+cnt);
    
    int n, m;
    for(int i = 1; i < cnt; i++)
    {
        if(a[i] == a[i-1]) n = a[i];
        else if(a[i] >= a[i-1] + 2) m = a[i] - 1;
    }
    
    cout << m << " " << n << endl;
    return 0;
}
```

5.回文日期

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期，其中，前 4 位代表年份，接下来 2 位代表月份，最后 2 位代表日期。

显然：一个日期只有一种表示方法，而两个不同的日期的表示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的8位数字是回文的。

现在，牛牛想知道：在他指定的两个日期之间（包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 8 位数字是回文的，当且仅当对于所有的 i(1≤i≤8) 从左向右数的第i个数字和第 9−i 个数字（即从右向左数的第 i 个数字）是相同的。

例如：

•对于2016年11月19日，用 8 位数字 20161119 表示，它不是回文的。

•对于2010年1月2日，用 8 位数字 20100102 表示，它是回文的。

•对于2010年10月2日，用 8 位数字 20101002 表示，它不是回文的。

输入格式

输入包括两行，每行包括一个8位数字。

第一行表示牛牛指定的起始日期date1，第二行表示牛牛指定的终止日期date2。保证date1和date2都是真实存在的日期，且年份部分一定为4位数字，且首位数字不为0。

保证date1一定不晚于date2。

输出格式

输出共一行，包含一个整数，表示在date1和date2之间，有多少个日期是回文的。

样例

输入样例

20110101
20111231
输出样例

1

题解

本题的第一个关键在于策略的选取，首先年份信息理论上分布于1000与10000之间，构成回文数又只需要前4位，因此我们考虑枚举前4位的所有可能，通过数位切分构成回文数。之后判别该回文数是否位于目标范围内。

之后就需要考虑日期的合理性，即分别对年、月、日进行讨论。月数不能超过112，天数不能超过131，这是最基本的要求。

最后，考虑日期的现实性，2月的天数取决于该年是否为闰年，我们需要对其做更深入的分类讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
```
#include <iostream>
#include <cstdio>

using namespace std;

int mon[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date)
{
    int year = date/10000;
    int month = date%10000/100;
    int day = date%100;
    
    if(month < 1 || month > 12) return false;
    if(month == 2)
    {
        int leap = year%4 == 0 && year%100 != 0 || year %400 == 0;
        if(day > mon[1]+leap) return false;
    }
    
    if(day == 0 || month != 2 && day > mon[month-1]) return false;
    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;
    
    int cnt = 0;
    for(int i = 1000; i <= 9999; i++)
    {
        int date = i, x = i;
        for(int j = 0; j < 4; j++)
        {
            date = date*10+x%10;
            x /= 10;
        }
        if(date >= date1 && date <= date2 && check(date)) cnt++;
    }
    
    cout << cnt << endl;
    return 0;
}
```
ACDaily
模拟 枚举

本文作者: waitingFor
本文链接: http://example.com/2022/03/09/ACDaily/ACDaily-7/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！