第33期宁波市小学生复赛题解(花式AC)

第33期宁波市小学生复赛 题解(花式AC)

目录

T1 数列游戏

题目描述1

小明最近为了锻炼智力,在玩一个数列求和的游戏。设数列的长度为n,每一个 数字都是整数,且在±1000范围内。小明可以从这个数列里面选一串任意长度的连续子串并求和,小明想知道子串和绝对值的最大值是多少,你能帮帮他吗?

题目大意1

求一个数列里面字段和绝对值的最大值。

解题思路1

很显然,这是一道 最大子段和 问题的变种,只是求的是 绝对值
最大子段和有如下方法:

方法1:大暴力

非常 暴力 的方法,不多说。
暴力 枚举 字段 起点、终点 ,对于每个子串 求和 ,最后求最大绝对值。
求和的过程可以用 前缀和 优化,复杂度 \(O(N^2)\), \(70pt\) 到手。

方法2:分治

先别急着搞 \(O(N)\) ,实际上分治也很容易想到当然是万物皆可 二分
如果用二分做法,那么对于每个区间,最大子段要么就在 左边一半,要么在 右边一半 ,要么 横跨中间
所以,显然可以这么设计:

  1. 原问题:求 \(a\) 中 \([L,R]\) 区间的最大子段和。
  2. 子问题1:求 \(a\) 中 \([L,mid]\) 区间的最大子段和。
    子问题2:求 \(a\) 中 \([mid+1,R]\) 区间的最大子段和。
  3. 基本情况:当 \(L=R\) 时,返回 \(a[L]\)
  4. 合并:\(\max_{子问题1,子问题2,横跨中间的}\)
    那么,横跨中间该怎么搞?
    如果横跨中间,那么肯定要包括 \(a[mid]\) 和 \(a[mid+1]\),所以可以把横跨中间的字段从中点分成两半来看,两边分别线性求解以 \(a[mid]\) 为右端点和以 \(a[mid+1]\) 为左端点的最大字段和,再相加。
    代数式就是:\(\max_{\sum_{i=x}^{mid}a[i]}+\max_{\sum_{i=mid+1}^{y}a[i]} (l \leqslant x \leqslant mid, mid+1 \leqslant y \leqslant r)\)

核心代码:

int solve ( int l, int r )
{
	
	if ( l == r ) return a [ l ];

	int mid = l + ( r - l >> 1 ), sum = 0, ansl = -1e9, ansr = -1e9;
	
	for ( int i = mid; i >= l; i -- ) ansl = max ( ansl, ( sum += a [ i ] ) );
	
	sum = 0;
	
	for ( int i = mid + 1; i <= r; i ++ ) ansr = max ( ansr, ( sum += a [ i ] ) );
	
	return max ( max ( solve ( l, mid ), solve ( mid + 1, r ) ), ansl + ansr );
	
}

方法3:贪心、DP

最大子段和的 \(O(N)\) 做法的确很基础,但对于怎么来的你或许不太清楚,所以这里再提一下。
优化暴力一般分为两种:重复和不必要。
首先,如果是小于零的负数,那么出现了不必要的情况,取了还不如不取。
其次,如果画一下图,可以看出不同起点的差值是固定的,所以只要舍弃 \([i,j]\) ,那么所有 \([*,j]\) 都可以舍弃,直接从 \([j+1,*]\) 开始。这个算法就出来了。

代码很简单,不写了。

T2 文明社会

题目描述2

在互联网上,会有一些不文明的人发送不文明的言论。我们的目的,就是要 自动过滤并且识别这些言论 给出一个字符串 S,表示那些可能不文明的言论。再给出一个字典 T,包含了 n 条违规的用语,T[1], T[2], …, T[n]。要在 S 中添加最少的,使得只要违规用语 T[i]在 S 中出现,就得在每个 T[i]的字符之间添加。 比如说 S=aaabbssss,T[1]=abb,T[2]=bbss。那么最后的符合规定的 S’就为 aaabbssss。其中 abb 在第 3 到第 5 个字符之间出现,bbss 在第 4 到第 7 个字符出现。 数据保证字符串 S 不包括字符‘*’,且 T[i]的长度一定大于 1。 其中|S|≤1000,n≤10,1<|T[i]| ≤100;|S|表示 S 字符串的长度,|T[i]|表示 T[i] 字符串的长度。

题目大意2

把 \(S\) 中所有包含在 \(T\) 中的子段的每个字符之间添加 ‘*’ ,并输出 S’。

解题思路2

这道题由于 \(|S|≤1000,n≤10,1<|T[i]| ≤100\),可以直接暴力做(而也没有其他方法)。
暴力匹配每个 \(T[i]\) ,在匹配位置打上标记,输出时在打标记位置输出 ‘*’ 。

核心代码:

for ( int i = 1; i <= n; i ++ )
      for ( int j = 1, pos = 1; j <= lens; j ++ )
      {
            if ( t [ i ] [ pos ] == s [ j ] ) pos ++;
            if ( pos == lent [ i ] )
                  for ( int k = j; k < j + lent [ i ] - 1; k ++ ) flag [ k ] = true;
      }
//输出
for ( int i = 1; i <= lens; i ++ )
{
      printf ( "%c", s [ i ] );
      if ( flag [ i ] ) putchar ( '*' );
}

T3 陷阱

题目描述3

给定一个n*m 的网格地图,格子有三种情况:

  1. ‘.’表示空,可以正常通行
  2. ‘#’表示有墙,不能通行
  3. 大写英文字母(A~Z)表示有陷阱,可以通行,但经过会扣一定的血量,并
    且不会消失

一共有k 个陷阱(编号从A 开始,ABCDE...),k<=26,并且给定起点,终点,
和初始血量H,行走方向只有上下左右四个方向,注意在行走过程中不能有任意
时刻的血量小于等于0。输出到达终点的最大血量。

题目大意3

额,真的没有

解题思路3

算法1:dfs - 30pt

原题中有一个 “30%的样例 k=0”,因此不考虑陷阱,可以那 \(30pt\) 。
DFS非常暴力:

void dfs ( int x, int y )
{

	vis [ x ] [ y ] = true;

	if ( x == ex && y == ey ) { ok = true; return ; }

	for ( int i = 0; i < 4; i ++ )
	{
		tx = x + d [ i ] [ 0 ], ty = y + d [ i ] [ 1 ];
		if ( ! vis [ tx ] [ ty ] && tx > 0 && tx <= n && ty > 0 && ty <= m && map [ tx ] [ ty ] != '#' ) dfs ( tx, ty );
	}

}

输出时如果ok,就输出h,否则就直接输出-1。

算法2:bfs - 30pt

虽然还是 \(30pt\) ,但BFS时间更短,为了后续方便还是值得写一下。

void bfs ( int sx, int sy )
{
      
      que.push ( node { sx, sy } );
      
      while ( ! que.empty ( ) )
      {
            
            t = que.front ( ); que.pop ( );

            if ( t.x == ex && t.y == ey ) { ok = true; return ; }
            
            for ( int k = 0; k < 4; k++ )
            {
                  tx = t.x + d [ k ] [ 0 ], ty = t.y + d [ k ] [ 1 ];
                  if ( tx >= 1 && tx <= n && ty >= 1 && ty <= m && map [ tx ] [ ty ] != '#' ) que.push ( node { tx, ty } );
            }

      }

}

算法3:DFS - 慢慢爆栈

再在算法1的基础上增加参数h,可以得出一个正确的算法:

void dfs ( int x, int y, int h )
{

	if ( x == ex && y == ey ) { ans = max ( ans, h ); return ; }

	for ( int i = 0; i < 4; i ++ )
	{
		tx = x + d [ i ] [ 0 ], ty = y + d [ i ] [ 1 ];
		if ( ! vis [ tx ] [ ty ] && tx > 0 && tx <= n && ty > 0 && ty <= m && map [ tx ] [ ty ] != '#' )
			vis [ tx ] [ ty ] = true, dfs ( tx, ty ), vis [ tx ] [ ty ] = false;
	}

}

额,TLE & MLE 祝你好运。

算法4:BFS - 真的AC了吗

你会想,如果要求血量,不就记录到每个点的扣血,加入队列时计算好了吗:

void bfs ( int sx, int sy )
{
      
      que.push ( node { sx, sy } );
      
      while ( ! que.empty ( ) )
      {
            
            t = que.front ( ); que.pop ( );

            if ( t.x == ex && t.y == ey ) return ;
            
            for ( int k = 0; k < 4; k++ )
            {
                  tx = t.x + d [ k ] [ 0 ], ty = t.y + d [ k ] [ 1 ];
                  if ( tx >= 1 && tx <= n && ty >= 1 && ty <= m ) que.push ( node { tx, ty } ), dis [ tx ] [ ty ] = dis [ t.x ] [ t.y ] + a /*扣血,请开大一点并预处理(把'.'看成扣血0,把‘#’看成扣血∞)*/ [ map [ tx ] [ ty ] ];
            }

      }

}

BUT,这样真的好了吗?
设计一个数据:

S 1
7 1
E 1

额,你炸了。。。一个点可以有多种方法到达,而最短的那一条不一定扣血最少。这道题和最短路径没有关系。
那咋办呢?

松弛

实际上,求最短路径有一个 “松弛” 算法:

if ( dis [ u ] > dis [ v ] + dam [ u ] )
      dis [ u ] = dis [ v ] + dam [ u ];

不难看出,“松弛” 就是通过介入第三点来缩短路径,其实就是一个贪心。因此,有两种 “松弛” 方式:

算法5:DFS松弛 100pt
void dfs ( int x, int y, int h )
{

	for ( int i = 0; i < 4; i ++ )
	{
		tx = x + d [ i ] [ 0 ], ty = y + d [ i ] [ 1 ];
		if ( ! vis [ tx ] [ ty ] && tx > 0 && tx <= n && ty > 0 && ty <= m && map [ tx ] [ ty ] != '#' )
			if ( dis [ tx ] [ ty ] > dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ] )
				dis [ tx ] [ ty ] = dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ], dfs ( tx, ty );
	}

}
算法6:BFS松弛 100pt
void bfs ( int sx, int sy )
{
      
      que.push ( node { sx, sy } );
      
      while ( ! que.empty ( ) )
      {
            
            t = que.front ( ); que.pop ( );
            
            for ( int k = 0; k < 4; k++ )
            {
                  tx = t.x + d [ k ] [ 0 ], ty = t.y + d [ k ] [ 1 ];
                  if ( tx >= 1 && tx <= n && ty >= 1 && ty <= m )
                        if ( dis [ tx ] [ ty ] > dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ] )
                              que.push ( node { tx, ty } ), dis [ tx ] [ ty ] = dis [ t.x ] [ t.y ] + a [ map [ tx ] [ ty ] ];
            }

      }

}

算法5:BFS优化

在这个BFS中,其实每个点都只用入队/出队一次,数值就固定了,以后不需要更新。
因此,可以再把FLAG数组开回来,每个点只要入队一次就打上标记,以后就不用再入队了:

void bfs ( int sx, int sy )
{
      
      que.push ( node { sx, sy } );
      flag [ sx ] [ sy ] = true;
      
      while ( ! que.empty ( ) )
      {
            
            t = que.front ( ); que.pop ( );
            flag [ t.x ] [ t.y ] = false;
            
            for ( int k = 0; k < 4; k++ )
            {
                  tx = t.x + d [ k ] [ 0 ], ty = t.y + d [ k ] [ 1 ];
                  if ( tx >= 1 && tx <= n && ty >= 1 && ty <= m )
                        if ( dis [ tx ] [ ty ] > dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ] )
                        {
                              if ( ! flag [ tx ] [ ty ] ) que.push ( node { tx, ty } ), flag [ tx ] [ ty ] = true;
                              dis [ tx ] [ ty ] = dis [ t.x ] [ t.y ] + a [ map [ tx ] [ ty ] ];
                        }
            }

      }

}

嗯,恭喜你,你一不小心发明了SPFA ( Shortest Path Fast Algorithm )。

在介绍两种算法

1. 灰常暴力的 Bellman-Ford 算法

其实对于 “松弛” 操作,还有另一种更暴力的方法:不断把矩阵里每一个点进行 “松弛”,直到全部完毕,没有再更新的为止。

void Bellman_Ford ( int sx, int sy )
{
	
        memset ( dis, 0x3f, sizeof ( dis ) );
        
	dis [ sx ] [ sy ] = 0; 
        
	for ( bool flag = true; ! flag; flag = true )
        {
		for ( int x = 1; x <= n; x ++ )
			for ( int y = 1; y <= m; y ++ )
				for ( int k = 0; k < 4; k++ )
                                {
					tx = x + d [ k ] [ 0 ], ty = y + d [ k ] [ 1 ];
					if ( tx > 0 && tx <= n && ty > 0 && ty <= m && map [ tx ] [ ty ] != '#' )
					        if ( dis [ tx ] [ ty ] > dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ] )
						        dis [ tx ] [ ty ] = dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ], flag = false;
				}

}
2. 稍稍改进的 Dijkstra 算法

你可能很快就看出来了贝尔曼-福特算法有着一个致命的缺陷:每一轮都遍历了很多无用的点,所以可以每一轮都只把伤害最少的一个点周围的四个点 “松弛” 一下,这样每个点至多更新一次,快乐(误 快了很多。另外,Dijkstra算法还可以做一个队列优化,基本上就变成了SPFA。

void Dijkstra ( int sx, int sy )
{
	
        memset ( dis, 0x3f, sizeof ( dis ) );
        
	dis [ sx ] [ sy ] = 0; 
        
	for ( int cnt = 1; cnt <= n* m; cnt ++ )
	{

		int mindis = 0x3f3f3f3f, minx, miny;

		for ( int x = 1; x <= n; x ++ )
			for ( int y = 1; y <= m; y ++)
				if ( ! flag [ x ] [ y ] && dis [ x ] [ y ] < mindis )
                                	mindis = dis [ x ] [ y ], midx = x, miny = y;

		if ( mindis == 0x3f3f3f3f ) break;

		flag [ minx ] [ miny ] = true;

		for ( int k = 0; k < 4; k ++ )
		{
			int tx = minx + d [ k ] [ 0 ], ty  = miny + d [ k ] [ 1 ];
                        if ( tx >= 1 && tx <= n && ty >= 1 && ty <= m )
                              if ( dis [ tx ] [ ty ] > dis [ x ] [ y ] + a [ map [ tx ] [ ty ] ] )
                                    dis [ tx ] [ ty ] = dis [ t.x ] [ t.y ] + a [ map [ tx ] [ ty ] ];
                 }
                 
	}

}

T4 汽车旅行

额,还没写好

上一篇:HDU-3020-Antenna Placement 二分图最小路径覆盖


下一篇:四个基本空间