算法竞赛专题讲座解题报告

920104330118

赵婧萱

[TOC]

（一）[NOIP2005 普及组] 采药

一、题目详情

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 22 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的 MM 行每行包括两个在 11 到 100100 之间（包括 11 和 100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

二、解题过程

2.1 尝试dfs暴搜->添加记忆数组->记忆化搜索

最开始学的就是dfs，虽然这道题是01背包经典题目，但还是决定用dfs来试一试。

超时代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,t;
int time_cost[105],money_get[105];
int ans = 0;//记录答案
void dfs( int pos , int time_left , int tans ){
    if( time_left < 0 ) return;//如果没有时间就退出
    if( pos == n+1 ){//如果采够了就记录
		ans = max(ans,tans);
		return;
	}
	dfs(pos+1,time_left,tans);//生成下一个节点
    dfs(pos+1,time_left-time_cost[pos],tans+money_get[pos]);
}
int main(){
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> time_cost[i] >> money_get[i];
    dfs(1,t,0);
	cout << ans << endl;
    return 0;
}
image-20210512203311380

好的，跑出来非常感人。怎样做才能不超时呢？

因为暴搜的时候走的弯路太多，我决定去开一个状态记忆数组vst,记录下来每个dfs(pos,time_left)的返回值.。刚开始把vst中每个值都设成 -1(代表没访问过)。每次刚刚进入一个 dfs 前(我们的 dfs 是递归调用的嘛), 都检测 vst [pos] [time_left]是否为-1 , 如果是，就正常执行并把答案记录到 vst中, 否则直接返回 vst 中的值。

附上AC代码（第七次终于AC了！）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
int n,t;
int time_cost[103],mget[103];
int vst[103][1003];
int dfs(int pos,int time_left){
	if( vst[pos][time_left] != -1 ) return vst[pos][time_left];
    if(pos == n+1)
        return vst[pos][time_left] = 0;
    int dfs1,dfs2=-1000000;//非常大的数
    dfs1 = dfs(pos+1,time_left);
	if( time_left >= time_cost[pos] )
    	dfs2 = dfs(pos+1,time_left-time_cost[pos]) + mget [pos];
    return vst[pos][time_left] = max(dfs1,dfs2);
}
int main(){
	memset(vst,-1,sizeof(vst));
    cin >> t >> n;
    for(int i = 1;i <= n;i++)
        cin >> time_cost[i] >> mget[i];
    cout << dfs(1,t) << endl;
    return 0;
}

此时vst的意义与 dfs 相同：是指在时间 time_left 内采集后 pos 个草药, 能获得的最大收益。

有一点不是很明白，为什么使用 money_get 这个名字的时候会报产生歧义的错。

什么是记忆化搜索呢？搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些关系比较复杂的题目面前，又显得无奈。记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用。

用一个公式简单地说：记忆化搜索=搜索的形式+动态规划的思想。

总结记忆化数组的做法

首先分析问题，写出dfs暴搜，再把外部记录答案的变量替换掉，添加vst数组记录状态，并将其作为dfs函数的返回值（不要把它当作参数），达到答案的递归调用效果。

看起来是做完了…？但这个记忆化搜索看起来非常像动态规划，又开始手痒…

2.2 尝试dp->01背包

我们很容易就知道，01背包的状态转移方程是这样的：

f[i][j]=max(f[i−1][j],f[i−1][j−w[i]]+c[i])(j>=w[i])f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i])(j>=w[i])

为什么呢？

想一想就明白，max内第一项是指不选这个物品，为这个重量的最大值；而第二项是选这个物品，从j-w[i]这个重量，加上当前重量w[i]的最大值，再加上本次选的物品的价值。

将状态转移方程简化（就像合并同类项）：

F[v]=maxf[v],F[v−c[i]]+w[i]F[v]=max{f[v],F[v-c[i]]+w[i]}

下面来理解一下01背包的二维数组。

输入：

7 4

4 9

7 5

1 4

接着画一下dp表格：

0 0 0 0 0 0 0
0 0 0 0 9 9 9
0 0 0 0 9 9 9
0 4 4 4 9 13 13

经过分析，二维01背包（一维本弱狗也不会）解题步骤如下：

1.定义二维数组 , f [i] [j]表示采第i株药,花费时间j可以采到的草药的最大总价值。

2.输入采摘某株草药的时间和这株草药的价值。

3.判断是否采摘这株草药

（1）不采摘(背包容量不够),则时间不变,当前采摘的药等于采摘的第i-1株药

1
f[i][j] = f[i - 1][j] ;

（2）采摘(背包容量足够),那么当前可以获得的草药为采i-1株草药,时间为少采第i种药的时间j-ti[i]并且加上当前草药的价值pri[i]。

1
f[i][j] = f[i - 1][j - ti[i]] + pri[i] ;

这里需要注意 : 如果当前采摘这株草药获得的价值比采摘（i-1）株草药的价值低的话也不摘。所以需要比较。因此无论摘不摘这一株草药,一开始的价值都应该是采摘i-1株草药的价值。

1
f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;

相当于初始化当前可以获得的价值为采摘（i-1）株草药的价值，只有背包容量足够采摘当前这一株草药的时候,才判断是否采摘当前的这一株草药。

1
2
3
f[i][j] = f[i - 1][j] ;
if(j >= ti[i]) 
	f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;

4.输出答案

下面是AC代码（正常状态转移方程版本）：

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 w[1005] , c[1005] ;  //w:重量 ,c:价值 , f:最优解。 
int f[1005][1005] ;
int main()
{
	int t , m ;
	cin >> t >> m ;
	for(int i = 1 ; i <= m ; ++i)
	{
		cin >> w[i] >> c[i] ;
        for(int j = 1 ; j <= t ; ++j)
		{
			f[i][j] = f[i - 1][j] ;
            if(j >= w[i]) 
				f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + c[i]) ;
        }
    }
    cout << f[m][t] ;
	return 0 ;
}

试着用一下优化过的状态转移方程（有点难理解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int w[200],c[200],f[200];
int main(){
	int m,n;//m包的容量  n物品数量 
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){  //循环物品 
		for(int j=m;j>=0;j--){  //循环容量,--是为了防止叠加 
			//判断当前物品是否可以放入包中
			if(j>=w[i]){   //能放进去的话就判断哪一种价值大 
				f[j]=max(f[j],f[j-w[i]]+c[i]);//状态转移方程 
			}	 
		}
	}
	cout<<f[m];
	return 0;
}

（二）[NOIP2000 提高组] 单词接龙

一、题目详情

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 nn 表示单词数，以下 nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

二、解题过程

2.1 题意理解

  • 一个单词最多用两次
  • 单词可以不全用完
  • 不可以包含：一旦包含了和不用岂不是一样
  • 按照贪心原则，重叠部分应该越少越好

基本思路是搜索。

处理的难点在于对重叠部分的处理。单词的使用次数很好判断，开一个数组即可，和正常dfs的vis数组差不多。

但对于重叠部分的处理，需要深入去看一下。因为连接起来的单词要最长，所以对比是选择从上一个单词的末尾与当前单词的开头进行比对，如果发现不符那就不能匹配。

2.2 实现分析以及AC代码

canlink()返回最小重叠部分的长度，没有返回0。

solve()进行dfs搜索。

主函数读取、调用和输出。

  1. 先输入，然后直接进入DFS深搜，在深搜里判断是这两个单词是否能连接；
  2. 判断两个单词是否能连接，需要保证这两个数都没被使用过两次，那么需要用数组存一下每个数使用的次数；
  3. 若两个数可以连接，进入判断。为了保证龙的长度最大，我们可以构建canlink函数返回最小重叠部分的长度，相当于同时判断了能否连接以及接口的“价值”。
  4. 如果两个单词可以连接，以新连接的单词作为开头，搜索，长度+这个单词长度-重复部分长度；
  5. 记得回溯；

下面是AC代码：

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
#include<bits/stdc++.h>
using namespace std;
string str[20];
int use[20], length = 0, n;//use记录使用次数
int canlink(string str1, string str2) {
	for(int i = 1; i < min(str1.length(), str2.length()); i++) {
        //重叠长度从1开始，直到最短的字符串长度-1（因为不能包含）
		int flag = 1;
		for(int j = 0; j < i; j++)
			if(str1[str1.length() - i + j] != str2[j]) flag = 0;//逐个检测是否相等
		if(flag) return i;//检测完毕相等则立即return
	}
	return 0;//无重叠部分，返回0
}
void solve(string strnow, int lengthnow) {
	length = max(lengthnow, length);//更新最大长度
	for(int i = 0; i < n; i++) {
		if(use[i] >= 2) continue;//该字符串使用次数需要小于2
		int c = canlink(strnow, str[i]);//获取重叠长度
		if(c > 0) {//有重叠部分就开始dfs
			use[i]++;
			solve(str[i], lengthnow + str[i].length() - c);
			use[i]--;
		}
	}
}
main() {
	cin >> n;
	for(int i = 0; i <= n; i++) use[i] = 0, cin >> str[i];//str[n]为开始字符 
	solve(' '+str[n], 1);//为了指定第一个字符，而且因为canlink需要重叠部分小于最短长度-1，所以要从前面添加一个无意义充长度的‘ ’。这样就强制了canlink函数比较最后一位。这点不加通过不了。
	cout << length ;
}

（三）[1007]魔法少女小Scarlet

一、题目详情

题目描述

Scarlet最近学会了一个数组魔法，她会在n*n二维数组上将一个奇数阶方阵按照顺时针或者逆时针旋转90°，

首先，Scarlet会把11到n^2的正整数按照从左往右，从上至下的顺序填入初始的二维数组中，然后她会施放一些简易的魔法。

Scarlet既不会什么分块特技，也不会什么Splay套Splay，她现在提供给你她的魔法执行顺序，想让你来告诉她魔法按次执行完毕后的二维数组。

输入格式

第一行两个整数 n,m表示方阵大小和魔法施放次数。

接下来m行，每行4个整数 x,y,r,z表示在这次魔法中，Scarlet会把以第x行第y列为中心的2r+1阶矩阵按照某种时针方向旋转，其中z=0表示顺时针，z=1表示逆时针。

输出格式

输出n行，每行n个用空格隔开的数，表示最终所得的矩阵

二、解题过程

2.1 一些解析

这是一道洛谷10月月赛的题目，也是一道模拟题。

题目大意：

给定一个n^2的矩阵，进行m次操作，每次将一个(2r+1)*(2r+1)的子矩阵进行顺时针或逆时针旋转

首先是顺时针旋转90°部分 如图一个3*3的矩阵

1 2 3
4 5 6
7 8 9

顺时针旋转过后

7 4 1
8 5 2
9 6 3

由此可以看出，第a行数字与第a列数字有关系。同理逆时针。

解析：

这题的n和m均小于500，所以直接对数组进行操作只需要500^3的时间。由于每次操作不可能全部是500*500的矩阵，

于是主要思路就非常清晰了

  • 首先对操作数组初始化
1
2
3
4
5
6
7
inline void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    a[i][j]=(i-1)*n+j;  //根据题目要求进行操作
}
  • 接下来进行旋转操作
  • 旋转分为两部分，一部分是顺时针旋转，一部分是逆时针旋转
  • 经过观察在我们可以发现顺时针旋转时原来的第x列，现在时x行，原来的第y行，现在时第n-y+1列

旋转的核心程序：a [i+sx-1] [j+sy-1]=b [j] [tr-i+1]（b为原数组，a为旋转后的数组）

  • 所以顺时针旋转代码：
1
2
3
4
5
6
for(int i=1;i<=tr;i++)
    for(int j=1;j<=tr;j++)
        b[i][j]=a[sx+i-1][sy+j-1];
for(int i=1;i<=tr;i++)
    for(int j=1;j<=tr;j++)
        a[i+sx-1][j+sy-1]=b[j][tr-i+1];
  • 逆时针旋转代码：
1
2
3
4
5
6
for(int i=1;i<=tr;i++)
	    for(int j=1;j<=tr;j++)
	      b[i][j]=a[sx+i-1][sy+j-1];
	  for(int i=1;i<=tr;i++)
	    for(int j=1;j<=tr;j++)
	      a[i+sx-1][j+sy-1]=b[tr-j+1][i];

2.2 AC代码

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
#include<bits/stdc++.h>
using namespace std;
int a[505][505],m,n,x,y,z,r,b[505][505];
inline void init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    a[i][j]=(i-1)*n+j;
}
inline void change()
{
	int sx=x-r,sy=y-r,tr=2*r+1;
	if(z){
	  for(int i=1;i<=tr;i++)
	    for(int j=1;j<=tr;j++)
	      b[i][j]=a[sx+i-1][sy+j-1];
	  for(int i=1;i<=tr;i++)
	    for(int j=1;j<=tr;j++)
	      a[i+sx-1][j+sy-1]=b[j][tr-i+1];
	}
	else{
	  for(int i=1;i<=tr;i++)
	    for(int j=1;j<=tr;j++)
	      b[i][j]=a[sx+i-1][sy+j-1];
	  for(int i=1;i<=tr;i++)
	    for(int j=1;j<=tr;j++)
	      a[i+sx-1][j+sy-1]=b[tr-j+1][i];
	}
}
inline void work()
{
	for(int i=1;i<=m;i++)
	  {
	  scanf("%d%d%d%d",&x,&y,&r,&z);
      change();
	  }
}
inline void out()
{
	for(int i=1;i<=n;i++)
	  {
	  for(int j=1;j<=n;j++)
	    printf("%d ",a[i][j]);
	  printf("\n");
      }
}
int main()
{
	init();
	work();
	out();
	return 0;
}

课程总结：

个人感觉算法竞赛入门的核心是掌握问题到算法的抽象化过程，而不仅仅是掌握算法本身和板子。那些抽象化过程形成的思维不仅可以服务于算法竞赛，还可以在数学建模等比赛中一展身手。建议还是细细讲一下算法的实现过程。

在课程中，我学得最熟练的是dfs暴力算法（虽然很简单），理解得最透彻的是01背包算法，最想掌握的是数学相关算法。各位集训队员的报告都很精彩，感谢课程让我看到了新的世界。虽然课程告一段落，但理解算法的路程还长。