机试基本代码片段
1.基本输入输出
关闭c++同步流，让cin效率更高
ios::sync_with_stdio(false);
getchar();获取一下之前的scanf操作的回车键。
scanf("%s")和cin不能读入空格的
需要使用gets(),puts()
c++中还有getline(cin,s);
2.结构体数组排序
#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
struct student{
int sum;//学号
string name;//姓名
int grade;//分数
}num[200];
bool cmp(student u,student v){
//按照成绩降序排列，如果成绩相同，按照学号升序排列
if(u.grade == v.grade){
return u.sum < v.sum;
}else{
return u.grade > v.grade;
}
}
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>num[i].sum>>num[i].name>>num[i].grade;
}
sort(num,num+n,cmp);
for(int i=0;i<n;i++){
cout<<num[i].sum<<" "<<num[i].name<<" "<<num[i].grade<<endl;
}
return 0;
}
3.十进制转二进制
#include <iostream>
#include <cstdio>
using namespace std;
//整数部分转换，除k取余法
void slove1(int number){
char ch[2000];
int len;
len = 0;
if(number == 0){
cout<<number;
}else{
while(number){
ch[len++]=number%2;
number /= 2;
}
for(;len>0;len--){
printf("%d",ch[len-1]);
}
}
}
//小数部分转换，乘k取整法
void slove2(double number){
int a[2000],len = 0;
while(number -(int)number){
int tmp;
tmp = int (number*2);
a[len++]=tmp;
//保留10位
if(len==10){
break;
}
number = 2*number- int(number*2);
}
cout<<".";//记得输出小数点
for(int i= 0;i<len;i++){
cout<<a[i];
}
}
int main(){
double number;
cin>>number;
int t;
t = (int)number;
double m;
m = number-t;
slove1(t);
slove2(m);
cout<<endl;
return 0;
}
4.二进制转十进制
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
//以字符串保存二进制数
string s;
cin>>s;
int len;
len = (int)s.size();
//定义k变量，将k移动到小数点.的下标位置处
int k;
k=0;
for(int i=0;i<len;i++){
if(s[i] == '.'){
k=i;
}
}
//从后往前扫描整数部分
//tt为对应为的2次幂
int tt;
tt=0;
int num1;
num1 = 0;
for(int i=k-1;i>=0;i--){
if(s[i] == '1'){
num1 += pow(2,tt);
}
tt++;
}
//从前往后扫描小数部分
double num2;
num2 = 0.0;
tt =-1;
for(int i = k+1;i<len;i++){
if(s[i] == '1'){
num2 +=pow(2,tt);
}
tt--;
}
printf("%.6f\n",num1+num2);
return 0;
}
5.判断一个数是素数
bool isPrime(int num){
int tmp = sqrt(num);
for(int i=2;i<=tmp;i++){
if(num%i==0){
return 0;
}
}
return 1;
}
6.深度优先搜索
举例题：
从任意的w开始，不停地把相邻的部分用“.”代替。
1次dfs后与初始的这个w连接的所有w都被替换成"."
因此，知道途中不再存在w位置，答案为进行dfs的次数。
8个方向一共对应8中状态转移，
每个格子作为dfs的参数最多被调用1次，复杂度为O（n*N
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int num1,num2,ans;
char map[100][100];
void dfs(int x,int y){
//每访问一处位置就将其标注为.
map[x][y]='.';
for(int dx=-1;dx<=1;dx++){
for(int dy= -1;dy<=1;dy++){
//设置nx，ny为想要走的下一个位置的坐标
int nx,ny;
nx = x+dx;
ny = y+dy;
//检查下一个位置的合法性
//1.检查在地图内，2.检查没有访问过和有没有访问的必要
//这里也可以用bool数组代替进行检查
if(nx>=0 &&nx<num1 && ny>=0&& ny<num2
&& map[nx][ny]=='W'){
dfs(nx,ny);
}
}
}
}
int main(){
while(cin>>num1>>num2){
//ans为最终的块数
ans = 0;
//输入地图
for(int i=0;i<num1;i++){
for(int j=0;j<num2;j++){
cin>>map[i][j];
}
}
for(int i=0;i<num1;i++){
for(int j=0;j<num2;j++){
if(map[i][j] == 'W'){
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}
7.动态规划
动规的定义：动态规划是解决多阶段决策过程最优化问题的一种方法
阶段：把问题分成几个相互联系的有顺序的几个环节，
这些环节称为阶段；
状态：把某一阶段的出发位置称为状态，通常一个阶段包含若干状态
注意：
动态规划适用的基本条件——满足无后效性
动态规划只适用于解决当前决策与过去状态无关的问题。
也就是说，如果当前问题的具体决策，会对解决其他未来的问题
产生影响，如果产生影响，就无法保证决策的最优性。
动态规划的一般步骤：
1.找到一个原问题，并分析它的子问题；
2.根据原问题和子问题确定状态
原问题和子问题中有几个变量一般状态就可以初步确定为几维
状态的参数一般有：
1.描述位置的：前后单位，第i到j单位，坐标等；
2.描述数量的，取i个，不超过i个，至少i个等；
3.描述对后有影响的：状态压缩，一些特殊的性质。
8.STL
min,max,sort,swap,next_permutation，reverse
top,back,insert,erase,push_back,pop_back,size,resize,clear,empty.
查找vector数据中最小值和最大值。
min_element，max_element
auto x =max_element(v1.begin(),v1.end());
cout<<*x<<endl;
判断vector中数据是否为堆is_heap,建堆make_heap
cout<<is_heap(v1.begin(),v1.end())<<endl;
make_heap(v1.begin(),v1.end());
9.贪心算法
1.简单贪心：
贪心法是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优(或较优)
的策略，来使全局的结果达到最优或较优的。
显然，如果采取较优的策略，得到的全局结果也无法使最优的。
要获得最优结果，则要求中间的每步策略都是最优的。
因此，严谨使用贪心法来求解最优化问题需要对采取的策略进行证明：反证法或者数学归纳法。
总的来说，贪心是用来解决一类最优化问题，并希望有局部最优策略来推出全局最优结果的算法思想。
贪心算法适用的问题一定要满足最优子结构的性质。
即一个问题的最优解可以由它的子问题的最优解有效的构造出来。
10.贪心和动规的区别：
动规具有两个性质：
1.重叠子问题；
2.最优子结构
贪心算法：
1.贪心选择性质；
2.最优子结构
最优子结构：
该问题的最优解包含子问题的最优解
则称该问题具有最优子结构性质。
重叠子问题：
子问题可能被多次用到，多次计算。
动态规划就是为了消除其重叠子问题而设计的。
其实贪心算法是一类特殊的动态规划，由于其具有
贪心选择性质，保证了子问题只会被计算一次，
不会被多次计算，因此贪心算法是最简单的动态规划。
某种程度上，动规是贪心的泛化，贪心是动规的特例。
动态规划是把问题分成尽可能多的相同的子问题，分治算法是把问题尽可能多的分成独立的子问题。
不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解
自己的话：
贪心，一步求下一步。
动规，求当前步，可能用到前面某个步，不一定是前一步。
11.判断是否为堆：
// is_heap example
#include <iostream> // std::cout
#include <algorithm> // std::is_heap, std::make_heap, std::pop_heap
#include <vector> // std::vector
int main () {
std::vector<int> foo {9,5,2,6,4,1,3,8,7};
if (!std::is_heap(foo.begin(),foo.end()))
std::make_heap(foo.begin(),foo.end());
std::cout << "Popping out elements:";
while (!foo.empty()) {
std::pop_heap(foo.begin(),foo.end()); // moves largest element to back
std::cout << ' ' << foo.back(); // prints back
foo.pop_back(); // pops element out of container
}
std::cout << '\n';
return 0;
}
12.最大公约数和最小公倍数
//最大公约数
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
//最小公倍数
a/d *b :d是最大公约数。
13.质因子分解
数据结构：
struct factor{
int x,cnt;//x为质因子，cnt为其个数
}fac[10];
完整代码：
/*对于一个正整数n来说，如果他存在2，n范围的质因子，
要么这些质因子全部小于等于sqrt(n),
要么只存在一个大于sqrt(n)的质因子，而其他的质因子全部小于等于sqrt(n).
所以整体思路：
1.枚举1-sqrt(n)范围内的所有质因子p，判断p是否是n的因子
2.如果在上面的步骤结束之后n仍然大于1，说明n有且只有一个大于sqrt(n)的质因子，就是n本身
*/
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
const int maxn = 10010;
bool is_prime(int n){//判断n是否为素数
if(n==1){
return false;
}
int sqr = (int)sqrt(1.0*n);
for(int i=2; i<=sqr;i++){
if(n%i==0){
return false;
}
}
return true;
}
int prime[maxn],pNum=0;
//prime数组收集1到maxn的所有素数
void find_prime(){//求素数表
for(int i=1; i<maxn; i++){
if(is_prime == true){
prime[pNum++] = i;
}
}
}
struct factor{
int x,cnt;//x为质因子，cnt为其个数
}fac[10];
int main(){
find_prime();//这一句必须写
int n,num=0;//num为n的不同质因子的个数
scanf("%d",&n);
if(n==1){
printf("1=1");//特判1的情况
}else{
printf("%d",n);
int sqr = (int)sqrt(1.0*n);//n的根号
//枚举根号n以内的质因子
for(int i=0; i<pNum && prime[i] <= sqr;i++){
if(n&prime[i] == 0){//如果prime[i]是n的因子
fac[num].x = prime[i];//记录该因子
fac[num].cnt = 0;
while(n%prime[i] == 0){//计算出质因子的个数
fac[num].cnt++;
n /= prime[i];
}
num++;//不同质因子个数+1
}
if(n == 1){
break;//及时退出循环，节省时间
}
}
if(n!=1){//如果无法被根号n以内的质因子除尽
fac[num].x = n;//那么一定有一个大于根号n的质因子
fac[num++].cnt = 1;
}
}
return 0;
}
核心部分：
if(n%prime[i] == 0){//如果prime[i]是n的因子
fac[num].x = prime[i];//记录该因子
fac[num].cnt = 0;
while( n%prime[i] == 0){//计算出质因子的个数
fac[num].cnt++;
n/=prime[i];
}
num++;//不同的质因子个数+1
}
14.组合
1.//计算n！中有多少个质因子p
int cal(int n,int p){
int ans = 0;
for(int i=2;i<=n;i++){//遍历2-n
int temp = i;
while(temp&p == 0){//只要temp还是p的倍数
ans++;//p的个数+1
temp /= p;//temp除以p
}
}
return ans;
}
或者
//计算n!中有多少个质因子p
int cal(int n,int p){
int ans = 0;
while(n){
ans += n/p;//累加
n /= p;
}
return ans;
}
利用这个算法可以很快算出n！末尾有多少个0.
由于末尾0的个数等于n！中因子10的个数，
而这又等于n！中质因子5的个数，因此只需要
代入cal(n,5)就可以得出末尾有多少个0；
2.组合数Cnm,从n个不同元素中选出m个元素的方案数。
核心：C(n,m) = C(n-1,m) + C(n-1,m-1);
long long C(long long n,long long m){
if(m == 0 || m == n){
return 1;
}
return C(n-1,m) + C(n-1,m-1);
}
15.排列
//用数组
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
int a[10] = {1,2,3};
do{
printf("%d%d%d\n",a[0],a[1],a[2]);
}while(next_permutation(a,a+3)); //关键就是这个do—while循环+next_permutation
return 0;
}
//或者用vector
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
vector<int> v1={1,2,3};
do{
for(auto x:v1){
cout<<x;
}
cout<<endl;
}while(next_permutation(v1.begin(),v1.end()));
return 0;
}
16.单源最短路径问题——Dijkstra算法
//邻接矩阵模板
const int MAXV = 1000;
const int INF = 100000000;
int n,G[MAXV][MAXV];//n为顶点数，MAXV为最大顶点数
int d[MAXV];//起点到达各点的最短路径长度
//初始化图G
fill(G[0],G[0]+MAXV*MAXV，INF);
bool vis[MAXV] = {false};//标记数组，true表示已访问，初值均为false
void Dijkstra(int s){//s为起点
fill(d,d+MAXV,INF);//fill函数将真个d数组赋值为INF
d[s] = 0;//起点s到达自身的距离为0
for(int i= 0;i<n;i++){//循环n次
int u = -1,MIN = INF;//u使d[u]最小，MIN存放该最小的d[u]
for(int j=0; j<n;j++){//找到未访问的顶点中d最小的
if(vis[j] == false && d[j] < MIN){
u =j;
MIN = d[j];
}
}
//找不到小于INF的d，说明剩下的顶点和起点s不连通，
if(u == -1){
return ;
}
vis[u] = true;//标记u已被访问
//下面的是更新工作
for(int v = 0; v<n; v++){
//如果v未访问&&u能到达v&& 以u为中介点可以使d[v]更优
if(vis[v] == false
&& G[u][v] != INF
&& d[u] + G[u][v] <d[v]){
d[v] = d[u] + G[u][v];//优化d[v]
}
}
}
}
17.文件操作：
利用文件重定向提高调试效率
用下面的形式调用函数freopen()会将标准输入stdin重定向到文件input.txt（这个名字可以自己定义）。
freopen("input.txt","r",stdin); //设置输入和输出文件
重定向后，原先从键盘（标准输入的默认设备）接受的输入，将统统从文件读取input.txt读取，这就是重定向。程序可以写作：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
freopen("input.txt","r",stdin); //只加这一句输入将被重定向到文件input.txt
int a,b;
cin>>a>>b;
cout<<a+b<<endl;
return 0;
}
于是，在运行程序前，将本该由键盘输入的数据，写到文件input.txt中。而在运行程序时，数据将不再需要人去输入。那个快，很享受。
下面是一个简单文件读取测试程序，首先是写数据，将数字0~9写入到data.txt文件中，然后再从data.txt中读取数据，将读到的数据存到数组a[10]中，并且打印到控制台上。
#include <stdio.h>
int main()
{
//下面是写数据，将数字0~9写入到data.txt文件中
FILE *fpWrite=fopen("data.txt","w");
if(fpWrite==NULL)
{
return 0;
}
for(int i=0;i<10;i++)
fprintf(fpWrite,"%d ",i);
fclose(fpWrite);
//下面是读数据，将读到的数据存到数组a[10]中，并且打印到控制台上
int a[10]={0};
FILE *fpRead=fopen("data.txt","r");
if(fpRead==NULL)
{
return 0;
}
for(int i=0;i<10;i++)
{
fscanf(fpRead,"%d ",&a[i]);
printf("%d ",a[i]);
}
getchar();//等待
return 1;
}
关键：c++中，重定向读freopen("input.txt","r",stdin);
重定向写freopen("input.txt","w",stdout);
c/c++ 读入一行不确定个数的整数,分两步
1、首先从文件中读入一行字符串，2、然后从这一行字符串中解析出整数。
c风格：
FILE *fp = fopen("input.txt", "r");
char buf[10000];
while(fgets(buf, 10000, fp))
{
//从buf解析出整数
}
c++风格：
ifstream infile("input.txt");
string s;
while(getline(infile, s))
{
//从s中解析出整数
}
方法1：利用字符串流istringstream
int getInt(string &s)
{
istringstream iss(s);
int num, res = 0;
while(iss >> num)
res++;
return res;
}
18.最小生成树
prim算法：思想和Dijkstra算法相似，不同之处，最短路径总是点思考问题添加新的边，
prim算法每次添加新的边时，将原来已经确定的节点包含在一个集合，想象成
一个不存在的大的节点。
克鲁斯卡尔算法：边权从小到大排序，先选小边，如果新加入一条边，不构成连通，就可以加入，
否则换其他边加入，直到最小生成树的变数等于总顶点数-1或是测试完所有边时结束。
当结束时如果最小生成树边数小于总顶点数-1，说明该图不连通。
19.高精度加法：
自己写的，自己容易理解
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
string add(string s1,string s2){
int len1 = s1.length();
int len2 = s2.length();
reverse(s1.begin(),s1.end());//将s1和s2整体翻转
reverse(s2.begin(),s2.end());
//将长度相对较短的字符串剩余部分用'0'填充，实现对齐效果
if(len1<len2){
for(int i=len1;i<len2;i++){
s1.push_back('0');
}
}
if(len1>len2){
for(int i=len2;i<len1;i++){
s2.push_back('0');
}
}
//结果字符串初始化为空
string res="";
//初始化进位为0
int carry=0;
int i;
for(i=0; i<len1 || i<len2; i++){
//num为对应位相加的结果
int num=(s1[i]-'0')+(s2[i]-'0')+carry;
int tmp = num%10;//计算得出加法之后该位应保存的数
carry=num/10;//计算加法之后得到的新的进位
res.push_back('0'+tmp);//将新的结果添加在res的结尾
}
//最后还需要检查一下进位是否不为0，如果这样还需要再添加1到最高位。
if(carry!=0){
res.push_back('1');
}
//注意这里需要逆序输出，对应一开始的将s1和s2逆置
reverse(res.begin(),res.end());
return res;
}
int main(){
string s1,s2,res;//将高精度整数用string保存
cin>>s1>>s2;
res=add(s1,s2);//通过高精度加法，返回加法结果string，res
cout<<res<<endl;
return 0;
}
京公网安备 11010502036488号