上午 基础算法#
搜索#
简介#
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
另#
两份课件，一份作业