算法竞赛常用知识

约定不等于承诺〃 2022-11-16 15:22 187阅读 0赞

**上一篇博客：蓝桥杯第六届C/C++ B组真题详解**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  简介
 *  日期问题
 *   *  如何判断闰年
     *  关于闰年平年的代码小模板
 *  求最大公约数
 *  求最小公倍数
 *  C++ STL
 *  静态链表

# 简介 #

本篇博客来整理一下在算法竞赛中经常用到但是可能会忘掉的知识，有些知识平时可能会记得，但是到真正算法竞赛的时候可能就会忘掉，甚至有一些很常见的知识再平时就忘掉了。但是在算法竞赛中碰到相关的题目还不得不使用这些知识，如果在算法竞赛的时候想不起来那是非常可惜的。

所以来总结一下一些在刷题中常用的知识以及需要注意的地方，如果有不足或者需要补充的地方欢迎大家评论留言，博主也会随时补充更新。

# 日期问题 #

当考到日期问题的时候要仔细阅读题目，看看是否需要考虑 `闰年问题`，或者是题目直接告诉我们一个月固定为 **30** 天。一定要注意这一点，搜则可能按照自己的想法，本来不需要考虑闰年问题，结果在写代码的时候下意识的考虑了，或者是忘了考虑闰年问题，但是题目要求我们考虑闰年。如果因为这一点而做错了题目，那就非常可惜了。

## 如何判断闰年 ##

这也是一个比较容易记错记混甚至忘记的知识点。判断年份是否是如闰年的方法为：如果年份能被 **4** 整除并且不能被 **100** 整除，或者能被 **400** 整除，那么当前年份就是闰年，当前年份的 **2** 月就有 `29` 天，否则为 `28` 天。

#include<iostream>
    
    using namespace std;
    
    int main() { 
        int year;
        cin >> year;
        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { 
            cout << year << "是闰年！";
        } else cout << year << "不是闰年！";
        return 0;
    }

## 关于闰年平年的代码小模板 ##

#include<iostream>
    
    using namespace std;
    
    // 用一个数组存储平年每个月份有几天，闰年只改二月份天数即可
    int mounth_day[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int main() { 
        // 求某一天之后的多少天是几月几日
        int year = 2014, mounth = 11, day = 9;
        int cnt = 0;
        while (cnt < 1000) { 
            // 判断当前年份是否是闰年，根据情况该变二月份的天数
            if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { 
                mounth_day[2] = 29;
            } else mounth_day[2] = 28;
            
            if (day == mounth_day[mounth]) { 
                // 先判断是否到了 12 月，到了则年份加一，月份初始化为 1 月
                if (mounth == 12) mounth = 1, year++, day = 1, cnt++;
                else mounth++, day = 1, cnt++; // 不是 12 月则只将月份加 1
            } else day++, cnt++;
        }
        cout << year << ' ' << mounth << ' ' << day << endl;
        return 0;
    }

# 求最大公约数 #

详见之前的博客：**[求最大公约数（辗转相除法）][Link 1]**

# 求最小公倍数 #

详见之前的博客：**[如何求最小公倍数][Link 2]**

# C++ STL #

详见之前的四篇博客：

*  **[C++ STL详解（1）][C_ STL_1]**
 *  **[C++ STL详解（2）][C_ STL_2]**
 *  **[C++ STL详解（3）][C_ STL_3]**
 *  **[C++ STL详解（4）][C_ STL_4]**

# 静态链表 #

详见之前的博客：**[静态链表的介绍及实现][Link 3]**

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_ffffff_t_70][]

[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://ac-fun.blog.csdn.net/article/details/90752742
[Link 2]: https://ac-fun.blog.csdn.net/article/details/90902890
[C_ STL_1]: https://ac-fun.blog.csdn.net/article/details/113864734
[C_ STL_2]: https://ac-fun.blog.csdn.net/article/details/113894814
[C_ STL_3]: https://ac-fun.blog.csdn.net/article/details/113918042
[C_ STL_4]: https://ac-fun.blog.csdn.net/article/details/113939257
[Link 3]: https://ac-fun.blog.csdn.net/article/details/113837773
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_ffffff_t_70]: /images/20221022/be1a9b550d44494f8e159b1d8bcf9642.png