网站建设最流行语言,电商系统功能模块,苏州公司网站建设服务,网站的推广方式包括今天继续整理一些关于算法竞赛中C适用的一些模板以及思想。
保留x位小数
保留x位小数在C语言中可以使用printf中的%.xf来实现#xff0c;但是很多C选手由于关闭了同步流#xff0c;害怕cin、cout与scanf、printf混用容易出错#xff0c;所以就给大家介绍一个强…今天继续整理一些关于算法竞赛中C适用的一些模板以及思想。
保留x位小数
保留x位小数在C语言中可以使用printf中的%.xf来实现但是很多C选手由于关闭了同步流害怕cin、cout与scanf、printf混用容易出错所以就给大家介绍一个强制保留x位小数的代码格式。
coutfixedsetprecision(x)浮点型变量;
其中的x可以根据题目中的要求更改接下来看一道例题来对这个函数加深印象。
排队接水
题目链接排队接水
排队接水问题是一个非常典型的贪心问题其中贪心的过程就不过多赘述了原则就是前面的人消耗的时间越多后面所有人等待的时间就越多所以要让耗时小的人在前面这样来构成全局最优解。可以试想一下同样是两个人其中一个人需要1小时另一个人需要10分钟如果让耗时多的人先接水的话总时间就是这个人的耗时 后面的人等待其接水的耗时 后面的人的耗时所以要对耗时进行排序根据贪心原则让耗时少的人先接水。
// Problem: P1223 排队接水
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1223
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;void solve()
{int n;cinn;vectorpii a(n1);for(int i1;in;i){cina[i].fi;a[i].se i;}sort(a.begin()1,a.end());//贪心double sum 0,ans0;for(int i1;in;i){couta[i].se ;if(in) break;//因为求的是等待时间 最后一个人不算sum a[i].fi;ans sum;}coutendl;//保留2位小数!coutfixedsetprecision(2)ans/n;
}signed main()// Dont forget pre_handle!
{IOSint T1;
// cinT;while(T--) solve(); return 0;
} 最长上升子序列
最长上升子序列是dp的一类入门题目我在前面的博客中有做过对一些常见的线性DP的题型、用法以及模板内容的介绍对这一块不熟悉的小伙伴可以去看一下线性DP对于最长上升子序列如果求的是长度可以用遍历 二分的方式降低时间复杂度而如果是需要求出具体的以每一个元素结尾的长度的话就需要用到双重循环来解决了当然也可以用时间复杂度更低的单调队列来解决单调队列我也有过总结感兴趣的小伙伴也可以去看一下总结的模板入门推广 具体情况视题目而定接下来看一道相关的题目。
合唱队形
这道题用到了正向和逆向双向相结合的思路这种思想特别重要很多像单调栈、最长子段和之类的题目也会用到这样的思想对于这道题而言我们需要正向用一遍最长上升子序列求出以每个点结尾的最长上升子序列的长度然后逆向再跑一遍求出以每个元素开头的最长下降子序列的长度然后再遍历一遍每个元素求出最大值就是一共可以留下来的人数题目中要求的移除的人数只需用总人数减去留下的人数即可得出。
// Problem: P1091 [NOIP 2004 提高组] 合唱队形
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1091
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;void solve()
{int n;cinn;vectorint a(n1);for(int i1;in;i) cina[i];int l[n1],r[n1];// for(int i1;in;i) l[i] 1,r[i] 1;fill(l1,l1n,1);fill(r1,r1n,1);for(int i2;in;i)//正序最长上升子序列{for(int j1;ji;j)if(a[j] a[i]) l[i] max(l[i],l[j] 1);}for(int in-1;i1;i--)//逆序最长上升子序列正序最长下降子序列{for(int jn;ji;j--)if(a[j] a[i]) r[i] max(r[i],r[j] 1);}int mx -inf;for(int i1;in;i){mx max(mx,r[i] l[i] - 1);//减去重复计算的自己}coutn - mxendl;
}signed main()// Dont forget pre_handle!
{IOSint T1;
// cinT;while(T--) solve(); return 0;
} 归并排序
相信部分C选手对排序并不感兴趣因为STL中有自带的搞笑的sort排序在nlogn的时间复杂度下满足了很多场景的需要但是归并排序的时间复杂度也是nlogn而且有很多题型都用到了类似于归并排序中的分治思想即将大问题转化为很多个小问题然后通过对小问题的高效解决来使得总问题的解决的思想其中较为典型的就是逆序对问题这个问题就是在归并排序的合并过程中完成的下面来回顾一下归并排序的代码以及对逆序对这一问题的高效求解。
逆序对
题目链接逆序对
我们对逆序对的寻找不需要每次都遍历计数而是可以先将集合分为两个部分而这两个部分又是有序的两个集合我们可以对两个集合的元素进行比较大小的同时用O(1)的方法计算逆序对的数量在合并的过程中如果左边的集合中的元素小直接将左边这个元素合并上去反之如果左边的元素大就应该将右边的元素合并上去而此时左边剩余元素的数量就是以右边的这个较小的数位第二个数的逆序对的数量所以能在归并排序合并过程的同时就将逆序对的数量进行统计了。代码如下所示
// Problem: P1908 逆序对
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1908
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;
const int N 5e510;
vectorint a(N,0),b(N,0);
int res0;
void gb_sort(int l,int r)
{if(l r) return ;int mid (l r) 1;gb_sort(l,mid);gb_sort(mid1,r);//分治过程int il,jmid1,kl;//分治过程while(i mid j r)//归并过程{if(a[i] a[j]) b[k] a[i];else b[k] a[j],res mid - i 1;}while(i mid) b[k] a[i];//对剩余元素的处理while(j r) b[k] a[j];//对剩余元素的处理for(int il;ir;i) a[i] b[i];//将排序后的数组保存
}
void solve()
{int n;cinn;for(int i1;in;i) cina[i];gb_sort(1,n);// for(int i1;in;i) couta[i] ;coutresendl;
}signed main()// Dont forget pre_handle!
{IOSint T1;
// cinT;while(T--) solve(); return 0;
} 高精度运算
C/C选手的痛在蓝桥杯等一些赛事中经常出现高精度和低精度之间的混合运算比较简单正常模拟即可我也有过总结需要的小伙伴可以去主页拿。这里主要整理高精度乘高精度下的快速幂。
麦森数
题目链接麦森数
这道题的数据范围比较大不仅仅用到了高精度✖️高精度还需要用快速幂来优化因为是2的n次方所以就要想到了以2位初始值的快速幂又因为数太大了光看样例就已经很恐怖了所以就又想到了高精度这时候整体的代码思路就出来了实现起来也不难整理这道题的主要原因就是便于对之后的快速幂以及高精度算法模板的需要有需要的小伙伴也可以保存起来以后备用。
// Problem: P1045 [NOIP 2003 普及组] 麦森数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1045
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;
const int N 505;
vectorint a(N,0),res(N,0);
void gjc_begin()
{int t0,c0;vectorint temp(1010,0);for(int i1;i500;i){for(int j1;j500;j) temp[ij-1] a[i] * a[j];}for(int i1;i500;i){temp[i] t;a[i] temp[i] % 10;t temp[i] / 10;}
}
void gjc_end()
{int t0,c0;vectorint temp(1010,0);for(int i1;i500;i){for(int j1;j500;j) temp[ij-1] res[i] * a[j];}for(int i1;i500;i){temp[i] t;res[i] temp[i] % 10;t temp[i] / 10;}
}
void ksm_plus(int x)
{while(x){if(x1) gjc_end();gjc_begin();x 1;}
}
void solve()
{int n;cinn;a[1] 2,res[1] 1;//快速幂的初始值位2 因为要求的是2的次方ksm_plus(n);int num0;//数学公式直接计算2^n的位数cout(int)(n*log10(2) 1)endl;int cnt0;int t 1;while(res[t] 0)//对最后的 -1 操作进行计算{res[t] 9;t;}res[t]--;for(int i500;i0;i--){coutres[i];cnt;if(cnt 50){coutendl;cnt 0;}}
}signed main()// Dont forget pre_handle!
{IOSint T1;
// cinT;while(T--) solve(); return 0;
} 求位数的高效方法
求x的位数相信很很堵人都会了用 (int)log10(x) 1即可也可转为字符串求长度。
这道题还需要用到的数学知识就是2的n次方的位数如果用模拟法计算的话还需要用到高精度算法而如果使用数学方法的话就很方便了而且时间复杂度也不高具体实现公式为
(int)(n*log10(2) 1)
倍增法
倍增法也是一个常用的算法其中在求最近共同祖先的时候最为有用可以将每次的O(N)时间复杂度的查询压缩至单次O(logN)的时间复杂度适用于多次查询最近共同祖先(LCA)的情况具体思路如下其中数组f[n][m]表示n的第2^m级祖先 最重要的是在dfs求深度时对倍增ST表进行预处理 图中左侧位预处理阶段右侧为查询LCA阶段。
LCA最近共同祖先
题目链接LCA最近共同祖先【模板】
为了方便之后对这一块模板代码的内容进行整理所以我在这里用一个模版题来对倍增法求LCA做一个记录如果之后有需要的话可以参考这个模板。
// Problem: P3379 【模板】最近公共祖先LCA
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3379
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f;
const int N 500010;
int n,m,s;
vectorint a[N];
int dep[N],fu[N][30];
void dfs(int x,int fa)//深搜预处理阶段
{dep[x] dep[fa] 1;fu[x][0] fa;for(int i1;i30;i) fu[x][i] fu[fu[x][i-1]][i-1];//祖先预处理阶段for(auto i : a[x]){if(i fa) continue;//无向边所以都存防止重复访问父节点dfs(i,x);}
}
int LCA(int x,int y)
{if(dep[x] dep[y]) swap(x,y);while(dep[x] dep[y]) x fu[x][(int)log2(dep[x] - dep[y])];//先移动到同一层if(x y) return x;//移动到同一层就重合了说明这个就是祖先了for(int ilog2(dep[x]);i0;i--)//根据二进制2的幂次方分解找到LCA的下一层子节点{if(fu[x][i] ! fu[y][i])是共同祖先但是要保证是最近的所以在没找到时才更新{x fu[x][i];y fu[y][i];}}return fu[x][0];//这一层的上一层就是LCA
}
void solve()
{cinnms;for(int i1;in;i){int u,v; cinuv;a[u].push_back(v);a[v].push_back(u);}dfs(s,0);while(m--){int x,y;cinxy;coutLCA(x,y)endl;}
// coutfixedsetprecision(x) ;
}signed main()// Dont forget pre_handle!
{IOSint T1;
// cinT;while(T--) solve(); return 0;
} [eJOI 2020] Fountain (Day1)
题目链接[eJOI 2020] Fountain (Day1)
这道题是很好的一道题他不仅仅考察了对倍增的运用而且还考察了单调栈。废话不多说接下来就来看一下这道题的详细解析。 首先看到这到题第一反应就是从这个位置开始一直找后面的比当前元素要大的位置然后不断的更新value最后到哪一个地方value小于或等于这里的盘子了就说明找到最终的答案了但是每次都遍历所有的点就会超时那么我们就开始想怎么去优化我们首先可以想到用单调栈来记录每一个元素下边的第一个大于他的元素等于不行!这样就不用每次都从当前点来事遍历找第一个大于他的点了只需要O(n)的复杂度就能处理完这一操作但是这就完了吗交上去发现只有30分还能怎么优化呢我们想既然有了单调性的话能不能用二分可是二分还需要知道每一段的容量也不好求我们既然是从当前开始一直找到下一个大于当前的点那我们是否可以跳着找呢跳着找第2的幂次方个大于他的盘子用倍增ST表来解决呢灵感来源于 所以我们可以先用单调栈因为是右边第一个大于他的元素所以用逆序遍历的单调递减栈来实现对单调栈这一方面不熟悉的小伙伴可以去看我的单调栈知识点的总结单调栈详解来处理每一段单调递增的盘子然后将他们建树这样就可以用倍增法来实现跳着找了。
将建起来大概是这样相信大家能够更形象地理解 代码如下
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pii pairint,int
#define fi first
#define se second
const int inf 0x3f3f3f3f3f3f3f3f; // 无穷大
const int N 1e5 10;
// 定义各数组和变量
vectorint a(N,0),v(N,0),r(N,0); // a存储直径v存储容量r存储右侧第一个大于当前直径的喷泉编号
stackint st; // 单调栈
int n,m; // n个喷泉m次查询
vectorint e[N]; // 邻接表存储树结构
vectorint dep(N,0); // 存储每个节点的深度
int fu[N][30],g[N][30]; // fu[i][j]表示i节点向上2^j层的祖先g[i][j]表示i节点向上2^j层的容量和// DFS预处理倍增数组
void dfs(int x,int fa)
{dep[x] dep[fa] 1; // 计算当前节点深度fu[x][0] fa,g[x][0] v[fa]; // 初始化直接父节点和容量// 预处理倍增数组for(int i1;i30;i) {fu[x][i] fu[fu[x][i-1]][i-1];// 计算祖先g[x][i] g[fu[x][i-1]][i-1] g[x][i-1];// 计算容量和}// 递归处理子节点for(auto i : e[x]) dfs(i,x);
}
void solve()
{cinnm;// 设置哨兵节点a[n1] inf,v[n1] inf; // 第n1个喷泉作为边界// 输入每个喷泉的直径和容量for(int i1;in;i) cin a[i] v[i];// 单调栈处理找到每个喷泉右侧第一个直径大于它的喷泉for(int in;i1;i--){// 维护单调递减栈while(!st.empty() a[st.top()] a[i]) st.pop();// 如果栈空则指向哨兵否则指向栈顶r[i] (st.empty() ? n1 : st.top());st.push(i); // 当前喷泉入栈} // 构建树结构for(int in;i1;i--) e[r[i]].push_back(i);// 从哨兵节点开始DFS预处理dfs(n1,0);// 处理查询for(int i1;im;i){int index,value; cinindexvalue;// 如果当前喷泉容量足够if(v[index] value){coutindexendl;continue;}// 否则减去当前喷泉的容量value - v[index];int xindex;int ans0;// 倍增查找能容纳剩余水量的最低祖先for(int i25;i0;i--){if(g[x][i] value (1LLi) dep[x]){value - g[x][i];x fu[x][i];}if(value 0) ans x;}// 如果还有剩余水量再向上走一步if(ans 0) ans fu[x][0];// 输出结果如果是哨兵则输出0if(ans n1) cout0endl;else coutansendl;}
}signed main()
{IOS // 加速输入输出int T1;while(T--) solve(); return 0;
}
之后的算法思维以及解题方法总结都会在本文进行更新有兴趣对这一块内容进行整理的小伙伴可以保存起来。
