T2

容斥原理

(1).总数：B-A+1
(2).Can C: B/C - (A-1)/C
(3).Can D: B/D - (A-1)/D
(4).BothCD: B/lcm(C,D)-(A-1)/lcm(C,D);

1-2-3+4

---

T3

1.质数筛预处理范围内所有质数
2.桶数组计数cnt[i]表示1~i之间满足条件的数的个数
3.l~r之间满足的个数为：cnt[r]-cnt[l-1];

T4

完全背包套壳

T5

DFS模板题
1.存图，邻接表 vector<int>adj[N]
2.从顶点1出发，遍历所有可能的路径
3.需要vis数组标记走过的点，不能重复走
4.注意边界判定，路径数>=10^6 停止。

T6

01背包变型题

思路：

1. **标准背包问题部分**：使用标准的0-1背包DP方法在T-1时间内处理前N-1道菜
2. **特殊处理最后一道菜**：对于每道菜，我们可以考虑将它作为最后一道菜，然后在剩下的时间（即使超过T-1）内吃完它。

**具体步骤**
1. 按时间排序，方便由小到大对每道菜进行处理（看作最后一道菜）。
2. 01背包计算前i道菜在j时间内的最大幸福度dp[j]
3. 对于每道菜，考虑将它作为最后一道菜的情况：即在$T-1$时间内选择其他菜，然后加上这道菜的美味值。

完整思路题解

T1 给我一张凳子

1. 关键观察：对于第i个人来说，他的最终身高（原身高+凳子高度）必须至少等于前面所有人中的最大身高。否则就无法满足条件。
2. 贪心策略：我们可以从左到右遍历数组，维护当前的最大身高。对于每个人：    - 如果当前人的原身高 >= 当前最大身高，则不需要凳子，并更新最大身高    - 否则，需要给他一个凳子，使得他的身高等于当前最大身高
3. 计算总和：在遍历过程中累加所有需要的凳子高度

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    long long total = 0;
    long long max_height = A[0];
    for (int i = 1; i < N; ++i) {
        if (A[i] < max_height) {
            total += max_height - A[i];
        } else {
            max_height = A[i];
        }
    }
    
    cout << total << endl;
    return 0;
}

T2 枚举是不可能枚举的

解题思路

使用容斥原理来计算：

1. 总数 = B - A + 1
2. 能被C整除的数 = ⌊B/C⌋ - ⌊(A-1)/C⌋
3. 能被D整除的数 = ⌊B/D⌋ - ⌊(A-1)/D⌋
4. 能被C和D同时整除的数 = ⌊B/LCM(C,D)⌋ - ⌊(A-1)/LCM(C,D)⌋ 最终答案为：总数 - (能被C整除的数 + 能被D整除的数 - 能被C和D同时整除的数)

算法知识点

• 容斥原理
• 最大公约数(GCD)和最小公倍数(LCM)计算
• 数学公式推导

时间复杂度

O(log(min(C,D))) - 计算GCD的时间复杂度

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

ll lcm(ll a, ll b) {
    return a / __gcd(a, b) * b;
}

int main() {

    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    ll l = lcm(C, D);
    ll total = B - A + 1;
    ll divC = B/C - (A-1)/C;
    ll divD = B/D - (A-1)/D;
    ll divBoth = B/l - (A-1)/l;
    ll ans = total - (divC + divD - divBoth);
    cout << ans << endl;
    return 0;
}

T3 起遇质数

解题思路

1. 预处理阶段：    - 使用埃氏筛法预处理出所有质数（直到最大可能的r值）    - 创建一个数组cnt，其中cnt[i]表示从1到i中满足条件的数的个数    - 对于每个奇数i，检查i和(i+1)/2是否都是质数，如果是则标记为满足条件

2. 查询处理：    - 对于每个查询[l, r]，答案就是cnt[r] - cnt[l-1]    - 使用前缀和思想可以使得每个查询可以在O(1)时间内完成

算法知识点

• 质数筛法（埃拉托斯特尼筛法）
• 前缀和思想

时间复杂度

• 预处理阶段：O(n log log n)（筛法的时间复杂度）
• 查询阶段：O(Q)（每个查询O(1)时间）

C++代码实现

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1e5 + 5;

int main() {

    // 预处理质数表
    vector<bool> is_prime(MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i < MAX; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 预处理满足条件的数
    vector<int> cnt(MAX, 0);
    for (int i = 1; i < MAX; i += 2) {
        if (is_prime[i] && is_prime[(i + 1) / 2]) {
            cnt[i] = 1;
        }
    }
    // 计算前缀和
    for (int i = 1; i < MAX; ++i) {
        cnt[i] += cnt[i - 1];
    }
    // 处理查询
    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        cout << cnt[r] - cnt[l - 1] << endl;
    }
    return 0;
}

T4魔法咒语

思路

转换成n个物品，背包容量为m的完全背包问题

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

const int N = 1e4 + 10;
int dp[N], v[N], w[N];

int main()
{
	int n, m;
	cin >> m >> n; // n物品个数，m背包容量
	for (int i = 1; i <= n; i++)
		cin >> v[i] >> w[i];
	// 状态计算
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			dp[j] = min(dp[j], dp[max(0,j-v[i])] + w[i]);
		}
	}
	cout << dp[m];
	
	return 0;
}

T5 简单路径统计

题目概述

题目要求我们计算从顶点1开始的所有简单路径的数量，其中简单路径是指不重复经过任何顶点的路径。由于结果可能非常大，题目规定如果路径数超过$10^6$ ，则直接输出$10^6$即可。

思路

这道题可以使用深度优先搜索(DFS)来解决，主要基于以下考虑：

1. 图的遍历：我们需要从顶点1出发，遍历所有可能的路径
2. 简单路径限制：路径中不能有重复顶点，需要使用访问标记数组
3. 终止条件：当路径数达到10^6时立即终止程序

由于题目特别给出了"每个顶点度不超过10"的条件，这使得DFS在本题中是可行的，不会因为指数级增长而导致不可控的复杂度。

算法实现

1. 邻接表存储图：使用vector数组来存储图的邻接关系
2. 访问标记数组：使用bool数组标记哪些顶点已经被访问过
3. 计数与剪枝：当计数达到10^6时立即终止程序

代码实现

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

const int N = 2e5 + 5;
const int M = 1e6;

int n , m , cnt , vis[N];
vector<int> g[N];

void dfs(int u){
	if(cnt > M) return;
	cnt ++;
	
	for(int i = 0 ; i < g[u].size() ; i ++){
		int v = g[u][i];
		if(vis[v]) continue;
		vis[v] = 1;
		dfs(v);
		vis[v] = 0;
	}
}

int main(){
	cin >> n >> m;
	
	for(int i = 1 ; i <= m ; i ++){
		int x , y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	vis[1] = 1;
	dfs(1);
	if(cnt > M) cout << M;
	else cout << cnt;
	
	return 0;
}

复杂度分析

• 时间复杂度：最坏情况下为$O(10^6)$， 因为当路径数达到$10^6$时会立即终止
• 空间复杂度：$O(N + M)$，用于存储图和访问标记数组

T6 自助餐

题目概述

题目描述了一种特殊的自助餐情景：你有$N$道菜可以选择，每道菜需要$A_i$时间来吃完，并提供$B_i$的美味值。你可以在$T-1$时间内点菜，但在$T$时间后就不能再点了。不过，已经点的菜可以继续吃完。我们的目标是在这些限制下最大化总美味值。

解题思路

这道题可以看作是一个变种的背包问题，但有一个关键的不同点：你可以在时间耗尽前点最后一道菜，然后继续吃完它。这意味着我们需要特别处理最后一道菜的选择。

动态规划方法

1. 标准背包问题部分：我们需要处理前N-1道菜，在T-1时间内选择，使用标准的0-1背包DP方法。
2. 特殊处理最后一道菜：对于每道菜，我们可以考虑将它作为最后一道菜，然后在剩下的时间（即使超过T-1）内吃完它。

具体步骤

1. 排序
2. 使用动态规划计算在时间$j$内选择前i道菜能获得的最大美味值。
3. 对于每道菜，考虑将它作为最后一道菜的情况：即在$T-1$时间内选择其他菜，然后加上这道菜的美味值。

复杂度分析

• 时间复杂度：O(nt)，其中N是菜品数量，T是时间限制。
• 空间复杂度：O(t)，使用一维数组优化空间。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    freopen("free.in", "r", stdin);
	freopen("free.out", "w", stdout);
    int n, t;
    cin >> n >> t;
    
    vector<pair<int, int>> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i].first >> w[i].second;
    }
    
    // 按照A_i排序，方便处理
    sort(w.begin(), w.end());
    
    // DP数组，dp[j]表示在j时间内能获得的最大美味值
    vector<int> dp(t, 0);
    int ans = 0;
    
    for (int i = 0; i < n; ++i) {
        int a = w[i].first;
        int b = w[i].second;
        
        // 检查将当前菜品作为最后一道菜的情况
        // 此时可以在T-1时间内选择其他菜品，然后加上当前菜品
        if (t - 1 >= 0) {
            ans = max(ans, dp[t - 1] + b);
        }
        
        // 标准背包DP更新
        for (int j = t - 1; j >= a; --j) {
            if (dp[j - a] + b > dp[j]) {
                dp[j] = dp[j - a] + b;
            }
        }
    }
    
    // 还需要考虑不使用最后一道菜的特殊情况（即所有菜都在t-1时间内吃完）
    ans = max(ans, dp[t - 1]);
    
    cout << ans << endl;
    
    return 0;
}