模板！供学习参考，会更！（我自己都不信） （￣︶￣）↗　出发！

寒假，致力把CSP-J的真题刷完。 每道题都会写题解。 从简单到难。 P5660 [CSP-J 2019] 数字游戏 题目大意：问一串字符串中字符一的个数 使用知识点：字符串的输入和遍历 注意点：是字符串，不要int类型输入啊。 代码： 难度评价：入门中的入门 P5681 [CSP-J 2019 江西] 面积 题目大意：问aa 和 bc 谁更大 使用知识点：int的范围 字符串输出 if else 注意点：19∗191^9 * 1^919∗19超出了 int 的范围 请使用 long long 代码： 难度评价：在人门中需要一点心眼，但不多 题目拓展： 这个题目，但拉出来简单，却会成为在难题中隐藏的小炸弹。 “不开long long 见祖宗”，想必各位都并不陌生。 所以在对题目进行检查的时候/做题的时候，切记要注意是否算出的答案会爆int。 （我的建议是最好直接用typedef 开，因为很多是你意想不到的：比如说折半搜索的答案最后往往是要爆的） P7071 [CSP-J 2020] 优秀的拆分 题目大意：对于数字n，询问其是否能分解为若干个不同的2的正整数次幂。 题目思路：对于“2的次幂”，需要有一定的敏感度，联想到二进制。 代码： 难度评价：入门中的战斗机，似乎有点普及-的影子。 题目拓展：可以去用“&"判断两者之间是否互相包含。对二进制要有一定敏感度。 P8813 [CSP-J 2022] 乘方

现在大概有洛谷，xmw，数学三个课。 到时候集训上完了可能还有。 集训 Day1 D1学习前缀和，差分，单调栈，单调队列。 早上是前缀和与差分。 在进行这两个算法的时候，你往往要注意到一件事： 如何体现其处理优势？ 有的时候，它们的用处可能仅仅是优化掉一次方N. 但有的时候，它们可能可以优化很多。 仅仅只是做区间和还不够体现它们的优势。 T1 优美子数列 链接描述 这道题的大意是让你在一段序列中找出和为k的倍数的子序列。 1.浅层运用前缀和： 首先预处理出所有子序列的前缀和。 然后枚举左右两个端点。 但不容易发现这样其实是在前缀和无效化。 那么如何更好地去运用前缀和？ 2.前缀和理解加深 当需要查找最终值为定值的序列中，我们首先需要观察等式的关系： pre[r]-pre[l-1]=-k -2k -3k -4k k 2k 3k …… 发现这里我们要查找的是k的倍数。 即%k=0的数 (pre[r]-pre[l-1])%k=0 也就是 (pre[r]%k-pre[l-1]%k)%k=0 在这种式子里，我们只需要确定两个未知数的一个即可知另一个未知数。 那么大概就能够得出如何去做了。 额注意一下负数取模。 要复习的题目： 课前小测-优美子数列 体现前缀和处理优势？ 区间段和为定值： pre[r]-pre[l-1]=x 当x被确定后 构造回文数组 模型：积木堆叠 上升：操作增加 下降：操作不变 本题本质上是一个差分，但需要再次分析一下。 在进行前缀和操作的时候，或者其他累加累乘操作的时候 要注意小心，开Longlong 会爆int mex 统计：利用前缀和 找出e前面有多少个m e后面有多少个x 比较复杂的代码要学会分块，更加容易调试。 前缀和与差分 - 区间操作 现在开始缓慢地写题解。 T1 优美子数列 下午开始学单调栈和单调队列 单调栈模板： 需要保证栈是否为空再去判断。否则会发生奇怪的问题 动物园的等待 链表？ 下一个更大的元素： 写单调栈和单调队列的时候要注意判断栈和队列是否为空。 在写单调栈和单调队列的时候要注意判断栈和队列是否为空。 构造回文数组 前缀和不开long long 见祖宗的嗷！ 前缀和：pre[r]-pre[l-1] 差分：pre[l]+x pre[r+1]-x D2 早上开模拟赛 下午摸题解。 想要找到第n大的质数。 欧拉筛：O(n) 每一个和数 都只会被自己的最小质因数标记。 埃氏筛：O(n log lon n) T2：可以使用暴力，也可以使用优先队列。 我觉得，做错的原因主要是我当时思路不太清晰。 做一道题，应该先想清楚思路在开始吧。 等一下。 我去找老师对了一下思路。理论上而言，我的思路应该是正确的。 不过正确了也T。 我觉得这题我没做出来的主要原因是我以前的东西忘得有点太多了。 啥都不记得了。 在想优化的时候大脑空空。 啥都不知道。 反正最后结果就是我养了优先队列。 然后我去看看欧拉筛是怎么写的。 用分块来写代码后，可以写一个快，检查一下 在做难题或者复杂的题目的时候，要先自己做一些小的样例。 然后慢慢总结规律。 摸个T4吧。 好可惜啊。 T4要是考场上再想想可能就写出来了。 但我去刷小红书了喵。（逃跑 但是没关系，让我们来美美地写一个题解吧遗憾弥补一下吧！ 这道题，它主要是想问在一颗树上，如何加才能使整体数值加到它期望的样子。 我觉得此题的难点有两个： 1.它的范围不太好判断。如果初读的话，你可能会有点懵。 （不过这个也是题目的必须点，亦是突破点） 2.它的思路有点难想（虽然其实很简单，但是如果你正常做的话，你可能会觉得自己遇到了一堆难点） 就这两个，平均下来应该是绿题里面比较简单的题目吧。 然后说说具体是怎么做的吧。 想动态规划一样，有两种遍历方法： 1.自顶向下 2.自底向上 这个提出的好像有点早了，到时候再说好了。 可以从一条链开始推。 然后你就会发现一个核心点： 从最下方开始，并且最好是取每个点的最大值（这个稍微推一推就出来了） 然后就没有了。 欧拉筛： 然后接下来去做点好玩的 咪。 1.优先队列 链接描述 神奇的优先队列介绍！ 优先队列分为两种：1.小根堆 2.大根堆 再要细分的话，还有结构体优先队列 和 数字优先队列。 看看： 1.数字大根堆（默认，大的数字在前）： 2.数字小根堆 结构体大/小根堆： 好的，那么现在理论成立，实践开始。 优先队列的运用主要有两个（为我所知的）： 1.优化 2.反悔贪心 这里主要介绍一下优先队列用来优化。 关于如何优化，让我们用一道题目见识一下。 舞蹈演出 这道题的题意非常清晰，在此就不过多赘述了。 暴力如何打应该已经知晓： 每次二分k的最小值，设置出k个值为t的变量，然后每次找值最小的一个减一个。 如果说，想要找最小的值且用暴力的话，一次就是O(n)界别。 而1e4的n没办法支撑O(n^2logn)的时间复杂度。 只能支撑O(nlogn)或者O(n)又或是O(nloglogn) 也就是，要优化一个log。 而且是要找动态最小值。 哦豁，答案呼之欲出！ 优先队列是也。喵。 关于神奇的链表！ 通常，我们不是用STL里面的链表（太难用了喵），而是自己通过结构体来模拟。 现在我们一起来做一道模板题目。 模板双向链表 这道题目钟一共要求了三个关于链表的更改操作。 1.将x插入到y的左侧 2.将x插入到y的右侧 3.删除x这个节点 我们来分析一下这三个操作： 将A插入到B的左/右侧 它本质是两个操作： 1.删除 2.插入 如果A原本存在于这个数组之中，那么将其删除。 先来看看如何实现删除这个操作： 删除一个元素，意味着这个元素的左边的右边要变成它的右边。 这个元素的右边的左边要变成它的左边。 这个就是删除操作： 然后思考一下插入操作怎么整。 将A插入到B的左边，也就意味着： B左边的右边变成A，B的左边变成A的左边，A的右边变成B，B的左边变成A 也就是这样： 最后输出一下就好了： 枚举： 枚举什么？ 1.确定枚举范围 2.如何是枚举不重不漏 要把一个大问题分解成若干个小模块去解决 T4：绝对值即距离 对于距离，考虑相对位置的情况。 1.重叠，包含 2.b在a 前面 3.a在b前 重点在于维护：amin bmin amax bmax 归并排序： 分治是很重要的思想：分而治之。 这是所有庞大规模问题的基础。 下午上倍增和ST表 关于倍增： RMQ问题：区间最值问题 额主要讲一讲如何使用吧。 一句话概括：倍增是思想，ST表是框架。 ST表的模板虽然是取区间最值，但是这并不代表它只能用来取区间最值。 相反，它的运用面是很广泛的。 拿一道题目来举例吧。 链接描述 利用ST表的框架。 先考虑大致思路框架： 每走一步，需要想的是：走到了哪里->拿了几个胡萝卜 而我们已知的是：我们走了几步 如果一次一次推的话，时间复杂度大概是O(m) 太高了。 如何优化？ 下午讲了选讲内容： 离散化

这题只有质子才看的懂

78题，千万别写，纯魔丸。

此题 ***等级为A级 *** ，很难 ，萌新不建议做

简单

"唯一"呢？

为什么洛谷过了，这里过不了？ @古希腊掌管AC和WA的神@Forwhy

#include<string>

（做不对的好神人）

我那个题解没用！求助

> 注意内存限制！\HUGE\COLOR{RED}\SF注意内存限制！注意内存限制！

#8测试点写错了 123 456得到的应该是975 ，不是777

666

#include <bits/stdc++.h> using namespace std; int a[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int main() { int y,m,flag=0; cin>>y>>m; if(y%100!=0&&y%40||y%4000){ flag=1; } if(flag && m==2)cout<<a[m]+1; else cout<<a[m]; return 0; }