清北学堂 2023 7月23日知识总结

上午 基础算法

搜索

简介

DFS BFS 迭代加深 双向搜索 A*

例题：k短路问题

todo

分治

例题：平面最近点对

todo

贪心

例题

1.[AHOI2018 初中组] 分组

排序后从前到后考虑每一个数$i$应该放到哪里，怎么放

2.删数问题

反向考虑。依次确定答案的第$i$位可以填什么数字，能填什么数字

3.[NOIP2012 提高组] 国王游戏

假设前方已经排好了$S$个人，再去考虑下面的两个人怎么排，拓展到所有人 。

下午 模拟赛

T1 美丽的序列

题面

给出一个长度为 $n$ 的序列 $a$ 和一个正整数 $k$。

小 A 认为一个长度为 $m$ 序列 $a$ 是美丽的，当且仅当这个序列所有相邻的两数之和是 $k$ 的倍数，即对于所有的 $i\in [1,m)$，需要满足 $k\ |\ (a_i+a_{i+1})$。

小 A 有一个长度为 $n$ 的序列 $a$，他想删去尽量少的数使得剩下的序列变得美丽。

你需要帮他计算这个最小需要删除的数的个数。

思考点

反向考虑，可以留多少。从结论入手，推出结论的性质

过程

首先，容易想到可以先给每一个输入的数模上k，不会对结果造成影响。

然后考虑结果的性质，若第一个数为$x$，则第二个数必须为$k-x$，第三个数必须为$x$，依此类推。

于是，我们扫描模完的数组，依次考虑每一个数（数本身）$i$，这一个数的前一个数必须 为$k-i$。由于结果求长度，所以我们用一个map$f[x]$（值域太大）来存下扫描到的数之前的，结尾为$k-x$的，满足结果性质的（统计起来说人话就是$i$能放在这个后面的），子序列的长度。这样，对于$i$，它的上一位为$k - i$，所以$f[i] = f[k - i] + 1$，同时顺便看是否可以更新答案ans

代码如下

#include<bits/stdc++.h>

using namespace std;

map<int, int> a;
int q[100010];


int main()
{
	int ans = 0;
	int n, k;
	cin >> n >> k;

	for(int i = 1;i <= n;i++)
	{
		cin >> q[i];
		q[i] %= k;
		ans = max(ans, ad = a[(k - q[i]) % k] + 1);
	}

	cout << n - ans;
	return 0;
}

T2 简单的数学题

题面

小 B 很喜欢数学，有一天，小 B 的一个朋友告诉了他两个数 $n,p$，并问他有多少对 $(i,j)$ 满足 $1≤i,j≤n$ 且 $i modj≤p$。

小 B 一下子就秒了，于是想问你会不会这个题。

思考点

不开longlong见祖宗，数论分块（todo）

过程

todo

T3 奇怪的栈

题面

小 C 有一个奇怪的栈，里面放了 $n$ 个元素，每个元素有三个属性 $a_i,b_i,c_i$。

每次小 C 会从这个栈顶的第一个元素和第三个元素中挑选一个拿出来，除了第一次拿，小 C 会保证每次拿出来的元素和上一次拿出来的元素的 $a_i$ 和 $b_i$ 会至少有一个相同。

小 C 想知道，他如何拿取元素能使得拿出来的元素的 $c_i$ 之和最大。

思考点

todo

过程

TODO

T4 有魔力的字符串

题面

小 B 有一个长为 $n$ 的字符串 $S$。

小 B 认为，对于这个字符串 $S$ 的某个子串来说，这个子串是有“魔力”的，当且仅当：

• 在该子串中出现过的字符的出现次数都相同。

小 B 想知道，串 $S$ 有多少子串是有“魔力”的。

本题字符串的子串定义为，该字符串某一连续段。

思考点

todo

过程

todo

另

两份课件，一份作业