编程好记

主题

补充板子 ​

一、闰年 ​

闰年的详细定义：

  1. 年份非整百且能被4整除的为闰年。（如2004 年就是闰年、2005 年不是闰年）
  2. 年份能被 400 整除的是闰年。（如2000年是闰年，1900年不是闰年）
  3. 注意：能被100 整除的年份，必须要被 400 整除才是闰年。
c
/**
 * 闰年
 * @author  王铭颢
 * @Date  2022/11/20 16:15
 */

int is_leap_year(int year) {
    return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
}

二、星期计算 ​

蔡基姆拉尔森计算公式

假设星期为ww，年份为yy，月份为mm，日期为dd

w=(d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7

然后把计算出来的ww加上1就是真正的星期几了。

每年的1、2月要当成上一年13、14月计算，上述的除法均为整除（地板除）。

三、代码 ​

1、星期推算 ​

已知1年1月1日是周一，求y年m月d日是周几？

1）推算法 ​

cpp
/**
 * 星期的计算
 * @author  王铭颢
 * @Date  2022/11/20 22:55
 */
#include "iostream"

using namespace std;

string Week[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

int is_leap_year(int year) {
    return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
}

int whatDay(int y, int m, int d) {
/*
 * 1 1 1是周一
 * 1900 1 1也是周一
 */
    int ans = 0;
    for (int i = 1; i < y; ++i) {
        ans += 365 + is_leap_year(i);
        ans %= 7;
    }
    for (int i = 1; i < m; ++i) {
        if (i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12) {
            ans += 31;
        } else if (i == 2) {
            ans += 28 + is_leap_year(y);
        } else {
            ans += 30;
        }
        ans %= 7;
    }
    ans += d - 1;
    ans %= 7;
    return ans;
}

int main() {
    int y, m, d;
    cin >> y >> m >> d;
    cout << Week[whatDay(y, m, d)] << endl;
    return 0;
}

2）公式法 ​

cpp
/**
 * 星期的计算公式
 * @author  王铭颢
 * @Date  2022/11/20 23:14
 */
#include "iostream"

using namespace std;

string Week[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};

int whatDay(int y, int m, int d) {
    if (m <= 2) {
        m += 12;
        y--;
    }
    return (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
}

int main() {
    int y, m, d;
    cin >> y >> m >> d;
    cout << Week[whatDay(y, m, d)] << endl;
    return 0;
}

2、生命计算器 ​

a年b月c日到d年e月f日共有多少天

cpp
/**
 * 生命计算器
 * @author  王铭颢
 * @Date  2022/11/20 23:28
 */

#include "iostream"

using namespace std;
int day[13] = {0, 31, 28, 31, 30, 31, 30,
               31, 31, 30, 31, 30, 31};

int main() {
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int ans = 0;
    for (;;) {
        if (a == d && b == e && c == f) break;
        else {
            c++;
            ans++;
        }
        day[2] = 28 + (a % 400 == 0 || (a % 100 != 0 && a % 4 == 0));
        if (c == day[b] + 1) {
            c = 1;
            b++;
        }
        if (b == 13) {
            b = 1;
            a++;
        }
    }
    cout << ans + 1 << endl;
    return 0;
}

3、恋爱纪念日 ​

a年b月c日后的n天是哪天

cpp
/**
 * 恋爱纪念日
 * @author  王铭颢
 * @Date  2022/11/20 23:21
 */

#include "cstdio"

int day[13] = {0, 31, 28, 31, 30, 31, 30,
               31, 31, 30, 31, 30, 31};

int main() {
    int y, m, d, k;
    scanf("%d%d%d%d", &y, &m, &d, &k);
    for (int i = 0; i < k; ++i) {
        day[2] = 28 + (y % 400 == 0 || (y % 100 != 0 && y % 4 == 0));
        d++;
        if (d == day[m] + 1) {
            m++;
            d = 1;
        }
        if (m == 13) {
            m = 1;
            y++;
        }
    }
    printf("%04d-%02d-%02d", y, m, d);
    return 0;
}

四、字符串的处理 ​

1、c ​

字符串是编程语言中非常常用的一种数据类型，字符串的处理也是各类算法竞赛中考察较多的一类题型。字符串，简单地说，就是由若干个字符连接在一起的串。

C语言中规定：末尾以\0结束的字符数组称为字符串，否则只能算作字符数组。只有以\0结束的字符数组才能以%s的方式用 printf 输出。

字符数组

| 索引 | 0 | 1 | 2 | 3 | | : | : | : | : | : | | 字符 | a | b | c | d |

字符串

| 索引 | 0 | 1 | 2 | 3 | 4 | | : | : | : | : | : | : | | 字符 | a | b | c | d | \0 |

2、c++ ​

使用提供的string类型。

char数组会比string更灵活

五、字符串操作库函数 ​

1、C ​

0）字符串的输入 ​

1. scanf ​

遇到空格、回车、制表符就会中断输入

c
scanf("%s",s);
// "rexhao work" = "rexhao"
2. gets ​

遇到回车中断输入，但是不安全

c
gets(s);
// "rexhao work" = "rexhao work"
3. fgets ​

遇到回车中断输入，但是会算入换行

c
fgets(s,499,stdin);
// "rexhao work" = "rexhao work\n"

1）字符串赋值 ​

将b赋值给a

c
char *strcpy(char *a, char *b);

2）字符串拼接 ​

将b拼接在a后面（a必须有足够的空间）

c
char *strcat(char *a, char *b);

3）字符串比较 ​

从第一个字符开始逐字符比较 ASCII 码，返回第一个不相同的ASCII码的差值，如果两个字符串完全相同，返回0。

c
int strcmp(char*str1, char *str2);

4）字符串长度 ​

字符串长度，不包括\0

c
int strlen(char *s);

时间复杂度O(n^2) => 先存值再跑循环

2、C++ ​

c++提供了cin、cout函数，简化了输入和输出，但效率远不如printf和scanf

cpp
#include "iostream"
using namespace std;
int main() {
    string s;
    cin >> s;
    cout << s << endl;
    return 0;
}

提高效率方法：

cpp
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

不要同时混用cout/cin和printf/scanf

这个函数是一个“是否兼容stdio”的开关，C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。

cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，而这段语句可以来打消iostream的输入输出缓存，可以节省许多时间，使效率与scanf与printf相差无几。

tie是将两个stream绑定的函数，空参数的话返回当前的输出流指针。

在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率

六、字符串模板 ​

1、子串出现次数 ​

cpp
/**
 * 子串出现次数
 * @author  王铭颢
 * @Date  2022/11/20 15:52
 */

#include "cstdio"
#include "cstring"

char s1[5000];
char s2[50];
int ans;

int main() {
    scanf("%s", s1);
    scanf("%s", s2);
    int slen1 = strlen(s1);
    int slen2 = strlen(s2);

    int flag;

    for (int i = 0; i < slen1 - slen2; ++i) {
        flag = 1;
        for (int j = 0; j < slen2; ++j) {
            if (s1[i + j] != s2[j]) {
                flag = 0;
                break;
            }
        }
        if (flag) ans++;
    }
    printf("%d", ans);
    return 0;
}

2、最后一个字符串 ​

输出最后一个输入的字符串

判题会用文件重定向，输入末尾存在EOF

调试窗口使用 Ctrl + Z 结束输入

cpp
/**
 * 最后一个字符串
 * @author  王铭颢
 * @Date  2022/11/22 13:31
 */

#include "cstdio"

char s[105];

int main() {
    while (scanf("%s", s) != EOF);
    printf("%s", s);
    return 0;
}

七、sort函数 ​

sort 是一个c++已经为我们实现好的工具，当我们要用它时，需要先引入一个算法的库"algorithm"。

sort 可以排序任何类型的元素，包括我们自己定义的结构体。

cpp
sort(arr + i, arr + j);

默认从小到大，被排序的是arr[i]到arr[j-1]

cpp
#include "iostream"
#include "algorithm"
using namespace std;
int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    sort(arr, arr + 5);     // 1 2 3 4 5
    return 0;
}

八、结构体 ​

1、结构体的构造方法 ​

cpp
struct Student {
    int num;
    int score;
	
    // 默认构造函数
    // 不能出现两个默认构造函数
    Student() {
        num = 0;
        score = 0;
    }
	
    // 带参构造函数
    Student(int num, int score) {
        this->num = num;
        this->score = score;
    }
};

2、初始化列表 ​

cpp
struct Node {
    int num;
    string name;
    Node(){};
    // 初始化列表
    Node(int n, string s):num(n),name(s){};
};
  1. 函数的参数列表不能省略
  2. 必须写大括号

3、构造方法的使用 ​

cpp
/**
 * 结构体构造函数
 * @author  王铭颢
 * @Date  2022/11/22 17:14
 */

#include "iostream"
using namespace std;
struct Student {
    int num;
    int score;
    Student() {
        num = 0;
        score = 0;
    }

    Student(int num, int score) {
        this->num = num;
        this->score = score;
    }
};

int main() {
    int num, score;
    cin >> num >> score;
    Student s = Student(num, score);
    cout << s.num << " " << s.score << endl;
    return 0;
}

九、sort的第三参：排序方法 ​

1、从大到小排序 ​

greater 表示“更大”，<int>表示待排序的数组中的元素类型为 int

cpp
/**
 * Sort基本使用
 * @author  王铭颢
 * @Date  2022/11/22 14:52
 */

#include "iostream"
#include "algorithm"

using namespace std;

int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    cout << endl;
    sort(arr, arr + 5, greater<>());     // 5 4 3 2 1
    return 0;
}

2、cmp()函数 ​

cmp通过回调函数（函数的指针）的方式，作为第三参传入给sort

sort通过cmp函数的返回值进行排序

cmp函数参数与返回值

  1. x：前一个值
  2. y：后一个值
  3. 返回值：return x > y => 结果 5 4 3 2 1
cpp
/**
 * sort第三参：cmp
 * @author  王铭颢
 * @Date  2022/11/22 16:46
 */


#include "iostream"
#include "algorithm"

using namespace std;

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    sort(arr, arr + 5, cmp);    // 5 4 3 2 1 
    for (int i: arr) {
        cout << i << " ";
    }
    return 0;
}

3、结构体排序 ​

cpp
bool cmp(Student s1, Student s2) {
    return s1.score > s2.score;
}

4、浮点数排序 ​

cpp
bool cmp(double a, double b) {
    if(fabs(a-b) < EPSILON) return true;
    else return a < b;
}

十、sort模板 ​

1、对3取余排序 ​

我们有N 个正整数，均小于 10000。现在需要将这些正整数按照除以2的余数从小到大排序，即除以3余0的数排在除以3余1的数前面，除以3余1的数排在除以3余2的数前面。如果余数相等，则按照正整数的值从小到大排序。

cpp
/**
 * 对三取余的排序
 * @author  王铭颢
 * @Date  2022/11/22 17:04
 */

/*
 * 我们有N 个正整数，均小于 10000。
 * 现在需要将这些正整数按照除以3的余数从小到大排序，
 * 即除以3余0的数排在除以3余1的数前面，除以3余1的数排在除以3余2的数前面。
 * 如果余数相等，则按照正整数的值从小到大排序。
 */

#include "iostream"
#include "algorithm"

using namespace std;

bool cmp(int x, int y) {
    if (x % 3 == y % 3) return x < y;
    else return x % 3 < y % 3;
}

int main() {
    int arr[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    sort(arr, arr + 9, cmp);
    for (int i: arr) {
        cout << i << " ";
    }
    return 0;
}

2、结构体排序 ​

cpp
/**
 * 结构体的排序
 * @author  王铭颢
 * @Date  2022/11/22 17:41
 */

#include "iostream"
#include "algorithm"

using namespace std;

struct Student {
    string name;
    int score;

    Student() {};

    Student(string name, int score) {
        this->name = name;
        this->score = score;
    }
};

bool cmp(Student s1, Student s2) {
    return s1.score > s2.score;
}

Student s[3];

int main() {
    for (int i = 0; i < 3; ++i) {
        cin >> s[i].name >> s[i].score;
    }
    sort(s, s + 3, cmp);
    for (int i = 0; i < 3; ++i) {
        cout << s[i].name << " " << s[i].score << endl;
    }
    return 0;
}

3、浮点数排序 ​

cpp
/**
 * 浮点数字的排序
 * @author  王铭颢
 * @Date  2022/11/22 17:50
 */

#include "iostream"
#include "algorithm"
#include "cmath"

using namespace std;
double arr[5];
const double EPSILON = 1e-6;

bool cmp(double a, double b) {
    if(fabs(a-b) < EPSILON){
        return true;
    }else {
        return a < b;
    }
}

int main() {
    for (int i = 0; i < 5; ++i) {
        cin >> arr[i];
    }
    sort(arr, arr + 5, cmp);
    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

十一、DP的推导 ​

纯DFS ​

记忆化搜索 ​

逆序递推 ​

正序递推 ​

Released under the MIT License.

code by wmh1024