蓝桥杯备战一个月多了。总结一些知识点。因为蓝桥杯不像ACM那样可以带资料。所以只能在考前把这些资料背下来了(QAQ)。
1.sort的用法
sort（数组名，数组长度）。
sort默认是降序排序，如果要升序排序，可以这样写
sort(f,f+len,greater<int>());2.大数加法
#include<bits/stdc++.h>
using namespace std;char a[10000],b[10000];
int main()
{int i,s1,s2;while(scanf("%s%s",a,b)!=EOF){s1 = strlen(a);s2 = strlen(b);reverse(a,a+s1);reverse(b,b+s2);if(s2>s1)s1 = s2;for(i=0;i<s1;i++){if(b[i]==0) b[i]='0';if(a[i]==0) a[i]='0';a[i] = a[i] + b[i] -'0';if(a[i]>=58){a[i] -= 10;a[i+1]++;if(a[i+1]==1) {a[i+1]='1';}}}s2=strlen(a);reverse(a,a+s2);printf("%s\n",a);memset(a,0,sizeof(a));memset(b,0,sizeof(b));}return 0;
}3.大数乘法
#include<iostream>
#include<cstring>
using namespace std;
char a1[50001],b1[50001];
int a[50001],b[50001],i,x,len,j,c[50001];
int main ()
{cin >>a1 >>b1;//读入两个数a[0]=strlen(a1);b[0]=strlen(b1);//计算长度for (i=1;i<=a[0];++i)a[i]=a1[a[0]-i]-'0';//将字符串转换成数字for (i=1;i<=b[0];++i)b[i]=b1[b[0]-i]-'0';for (i=1;i<=a[0];++i)for (j=1;j<=b[0];++j)c[i+j-1]+=a[i]*b[j];//按乘法len=a[0]+b[0]; //原理进行高精乘for (i=1;i<len;++i)if (c[i]>9){c[i+1]+=c[i]/10;c[i]%=10;}//进位while (c[len]==0&&len>1)len--;//判断位数for (i=len;i>=1;--i)cout <<c[i];//输出return 0;
}4.大数除法
#include<string>
#include<iostream>
using namespace std;
string a,c;
int b,i,d;
int main()
{cin>>a>>b; //神奇的读入for (;i<a.length();i++)a[i]-=48; //字符串转数字for (i=0;i<a.length();i++)c.push_back((d*10+a[i])/b+48),d=(d*10+a[i])%b; //模拟竖式for (i=0;c[0]==48;i++)c.erase(c.begin(),c.begin()+1); //去0cout<<c; //华丽的输出return 0; //完美的结束
}5.大数减法
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{char a[100010],b[100010];//设两个字符串 cin>>a>>b;//读入两个字符串 int c[100010],d[100010],h[100010],n1,n2,i,f=0,l=0;n1=strlen(a);//求字符串长度 n2=strlen(b);for(i=0;i<n1/2;i++) swap(a[i],a[n1-1-i]);for(i=0;i<n2/2;i++) swap(b[i],b[n2-1-i]);for(i=0;i<n1;i++) c[i]=a[i]-'0';//把字符串a的字符转化为数字存到数组c当中。其中“-‘0’”为转换方法 for(i=0;i<n2;i++) d[i]=b[i]-'0';if(n2>n1)//这一步是判断那个数长，哪个就大，就用哪个做被减数存到数组c中，哪个小就存到d中 {for(i=0;i<n2;i++) swap(c[i],d[i]);//把两数交换，swap为交换函数 f=1;//设一个旗帜，以后如果f=1就说明这数被减数比减数小，是负数。 }if(n1>n2) swap(n1,n2); //取长的做for循环条件 for(i=0;i<n2;i++) h[i]=c[i]-d[i]; for(i=0;i<n2;i++)//这部就是借位 {if(h[i]<0){ h[i]=10+h[i];h[i+1]--; } }if(f==1) cout<<"-";//如果f等于一也就是结果为负数，打印“-” for(i=n2-1;i>=0;i--)//这步很重要！ 这是在输出时把首位的0都去掉 {if(l==0)//设了一个l，如果l为0意味着还没有碰到非零数，也就是有0就要去掉的0 {if(h[i]!=0) //如果这数不为零 {l=1;//l=1表明碰到了非零数了以后的0有实际意义要打印出来 cout<<h[i];//打印此数 continue;//然后跳出本次循环 } }if(l!=0)//如果l不等于0，就说明这时的0有实际意义，要打印出来 {cout<<h[i];}}
}6.并查集
#include<bits/stdc++.h>
using namespace std;
int f[1000001];
int find(int k){if(f[k]==k)return k;return f[k]=find(f[k]);
}
void join(int x,int y){int fx = find(x);int fy = find(y);if(fx!=fy)f[fy] = fx;
} int main(){int m,n,k,ans=0,sum;scanf("%d%d%d",&m,&n,&k);sum = m*n;for(int i=1;i<=m*n;i++)f[i] = i; for(int i=0;i<k;i++){int t1,t2;scanf("%d%d",&t1,&t2);join(t1,t2);}for(int i=1;i<=sum;i++){if(f[i]==i)ans++;} cout<<ans;return 0;
} 7.01背包
#include<bits/stdc++.h>
using namespace std;int dp[1000][1000];
int val[1000];
int cost[1000];
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&cost[i],&val[i]);for(int i=1;i<=n;i++){for(int j=m;j>=0;j--)if(j>=cost[i])dp[i][j] = max(dp[i-1][j-cost[i]]+val[i],dp[i-1][j]);elsedp[i][j] = dp[i-1][j];}printf("%d",dp[n][m]);return 0;
} 8.快速幂
?
typedef long long LL; // 视数据大小的情况而定LL powerMod(LL x, LL n, LL m)
{LL res = 1;while (n > 0){if (n & 1) // 判断是否为奇数，若是则trueres = (res * x) % m;x = (x * x) % m;n >>= 1; // 相当于n /= 2;}return res;
}?9.素数
int prime[maxn];
bool is_prime[maxn];int sieve(int n){int p = 0;for(int i = 0; i <= n; ++i)is_prime[i] = true;is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i){ // 注意数组大小是nif(is_prime[i]){prime[p++] = i;for(int j = i + i; j <= n; j += i) // 轻剪枝，j必定是i的倍数is_prime[j] = false;}}return p; // 返回素数个数
}
10.dfs
dfs(n) {if (碰到边界) //如上面例子中的分解完就是基本情况返回 值，并退出for i=可以继续搜下去的情况if(可以){标记为不可以dfs(i);//继续往下搜标回可以}
}