2024年

1月

1日XXX 1214. 波动数列

思路严重偏差，一定一定想清楚再写代码；
集合：所有只考虑前i项，且当前的总和除以n的余数是j 的方案 的集合
状态计算：f(i, j) -> 最后一项是+a的所有方案 -> f(i-1, (j - i * a) % n)
-> 最后一项是-b的所有方案 -> f(i-1, (j + i * b) % n)
初始化：f(0, 0) = 1
由题意可得，设第一项为x，nx+(n-1)d1+(n-2)d2+…dn-1=s
-> d有两种选法，a或者b
-> 同余数，s%n==((n-1)d1+(n-2)d2+…dn-1)%n
-> 第i个数选择加a：((n-1)d1+(n-2)*d2+…(n-(i-1))dn-1+(n-i)a)%n==j%n
将全过程中可能得到的余数的各个方案数记录下来，最后只需要等于s%n的余数的方案数

2日 1210. 连号区间数

最小值和最大值的差值即为长度
排列：没有重复数字
将找最大最小值的循环融进第二循环，因为每次只添加一个数到区间内，最后判断最大最小的差值是不是等于区间长度即可

3日 1236. 递增三元组 二分

可以采用二分，遍历一次b数组就可以找到答案，nlogn
注意

// b[k]是目标值
while (l < r)
{
    long long mid = (l + r + 1) / 2;
    if (b[k] > a[mid])
    {
        l = mid;
    }
    else
    {
        r = mid-1;
    }
}
l为边界

// b[k]是目标值
while (l < r)
{
    long long mid = (l + r) / 2;
    if (b[k] < c[mid])
    {
        r = mid;
    }
    else
    {
        l = mid + 1;
    }
}
r为边界

还可以用哈希加前缀和做

4日 1245. 特别数的和

很简单的模拟题

5日 1204. 错误票据

题目思路简单，读入数据的方式比较麻烦
可以不管有几行一直读入直到没有输入：

while(cin>>id)
{
    ...
}

<br />也可以： ```cpp int cnt; cin >> cnt; // 数据一共有cnt行

string line; // 消除cin读完第一行，剩下最后的回车的影响 getline(cin, line); while(cnt–) { getline(cin, line); // 从line内读出数据 stringstream ssin(line); // n=0 while(ssin » a[n]) n++; }

<a name="sNTb4"></a>
### 6日 [466. 回文日期](https://www.acwing.com/problem/content/468/) ※
判断一个数字是否回文
```cpp
bool judge(int x)
{
    int cnt = 7;
    while (x >= 10)
        {
            int x1 = x / pow(10, cnt);
            if (x1 != x % 10) return false;
            x -= x1 * pow(10, cnt);
            x /= 10;
            cnt-=2;
        }
    return true;
}

思路想对了，枚举年份，以是回文数为前提，判断是否小于第二个日期（这里可以直接判断大小不需要转换），再判断该日期是否合法；

int v1, v2;
int ans;
int m[13]{0,31,28,31,30,31,30,31,31,30,31,30,31};

// 判断日期是否合法
bool judge(int date)
{
    int year = date/10000;
    int mouth = date%10000/100;
    int day = date%100;
    
    if(mouth==0 || mouth>12) return false;
    if(day==0 || mouth!=2 && day>m[mouth]) return false;
    // 2月
    if(mouth==2)
    {
        int leap = year%100 && year%4==0 || year%400==0;
        if(day>28+leap) return false;
    }
    return true;
}

int main()
{
    cin>>v1>>v2;
    
    for(int i=1000; i<10000; i++)
    {
        int date=i,x=i;
        // 枚举年份，得到回文数，再判断其合法与否
        for(int j=0; j<4; j++)
        {
            date = date*10+x%10;
            x/=10;
        }
        if(v1<=date && date<=v2 && judge(date))
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

7日 787. 归并排序 ※

整体时间复杂度为nlogn，需要多开辟一个数组存部分排序后的顺序；
先将数组递归分治，即等到数组长度为2时，开始排序，两个指针分别从l和mid+1开始排序，从小到大存入额外的数组内，记得将多余的数组放到额外数组内，最后将额外数组存回对应的原数组内

9日 1219. 移动距离

需要发现如果按照题目从1开始，会发现需要特判，因为开头，末尾这两和中间不一样，简单来说取余时变成1，2…n，0这样，0到最后了，如果将数据减一，等同于从0开始，取余就是正常0，1，…n，接着只需要特判奇数行翻转即可

10日 1229. 日期问题

题目要求：输出日期从小到大，直接判断有点难特判日期大小，所以直接遍历从小到大找对应日期；
技巧：
输入特定格式：scanf("%d/%d/%d", &a, &b, &c);
补充前导0：printf("20%02d-%02d-%02d\n", p1, p2, p3);

11日 1231. 航班时间

思路很简单，时间差的和除二即为时差；
读入数据：scanf("%d:%d:%d %d:%d:%d (+%d)", &a, &b, &c, &d, &e, &f, &g);
g不一定会得到输入
scanf不会读入最后的回车
string line; getline(cin, line);需要用getline读掉那个多余的回车
判断需不需要加天数，统一格式 if(line.back()==')') line +="(+0)";
读一行数据：sscanf(line.c_str, "%d:%d:%d %d:%d:%d (+%d)", &a, &b ...);

13日 1241. 外卖店优先级

注意：pair自带有sort：sort(order, order+m);默认排第一个，第一个相同排第二个；

14日 788. 逆序对的数量

ans+=mid-i+1;
思路反过来了，找大于右边第一个目标值，则左半部分大于的右边的数都符合要求

15日 1264. 动态求连续区间和

前缀和可以过大多测试用例；

树状数组

单点修改，区间查询
lowbit(x) = x & -x = 2k; k为二进制形式的x末尾的0的数量；c[x] = (x - lowbit(x), x);c[x]为树状数组区间x - lowbit(x)到x的和

int lowbit(int x)
{
    return x&-x;
}

// v为加的数
int add(int x, int v)
{
    for(int i=x; i<=n; i+=lowbit(i)) q[i]+=v;
}

// 求和
void query(int x)
{
    int res=0;
    for(int i=x; i; i-=lowbit(i)) res+=q[i];
    return res;
}

• n为数组长度
• q为树状数组

16日 1215. 小朋友排队

重点在于每个小朋友移动的次数一定是左边比它大的数的数量和右边比它小的数的数量之和；
因为最大值不会超过一百万，所以可以直接用一百万作为树状数组最大值
树状数组记录的是落在这个区间内的个数，所以add都是1
（明白60%）

18日 线段树

单点修改
区间查询

struct Node
{
    int l, r;
    int sum;
}tr[4*N];

// 对于x节点，父节点为 x >> 1; 左子节点为 x << 1; 右子节点为 x << 1 | 1;

// 用子节点消息更新当前节点信息（可能可以省略，将这句代码移到其他函数中）
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

// 在一段区间上初始化线段树，(根节点下标，区间)
void build(int u, int l, int r)
{
    // 如果是叶子节点
    if(l == r) tr[u] = {l, r, a[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >>1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid +1, r);
        pushup(u);
    }
}

// 查询
int query(int u, int l, int r)
{
    // 如果当前区间包含要查的部分，直接返回当前总和
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    // 如果mid大于等于查询区间左端点，则拿mid的sum
    if(l <= mid) sum = query(u << 1, l, r);
    // 如果mid小于查询区间右端点，则拿mid的sum
	if(r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

// 修改
void modify(int u, int x, int v)
{
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else
    {
        int mid = tr[u].l +tr[u].r >> 1;
        // 小于等于找左子节点
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

20日 1265. 数星星

注意树状数组存的应该是对应位置的等级；故最大可能是32000；
题目要求每个等级的星星数量，可以将等级作为key，数量作为value，额外开一个哈希数组存并输出。

21日 1270. 数列区间最大值

线段树做法，但注意要用scanf和printf，不然也会超时；
区间和换成区间内最大值

22日 1237. 螺旋折线

曼哈顿距离，找第几层，算当前点和右上角点的位置差别，在左上则减去曼哈顿距离，右下则加；

23日 797. 差分

差分中的正负是相对的，即不可能单独出现
为原数组构造一个差分数组，b[i]=a[i]-a[i-1];，反过来等于说a是b的前缀和数组
a的区间加等于b节点加后，a右区间之后再减回来；
即：[l, r] + n => b[l]+n; b[r+1]-n;

24日 798. 差分矩阵

同理，构建二维矩阵的前缀和，自己画一下前缀和矩阵推出公式：
b[x1, y1] += C; b[x1, y2+1] -= C; b[x2 + 1, y1] -= C; b[x2 + 1, y2 + 1] += C;

25日 1238. 日志统计 滑动窗口

按照时间排序，先遍历所有日志，中间延迟指针开始减去过期的，使用哈希数组存时间内的点赞；

26日 1101. 献给阿尔吉侬的花束

bfs，记得用cin读入地图；构建一个步骤的地图，下一步就在上一步的总步数基础上加一；

27日 1113. 红与黑

dfs，scanf需要这样写：

while(true)
{
    cin >> col >> row;
    string line;
    getline(cin, line);
    ...
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            scanf("%c", &b[i][j]);
            ...
        }
        getline(cin, line);
    }

28日 1224. 交换瓶子

可以直接暴力，一个数字如果不在对于位置上，就必须操作一次回去，on从1开始扫描哪个位置数字不对就swap过来，扫过的位置一定就匹配ok了；
或者要想到用图论解决，，

29日 1240. 完全二叉树的权值

注意数据可以取负数，且是完全二叉树，则最后一层可能不满，深度从1开始；

30日 1050. 鸣人的影分身 - AcWing题库

dfs可以做，但注意好终止条件，应该是个数相同的时候判断，和相同答案就++再返回，不同就直接返回；
动规做法：
dp代表所有总和是 i，且分成 j 个数的和的方案；
状态分为有0的分身和没有0的分身，即f（i，j）= f（i，j-1）+ f（i-j，j）；
初始化 dp[0][0] 应该为 1，对于 dp[0][n] 都是0；
循环注意总和可以是0，但是不可以分成0个数，至少为1；

31日 1047. 糖果 - AcWing题库

（压缩到一维的前提：j 要单调）
dp：从前 i 个物品选，且总和除以 k 的余数为 j 的所有方案数；
需要最大值；
状态计算：不包含物品 i 和包含物品 i；
初始化：因为存在dp[0][n]的非法方案，所以需要将dp先置为负无穷，再初始化dp[0][0]为0；
i 从一到 n，j 从0到 k；
dp[i][j]=max(dp[i-1][j], dp[i-1][(j-a%k+k)%k]+a);

2月

1日 1222. 密码脱落

计算要补几个字母等效于删几个字母变成回文串，即求字符串总长减去字符串中最大回文序列的长度；

3日 1220. 生命之树 X 树dp

dp[u]所有以u为根的子树中包含u的所有连通块的权值的最大值；
图相关的不太想做了，，

6日 4956. 冶炼金属

推公式；

7日 1070. 括号配对

集合：所有将 [i, j] 变成合法括号序列的方案的集合；
属性：最小值；
状态计算：左边为(a)，[a] ，右边为ab

15日 3025. 人员站位的方案数 I

需要完整思考，将坐标按照从左到右，从上到小排序，然后固定一个点后，遍历这个点之后的所有点，判断条件简单，就是当前（后一个）的y坐标必须同时小于等于固定的y和大于前一个作为答案的y（当前循环），如果大于则ans++并更新最大y；
因为已经排序了，所以不需要第二个循环不用考虑第一个循环之前的位置了（位于左方和上方，肯定不成立；

16日 49. 字母异位词分组

思路一：大力出奇迹，将每个字母对应上一个质数，一个单词所代表的哈希的键为其中的对应的质数相乘，数组要用unsigned long long；
思路二：将单词排序，排序后的string如果相同，则一定是异位词，按照排序后的单词为key，原本的**单词集（此处类型应该为verctor）**为value即可；

17日 128. 最长连续序列

考虑好边界情况（比如：最后一个更新的情况），并且状态变换的情况，因为sort后变为单调增的数组，故分别为 符合要求：+1 和 相同数字 和 不符合要求的数字；
想好开始状态和结束状态的区别；

18日 11. 盛最多水的容器

需要确定什么情况下得到一定发生的结果，即**x**的差值缩小同时降低线的高度，可得到面积缩小的结论，所以此时要找最大值，理论上来说是x差值大且线高；
所以每次将两侧线相对低的一侧向内移动，保证最高的线还在；或者说缩小x的差值，可能降低或者提高线的高度，再次计算面积取最大值，重复到两侧合并为止，即可获取最大值；

19日 15. 三数之和

因为题目要求返回三元组是值的形式而不是index，所以可以sort数组；
先枚举第一个数，因为数组单增，所以可以用双指针，左侧为第一个数+1（即除第一个数之外最小堆数），右侧为数组最后一个数（即最大的数），此时再判断和0的对比情况，小于0则l++，大于则r–，等于则保存结果，且左右指针向内移动，由于防止重复的三元组出现，所以还需要while loop排除指针指向下一个数和上一个数相同的情况（因为第一个数是固定的，所以后两个数不能和当前第一个数字已经成立的三元组重复，需要分别右/左移到不同的数）；

20日 42. 接雨水

暴力做法，遍历数组时，每一位为底，记录左最高，寻找右最高，计算每个位置可以的水位再加一起；
使用一个数组记录每个位置对应的左边最大值，第二个循环找右侧最大值（第一个index的右侧最大值是0，所以右侧最大值在循环最后更新），从后往前遍历数组，记录左右最大值中的最小值，如果这个最小值比当前位置的底座高度高，则说明可以接到水，加入ans；

21日 3. 无重复字符的最长子串 滑动窗口

典型，可以用uset或者hash，核心在于更新状态是滑动窗口至当前重复字母不重复了为止；
先增大在缩小窗口；
438. 找到字符串中所有字母异位词
直接暴力前缀和，特殊对应值为质数平方；如果从后往前遍历，注意特判index=0的时候是否成立；

22日 560. 和为 K 的子数组 unordered_map

注意:
while内如果判断a<b，最后因为a自增后，不满足这个条件而退出循环时，a最后应该等于上一个满足条件的值再加上一次自增；
对于unordered_map，如果使用了一个不存在的键，它会返回一个默认值，对于int类型，默认值为0。因此，当sum - k为负数时，cul[sum - k]会返回0，而不会导致错误或异常；
方法：使用哈希表可以省去查找的第二层循环，key为sum的大小，value为sum出现次数；先计算前缀和，再使用cul[sum - k]查找（此处的作用等同于当前 index 对于的前缀和 减去 之前任一（查表）的前缀和 要等于 k），将查询结果加到ans内，如果没找到则会返回0，最后将当前前缀和作为key，++；
记得哈希表初始化key：0为value：1，因为此时代表sum刚好等于k，则意思为从0开始的前缀和刚好等于k，则至少需要加一；

23,24日 239. 滑动窗口最大值 双端队列deque实现单调队列

挺好的题，自己实现pop()和push()；
push：为了保证队列是从大到小排列，所以队尾入队时，需要pop_back()尾部比当前v还小的值；
pop：为了在窗口滑动后弹出对应左侧值，如果当前弹出的左侧值与deq的头值相同才弹出，否则说明当前头值仍在窗口内，当前deq的front()就是最大值，因为队列是按照顺序存储的，所以即使有重复数字也不影响什么；

25日 100225. 求交集区域内的最大正方形面积

找交集：

int x1 = max(a[i][0], a[j][0]); //x1, a1
int x2 = min(b[i][0], b[j][0]); //x2, a2
int y1 = max(a[i][1], a[j][1]); //y1, b1
int y2 = min(b[i][1], b[j][1]); //y2, b2

满足x2 > x1 && y2 > y1即为可选答案；

26日 76. 最小覆盖子串 好题 滑动窗口

注意：
umap[s[i]]，如果该key不存在，umap会自动创建默认value为0的kv；而umap.count()是查找以 key 键的键值对的个数，可以无修改返回0；
判断是否已经包含目标串，可以用umap.size()而不是t.size()，这样可以排除重复字母的判断逻辑，不用考虑该不该多一个字母；
使用s.substr(start, len)可以将s串对应start开始，长度为len的字串截下来，这样不用考虑如何找历史最短的字串了；
扩张窗口：

if(umap.count(s[i]))//注意不能用umap[s[i]]
{
    backup[s[i]]++;
    if(umap[s[i]] == backup[s[i]]) index++;
}

收缩窗口：

if(umap.count(s[l]))//如果字串起始位置就是目标串内字母
{
    if(umap[s[l]] == backup[s[l]]) index--;
    backup[s[l]]--;
}

记得扩张/收缩后移动r和l；

27日 53. 最大子数组和 56. 合并区间

一句话：当前状态和当前状态加上一状态取最大即可，即上一状态是否为正数；
简单的逻辑为：直接将区间放入ans，如果下一个区间重复了，即直接在ans内修改右边界为最大原右边界和新右边界即可，否则直接将新区间加入ans；

28日 189. 轮转数组

go，copy临时slice，再赋值回原来的nums；

29日 238. 除自身以外数组的乘积 503. 借教室 差分

找规律，可以开两个额外数组，分别存前缀乘和反过来的前缀和（对应index相乘即为对应答案）；

503：差分+二分，核心在于判断一个订单是否可以完成，
差分即反前缀和；

// 构建差分
for(int i=1; i<=n; i++)
{
    b[i]=day[i] - day[i-1];
}

// 区间修改等于差分单改
for(int i=1; i<=mid; i++)
{
    b[d_start[i]] -= need_room_nums[i];
    b[d_end[i]+1] += need_room_nums[i];
}

// 前缀和算法，构建回原数组，如果有负数则代表订单不能满足
// 外面利用二分查找第一个不满足的订单即可
for(int i=1; i<=n; i++)
{
    b[i]+=b[i-1];
    if(b[i]<0) return true;//表示订单不能满足
}
return false;

3月

1日 562. 壁画

等同于求长度为n/2上取整的数组和最大；0~mid一直移动到mid~n-1；

2日 796. 子矩阵的和?

以第一次出现的余数为key，找到后才value++，判断如果第二次及以后出现都是条件成立;
key之前出现过几次，ans就加几次，即有几段子序列都符合条件;
注意有一个额外的情况，即余数为0时，第一次出现的key也要算进去，即c[0]一开始就需要++

4日 4262. 空调

关键：计算正数和，负数和，答案一定大于等于正数和以及负数和的绝对值的最大值，所以最少取等于，即正数和以及负数和的绝对值的最大值；
差分中的正负是相对的，即不可能单独出现

5日 3745. 牛的学术圈

思路大体正确，但是细节边界根据结果反馈才调对的；
前提：0~n读入数据，从大到小排序；
要注意：
当paper[i] < i + 1时，说明此时前一个的索引是可能是次大的结果，并且可以完全不用考虑后面了，当前最多+1（在**l>0**时），注意此时分为两种情况，要在前一个索引和当前值+1取最大；
当paper[i] == i + 1时，说明当前值刚好可能是最大的h值，先记录下ans，但是需要考虑到如果**l**足够大，且当前索引后一个值和当前值相同，以及如果当前索引之前的值和当前值一样时，要计算这几个部分加起来是否小于等于l，即**当前索引之前的值和当前值一样的索引数量 + 1（当前索引） + 1（下一个值和当前值一样） <= l**，是则让ans++，否则直接break即可；

ℎ 指数等于使得研究员有至少 ℎ 篇引用次数不少于 hℎ 的论文的最大整数 ℎ。

6日 505. 火柴排队 相邻可移动等于求逆序对

让一个数组尽可能与目标数组的各个位置的数字相近或者相等，
一个数组，index和value，index是单调自增的，而value是乱序的；此时排序后可以得到 -> value也是单调的了，此时满足题意，火柴间尽可能小对小，大对大；
但是此时a和b数组都是乱序的，所以需要先对他们的值分别进行排序，此时他们的index对应的就是原本值从小到大的位置，注意这个时候两个数组第**i**小的数字的索引一一相对；即a[i] => a的第i小的数字的索引，b[i] => b的第i小的数字的索引，而题目等于求两个数组第i小的数尽量一一对应，则等于求hmap[a[i]]=b[i]哈希数组的排序；而调整几次即归并排序相邻才可移动条件下等于求逆序对ans += mid-i+1;；

7日 1262. 鱼塘钓鱼

拿一个数组保存第i个鱼塘的钓鱼时间，记录去第i个池塘在路上花费的时间（即前往鱼塘的前缀和），
先遍历最远去第几个池塘，以当前去的第几个池塘为最远距离，遍历时间，对应每一分钟选哪个池塘钓鱼，然后将钓到的鱼加入res，并且对应第i个鱼塘的钓鱼时间++；最后返回res，外层遍历最远去第几个池塘用ans记录最大值；

8日 4261. 孤独的照片 乘法原理

数据读入：char arr[500010];scanf("%s", arr);
因为确定序列中，字母只出现一次时一定要被抛弃；
所以由此确定边界情况：字母只出现一次在中间，即左右两侧均为连续的不同字母（这部分的和为左右两部分连续字母的数量相乘），字母只出现在第一个位置，即右侧均为连续的不同字母（这部分的和为右部分连续字母的数量-1，如果小于0则不加），字母只出现在最后一个位置，即左侧均为连续的不同字母（这部分的和为左部分连续字母的数量-1，如果小于0则不加），
-1的原因是，序列需要大于等于3，这里等于是在枚举至少一个位置，所以为了确保最后加起来一定>=3，所以需要一个位置提前和只出现一次的字母绑定一起；
关键在于存储当前i个字母左边和右边各自的连续不同字母的数量；

if(arr[i]=='G')
{
    l[i]=h;
    h=0;//清空连续h的数量
    g++;
}else{
    l[i]=g;
    g=0;
    h++;
}

求解即为每个位置对应左侧和右侧连续不同字母的数量相乘，再加上左边连续不同字母-1+右边连续不同字母-1

9日 4405. 统计子矩阵 二维前缀和优化

枚举上下边界，确定左右缩小刚好小于等于k的边界，此时内部所有列矩阵符合要求（即上下边界内看作一维矩阵）

for(int s = 1, t = 1; t <= n; t ++ ){
    while(s <= t && arr[t][j] - arr[s - 1][j] - arr[t][i - 1] + arr[s - 1][i - 1] > k) s ++ ;
    if(s <= t) ans += t - s + 1;
}

5481. 双端队列
注意如果使用了递归，谨慎使用全局函数，否则递归返回后，变量的状态可能没有返回到上一状态；
5480. 截断数组
逻辑上思考漏了一点 -> 一次切割刚好最小就是等于B时；

10日 100251. 数组中的最短非公共子字符串

string::npos 是 std::string 类的一个静态成员常量，通常用于表示字符串中未找到指定子字符串或字符的位置。它的值是一个特殊的无符号整数常量，通常被定义为 -1，但实际上是一个极大的正整数。在字符串查找函数中，如果找不到指定的子字符串或字符，那么返回值将会是 string::npos。
举个例子，如果使用 find() 函数在字符串中查找某个子字符串，如果找到了，它将返回找到的子字符串的位置，但如果没找到，它将返回 string::npos；

std::string str = "Hello, world!";
size_t found = str.find("world");
if (found != std::string::npos) {
    std::cout << "Substring found at position: " << found << std::endl;
} else {
    std::cout << "Substring not found!" << std::endl;
}

枚举字符串，再枚举字串长度，再枚举字串开头，再检查该字串在其他字符串内是否出现（find()），如果有则更新答案数组，并在枚举字串长度的循环内使用break；

11日 3498. 日期差值

模板：

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

//判断闰年
int is_leap(int year)
{
    if(year % 4 == 0 && year % 100 || year % 400 == 0)
        return 1;
    return 0;
}

int get_days(int y, int m)
{
    if(m == 2) return mouth[m] + is_leap(y);
    return mouths[m];
}

//读入数据：
while(scanf("%04d%02d%02d", &y1, &m1, &d1)!=-1)
{
    scanf("%04d%02d%02d", &y2, &m2, &d2)
    ...
}

将日期差值当作两个日期到起点的长度的天数差值；
4957. 飞机降落 - AcWing题库
dfs
4958. 接龙数列 - AcWing题库
dp[i]表示为以i结尾的最长接龙数列；因为当前状态的更新取决于上一状态的尾巴；
如果上一个状态的末尾需要等于当前状态的头，则说明dp可以更新，更新的值即为以上个状态的末尾为结尾的最长接龙数列+1，就等于以当前状态的头为结尾的最长接龙数列+1，

12日 1343. 挤牛奶

又忘记最终状态了，如果最后没触发，数组有数据，则记得更新；

13日 1360. 有序分数

小失误，判断公因数不能直接用%，

14日 2060. 奶牛选美

注意原地也要计算，即偏移量有五个；

15日 167. 木棒 dfs

记得初始化的visit；
因为要全拼接一起，防止多个小的合成，所以要先从大到小排序；
285错6

16日 5556. 牛的语言学 vector去重，substr

暴力dfs过部分数据：注意map.count是找几个KV，即使V==0也是一个KV；
vector去重：sort排序后，使用v.erase(unique(v.begin(), v.end()), v.end());
unique将重复的数据放到末尾并返回第一个指针；
substr(start, len);start为开始复制截取的位置，len为截取的长度，如果不合法则默认截到最后面；
f[i]表示为0~i长度的串能否成为词根；
5557. 孤立点数量
成环则无孤立点，树状则最少有一个孤立点；

17日 成为 K 特殊字符串需要删除的最少字符数

正常哈希后排序，枚举 字母出现次数_cnt[i]_ 为最小值；
即删除所有出现次数小于cnt[i]的字母，多于它的取min(cnt[i]+k, cnt[j]);；
找最多可以留下多少字母，最后剪掉就是最少了；

18日 1355. 母亲的牛奶 bfs

整体思路正确，但是小细节坑了好久；
注意：遍历的正确性，一共三个桶；
整体bfs过程中可以全用局部变量，一个状态在一轮循环中，生出多个状态，如果没出现过就将其加入队列；

20日 528. 奶酪

小细节：
如果dfs结束条件只需要执行一次，记得将标志位一起放到for循环中，避免多次判断结束条件；
但是dfs会超时；

并查集：将连通的洞合并，再遍历底下和顶上的洞有没有被连通，有则yes；

21日 1402. 星空之夜

主要hash难，一种做法是计算连通块内任意两两间的直线距离和作为key；
连续读入，可用char直接读行；

22日 739. 每日温度 单调栈

简单来说就是利用栈按顺序从小到大保存元素（从top到bottom），遇到一个元素比top大时，while判断直到top>=新元素；

23日 1413. 矩形牛棚 单调栈 5559. 摆放棋子

同样使用单调栈，但是需要先枚举每块地向上的符合要求的地一共有几块，等于说找到当前的最高；
然后再重新遍历一次，判断每块地的左边第一块小于当前高度的地和右边第一块第一块小于当前高度的地，这左右两边夹的中间的面积就是当前地的最大面积，然后所有地的最大面积取max即可；
第二题思路对了一半，双指针应该逐步移动，如果超过k就移动l，正常情况下移动r；

24日 100258. 最高频率的 ID multiset和priority_queue

multiset：*ms.rbegin()：取最大值；
逻辑简单一点，直接先找当前频率是否存在，存在则将其删除，重新计算当前频率后再insert回multiset，ms.rbegin()返回最大值的指针；
priority_queue：pq.emplace(hmap[nums[i]], nums[i]); 在优先队列的顶部插入一个新元素；
默认从大到小；

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

//升序队列 priority_queue <int,vector<int>,greater<int> > q;
//降序队列 priority_queue <int,vector<int>,less<int> >q;
对于优先队列，需要判断当前的最大频率对于实际哈希表内记录的真实值是否相同，如果相同就继续，如果不同说明当前频率被减少了，需要弹出最大值；

26日 312. 乌龟棋

四维dp[b1, b2, b3, b4]含义：第i张卡用了bi张的走法的最大值；
四种的前一个状态分别加上当前位置的值，遍历所有可能取最大，记得初始化第0步的值；

27日 1371. 货币系统

容量为0，价值为0也是一种方案；记住找状态转移，不要中间还想dfs；
要清楚dp是一类状态，小于的一定全统计了；

29日 拉马车 string类 dp

模拟题一定要确定逻辑，不能想当然；

// .erase()
//删除起始位置为0，长度为1的字符串；返回值：删除后的字符串
str.erase(0, 1);			
//删除str.begin() + 5所指向的单字符
str.erase(str.begin() + 5);	
//删除指定范围字符串，左闭右开；
str.erase(str.begin() + 5, str.end() - 3);

// 翻转字符串
// 无返回值
reverse(str.begin(), str.end());  	//algorithm
strrev(str);						//cstring
string(str.rbegin(), s.rend()); 	//string，传入的是逆向迭代器

// .find()

char c='a';
string b="d";
// 正向查找，如果没有找到会返回string::npos，找到则返回下标
int index = s.find(c);
int index = s.find(b);

// 在原本的基础上，改为从下标3开始匹配（包含3）
int index = s.find(c, 3);
int index = s.find(b, 3);

// 找到目标字符在字符串中第一次出现的位置
int index = s.find_first_of(c);
..

// 找到目标字符在字符串中最后一次出现的位置
int index = s.find_last_of(c);
..   

5406. 松散子序列
主要难度就在理解题意，，它的意思是，松散子序列指在原字符串中挑选不能相邻的字符组合而成；

718. 最长重复子数组和1143. 最长公共子序列
前者因为需要连续，所以不满足条件是没有状态转移，后者不需要连续所以需要记录历史状态；

115. 不同的子序列
想清楚：什么时候匹配的次数会变多：即s中有重复的字母：即s单独回退时，此时作为上一状态可额外增加到正常情况下匹配到的字符串次数内；
初始化：当t长度为0时，s有且仅有一种方法和t匹配，即删光所有元素；
转移公式：考虑的是上一状态s和t都回退一位时，相同字符串的个数 加上 仅回退s的相同字符串个数，因为此时个数是由这两部分组成的，第一部分是既有的一个，也就是正常情况下的匹配字符串（一开始是1，后面可能因为添加过第二部分变大），第二部分是由于s有重复的字符时，个数就相应变多一个，正是第二部分才让t可以匹配多个s内的子序列；

30日 4959. 岛屿个数

读入二维char数组：直接一重循环即可，二维int数组就不行；
二维数组也支持两重循环读入

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        cin>>b[i][j];

水一定是全流通（偏移量为8个）的，但凡水流不进去的一定是岛，则计算水碰到几片岛即可；

31日 5562. 最大生产

注意二段性，直接二分秒杀了；判断题目类型很重要！！！
vector找最小和最大：min_element和max_element；

4月

1日 2563. 统计公平数对的数目

可查找有序数组的上下界：
upper_bound : >
lower_bound :>=

2300. 咒语和药水的成功对数
a/b上取整 == (a+b-1)/b下取整 == (a-1)/b下取整+1
故a*b>=c 等价于 b>= c/a上取整 等价于 b>(c-1)/a下取整
注意：两个long long类型即使是相除得到int内的数据，也必须用long long类型保存数据，否则计算的中间结果可能溢出；

3日 4199. 公约数

a和b的约数一定是a和b的最大公约数的约数；

约数只能是自然数，而因数可以是任何数

4日 740. 删除并获得点数 dp 快速幂

dp一定是一类的最优情况，注意定义dp时尽量不要出现非最优的位置；
注意判断dp在递推时，什么情况下会出现真正的状态转移（而不是单纯计算过程，过程最后才需要真正判断dp）；比如此题，真正的状态转移应该发生在一串连续数字的最后，要么这串数字之和才需要进行判断：选自己加上i-2（非相邻的连续数字自己的和），及相邻数字和的大小，取最大即可；
注意不需要dp过程中计算同样数字的长度，因为最终判断dp时，一定用的是各个数字的最大分数进行比较的，所以应该一开始就算出各个数字所代表的数字，这样化简题目后，就等于打家劫舍了；

504. 转圈游戏
282. 石子合并
dp[i,j]：将[i,j]合并成一堆的方案的集合内的最小值，分治
先算前缀和，方便算当前合并时的代价；
先枚举合并的长度，从2开始，然后再枚举左端点，然后再枚举中间点（最小为左端点，小于右端点，即小于左端点加区间长度-1），枚举中间点时更新dp[i][j]；

5日 4408. 李白打酒加强版

思路正确，但是细节出错：
1、初始化&遍历起始位置错误，可能一开始连续碰到花或者店，所以起始位置应该从0开始，初始化最开始dp[0][0][2]为1即可；
2、这类返回方案的dp问题，最后的答案一定由上一个确定的方案返回的，上一个确定的方案才符合一般的递推要求，所以答案直接就是上一个方案的最大方案数；

6日 275. 传纸条

dp[k][i][j]：横纵坐标之和为k，i为x1，j为x2；
先取出对应坐标的值，如果x1!=x2则可以取两个；
进行状态转移：因为有两个x，所以有四个状态，分别是上一状态需要往下，下走、下，右、右，下、右，右，
转移后再将对应坐标的值加上当前位置（当前位置已经转移为历史最大值了）；

7日 3417. 砝码称重 dp 贪心

1、初始化记得大概率是0开始的，此处是当需要凑的重量为0时，写为true，其实意思是当凑到某一重量时，值是相等即相减等于0的；
2、考虑状态转移时，要明白当前状态由上一状态转换而来时，上一状态不一定是需要的值，即此处为减去重量的dp，因为减去重量等效于加上负重量的方案，重点在于方案的变化，负数即减去也是一种方案；

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

104. 货仓选址
应该选中间的商店的位置，而不是两侧最远商店的中间位置；

10的五次方的贪心一般是排序，10的六或者七次方一般是遍历一次即O(n)，如果是1000则为三重循环

12日 1349. 修理牛棚

贪心还是容易细节出错：
注意原数组如果题目没有明确说排序了，则需要自己重新排序；
注意数组的初始化，如果最大项是n，则应该sort(arr+1, arr+n+1);；
一定想清楚数组的初始化及排序后的情况；

14日 41. 缺失的第一个正数

因为是按照正整数排序，所以可以考虑当前index和值不对应时，遍历到对应的值就放到对应的index上，保证数组的正整数按照顺序排序，当遇到第一个index不等于值的地方，此处的index就是缺失的第一个正数；

16日 54. 螺旋矩阵

核心在于用一个矩阵记录走过的部分，当下一步将走到边界或者走过的部分时，顺时针旋转下一步的方向；

17日 48. 旋转图像

将一个矩阵分成四个相等的部分（如果边为奇数，中间一个小矩阵不用旋转故不考虑），旋转矩阵就是将这四个部分 转 一次，可推出数学公式，故只需遍历一个部分的所有矩阵就可以翻转矩阵了，此时长宽分别为**边/2**上取整和下取整，这样这四个矩阵才可能是拼接在一起的；

18日 240. 搜索二维矩阵 II

经典需要分析题目，每行/列从左到右，从上到下是递增的，所以可以考虑右上角开始从大到小搜索，碰到比target小的数，则往下一行同一列继续搜索；
如果是从小到大，容易分析出：转折点在于比target大的位置，但是下一个位置一定也比target大，需要冗余查询；

19日 160. 相交链表

因为链表不等长，所以指针遍历的时候，当两个指针第一次遍历后，第二次遍历对方的链表，这样可以使指针遍历的链表总长度相同，所以最多遍历n+m的长度，如果两个指针都同时指向nullptr则说明链表不相交，如果两个指针中途相等了，说明这个节点就是第一个相交的节点；

5月

1日

2023第十四届蓝桥杯国赛 C/C++ 大学 B 组 (赛后记录)_蓝桥杯2023csdn-CSDN博客
A题 子 2023
头文件：**#include<string>**
string s = to_string(i); //将整数i转换为字符串表示形式
直接将1到2023中，提取2，0，3后全拼接到字符串上，然后dfs2023；

for (auto a : temp){}

5日

push_front()//在队列的头部插入元素。
push_back()//在队列的尾部插入元素。
    
emplace_front()//与push_front()的作用一样 
emplace_back()//与push_back()的作用一样

pop_front()//删除队列头部的元素。
pop_back()//删除队列尾部的元素。

front()	//返回队列头部元素的引用。
back()	//返回队列尾部元素的引用。

clear()	//清空队列中的所有元素。

empty()	//判断队列是否为空。

size()	//返回队列中元素的个数。

begin()	//返回头位置的迭代器
end()	//返回尾+1位置的迭代器

rbegin()//返回逆头位置的迭代器 
rend()	//返回逆尾-1位置的迭代器 

insert()//在指定位置插入元素 
erase()	//在指定位置删除元素 

bool isEqual(double a, double b, double epsilon = 1e-9) {
	return fabs(a - b) < epsilon;
}

// 如果它们的斜率相等，则返回 true，否则返回 false。
bool areCollinear(double x1, double y1, double x2, double y2, double x3, double y3) {
	return fabs((y2 - y1) * (x3 - x2) - (y3 - y2) * (x2 - x1)) < 1e-9;
}

16日

92. 递归实现指数型枚举
注意打印条件：每个位置都选好：是选or不选后再打印；

6月

15日

300. 最长递增子序列
时间复杂度优化到O(NlogN)的思路：
遍历一次原数组，在新数组中，找到第一个大于等于nums[i]的值的位置（二分），替换掉它，如果新数组中没有找到，即当前nums[i]为最大的，添加到新数组末尾，重复操作即可；
eg：2 6 7 3 4 5
2 -> 2 6 -> 2 6 7 -> 2 3 7 -> 2 3 4 -> 2 3 4 5