投稿
  1. 首页
  2. C

蓝桥杯要背的板子哦（基础版）

code • 2022-4-9 • C • 阅读 46

蓝桥杯要背的板子哦（基础版）,第1张

  • 优先队列
  • 结构体排序
  • 求最大公因数
  • 求最小公倍数
  • 等差等比数列求和
  • 闰年
  • 打表freopen()
  • 读取一行内容
    • 当一行中有多个字符串
    • cin.get()和cin.getline()
  • 单位换算
  • k进制分解
  • 质因数分解
  • 二分板子
  • 快速幂板子
  • 线段树板子
  • 树状数组板子
  • 前缀和板子
  • 差分板子
  • kruskal板子
  • prim板子
  • dp板子
    • 线性dp
    • 01背包
  • dijstra板子
  • floyd板子
  • 杂

优先队列 
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数
//（就是使一个类的使用看上去像一个函数。


//其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

push()　　　　压入栈中
pop() 　　　　d出栈顶元素
top() 　　　　队列中第一个元素
empty() 　　 如果队列为空，则返回真

结构体排序

这个是放在struct里面的进行结构体排序比较的

bool operator<(const tmp& a) const
    {
        return x < a.x;
       //大顶堆，如果是priority_queue，则是最大的数，在前面，若是数组，则是升序的
    }

也可以在外面设置一个cmp的bool型函数，这样子就是升序哦

bool cmp(node x,node y)
{
    return x.l <y.l ;
}
求最大公因数 
ll gcd(ll a, ll b)   //求最大公因数
{
	return a % b == 0 ? b : gcd(b, a % b);
}
求最小公倍数 
ll lcm(ll a, ll b)	//求最小公倍数
{
	return a * b / gcd(a, b);
}
等差等比数列求和 
等差数列{an}的通项公式为：an=a1+(n-1)d。

前n项和公式为：Sn=n*a1+n(n-1)d/2或Sn=n(a1+an)/2 。


等比数列{an}求和公式：Sn=na1(q=1)，Sn=[a1(1-q)^n]/(1-q)（q≠1）
闰年

闰年的计算方法：
1、非整百年：能被4整除的为闰年。


（如2004年为闰年，2001年就不是闰年）
2、整百年：能被400整除的为闰年。


（如2000年为闰年，1900年不是闰年）

if(y%4==0&&y%100!=0||y%400==0) {
		
		cout<<“YES”;
	}
打表freopen()

所在文件： 

#include 
#include 
int main()
{ 
	int a,b; 
	freopen("D:\in.txt","r",stdin); //输入重定向，输入数据将从D盘根目录下的in.txt文件中读取 
	freopen("D:\out.txt","w",stdout); //输出重定向，输出数据将保存在D盘根目录下的out.txt文件中 
	while(cin>>a>>b) 
	cout<<a+b<<endl; // 注意使用endl 
	fclose(stdin);//关闭重定向输入
	fclose(stdout);//关闭重定向输出 
	return 0; 
}
读取一行内容 当一行中有多个字符串 
while(getline(cin,line))
	{
		string x;
		flag1++;
		flag2=0;
		stringstream ss(line);
		while(ss>>x)
		{
			cout<<x<<' ';
			flag2++;
			t[flag1][flag2]=x;
		}
		cout<<endl;
	}
cin.get()和cin.getline()

这个总结我觉得总结的很好

#include

using namespace std;

int main()
{

    cout << "----------getline忽略'\n-----------------" << endl;
    char str0[30], str1[30];
    cin.getline(str0, 30);
    cin.getline(str1, 30);
    cout << "str0:" << str0 << endl;
    cout << "str1:" << str1 << endl;

    cout << "---------利用get()消除get()遗留下来的'\n'-------" << endl;
    char str2[30], str3[30];
    cin.get(str2, 30).get();   // 注意这里！
    cin.get(str3, 30).get();
    cout << "str1: " << str2 << endl;
    cout << "str2: " << str3 << endl;

    cout << "--------没消除get()遗留下来的'\n'就被下一个get()读取了，所以str5输出为空-----" << endl;
    char str4[30], str5[30];
    cin.get(str4, 30);   // 注意这里！
    cin.get(str5, 30);
    cout << "str4: " << str4 << endl;
    cout << "str5: " << str5 << endl;
    return 0;

}
单位换算

k进制分解 
// 返回x的k进制表示
vector<int> Split(int x, int k) {
  vector<int> ret;

  if (x == 0) { // 如果输入数据就是0那么需要返回一个单独的0数字
    ret.push_back(0);
    return ret;
  }
  while (x > 0) {
    ret.push_back(x % k);
    x /= k;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
质因数分解 
// 返回x的质因数分解结果，每一个pair的第一个元素为质因数p，第二个元素为指数a。


vector<pair<int, int> > GetPrimeFactor(int x) {
  vector<pair<int, int> > ret;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) {
        cnt++;
        x /= i;
      }
      // x的质因子i出现了cnt次
      ret.push_back(make_pair(i, cnt));
    }
  }
  if (x > 1) {
    ret.push_back(make_pair(x, 1));
  }
  return ret;
}

// 打印结果
void PrintAns(int x, const vector<pair<int, int>> ans) {
  printf("%d = ", x);
  for (int i = 0; i < ans.size(); i++) {
    if (i != 0) {
      printf(" + ");
    }
    printf("%d^%d", ans[i].first, ans[i].second);
  }
  printf("\n");
}

可以试着去玩玩的一波代码！

#include

using namespace std;
// 返回x的质因数分解结果，每一个pair的第一个元素为质因数p，第二个元素为指数a。


vector<pair<int, int> > GetPrimeFactor(int x) {
  vector<pair<int, int> > ret;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      int cnt = 0;
      while (x % i == 0) {
        cnt++;
        x /= i;
      }
      // x的质因子i出现了cnt次
      ret.push_back(make_pair(i, cnt));
    }
  }
  if (x > 1) {
    ret.push_back(make_pair(x, 1));
  }
  return ret;
}

// 打印结果
void PrintAns(int x, const vector<pair<int, int>> ans) {
  printf("%d = ", x);
  for (int i = 0; i < ans.size(); i++) {
    if (i != 0) {
      printf(" + ");
    }
    printf("%d^%d", ans[i].first, ans[i].second);
  }
  printf("\n");
}


int main()
{
    vector<pair<int, int> >a;
    a=GetPrimeFactor(57);
    PrintAns(57,a);
    return 0;
}

二分板子

①

while(l<r)
{
    int mid=l+r>>1;
    if(check(mid)>=x)r=mid;
    else l=mid+1;
}

②


while(l<r)
{
    int mid=l+r+1>>1;
    if(check(mid)<=x)l=mid;
    else r=mid-1;
}
快速幂板子 
long long fastPower(long long base, long long power) {
    long long result = 1;
    while (power > 0) 
    {
        if (power & 1) 
            result = result * base % 1000;
        power >>= 1;
        base = (base * base) % 1000;
    }
    return result;
}
线段树板子 
#include 
using namespace std;

const int N=100010;
int n,m;
int w[N];
struct node{
    int l,r;
    int sum;
}tr[N*4];

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,w[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;
    if(l<=mid)sum=query(u<<1,l,r);
    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].r+tr[u].l >>1;
        if(x<=mid)modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
    	pushup(u);
           }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    build(1,1,n);
    int k,a,b;
    while(m--)
    {
        scanf("%d%d%d",&k,&a,&b);
        if(k==0)
        printf("%d\n",query(1,a,b));
        else modify(1,a,b);
    }
    return 0;
}
树状数组板子 
//树状数组
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=v;
}
int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=tr[i];
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        add(i,a[i]);
    while(m--)
    {
        int k,x,y;
        ....
    }
    
    
    
    
    return 0;
}
前缀和板子 
int a[N];//代表原数组
int s[N];//代表前缀和数组

s[i]=s[i-1]+s[i];
s[r]-s[l-1];//这个是a[l]~a[r]的和
差分板子 
int a[N];//原数组
int b[N];//差分数组

void insert(int l,int r,int k)
{
    b[l]+=k;
    b[r+1]-=k;
}


int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)//前缀和和差分的下标都要从1开始
    {
        cin>>a[i];
        insert(i,i,a[i]);
    }
    while(m--)
    {
        int l,r,w;
        cin>>l>>r>>w;
        insert(l,r,w);
    }
    for(int i=1;i<=n;i++)
  {
        b[i]+=b[i-1];//还原成原数组了！
        printf("%d ",b[i]);
  }
    
    
    return 0;
}
kruskal板子 prim板子 dp板子 线性dp 
dp[1]=a[1];
dp[0]=0;	
for(int i=1;i<=n;i++){
  dp[i]=max(dp[i-1]+a[i],a[i]);	
  sum=max(dp[i], sum);
｝
01背包 
 for(int i=1;i<=M;i++){
        scanf("%d %d",&t[i],&a[i]);
        for(int j=T;j>=t[i];j--){
            f[j]=max(f[j],f[j-t[i]]+a[i]);
        }
    }
dijstra板子 
const ll inf =1e12;
//最短路径模板 dijstra算法
fill(dis,dis+2050,inf);//一维数组
fill(e[0],e[0]+2050*2050;inf);//二维数组

for(int i=1;i<=x;i++)
    for(int j=1;;j<=y;j++)
{
    int k=i+j;
    e[i][k]=e[k][j]=w;//赋予他们的长度
}
//求1到2021最短距离
dis[1]=0;
for(int i=1;i<=2021;i++)
{
    ll u=-1,minn=inf;
    for(int j=1;j<=2021;j++)//找到起点
    {
        if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j];//找到dis数组中最小的下标
                u=j;
            }
    }
    if(u==-1)//说明没有找到起点
        break;
    vis[u]=1;
    for(int v=1;v<=2021;v++)
    {
        if(!vis[v])
            dis[v]=min(dis[v],e[u][v]+dis[u]);
    }
}
cout<<dis[2021];
floyd板子 杂

1、基本输入输出语法：
(1)如cin速度比scanf慢 两者遇到空格回车会停止读入
(2)若想读整行需要cin.getline()或gets函数
(3)读到文件尾用scanf()!=EOF等等
(4)占位符‘%’相关格式，如对齐方式，补0等。



2、C/C++库函数以及stl模板
(1)algorithm: sort next_permutation lower_bound/upper_bound
(2)queue(priority_queue) stack vector set map基本 *** 作等
3、数据结构
(1)结构体：注意结构体用sort排序，可自定义cmp函数，也可在结构体内重载“<”运算符。



(2)字符串：string类的使用、字典树（用于求解前缀和后缀问题）。



(3)栈、队列：前缀、后缀表达式计算等。



(4)图：两种表示方法，邻接表和邻接矩阵，当n较大时只能采用邻接表。



(5)树：树是一种特殊的图。


如按层输出节点等
(6)线段树：基本的单点修改、区间修改、区间查询等。



4、算法
(1)暴力：蓝桥杯又称暴力杯，n<=1e3(1000)， O ( n 2 ) O(n^2) O(n2)的代码大概率能解，如果1e4<=n<=1e6，则要考虑O(n*logn)的算法，不过蓝桥按测试点得分，实在不会，可用 O ( n 2 ) O(n^2) O(n2)骗分，骗到了就是赚到了。



(2)思维：不涉及算法，不涉及复杂数据结构，往往几行代码就可以解决，考验思维能力，多训练此类题目即可。



(3)模拟：模拟指根据题目描述，按部就班的写代码就可以AC，通常思路容易看出但是代码量较大，考验细节与心态。



①大数加减法
②进制转换
(4)数学问题：
①质数相关：埃式筛、欧拉筛、唯一分解定理等。



②求最大公因数：要自己会写gcd函数（欧几里得算法）
③快速幂模板，矩阵快速幂模板
④慢速乘模板（防止相乘的时候数太大爆掉long long）
(5)贪心
(6)动态规划：
①最长公共子序列
②最长上升/不下降子序列
③背包问题（01背包、多重背包、完全背包等）
④前缀和问题（一维/二维前缀和）
(7)搜索：搜索基本是必考的点，包括DFS/BFS，可分别用栈和队列模拟。


记忆化搜索也是常考的点，用于避免重复搜索。



(8)图论：
①最短路：最基本要掌握两种求法，floyd算法和dijkstra算法。


前者O(n^3)，适用于n不大于500的情况。


后者dijkstra用的较多，数据结构实现有两种，邻接矩阵与邻接表，建议用邻接表（具体实现啊哈算法上有）。



②最小生成树：kruscal算法和prim算法
③拓扑排序
(9)字符串：回文、kmp算法（字符串匹配算法）
(10)其他：并查集、二分/三分算法等

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/568449.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表（0条）

保存