前言：
做模拟题给我做的道心破碎了，还是要系统的练习一下，今天就先练习一下简单的bfs和前缀和吧， 当然也可以访问我的GitHubhttps://github.com/KiloMing/MyCode。
第一题
这题太简单，不好意思拿出来（但还是要注意细节问题）
/*
题 1：闰年统计
输入两个年份 L, R，输出区间 [L, R] 中闰年的个数。
目标
练：
条件判断
循环枚举
基础模拟
知识点
闰年判断
边界处理
*/
#include <iostream>
using namespace std;
bool JudgeYear(int year){
if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0){
return true;
}else{
return false;
}
}
int main(){
int y1, y2;
int sum;
cin >> y1 >> y2;
for(int i = y1; i <= y2; i++){
if(JudgeYear(i)){
sum++;
}
}
cout << sum << endl;
}第二题
/*
输入 y, m, d，判断这个日期是否合法。
目标
练：
分类讨论
月份天数
闰年二月
知识点
模拟
条件分支
*/
#include <iostream>
using namespace std;
int month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool JudgeYear(int year){
if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0){
return true;
}else{
return false;
}
}
int main(){
int year;
int mon;
int day;
cin >> year >> mon >> day;
if(JudgeYear(year)){
month[1] = 29;
}else{
month[1] = 28;
}
int flag = 1;
if(!(mon >= 1 && mon <= 12)){
flag = 0;
}else if(!(day >= 1 && day <= month[mon-1])){
flag = 0;
}
if(flag){
cout << "Right" << endl;
}else{
cout << "Error" << endl;
}
}
第三题
这一题一定要注意，当使用前缀和求区间[a, b]的和时，一定是s[b] - s[a-1]不然会漏减
/*
题 3：区间和查询
给一个长度为 n 的数组，再给 q 次询问，每次问区间 [l, r] 的元素和。
输入格式
第一行 n q
第二行 n 个整数
接下来 q 行，每行两个整数 l r
输出
每次询问输出一个区间和。
目标
练：
前缀和定义
区间和公式
下标稳定性
要求
数组你先统一按 1 下标 写一版，再按 0 下标 自己重写一版。
*/
#include <iostream>
using namespace std;
int main(){
int n, q;
cin >> n >> q;
int *a1 = new int[n];
cin >> a1[0];
for(int i = 1; i < n; i++){
cin >> a1[i];
}
int *s1 = new int[n+1];
s1[0] = 0;
for(int i = 0; i < n; i++){
s1[i+1] = s1[i] + a1[i];
}
int l, r;
for(int i = 0; i < q; i++){
cin >> l >> r;
cout << s1[r] - s1[l-1] << endl; //注意 ：这里l要减1
}
}第四题
这题涉及到<unordered_map>容器，它与map(map可以去看我的 C++ 容器那一篇)的区别是：
| map | 有序 | 稍微有点满 |
| unordered_map | 无序 | 快（哈希） |
/*
题 4：和为 0 的最长连续子数组
给一个数组，求和为 0 的最长连续子数组长度。
目标
知识点
前缀和
哈希表记录前缀和第一次出现的位置
核心思路提示
如果 s[i] == s[j]，那中间这段和就是 0。
要求
不能写双重循环，必须练成 O(n)。*/
#include <iostream>
#include <unordered_map>
using namespace std;
int main(){
int n;
cin >> n;
int *a = new int[n];
for(int i = 0; i < n; i++){
cin >> a[i];
}
unordered_map<int, int> map;
map[0] = -1; //不要忘记初始化
int sum = 0;
int ans = 0;
for(int i = 0;i < n; i++){
sum += a[i];
if(map.count(sum)){
ans = max(ans, i - map[sum]);
}else{
map[sum] = i;
}
}
cout << ans <<endl;
}
第五题
这一题牵扯到简单的dfs和回溯，可以看一下我的CSND：https://blog.csdn.net/2501_94293581/article/details/158704997?spm=1001.2014.3001.5501
/*
题 5：输出 1~n 的所有组合
输入 n, k，输出从 1~n 中选 k 个数的所有组合。
目标
练：
组合枚举
路径 path
回溯写法
终点 return
知识点
DFS
回溯
要求
这题你要特别注意：
到 path.size() == k 后立刻 return。*/
#include <iostream>
#include <vector>
using namespace std;
void Compare(int start, int n, int k, vector<int> &path){
if(path.size() == k){
for(int i = 0;i < path.size(); i++){
cout << path[i] << " ";
}
cout << endl;
return;
}
for(int i = start; i <= n; i++){
path.push_back(i);
Compare(i+1, n, k, path);
path.pop_back();
}
}
int main(){
int n, k;
cin >> n >> k;
vector<int> path;
Compare(1, n, k, path);
}第六题：
刚开始想的麻烦了，用vector回溯列出了所有组合再相加，当数比较小的时候可以，但是如果竞赛肯定过不了，所以就用dfs，遍历到这个元素的时候就两种选择选还是不选
/*
题 6：子集和个数
给定 n 个数和目标值 S，问有多少种选法使得选出的数之和等于 S。
目标
练：
DFS 枚举选或不选
参数传递当前和
不重复计算
知识点
子集枚举
递归
要求
这题不要每次搜到叶子再遍历数组求和，直接把 sum 当参数传下去。*/
/*
题 5：输出 1~n 的所有组合
输入 n, k，输出从 1~n 中选 k 个数的所有组合。
目标
练：
组合枚举
路径 path
回溯写法
终点 return
知识点
DFS
回溯
要求
这题你要特别注意：
到 path.size() == k 后立刻 return。*/
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int n, S;
int a[1005];
int ans = 0;
void dfs(int u, int sum){
if(u == n){
if(sum == S) ans++;
return; //注意一定要return
}
dfs(u+1, sum); //不选
dfs(u+1, sum+a[u]); // 选
}
int main(){
cin >> n >> S;
for(int i = 0; i < n; i++){
cin >> a[i];
}
dfs(0, 0);
cout << ans << endl;
}
总结
今天的题还是挺基础的，但要吧细节做好，比如前缀和的边界问题，回溯和dfs的模版不能写错；
