Day1

1.二维数组的遍历 二维数组复习资料

2.字符串的遍历与查找 字符串复习资料

3.STL容器之优先队列

使用情景：若需要对某个序列进行最大或者最小值的动态维护与查询，要想到堆（优先队列）

#include<queue>  // 也可以直接使用万能头
priority_queue <int> q;  // 默认是大根堆
priority_queue < int, vector<int>, greater<int> > p;  // 小根堆
q.empty()   判断priority_queue是否为空，是返回true，否则false
q.pop()     移除堆顶元素
q.push(x)    添加元素x到优先队列
q.size()    返回队列中元素个数
q.top()    返回对优先队列顶部元素的引用

4.质因数分解

参考代码：

#include<bits/stdc++.h>
using namespace std;

map<int, int>st;  // 有序哈希表

int main()
{
	int n;
	cin >> n;
	for (int i = 2; i <= n/i; i++)
	{
		int k = 0;
		while (n % i == 0)
		{
			n /= i;
			k ++;
		}
		if (k)
			st[i] = k;
	}
	if (n > 1)
		st[n] = 1;
	for (auto it : st)
		cout << it.first << " " << it.second << endl;
	return 0;
}

5.STL常见容器用法

点我跳转

Day2

1.等差数列求和（高斯求和）

拓展：等比数列求和

等比数列，又名几何数列，是数列的一种。在等比数列中，任何相邻两项的比例相等，该比值称为公比，公比常用字母q表示。例如数列：3,6,12,24,48,96,... 就是一个等比数列。 在这个数列中，从第二项起，每项与其前一项之公比都等于2。

2.暴力枚举算法

模板
for (int x = 左边界; x <= 右边界; x++)
  for (int y = 左边界; y <= 右边界; y++)
    if (x和y满足某个条件)
      // 满足条件的具体处理逻辑

3.前缀和 前缀和的资料：资料

4.哈希表

5.递归的概念 资料

6.树和图的存储

• 邻接矩阵

• 邻接表

7.dfs深度优先搜索

基础模板
void dfs(参数) {
    if (到达边界) {
		进行答案处理
        return ;
    }
    往下递进  // 可能用循环，也可能题目的分支数是固定的，不用循环
    回溯状态  // 有些情况也不用回溯
}

• 全排列问题

vector<int> v;
bool vis[10];
int n;
void dfs(int k)
{
	if (k == n+1)
	{
		for (auto x:v)
			cout << x << " ";
		cout << endl;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (vis[i]) continue; // 已经用过i，跳过
		v.push_back(i); // 选i
		vis[i] = true; // 标记已用
		dfs(k+1); 
		// 回溯，还原现场
		v.pop_back();
		vis[i] = false;
	}
}

int main()
{
	cin >> n;
	dfs(1);
	return 0;
}

• 枚举子集问题

vector<int> v;
int n;
void dfs(int k)
{
	if (k == n+1)
	{
		for (auto x:v)
			cout << x << " ";
		cout << endl;
		return;
	}
	dfs(k+1); // 不选k
	v.push_back(k); // 选k
	dfs(k+1);
	v.pop_back();
}

int main()
{
	cin >> n;
	dfs(1);
	return 0;
}

• 连通性问题
• 树和图的遍历

Day5

T1

首先不考虑相同或者不同的情况，n个元素任意交换两个元素后的方案数有：(n-1)*n/2种

若能求出交换后相同的串cnt，将总数减去cnt即可以得到不同的方案数。

用桶数组记录所有字母a~z出现的次数，cnt[i]表示字符i出现的次数。

ans = 总方案数 - C(cnt[i], 2) C(cnt[i],2)表示从cnt[i]个字符中任选2个的方案数。

T2:

dfs枚举所有开关状态，检测当前状态下是否所有灯泡都能亮。

枚举1~n子集：

vector<int> chosen;
dfs(int u)
{
	if (u == n+1)
	{
		// 处理子集
	}
	// 选u
	chosen.push_back(u);
	dfs(u+1);
	chosen.pop_back();
	// 不选
	dfs(u+1)
}
dfs(1);

T3:

思路：正难则反 算出所有可以表示为a^b的个数cnt，n-cnt即为答案。

T4:

1.质数筛得到2~1e6之间的质数存于primes中 筛法参考

2.. 暴力枚举第$p$个质数，$p<q, p*q^3<n$那么$p^4<n$

for 枚举p：
	特判p^4 >= n;    // p*q*q*q 
		break;
	for 枚举q:
		q = q*q*q;
		判定 p*q >= n：
			break
		ans++;

Day 10

最大公约数和最小公倍数

/*
gcd的常用性质：
1. gcd(a, b) = gcd(b, a) 交换律
2. gcd(a,b,c) = gcd(gcd(a,b),c)结合律
3. gcd(ma,mb) = m*gcd(a,b) 分配律
4. gcd(a, b) = 1，说明a b互质
5. gcd(a, 0) = a


辗转相除法：
gcd(a, b) = gcd(b, a%b)
更相减损法：
gcd(a, b) = gcd(a, b-a), b >= a;
最小公倍数：
lcm(a,b) = a/gcd(a,b)*b
*/