24 CSPJ模拟赛7 总结

经验分享区
1

T1：

方法思路：

我们需要判断多个查询字符串是否是给定主字符串的子序列。子序列的定义是不需要连续，但必须保持字符出现的顺序。为了高效地解决这个问题，我们可以预处理主字符串，以便快速判断每个查询字符串是否是子序列。

具体实现：

  1. 预处理主字符串：我们构建一个二维数组 next_pos，其中 next_pos[i][c] 表示在主字符串的位置 i 之后（包括 i）字符 c 第一次出现的位置。如果不存在该字符，则设为字符串的长度。
  2. 处理查询字符串：对于每个查询字符串，使用预处理后的 next_pos 数组快速判断其是否是主字符串的子序列。具体方法是逐个字符查找，若遇到无法找到的字符，则判定该字符串不是子序列。
核心代码 
mp.clear();
    	s1.clear();
    	cin >> n;
    	for(int i=1;i<=n;i++)
		{
			cin >> a[i];
			mp[a[i]]++;
		} 
		bool flagg=0;
    	for(int i=1;i<=n;i++)
    	{
    		if(mp[a[i]]%2!=0)
			{
				cout << "What a pity!\n";
				flagg=1;
				break;
			} 
		}
		if(flagg==1) continue;
		flag=0;
		dfs(1,0);
		if(!flag)
			cout << "What a pity!\n";

这题没失分 :slight_smile:

T2:

方法思路

  1. 枚举加长方案：我们需要枚举所有可能的加长方案，即对每根铁棒加长的长度。设加长后的长度分别为 a + x, b + y, c + z，其中 x + y + z <= L。
  2. 判断三角形条件：对于每一种加长方案，判断加长后的三根铁棒是否满足三角形的条件。
  3. 统计有效方案：统计所有满足条件的加长方案的数量。

由于直接枚举所有可能的 x, y, z 会导致时间复杂度过高，我们需要优化枚举过程。

优化思路

  1. **枚举 z ：我们可以固定 z ，然后计算x 和 y的最大值 （使用隔板法）。

T3：
（理解错题意然后悲剧了）
正解：现将原串分成两半，枚举先后顺序。
如 果有一个串是另外一个串的前缀，那么把剩下的后缀插入到字典树中。否则不插入。

T4：

问题分析

  1. 基本思路：如果N <= K，那么汽车可以直接一次性到达目的地，消耗的苹果数量为N。
  2. 当N > K时：我们需要在途中设置补给点，分段运输苹果。每次运输苹果到补给点时，汽车需要往返多次，消耗的苹果数量会增加。
  3. 补给点的设置：我们需要计算在每个补给点需要存储多少苹果，以及如何分段运输这些苹果。

算法思路

  1. 分段运输：将整个路程分成若干段，每段的长度为K。这样，汽车可以在每段的起点和终点之间往返运输苹果。
  2. 计算消耗：对于每一段路程，计算汽车往返运输苹果所需的苹果消耗。
  3. 累加总消耗：将所有段的苹果消耗累加，得到总的苹果消耗。
1 个赞