上午 基礎算法#
搜索#
簡介#
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
另#
兩份課件，一份作業