上海网站建设推荐q479185700顶你,百度电脑网页版入口,男女直接做视频教学视频网站,沭阳那家做网站的愿意的可以跟我一起刷#xff0c;每个类型做1~5题 #xff0c;4月前还可以回来系统复习 2月13日 ~ 3月28日#xff0c;一共32天
一个月时间#xff0c;0基础省三 -- 省二#xff1b;基础好点的#xff0c;省二 -- 省一
目录
#x1f33c;前言
#x1f33c… 愿意的可以跟我一起刷每个类型做1~5题 4月前还可以回来系统复习 2月13日 ~ 3月28日一共32天
一个月时间0基础省三 -- 省二基础好点的省二 -- 省一
目录
前言
一前缀和
一3956. 截断数组
Time Limit Exceeded
Accpted
二[NewOJ Week 1] 前缀和的因子数
三P4702 取石子
四P3056 [USACO12NOV]Clumsy Cows S
栈 AC 12%
栈 AC 75%
栈 AC 100%
前缀和 AC 100%
五P1147 连续自然数和
AC 56%
AC 100%
二差分
一AcWing 3729. 改变数组元素
二P2367 语文成绩
三P8772 [蓝桥杯 2022 省 A] 求和
三二分
一1460. 我在哪
四
五
六
七
八
九
十
十一
十二
十三
十四
十五
十六
十七
十八
十九
二十
二十一
二十二
二十三
二十四
二十五
二十六
二十七
二十八
二十九
三十 前言 每个类型第一题来自AcWing蓝桥杯集训-每日一题 1花5块钱 2上洛谷找替代 / 原题 题型有 前缀和差分二分双指针递推递归并查集哈希单调队列 KMPTrieBFSDFS拓扑排序DijkstraFloyd最小生成树 最近公共祖先二分图筛质数最大公约数快速幂组合计数博弈论 背包DP线性DP区间DP树型DP树状数组线段树矩阵乘法 如果你想冲省一拿22年A组为例你得拿60分也就是2道填空题 4道编程题 5 5 10 10 15 15 省赛需要掌握的有 前缀和差分二分双指针递归递推BFSDFSDijkstra, Floyd质数筛最大公约数背包dp线性dp区间dp组合计数快速幂KMP哈希并查集博弈论 围绕省赛需要掌握的类型针对性地下手
先给大家看个时间复杂度来源于AcWing 一前缀和 多年后再见你 - 乔洋/周林枫 - 单曲 - 网易云音乐
→ 前缀和 差分 - OI Wiki (oi-wiki.org)
一3956. 截断数组
3956. 截断数组 - AcWing题库 类型枚举前缀和中等 还有个坑虽然10^5 * 10^4 int但是由于存在1e5个0的情况这时答案约等于1e10就会爆int所以ans还是开long long 按着思路枚举将数组分为3部分中间部分左边界i游标右边界j游标 然后在过了所有样例的基础上再想2组测试可以就提交 两组测试
8
7 2 3 2 1 3 10 14
17
3 -2 1 5 -3 4 -2
1
Time Limit Exceeded
#includeiostream
#includecstdio //scanf()
using namespace std;
int a[100010], n;
bool check(int i, int j) //i左游标, j右游标
{int sum1 0, sum2 0, sum3 0;for(int m 0; m n; m) {if(m i)sum1 a[m];else if(m i m j)sum2 a[m];elsesum3 a[m];}if(sum1 sum2 sum2 sum3)return true;elsereturn false;
}
int main()
{int i, j;scanf(%d, n);for(i 0; i n; i)scanf(%d, a[i]); //读入数据int ans 0; //截断方法数量for(i 1; i n - 1; i) //枚举中间部分for(j i; j n - 1; j) {if(check(i, j)) ans;}coutans;return 0;
}当n 100000直接暴力会超时下面是优化 第一次接触前缀和本题注意几个点 1ans开long long 2三部分都非空 3数据达到1e5所以复杂度O(n^2)暴力枚举不行至少得O(nlogn) 4代码第1718行s[i]表示第一部分前缀和s[i 1]表示第二部分前缀和 补充一组测试
8
1 0 1 0 0 0 0 1
10
Accpted
#includeiostream
#includecstdio //scanf()
using namespace std;
int s[100010];
int main()
{int n;scanf(%d, n);for(int i 1; i n; i) { //从1开始读入scanf(%d, s[i]);s[i] s[i - 1]; //前缀和, s[i]表示前i项的和}long long cot 0, ans 0; //截断方法数量if(s[n] % 3 ! 0) cout0;else {for(int i 1; i n - 2; i) { //整个数组下标从1到nif(s[i] s[n] / 3) cot; //if(s[i 1] s[n] / 3 * 2) ans cot; //}coutans;}return 0;
}解释cot先自增ans再加上cotcot表示第一部分满足三等分的数量ans表示既满足第一部分三等分又满足第三部分三等分的情况
二[NewOJ Week 1] 前缀和的因子数 P1791 - [NewOJ Week 1] 前缀和的因子数 - New Online Judge (ecustacm.cn)
分类基础题欧拉数论前缀和 细心是关键 1前缀和怎么求要会 2因数怎么求要会 3i, j游标别搞反了 AC 代码
#includeiostream
#includecstdio //scanf()
using namespace std;
int s[100010];
int main()
{int n;scanf(%d, n);for(int i 1;; i) {s[i] i;s[i] s[i - 1]; //前缀和int sum 0;for(int j 1; j * j s[i]; j) { if(s[i] % j 0 j * j ! s[i])sum 2; //求因数else if(s[i] % j 0 j * j s[i])sum;}if(sum n) {couts[i];break;}}return 0;
}三P4702 取石子
P4702 取石子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型前缀和入门 一看感觉好难为什么才入门。。看了眼题解。。 确实入门纯前缀和只是前面加了个类似贪心的判断 →想要分出输赢石子必须取完 为什么呢因为“a0视为0”所以。。显而易见 AC 代码
#includeiostream
#includecstdio //scanf()
using namespace std;
int s[100010];
int main()
{int n;scanf(%d, n);for(int i 1; i n; i) {scanf(%d, s[i]);s[i] s[i - 1];}if(s[n] % 2 0) coutBob;else coutAlice;return 0;
}四P3056 [USACO12NOV]Clumsy Cows S
P3056 [USACO12NOV]Clumsy Cows S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 大概意思就是输入偶数长度的括号最少修改多少次使左右匹配也就是都朝里 第一次我用栈做(4条消息) C STL 之stack_buyizhu021的博客-CSDN博客_stack赋值 栈 AC 12%
#includeiostream
#includestack //st.push(), st.pop(), st.top()
using namespace std;
string s;
int main()
{stackcharst;cins;for(int i 0; i s.size(); i) {if(st.size() 0)st.push(s[i]); //元素不足2个else if(st.size() 1) {if(st.top() ( s[i] )) {st.pop(); //如果栈顶元素和新的元素匹配}elsest.push(s[i]); //不匹配就把新的元素入栈}}coutst.size();return 0;
}原来是忘记对结果分类讨论了 如果最后剩下 ))(( 或者 ((((都需要2次而剩下 )((( 需要3次 栈 AC 75%
#includeiostream
#includestack //st.push(), st.pop(), st.top()
using namespace std;
string s;
int main()
{stackcharst;cins;for(int i 0; i s.size(); i) {if(st.size() 0)st.push(s[i]); //元素不足2个else if(st.size() 1) {if(st.top() ( s[i] )) {st.pop(); //如果栈顶元素和新的元素匹配}elsest.push(s[i]); //不匹配就把新的元素入栈}}//分类讨论int a 0, b 0;for(int i 0; i st.size(); i) {if(s[i] )) a;if(s[i] () b;}int c min(a, b) (max(a, b) - min(a, b)) / 2;coutc;return 0;
}找到问题了第2324行应该用st[i]代替s[i]无奈栈没有这种用法应该改用st.top(), st.pop()来操作 栈 AC 100%
#includeiostream
#includestack //st.push(), st.pop(), st.top()
using namespace std;
string s;
int main()
{stackcharst;cins;for(int i 0; i s.size(); i) {if(st.size() 0)st.push(s[i]); //元素不足2个else if(st.size() 1) {if(st.top() ( s[i] )) {st.pop(); //如果栈顶元素和新的元素匹配}elsest.push(s[i]); //不匹配就把新的元素入栈}}//分类讨论int a 0, b 0;while(!st.empty()) {if(st.top() )) {a;st.pop();}else if(st.top() () {b;st.pop();}}int c;if(a % 2 1) c 2 (a b - 2) / 2;else c (a b) / 2;coutc;return 0;
}常犯错误了栈就要用栈的表达不要老想着什么st[i]日后多多复盘 #includestack
int main()
{stackcharst;st.push();st.top();st.pop();if(!st.empty())......return 0;
}
前缀和 AC 100% 说实话怎么用前缀和我没想清楚不过你可以用))((, ((((, ))))三个例子去模拟以下就知道了 #includeiostream
using namespace std;
string s;
int main()
{cins;int m 0, n 0;for(int i 0; i s.size(); i) {if(s[i] () m;else m--;if(m -1) {n;m 1;}}coutn m / 2;return 0;
}五P1147 连续自然数和
P1147 连续自然数和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签普及-前缀和双指针 真的就前缀和 双指针 AC 56% 最后三个样例TLE(Time Limit Exceeded)超时了 想法是把第89行代码去掉放到第二部分里算前缀和这样就少一个O(n)的复杂度 毕竟题目是2e6的数据 #includeiostream
using namespace std;
int s[10010];
int main()
{int n, i, j;cinn;for(i 1; i 10010; i)s[i] i s[i - 1]; //前缀和for(i 0, j 2; i n / 2;) {if(s[j] - s[i] n) {couti 1 jendl;i; //漏了会无限循环}if(s[j] - s[i] n) //尺取法i; //左指针if(s[j] - s[i] n)j; //右指针}return 0;
}我们用sum代替前缀和的差值注意 sum j 和 sum - i 与 j 和 i 的相对位置关系 AC 100%
#includeiostream
using namespace std;
int s[10010];
int main()
{int n, i, j, sum 3;cinn;for(i 0, j 2; i n / 2;) {if(sum n) {couti jendl;sum - i;i; //漏了会无限循环}if(sum n) {//尺取法sum - i;i; //左指针}if(sum n) {j; //右指针sum j;}}return 0;
}二差分 自在的少年 - 要不要买菜 - 单曲 - 网易云音乐
→ 差分算法介绍_木木夕夕山的博客-CSDN博客_差分算法
→ (1条消息) 算法笔记六差分法_G鸦青的博客-CSDN博客_差分法
→ 前缀和 差分 - OI Wiki (oi-wiki.org)
→ 前缀和、二维前缀和与差分的模板小总结 - AcWing
概以括之
差分是前缀和的逆运算假设有两个数组a[], b[]数组a是数组b的前缀和
即a[i] b[1] b[2] ... b[i]那么数组b就是a的差分数组
差分算法有什么用呢比如给定数组a有n个元素要求在[left, right]上每个元素 c这时你可能会想遍历一次加c不就好了可是这样时间复杂度达到O(n)而采用差分只有O(1)的复杂度
如果进行m次区间[left, right] c 或 -c 的操作呢这时遍历m次的复杂度为O(nm)而差分只需O(m)
在数据量达到1e5的情况下直接遍历会TLE对于OI赛制只能拿到10%~50%的分ACM赛制0分
所以学习差分还是有必要的
具体操作
给定数组an个元素我们创建数组b为数组a的差分数组
令b[i] a[i] - a[i - 1]因为a是b的前缀和数组
模板
#includeiostream
using namespace std;
int n;
int a[10010], b[10010];
//插入函数
void insert(int l, int r, int c)
{b[l] c;b[r 1] - c;
}
int main()
{cinn;//输入数据for(int i 1; i n; i)cina[i];//差分后的数组bfor(int i 1; i n; i)insert(i, i, a[i]);//执行操作int l, r, c;cinlrc;insert(l, r, c);//输出操作后数组for(int i 1; i n; i) {b[i] b[i - 1]; //前缀和coutb[i] ;}return 0;
}执行m次只需在“执行操作”那里加个while(m--)不过我更习惯while(m){ ......m--; } 8
1 2 3 4 5 6 7 8
2 5 3
1 5 6 7 8 6 7 8
先记套路你可以假设1 3 5 7的数组a经过insert()函数后得到的数组b就是1 2 2 2数组b的前缀和就是原来的数组a
一AcWing 3729. 改变数组元素
3729. 改变数组元素 - AcWing题库
标签中等差分区间合并 题目没给初始数组所以我们只需要差分数组b 第二是我们假定初始长度就为n用一个for(int i 1; i n; i)循环遍历1~n 如果输入的x大于等于当前的长度 i 就对所有元素执行insert操作 如果输入的x小于 i 只需要insert(i - x 1, i)i 表示最后一个元素 #includeiostream
#includecstdio //scanf(), printf()
#includecstring //memset()
using namespace std;
int b[200010]; //题目中没有给定初始数组所以不需要数组a
void insert(int l, int r)
{b[l] 1;b[r 1] - 1; //套路
}
int main()
{int t, n;scanf(%d, t);while(t) {scanf(%d, n);memset(b, 0, sizeof(b)); //初始化//执行操作for(int i 1; i n; i) {int x;scanf(%d, x); //每输入一个数, 就操作一次if(x 0) continue; //跳过本次else if(x i) insert(1, i); //全部操作一次else insert(i 1 - x, i);}for(int i 1; i n; i)b[i] b[i - 1]; //前缀和得到操作后的数组for(int i 1; i n; i) {if(b[i] 1) printf(%d , b[i]);else printf(1 ); //如果大于1就输出1}printf(\n);t--;}return 0;
}二P2367 语文成绩
P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签普及/提高- 这是一道最简单模板题不需要变形直接套模板就能AC 不开O2优化就AC 80%开了AC 100% 能直接套模板的题基本一次过而且耗时才几分钟 #includeiostream
#includecstdio //scanf(), printf()
using namespace std;
int a[5000010], b[1000010];
void insert(int l, int r, int c)
{b[l] c;b[r 1] - c; //模板
}
int main()
{int n, p;scanf(%d%d, n, p);for(int i 1; i n; i)scanf(%d, a[i]); //初始分数for(int i 1; i n; i)insert(i, i, a[i]); //逆前缀和while(p) { //p次操作int l, r, c;scanf(%d%d%d, l, r, c);insert(l, r, c);p--;}for(int i 1; i n; i)b[i] b[i - 1]; //前缀和int Min 1e9;for(int i 1; i n; i)Min min(Min, b[i]); //找最小值printf(%d, Min);return 0;
}三P8772 [蓝桥杯 2022 省 A] 求和
P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签普及-前缀和差分 虽然标签有差分但我觉得它只考了前缀和 temp 数组a[i]的前缀和然后用a[i] * temp。暴力的话只能AC 70% temp a[1], sum a[2] * a[1]
temp a[1] a[2], sum a[3] * (a[1] a[2])
temp a[1] a[2] a[3], sum a[4] * (a[1] a[2] a[3])
......
#includeiostream
using namespace std;
int a[200010];
int main()
{int n;cinn;for(int i 1; i n; i)cina[i];long long sum 0, temp a[1];for(int i 2; i n; i) {sum temp * a[i];temp a[i];}coutsum;return 0;
}三二分 活着 - 郝云 - 单曲 - 网易云音乐
→ 二分算法学习_码龄?天的博客-CSDN博客
→ OI Wiki - OI Wiki (oi-wiki.org)
模板
int binary_search(int left, int right, int key)
{int ret -1; //未搜索到数据返回-1下标int mid;while(left right) {mid left ((right - left) 1); //避免溢出,用该算法if(key a[mid]) left mid 1;else if(key a[mid]) right mid - 1;else { //最后检测相等ret mid;break;}}return ret; //单一出口
} 要用二分算法首先判断 1能不能用 即是不是一个有序数组这里的“有序”是广义的有序也就是一个数组中某个点左侧或右侧都满足某一条件而另一侧不满足 2其次判断左右边界是什么 一1460. 我在哪
1460. 我在哪 - AcWing题库
标签简单二分哈希 原文是“最小的K值使任意连续K个唯一”比如样例ABCDABC中有人问为什么CD确定不了2呢因为任意2个里面包含AB而AB的位置显然不是唯一的3个的话也存在ABC重复所以只能4个 方法一二分 哈希 但是我不会哈希想了半小时只用二分没结果 方法二利用set中元素不重复的特点但是没想明白怎么做 方法三考虑到数据量不大还是暴力 s.substr() s.find() (9条消息) C中s.find()和s.rfind()的用法_暖风有凉意的博客-CSDN博客_s.find 1s.find(str)或s.find(str, pos)要与 ! string::npos连用最后没有找到子串的话会返回 string::npos 2s.substr(i)从下标 i 开始到结尾s.substr(i, j)从下标 i 开始截取 j 个字符 string s1 s.substr(j, i);
if(s.find(s1, j 1) string::npos)
//没有找到子串, 返回string::nposif(s.find(s1, j 1) ! string::npos)
//找到子串
#includeiostream
#includecstring //s.substr(), s.find()
using namespace std;
int main()
{int n;cinn;string s;cins;for(int i 1; i n; i) { //i表示截取长度int flag 1;for(int j 0; j n - i; j) { //j为截取起始坐标string s1 s.substr(j, i); //下标j开始截取i个字符if(s.find(s1, j 1) ! string::npos) //j 1flag 0;}if(flag) {couti;break;}}return 0;
}四 就是我 - 林俊杰 - 单曲 - 网易云音乐
五 菲菲 - 沈以诚 - 单曲 - 网易云音乐 六
七
八
九
十
十一
十二
十三
十四
十五
十六
十七
十八
十九
二十
二十一
二十二
二十三
二十四
二十五
二十六
二十七
二十八
二十九
三十
