【马蹄集】—— 递归与分治专题_马蹄集mt3016

递归与分治专题

---

MT2030 邮箱地址

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

一个地址由 <username>@<hostname>[/resource] 组成。
其中 username 和 hostname 之间只允许有一个 @；尖括号 < > 内包含的为必选项，方括号 [ ] 内包含的为可选项。如果 / 出>现，则必须跟有resource字段。各字段要求如下：

1. username字段允许大写字母、小写字母、数字、下划线，其长度应在1到16。
2. hostname字段类似网址，允许用零个或多个 . 来分割，但不允许连续两个 . 连在一起。同时，hostname不允许以 . 开头或结束。每一段的要求同 username字段， hostname字段的总长度在1到32。
3. resource 字段要求同 username 字段，不限制长度。
   现给出一个地址，请判断是否合法。

格式

输入格式：一行，一个字符串，表示一个地址（保证地址的字符的ASCII在33到127间），地址长度不超过1000字符。
输出格式：一行，如果合法输出YES，否则输出NO。

样例 1

输入：123@npu.com
输出：YES

相关知识点：模拟、字符串

题解

本题的目的是检测待输入字符串是否满足给定的 3 个条件。最简单的方法就是直接模拟这个检测过程，即对输入字符串进行扫描（判断各字段是否满足给定条件）。由于该题并不是很难，因此将求解的步骤全部注释在代码中，如下（已 AC）：

/*
	MT2030 邮箱地址
*/ 

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

const int MAX = 1005;
// username 字段长度上限 
const int USERNAMEMAX = 16;
// hostname 字段长度上限 
const int HOSTNAMEMAX = 32;
char address[MAX];

// 该函数用于检测要求 1 所提限制 
bool judgeLetter(char c)
{
	if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_') return true;
	return false;
}

bool judgeMailAddress(char *str)
{
	// p 为临时指针、atNum 为 @ 符号的个数、resPos 为资源符号 / 的位置、resNum 为资源符号 / 的个数、strlen 为字串总长度寄存器 
	int p = 0, atPos = 0, atNum = 0,  resPos = 0, resNum = 0, strlen = 0;
	
	// 下面的循环将完成以下功能： 
	// 1、求出字串 str 的长度 
	// 2、获取 @ 符号的位置并记录最后一个 @ 符号的位置 
	// 3、获取 / 符号的位置并记录最后一个 / 符号的位置
	while(str[p]){
		if(str[p] == '@') {
			atPos = p;
			atNum++;
		}
		if(str[p] == '/'){
			resPos = p;
			resNum++;
		}
		p++;
	}
	
	// 将字串 str 的长度存入 strlen
	strlen = p;
	
	// 判断符号的合法性：当 @ 符号个数不为 1 或 / 符号的个数大于 1 时，该邮箱地址非法 
	if(atNum != 1 || resNum>1) return false;
	
	// 下面判断 username 字段的合法性
	// 判断 username 的长度合法性： 当username 字段长度为 0 或大于给定长度时，该邮箱地址非法 
	if(atPos == 0 || atPos > USERNAMEMAX) return false;
	
	// 判断 username 的字符合法性 
	p = 0;
	while(p<atPos){
		if( judgeLetter(str[p]) ) p++;
		else return false;
	}
	
	// 下面判断 hostname 的合法性
	p++; 
	// 判断 hostname 的长度合法性（至少为 1，至多不超过 HOSTNAMEMAX）：
	// 1、当无 resource 字段时，需要用整个字段的长度 strlen 来与 p 指针的位置进行比较
	// 2、当有 resource 字段时，需要用资源字段的指针 resPos 来与 p 指针的位置进行比较
	if(( resNum == 0 && (strlen==p || strlen-p>HOSTNAMEMAX) ) || ( resNum == 1 &&  ( resPos==p || resPos-p>HOSTNAMEMAX))) return false;
	
	// 判断 hostname 内"." 的合法性 
	if(str[p] == '.' || ( resNum == 0 && str[strlen-1] == '.') || ( resNum == 1 && str[resPos-1] == '.') ) return false;
	
	// namelen 为每次扫描时，两个 "." 内的子串长度寄存器； plimit 为 hostname 字段指针 p 的限制长度（它应该是 resPos 和 strlen 中的较大者） 
	int namelen, plimit = (resNum == 1 ? resPos : strlen);
	
	// 下面的循环将取出 hostname 字段中被 "." 隔开的每一段 
	while(p<plimit){
		namelen = 0;
		
		// 只要当前指针 p 未“走到尽头” 或 遇到"." 就检测当前字符的合法性 
		while(p<plimit && str[p] != '.'){
			if(judgeLetter(str[p])){
				namelen++;
				p++;
			}
			
			// 一旦某个字符非凡直接判当前邮箱地址非法 
			else return false;
		}
		
		// 若当前得到的某个子串长度为 0 或者超过 USERNAMEMAX 限制，则邮箱地址非法 
		if(namelen==0 || namelen>USERNAMEMAX ) return false;
		
		// 只要当前 p 指针还“未走到尽头”就将 p 指针后移 
		if(p < plimit) p++;
	}
	
	// 判断是否有 resource 字段
	if(resNum == 1){
		
		// 若有则将指针后推 
		p++;
		
		// 条件3：当资源符合 / 存在时，resource 字段长度至少为 1 
		if(p == strlen) return false; 
		
		// 判断 存在时，resource 字段中的各字符是否合法 
		while(p<strlen){
			if( judgeLetter(str[p]) ) p++; 
			else return false;
		}
	}
	
	// 上面所有测试都能通过，则邮箱地址合法 
	return true;
}

int main( )
{
	// 获取输入 
	cin>>address;
	
	// 执行判断并输出对应结果 
	if(judgeMailAddress(address)){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
    return 0;
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

---

MT2039 换换换

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

机器人小R在看一个魔术表演，魔术师面前有一排共 N 个倒扣着的杯子，其中每一个下面都有一个小玩具 $t_i$ ，并且每个小玩具都是唯一的。魔术师飞快地变换杯子之后让小 R 猜其中 M 个玩具 $t_j$ 在哪个杯子里。由于机器人小 R 内置的程序只能记录杯子的数量 N，小玩具初始的位置 p，以及魔术师每次变换杯子的位置 $p_1,p_2$ 。小 R 的主人希望你能写一个程序，帮助小 R 找出玩具。

格式

输入格式：第一行给定三个整数N , M , T，T为魔术师操作的次数；
     接下来的 N 行，每行给定一个字符串 $t_i$；
     之后的 T 行，每行给定两个位置 $p_1,p_2$ ，位置从1开始计数；
     最后 M 行，每行给定一个字符串 $t_j$ 。
输出格式：M 行，每行一个整数，表示杯子现在的序号。

样例1

输入：5 5 5
   car
   van
   track
   dog
   cat
   1 2
   4 5
   3 2
   5 1
   1 4
   van
   car
   track
   dog
   cat
输出：5
   3
   2
   4
   1

备注

$100\le N,M,T\le 5e4,1\le |t_i|\le 20,t_j\in t_i$

相关知识点：模拟

题解

本题中，假设构建一个用于存放玩具与其位置的字符串型数组 string tricks[N] ，则当对玩具进行位置交换时，我们只需要将数组中对应索引的值进行交换。如，假设对样例 1 中的 1 2 进行交换时，实际上只需要：tmp= tricks[1], trick[1] = tricks[2], trick[2] = tmp; 即可。这样一来，直接模拟整个交换过程就能在最后将所有玩具的位置信息都记录下。

但是问题的关键在于，题目最后要求的映射关系是从“玩具名称”得到“对应所在杯子的序号”（即从字符串到整型数字）。那要怎么做呢？最直截了当的做法是每次都遍历tricks数组，去搜索输入的某个指定字符串，然后再将找到的字符串对应的序号（即索引）输出，但是这样的做法太繁琐，并且超时无疑。最简单的做法是再建立一个从“字符串”到“索引”的映射，并参与交换过程即可（跟踪索引的变换情况），这样就能直接得到从字符串到序号的映射。这种数据结构可直接用 STL 提供的模板，如 map、pair 等。下面直接给出求解该题的完整代码（已 AC）:

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

const int N = 50005;

// "索引" 到 "字符串" 的映射
string tricks[N];

// "字符串" 到 "索引" 的映射
map<string,int> mp;

int main( )
{
	int n,m,t,p1,p2;
	string tmp;
	
	// 获取输入 
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		cin>>tmp;
		tricks[i] = tmp;
		mp[tmp] = i;
	} 
	
	// 模拟交换过程 
	while(t--){
		cin>>p1>>p2;
		
		// 跟踪玩具（字符串）的交换情况 
		swap(tricks[p1],tricks[p2]);
		
		// 跟踪序号（索引）的交换情况 
		swap(mp[tricks[p1]],mp[tricks[p2]]);
	}
	
	// 对 m 次询问予以回复 
	while(m--){
		cin>>tmp;
		cout<<mp[tmp]<<endl;
	}
    
    return 0;
}
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

---

MT2040 银行账户

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

据说对银行账户进行盗窃时，如果只盗取小数点下的数值，就不容易引起注意，所以你决定进行尝试。
银行总共有 n 个账户，m 次转账，对每次转账，你可以盗取（转账金额-转账金额下取整）的资金，并使转入账户的警戒值增加相同数值，当任意账户的警戒值 > 1，或者无法实现转账 (转出账户余额不足)，或者 m 次转账全部完成，你停止盗取，请计算总盗取金额。

格式

输入格式：第一行 n, m，表示有 n 个账户，m 条转账记录；
第二行 n 个实数，表示每个账户的资金；
接下来 m 行，每行有三个参数；
整数 x，整数 y，实数 z，分别表示转出账户，转入账户，和转账金额。
输出格式：输出盗取金额，保留两位小数。

样例 1

输入：5 5
   2 2 2 2 2
   1 2 1.5
   2 1 1.5
   1 2 1.5
   2 1 1.5
   1 2 1.5
输出：2.00

备注

$1\le n\le 1000,1\le m\le 1000；$
$0<每个账户初始资金<10；$
$1\le x,y\le n,x\ne y；$
样例解释：
第一次转账后：0.5 3 2 2 2，已盗取金额 0.5，账户 2 警戒值 0.5；
第二次：1.5 1.5 2 2 2，已盗取 1，账户 1 警戒值 0.5；
第三次：0 2.5 2 2 2，已盗取 1.5，账户 2 警戒值 1；
第四次：1 1 2 2 2，已盗取 2，账户 1 警戒值 1；
第五次，账户 1 余额不足，转账无法进行，停止。

相关知识点：模拟

题解

这道题应该是这周最简单的一道题，直接模拟整个过程就行，不需要任何技巧，只需要最后进行下格式化输出即可，AC 代码如下：

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

const int MAX = 1005;
const int REDLINE = 1;

// 定义账户信息：维度 0 表示余额；维度 1 表示警戒值 
float accounts[MAX][2];

int main( )
{
	int n,m,x,y;
	float money,delta,steal = 0; 
	
	// 录入账户信息 
	cin>>n>>m; 
	for(int i=1;i<=n;i++){
		cin>>accounts[i][0];
		accounts[i][1] = 0;
	}
	
	// 执行 m 次转账 
	while(m--){
		cin>>x>>y>>money;
		
		// 判断当前转账是否能执行
		if(accounts[x][0] < money) break;
		
		// 发起转账的账户扣钱 
		accounts[x][0] -= money;
		
		// 盗取其中的蝇头小利 
		delta = money - int(money);
		steal += delta;
		
		// 接受转账的账户收钱 
		accounts[y][0] += int(money);
		
		// 接受转账的账户增加警戒 
		accounts[y][1] += delta;
		
		if(accounts[y][1] > REDLINE) break;
	}
	
	// 注意格式化输出 
	cout<<fixed<<setprecision(2)<<steal;
	
    return 0;
}
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
47
48
49

---

MT2041 三角形的个数

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

最近璃月的海灯节到了，一位来自码蹄集的小码哥正好游历至此，一种有趣的装饰图案引起了他的兴趣：这种图案将一个三角形每条边分为 n 等分，然后将对应的等分点相连，使得连成的线段平行于三条边中的一条，这样就构成了大三角套小三角的繁复图案。现在有许多类似的图案，这名学者想知道每个图案中各包含了几个三角形，请你帮帮他。
如图所示是一个二等分的例子：

格式

输入格式：第一行一个正整数 N，代表图案个数。
接下来 N 行每行一个正整数 $n_i$ ，代表第 i 个三角形每条边被分为了 $n_i$ 等分。
输出格式：输出 N 行，每行一个正整数代表第 $i$ 个图案中包含的三角形个数。

样例 1

输入：2
   2
   3
输出：5
   13

备注

$1\le N\le 100,1\le n\le 500。$
最大的三角形别忘了算哦！

相关知识点：递推、递归、分治

题解

方法一

在求子三角形个数时，为了避免漏解，我们应当从某个 “连续” 的属性出发，去一一算出在该情况下的解的个数，然后再进汇总即可。一个很直观的 “属性” 是子三角形的边长（也许第一次做题的你会很难想到，但当你做多了这种类型的题后，你就会慢慢地习得这一技能了）。于是，从这一层面出发，该问题就转变为 “求边长为 1 的三角形个数 + 求边长为 2 的三角形个数 + ……” 。
如果你能想到上一点，那么恭喜你，你已经具备了基础的 ACM 选手的思维能力。但是当你用前面的结论在求解题目时，会发现依然很难找到各边长的小三角形之间的迭代规律（一个通用的方程，或者说递推式）。因此，我们还需要深挖这里面的细节。如果你足够聪明，也许你会发现：大三角形内部的小三角形其实有两种类别：一种是 “角朝上” 的小三角形，另一种是 “角朝下” 的小三角形。于是，我们可对此再进行一个划分，并分别讨论。
基于这样的思路，可以将整个大三角形（设其边长为 n ）中的小三角形分为以下 3 部分进行统计：

1. 边长为 1 的所有小三角形个数为 $n\times n$；
2. 边长为 2~n 的所有 “角朝上” 的小三角形个数为 $(1+2+...+n-1)+(1+2+...n-2)+...+1=\frac{n(n+1)}{2}+\frac{(n-1)(n-2)}{2}+\cdots +1$；
3. 当边长大于 3 时，“角朝下”的小三角形个数。由于在 1 中已经统计了边长为 1 的小三角形个数，因此在这里仅统计边长不低于 2 的 “角朝下” 的小三角形。实际上，当 “角朝下” 的小三角形边长为 $i$ 时，其数量为（画图找规律，这个很显而易见）： $Su{m}_i=1+2+\dots +i=\frac{i(i+1)}{2}$。

基于这样的思路，可写出以下代码（已 AC）：

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

int getTheTriangle(int n){
	if(n==0) return 0;
    int sum = 0;
    if(n>=2){
    	sum += n*n;
    	for(int i=1; i<n; i++) sum += i*(i+1)/2;
    	if(n>=4)
    		for(int i=n-3;i>0;i-=2) sum += (1+i)*i/2;
    }
    return sum;
}

int main( )
{
	int N, n;cin>>N;
	while(N--){
		cin>>n;
		cout<<getTheTriangle(n)<<endl;
	}
	
    return 0;
}
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

方法二

对原问题进行抽象，可将其转换为以下问题：
将一个正三角形的各边都 $n$ 等分，过各分点作其它两边的平行线，一共可产生多少个三角形？


解：不妨设正 ΔABC 的边长为 n，则该三角形仅含两类子三角形：
  1、角朝上的子三角形（任意情况下都存在）；
  2、角朝下的子三角形（原三角形边长 n≥2）。

从上图中不难总结出：在边长为n的三角形中对其进行n等分时，其子三角形数量满足：

第 1 类子三角形：
  边长为 1 的三角形数量为：$1+2+\cdots +n=\frac{n(n+1)}{2}$；
  边长为 2 的三角形数量为：$1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$；
  ……
  边长为 n 的三角形数量为：1。
将上述所有式子求和可得到第1类子三角形的总数为：$\frac{n(n+1)(n+2)}{6}$

第 2 类子三角形：
  边长为 1 的三角形数量为：$1+2+\cdots +(n-1)=\frac{n(n-1)}{2}$；
  边长为 2 的三角形数量为：$1+2+\cdots +(n-1)=\frac{(n-3)(n-2)}{2}$；
  ……
  边长为 m 的三角形数量为：$1+2+\cdots +(n-(m+1))=\frac{(n-m-1)(n-m)}{2}$。
将上述所有式子求和可得到第2类子三角形的总数，但是此值受n的奇偶性制约。
当n为奇数时，此类子三角形的总数为：$\frac{(n-1)(n+1)(2n+3)}{24}$；
当n为偶数时，此类子三角形的总数为：$\frac{n(n+1)(2n-1)}{24}$；


综上可知，总的子三角形个数为
N = { ( n + 1 ) ( 2 n 2 + 3 n − 1 ) 8 ， n 为偶数 n ( n + 2 ) ( 2 n + 1 ) 8 ， n 为奇数 N=

$$\begin{equation} \left\{ \begin{aligned} \nonumber &\frac{(n+1)(2n^2+3n-1)}{8} ，n 为偶数\\ &\frac{n(n+2)(2n+1)}{8}，n 为奇数\\ \end{aligned} \right. \end{equation}$$ N=⎩ ⎨ ⎧​​8(n+1)(2n2+3n−1)​，n为偶数8n(n+2)(2n+1)​，n为奇数​​
基于这样的思路，可写出以下代码（已 AC）：

#include<bits/stdc++.h> 

using namespace std;

int getTheTriangle(int n){
    if(n%2) return (n+1)*(2*n*n+3*n-1)/8;
    else return n*(n+2)*(2*n+1)/8;
}

int main( )
{
    int N, n, cnt; cin>>N;
    while(N--){
        cin>>n;
        cout<<getTheTriangle(n)<<endl;
    }
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

MT2046 巨大的错误

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

提瓦特大陆上有一个贫穷的占星术士小码哥，在占星的时候，小码哥时常需要将命运启示他的信息与手中命运之轮上的命星一一对应，现在有n个启示和n个命星需要一一对应，有时，因为命运实在太过难以言明，小码哥会将所有的启示与命星都对应错了，此时称小码哥犯了一个巨大的错误，问一共有多少种情况可被称为“巨大的错误”。

格式

输入格式：输入一个正整数 $n$。
输出格式：输出一个正整数表示所求答案。

样例 1

输入：2
输出：1

备注

其中 $n\le 20$。

相关知识点：递推、递归、分治、组合数学

题解

这个问题的本质是：对 $n$ 个数进行排列，问每一个数都不待在原来位置的情况有多少种？该问题也被称为 “全错位排列” 问题，源自于当时最有名的数学家约翰·伯努利 (Johann Bernoulli，1667－1748) 的儿子丹尼尔·伯努利 (DanidBernoulli，1700－1782) 提出的 “装错信封问题” 。


该问题通常可以通过递推公式进行计算。假设现在对 $n$ 个数进行排列，设每个数都不在原来的位置的情况为 $F(n)$ 种 ($n\ge 2$)。
先考虑第 $n$ 个数，有 $n-1$ 种选择，假设第 $n$ 个数的位置为 $x_n(x_n=k,k\ne n)$ ；接着考虑第 $k$ 个数，这时需要分两种情况讨论：

• 若第 $k$ 个数的位置 $x_k=n$，则就相当于将位置 $k,n$ 的数进行了对换，那么接下来就只需要对剩余的 $n-2$ 个数进行全错位排列。这就相当于将问题规模由 $n$ 变为 $n-2$，即有 $F(n-2)$ 种排法；
• 若第 $k$ 个数的位置 $x_k\ne n$，（这就相当于位置 $n$ 不能与数 $x_k$ 组合），那么对于当前这 $n-1$ 个数而言，其还是等价于对当前 $n-1$ 个数进行全错位排列。即将问题规模由 $n$ 变为 $n-1$，即有 $F(n-1)$ 种排法。

综上可得到该问题的递推公式为： $F(n)=(n-1)\ast (F[n-1]+F[n-2])$，其中： $n>2$ ，初始情况下： $F(1)=0,F(2)=1$。
例如：当 $n=3$ 时，对应的情况有：(2,3,1)，(3,1,2)，共2种，而 $F(3)=2\ast (F(2)+F(1))=2$，公式成立;
   当 $n=4$ 时，对应的情况有：(2,1,4,3)，(2,3,4,1)，(2,4,1,3)， (3,1,4,2)， (3, 4,1,2)，(3,4,2,1)，(4,1,2,3)，(4,3,1,2)，(4,3,2,1)，共9种，而 $F(4)=3\ast (F(3)+F(2))=3\ast (2+1)=9$，公式成立。

其他的情况可自行验证。


基于此，可直接写出以下代码（已 AC）:

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

int main( )
{
	int n, p = 3;
	long num1 = 0, num2 = 1, num3;
	
	// 获取输入 
	cin>>n;
	
	// 特殊处理
	if(n==2){
		cout << num2;
		return 0;
	}
	
	// 递推 
	while(p <= n){
		// 递推 
		num3 = (p-1)*(num1+num2);
		
		// 移位 
		num1 = num2;
		num2 = num3;
		
		// 指针移动 
		p++;
	}
	
	cout<<num3;
	
    return 0;
}
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

END

---