算法复习笔记

最大公约数

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 使用欧几里得算法计算两个数的GCD
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}// 计算整个数组的GCD
int arrayGCD(const vector<int>& nums) {if (nums.empty()) return 0;int result = nums[0];for (size_t i = 1; i < nums.size(); ++i) {result = gcd(result, nums[i]);// 如果已经得到1，可以提前终止if (result == 1) {break;}}return result;
}int main() {vector<int> arr = {24, 36, 48, 60};int result = arrayGCD(arr);cout << "数组的最大公约数是: " << result << endl;return 0;
}

枚举

abc

#include <iostream>
using namespace std;int main() {int a, b, c;for(int a=0;a<=9;a++){for(int b=0;b<=9;b++){for(int c=0;c<=9;c++){if((a+b)*100+(b+c)*10+2*c==532){printf("%d %d %d\n",a,b,c);}}}}return 0;
}
// 64 位输出请用 printf("%lld")

反序数

#include<iostream>
using namespace std;
int reverse(int n){int res=0;while(n!=0){res+=n%10;res*=10;n/=10;}return res/=10;
}
int main(){for(int i=1000;i<=9999;i++){if(i*9==reverse(i)){printf("%d\n",i);}}return 0;
}

模拟

xxx定律

#include <iostream>
using namespace std;int main() {int n;while(scanf("%d",&n)!=EOF){int res=0;if(n==1){printf("%d",res);continue;}while(true){if(n%2==0){n/=2;}else{n*=3;n++;n/=2;}res++;if(n==1){printf("%d\n",res);break;}}}return 0;
}

打印数字菱形

#include<iostream>
#include<string.h>
using namespace std;
int main(){char str[1000]={0};int n;scanf("%d",&n);int i=0;for(i=0;i<n;i++){int j=0;memset(str,0,1000);for(j=0;j<2*n-2*i;j++){str[j]=' ';}for(int k=0;k<=i;k++){str[j]='0'+k;str[j+1]=' ';j=j+2;}for(int k=i-1;k>=0;k--){str[j]='0'+k;str[j+1]=' ';j=j+2;}printf("%s\n",str);}for(i=n+1;i<=2*n;i++){int j=0;memset(str,0,1000);for(j=0;j<2*i-2*n;j++){str[j]=' ';}for(int k=0;k<=2*n-i;k++){str[j]='0'+k;str[j+1]=' ';j=j+2;}for(int k=2*n-i-1;k>=0;k--){str[j]='0'+k;str[j+1]=' ';j=j+2;}printf("%s\n",str);}return 0;
}

今年的第几天？

#include<iostream>
using namespace std;
void nextday(int &year,int &month,int &day){int dayofmonth[]={0,31,28,31,30,31,30,31,31,30,31,30,31};if(year%400==0||year%4==0&&year%100!=0){dayofmonth[2]=29;}day++;if(day>dayofmonth[month]){day=1;month++;if(month>12){year++;month=1;}}
}
int main(){int y,m,d;while(scanf("%d %d %d",&y,&m,&d)!=EOF){int curm=1;int curd=1;int res=1;while(1){if(curm==m&&curd==d){printf("%d\n",res);break;}nextday(y,curm,curd);res++;}}return 0;
}

vector

完数VS盈数

#include<iostream>
#include<vector>
using namespace std;
int Sum(int n){int res=0;for(int i=1;i<n;i++){if(n%i==0){res+=i;}}return res;
}
int main(){vector<int> Evec;vector<int> Gvec;for(int n=2;n<=60;n++){if(Sum(n)==n){Evec.push_back(n);}else if(Sum(n)>n){Gvec.push_back(n);}}vector<int>::iterator it;printf("E:");for(it=Evec.begin();it!=Evec.end();it++){printf(" %d",*it);}printf("\n");printf("G:");for(it=Gvec.begin();it!=Gvec.end();it++){printf(" %d",*it);}printf("\n");return 0;
}

剩下的树

#include<iostream>
#include<vector>
using namespace std;
int main(){int L,M;scanf("%d%d",&L,&M);vector<int> road(L+1);for(int i=0;i<M;i++){int left,right;scanf("%d%d",&left,&right);for(int j=left;j<=right;j++){road[j]=1;}}vector<int>::iterator it;int res=0;for(it=road.begin();it!=road.end();++it){if(*it==0)res++;}printf("%d",res);return 0;
}

排序和查找

顺序查找

找x

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){int n;while(scanf("%d",&n)!=EOF){vector<int> vec(n);for(int i=0;i<n;i++){scanf("%d",&vec[i]);}int x;scanf("%d",&x);vector<int>::iterator it;it=find(vec.begin(),vec.end(),x);if(it==vec.end())printf("-1\n");else printf("%d\n",it-vec.begin());}return 0;
}

二分查找

#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main(){int n,m;while(scanf("%d",&n)!=EOF){vector<int> a(n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}map<int,int> findA;for(int i=0;i<n;i++){findA.insert({a[i],i});}scanf("%d",&m);int b;for(int i=0;i<m;i++){scanf("%d",&b);if(findA.find(b)==findA.end()){printf("NO\n");}else{printf("YES\n");}}}return 0;
}

找位置

#include<iostream>
#include<map>
#include<vector>
using namespace std;
int main(){char str[200]={0};scanf("%s",str);map<char,vector<int>> timesMap;vector<char> charSeq;for(int i=0;str[i]!='\0';i++){timesMap[str[i]].push_back(i);if(timesMap[str[i]].size()==1){charSeq.push_back(str[i]);}}vector<char>::iterator it;for(it=charSeq.begin();it!=charSeq.end();it++){if(timesMap[*it].size()>1){vector<int>::iterator mapit=timesMap[*it].begin();printf("%c:%d",*it,*mapit);for(mapit=timesMap[*it].begin()+1;mapit!=timesMap[*it].end();++mapit){printf(",%c:%d",*it,*mapit);}printf("\n");}}return 0;
}

字符串

统计单词

#include<iostream>
#include<map>
#include<vector>using namespace std;
int main(){char arr[200]={0};fgets(arr,200,stdin);vector<int> wordCount={0};bool isSpace=true;int i=0;while(true){if(arr[i]=='.')break;else if(arr[i]==' ')isSpace=true;else{if(isSpace){wordCount.push_back(0);}wordCount[wordCount.size()-1]++;isSpace=false;}i++;}vector<int>::iterator it;for(it=wordCount.begin()+1;it!=wordCount.end();it++){printf("%d ",*it);}return 0;
}

浮点数加法

#include <iostream>
#include<string>
using namespace std;string getInt(string a){return a.substr(0,a.find('.'));
}
string getFraction(string b){return b.substr(b.find('.')+1,b.size()-b.find('.'));
}void FractionPlus(string &s,int &carry,string a,string b){int size=max(a.size(),b.size());while(size>a.size()){a.push_back('0');}while(size>b.size()){b.push_back('0');}s.resize(size);carry=0;for(int i=size-1;i>=0;i--){if(a[i]+b[i]+carry-'0'>'9'){s[i]=a[i]+b[i]+carry-'0'-10;carry=1;}else{s[i]=a[i]+b[i]+carry-'0'; carry=0;}}
}void IntPlus(string &s,int &carry,string a,string b){s.clear();for(int i=a.size()-1,j=b.size()-1;i>=0||j>=0||carry==1;i--,j--){if(i>=0&&j>=0){if(a[i]+b[j]+carry-'0'>'9'){s.insert(s.begin(),a[i]+b[j]+carry-'0'-10);carry=1;}else{s.insert(s.begin(),a[i]+b[j]+carry-'0');carry=0;}}else if(i>=0&&j<0){if(a[i]+carry>'9'){s.insert(s.begin(),a[i]+carry-10);carry=1;}else{s.insert(s.begin(),a[i]+carry);carry=0;}}else if(i<0&&j>=0){if(b[j]+carry>'9'){s.insert(s.begin(),b[j]+carry-10);carry=1;}else{s.insert(s.begin(),b[j]+carry);carry=0;}}else{s.insert(s.begin(),'1');carry=0;}}
}int main() {char arra[1000]={0};char arrb[1000]={0};while(scanf("%s%s",arra,arrb)!=EOF){string a=arra;string b=arrb;string ia=getInt(a);string ib=getInt(b);string fa=getFraction(a);string fb=getFraction(b);string fs;string is;int carry;FractionPlus(fs,carry,fa,fb);IntPlus(is,carry,ia,ib);printf("%s.%s\n",is.c_str(),fs.c_str());}return 0;
}

线性数据结构

队列

约瑟夫问题（队列）

#include<iostream>
#include<queue>
using namespace std;
int main(){queue<int> myQueue;int n,p,m;while(1){scanf("%d%d%d",&n,&p,&m);if(n==0&&p==0&&m==0){break;}int no=p;for(int i=0;i<n;i++){myQueue.push(no);++no;if(no>n){no=1;}}int say=1;while(1){int cur=myQueue.front();myQueue.pop();if(say==m){say=1;if(myQueue.empty()){printf("%d\n",cur);break;}else{printf("%d,",cur);}}else{++say;myQueue.push(cur);}}}return 0;
}

计算表达式（栈）

#include<iostream>
#include<map>
#include<stack>
#include<string>using namespace std;int main(){map<char,int> priority={{'\0',0},{'+',1},{'-',1},{'*',2},{'/',2}};char arr[1000]={0};while(scanf("%s",arr)!=EOF){stack<double> numStack;stack<char> opStack;string str="";for(int i=0;;i++){if(arr[i]>='0'&&arr[i]<='9'){str.push_back(arr[i]);}else{double num=stod(str);numStack.push(num);str="";while(!opStack.empty()&&priority[arr[i]]<=priority[opStack.top()]){double rhs=numStack.top();numStack.pop();double lhs=numStack.top();numStack.pop();char curOp=opStack.top();if(curOp=='+'){numStack.push(lhs+rhs);}else if(curOp=='-'){numStack.push(lhs-rhs);}else if(curOp=='*'){numStack.push(lhs*rhs);}else if(curOp=='/'){numStack.push(lhs/rhs);}opStack.pop();}if(arr[i]=='\0'){printf("%d\n",(int)numStack.top());break;}else{opStack.push(arr[i]); }}}}return 0;
}

递归和分治

跳台阶

#include<iostream>
#include<string.h>
using namespace std;
int f(int n){if(n==1){return 1;}else if(n==2){return 2;}else{return f(n-1)+f(n-2);}
}
int main(){int n;scanf("%d",&n);printf("%d\n",f(n));return 0;
}

不连续1的子串

#include<iostream>
#include<string.h>
using namespace std;
int f0(int n);
int f1(int n);
int f0(int n){if(n==1){return 1;}else{return f0(n-1)+f1(n-1);}
}
int f1(int n){if(n==1){return 1;}else {return f0(n-1);}
}
int main(){int n;scanf("%d",&n);printf("%d\n",f0(n)+f1(n));}

2的幂次方

#include<iostream>
#include<vector>
#include<string>
using namespace std;
string Get2sExponet(int n){vector<int> exp;if(n==0){return "0";}for(int i=15;i>=0;i--){if((n&(1<<i))!=0){exp.push_back(i);}}string res="";for(int i=0;i<exp.size();i++){if(i!=0){res+="+";}if(exp[i]==1){res+="2";}else{res+="2("+Get2sExponet(exp[i])+")";}}return res;
};
int main(){int n;while(scanf("%d",&n)!=EOF){printf("%s\n",Get2sExponet(n).c_str());};return 0;
}

树

二叉树

#include<iostream>
using namespace std;
int main(){int m,n;while(scanf("%d %d",&m,&n)!=EOF){if(m==0&&n==0)break;int treeNum=0;int right=m;int left=m;int begin;int final;for(int i=1;;i++){if(m>=1<<(i-1)&&m<1<<i){begin=i;}if(n>=1<<(i-1)&&n<1<<i){final=i;break;}}for(int i=begin;i<final;i++){left=left*2;right=right*2+1;}if(left>n){treeNum=(1<<(final-begin))-1;}else if(right>=n){treeNum=(1<<(final-begin))-1;treeNum+=n-left+1;}else{treeNum=(1<<(final-begin+1))-1;}printf("%d\n",treeNum);}return 0;
}

层序建树

#include<iostream>
#include<queue>
using namespace std;
struct TreeNode{char data;TreeNode* left;TreeNode* right;
};
struct QueueNode{TreeNode* parent;bool isLeft;
};
void BuildTree(TreeNode*& proot,queue<QueueNode*>& pos,char data){if(data!='#'){TreeNode* pNew=new TreeNode; pNew->data=data;QueueNode* pQueueNode=new QueueNode;pQueueNode->parent=pNew;pQueueNode->isLeft=false;pos.push(pQueueNode);if(proot==NULL){proot=pNew;}else{QueueNode* pCur=pos.front();if(pCur->isLeft==false){pCur->parent->left=pNew;pCur->isLeft=true;}else{pCur->parent->right=pNew;pos.pop();delete pCur;}}}else{if(proot!=NULL){QueueNode* pCur=pos.front();if(pCur->isLeft==false){pCur->parent->left=NULL;pCur->isLeft=true;}else{pCur->parent->right=NULL;pos.pop();delete pCur; }}}}
int main(){TreeNode* proot=NULL;char data;queue<QueueNode*> pos;while(1){scanf("%c",&data);if(data=='\n'){break;}BuildTree(proot,pos,data);}return 0;
}

层序遍历

void levelOrder(TreeNode* proot){queue<TreeNode*> pos;pos.push(proot);while(!pos.empty()){TreeNode* pCur=pos.front();pos.pop();printf("%c",pCur->data);if(pCur->left!=NULL){pos.push(pCur->left);}if(pCur->right!=NULL){pos.push(pCur->right);}}printf("\n");
}

先序遍历

void PreOrder(TreeNode* proot){if(proot==NULL){return;}else{printf("%c",proot->data);PreOrder(proot->left);PreOrder(proot->right);}
}

void InOrder(TreeNode* proot){if(proot==NULL){return;}else{InOrder(proot->left);printf("%c",proot->data);InOrder(proot->right);}
}//中序
void PostOrder(TreeNode* proot){if(proot==NULL){return;}else{PostOrder(proot->left);PostOrder(proot->right);printf("%c",proot->data);}
}//后序

二叉树最短路径长度

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode{int num;TreeNode* left;TreeNode* right;TreeNode* parent;
};
int main(){int t;scanf("%d",&t);for(int i=0;i<t;i++){int n,m;scanf("%d%d",&n,&m);vector<TreeNode*> nodeArr(n+1);for(int j=1;j<=n;j++){nodeArr[j]=new TreeNode;nodeArr[j]->num=j;}nodeArr[1]->parent=NULL;for(int j=1;j<=n;j++){int left,right;scanf("%d%d",&left,&right);if(left!=-1){nodeArr[j]->left=nodeArr[left];nodeArr[left]->parent=nodeArr[j];}else{nodeArr[j]->left=NULL;}if(right!=-1){nodeArr[j]->right=nodeArr[right];nodeArr[right]->parent=nodeArr[j];}else{nodeArr[j]->right=NULL;}}int lhs,rhs;for(int j=0;j<m;j++){scanf("%d%d",&lhs,&rhs);vector<int> lvec;TreeNode* p=nodeArr[lhs];while(p!=NULL){lvec.push_back(p->num);p=p->parent;}vector<int> rvec;p=nodeArr[rhs];while(p!=NULL){rvec.push_back(p->num);p=p->parent;}int l=lvec.size()-1;int r=rvec.size()-1;while(true){if(l<0||r<0||lvec[l]!=rvec[r]){break;}l--;r--;}printf("%d\n",l+r+2);}}
}

二叉树遍历

#include<iostream>
using namespace std;
struct TreeNode
{char data;TreeNode* left;TreeNode* right;
};
TreeNode* BuildTree(int &i,char str[]){char c=str[i];i++;if(c=='#'){return NULL;}else{TreeNode* pNew=new TreeNode;pNew->data=c;pNew->left=BuildTree(i,str);pNew->right=BuildTree(i,str);return pNew;}
}
void InOrder(TreeNode*& proot){if(proot==NULL){return;}InOrder(proot->left);printf("%c ",proot->data);InOrder(proot->right);return;
}int main(){char str[1000]={0};while(scanf("%s",str)!=EOF){int i=0;TreeNode* res=BuildTree(i,str);InOrder(res);printf("\n");}return 0;
}

重建二叉树

#include<iostream>
#include<string>
using namespace std;
struct TreeNode{char data;TreeNode* left;TreeNode* right;
};
TreeNode* Rebuild(string preorder,string inorder){if(preorder.size()==0){return NULL;}else{TreeNode* pNew=new TreeNode;char rootdata=preorder[0];pNew->data=rootdata;int pos=inorder.find(rootdata);pNew->left=Rebuild(preorder.substr(1,pos),inorder.substr(0,pos));pNew->right=Rebuild(preorder.substr(pos+1),inorder.substr(pos+1));return pNew;}
}
void PostOrder(TreeNode* proot){if(proot==NULL){return;}PostOrder(proot->left);PostOrder(proot->right);printf("%c",proot->data);
}
int main(){char preorder[30];char inorder[30];while(scanf("%s%s",preorder,inorder)!=EOF){TreeNode* res=new TreeNode;res=Rebuild(preorder,inorder);PostOrder(res);printf("\n");}return 0;
}

二叉排序树

#include<iostream>
#include<string>
using namespace std;
struct TreeNode{int data;TreeNode* left;TreeNode* right;
};
void insertBST(TreeNode*& proot,int m){TreeNode* pNew=new TreeNode;pNew->data=m;pNew->left=NULL;pNew->right=NULL;if(proot==NULL){proot=pNew;printf("-1\n");}else{TreeNode* pCur=proot;TreeNode* pPre;while(1){if(pCur->data>m){pPre=pCur;pCur=pCur->left;if(pCur==NULL){pPre->left=pNew;printf("%d\n",pPre->data);break;}}else{pPre=pCur;pCur=pCur->right;if(pCur==NULL){pPre->right=pNew;printf("%d\n",pPre->data);break;}}}}
}int main(){int n;TreeNode* proot=NULL;scanf("%d",&n);for(int i=0;i<n;i++){int m;scanf("%d",&m);insertBST(proot,m);}return 0;
}

二叉搜索树

#include<iostream>
#include<string>
using namespace std;
struct TreeNode{char data;TreeNode* left;TreeNode* right;
};
void insertBST(TreeNode*& proot,char m){TreeNode* pNew=new TreeNode;pNew->data=m;pNew->left=NULL;pNew->right=NULL;if(proot==NULL){proot=pNew;}else{TreeNode* pCur=proot;TreeNode* pPre;while(1){if(pCur->data>m){pPre=pCur;pCur=pCur->left;if(pCur==NULL){pPre->left=pNew;break;}}else{pPre=pCur;pCur=pCur->right;if(pCur==NULL){pPre->right=pNew;break;}}}}
}
string preOrder(TreeNode* proot){if(proot==NULL){return "";}else{return proot->data+preOrder(proot->left)+preOrder(proot->right);}
}
string InOrder(TreeNode* proot){if(proot==NULL){return "";}else{return InOrder(proot->left)+proot->data+InOrder(proot->right);}
}int main(){int n;TreeNode* proot=NULL;scanf("%d",&n);char arr[21]={0};scanf("%s",arr);for(int i=0;arr[i]!='\0';i++){insertBST(proot,arr[i]);}string preorder=preOrder(proot);string inorder=InOrder(proot);for(int i=0;i<n;i++){char tmp[21]={0};TreeNode* pos=NULL;scanf("%s",tmp);for(int i=0;tmp[i]!='\0';i++){insertBST(pos,tmp[i]);}if(preOrder(pos)==preorder&&inorder==InOrder(pos)){printf("YES\n");}else{printf("NO\n");}}return 0;
}

优先队列

复数集合

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct Complex{int re;int im;Complex(int _re,int _im){re=_re;im=_im;}
};
bool operator < (Complex lhs,Complex rhs){return lhs.re*lhs.re+lhs.im*lhs.im<rhs.re*rhs.re+rhs.im*rhs.im||(lhs.re*lhs.re+lhs.im*lhs.im==rhs.re*rhs.re+rhs.im*rhs.im)&&(lhs.im>rhs.im);
}
int main(){int n;scanf("%d",&n);priority_queue<Complex> myq;for(int i=0;i<n;i++){char arr[10]={0};scanf("%s",arr);string str=arr;if(str=="Pop"){if(myq.empty()){printf("empty\n");}else{printf("%d+i%d\n",myq.top().re,myq.top().im);myq.pop();printf("SIZE = %d\n",myq.size());}}else{int re,im;scanf("%d+i%d",&re,&im);myq.push(Complex(re,im));printf("SIZE = %d\n",myq.size());}}return 0;
}

哈夫曼树

#include<iostream>
#include<queue>
using namespace std;
int main(){int n;while(scanf("%d",&n)!=EOF){priority_queue<int> myq;for(int i=0;i<n;i++){int m;scanf("%d",&m);myq.push(-1*m);}int res=0;while(myq.size()>=2){int l1,l2;l1=myq.top();myq.pop();l2=myq.top();myq.pop();res+=l1+l2;myq.push(l1+l2);}printf("%d\n",-1*res);}return 0;
}

搜索

树的高度

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){int n,m;scanf("%d%d",&n,&m);vector<vector<int>> tree(n+1);for(int i=0;i<n-1;i++){int u,v;scanf("%d%d",&u,&v);tree[u].push_back(v);tree[v].push_back(u);}queue<int> toVisit;toVisit.push(m);vector<int> distance(n+1);for(int i=1;i<n;i++){distance[i]=-1;}distance[m]=0;int maxdist=0;while(!toVisit.empty()){int current=toVisit.front();toVisit.pop();for(int i=0;i<tree[current].size();i++){int child=tree[current][i];if(distance[child]!=-1){continue;}toVisit.push(child);distance[child]=distance[current]+1;maxdist=distance[child];}}printf("%d\n",maxdist);return 0;
}

玛雅人的密码

#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
using namespace std;
int main(){int n;scanf("%d",&n);char arr[20]={0};scanf("%s",arr);string str=arr;if(n<4){printf("-1\n");return 0;}queue<string> toVisit;toVisit.push(str);unordered_map<string,int> distance;distance.insert({str,0});while(!toVisit.empty()){string current=toVisit.front();toVisit.pop();if(current.find("2012")!=string::npos){printf("%d\n",distance[current]);return 0;}for(int i=0;i<n-1;i++){string exc=current;char tmp=exc[i];exc[i]=exc[i+1];exc[i+1]=tmp;if(distance.count(exc)==0){toVisit.push(exc);distance.insert({exc,distance[current]+1});}}}printf("-1\n");return 0;
}

八皇后

打表取巧

#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<vector<int>> QueenVec;
void DFSFindQueen(vector<int>& queen,int pos){for(int i=1;i<=8;i++){bool isOK=true;for(int j=0;j<pos;j++){if(queen[j]==i||pos-j==queen[j]-i||pos-j==i-queen[j]){isOK=false;break;}}if(isOK==true){queen.push_back(i);if(pos==7){QueenVec.push_back(queen);printf("\"");for(int k=0;k<8;k++){printf("%d",queen[k]);}printf("\",\n");}else{DFSFindQueen(queen,pos+1);}queen.pop_back();}}
}
vector<string> queentable={"15863724",
"16837425",
"17468253",
"17582463",
"24683175",
………………
"73825164",
"74258136",
"74286135",
"75316824",
"82417536",
"82531746",
"83162574",
"84136275"
};
int main(){//vector<int>queen;//DFSFindQueen(queen,0);int n;while(scanf("%d",&n)!=EOF){printf("%s\n",queentable[n-1].c_str());}return 0;
}

数组划分

剪枝

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int sum=0;
int diff=0;
bool exitFlag=false;//记录是否提前退出
void DFSFindMinDiff(vector<int> &arr,int pos,int sa){if(pos==arr.size()||exitFlag){return;}//arr[pos]放入a集合中int newdiff;if(2*(sa+arr[pos])-sum>0){newdiff=2*(sa+arr[pos])-sum;}else{newdiff=sum-2*(sa+arr[pos]);}if(newdiff<diff){diff=newdiff;if(diff==0||diff==1||2*arr[pos]>sum){exitFlag=true;}}if(2*(sa+arr[pos])-sum<0){DFSFindMinDiff(arr,pos+1,sa+arr[pos]);}//arr[pos]不放入a集合中DFSFindMinDiff(arr,pos+1,sa);
}
bool compare(int lhs,int rhs){return lhs>rhs;
}
int main(){vector<int> arr;int i;while(scanf("%d",&i)!=EOF){arr.push_back(i);}for(int i=0;i<arr.size();i++){sum+=arr[i];}diff=sum;sort(arr.begin(),arr.end(),compare);DFSFindMinDiff(arr,0,0);int sa=(sum-diff)/2;int sb=sa+diff;printf("%d %d\n",sb,sa);return 0;
}

图

图的构建：邻接表

#include<iostream>
#include<vector>
using namespace std;
//A-B A-C A-D C-D
int main(){//A-0 B-1 C-2 D-3vector<int> graph[4];int u,v;u=0,v=1;graph[u].push_back(v);graph[v].push_back(u);u=0,v=2;graph[u].push_back(v);graph[v].push_back(u);u=0,v=3;graph[u].push_back(v);graph[v].push_back(u);u=2,v=3;graph[u].push_back(v);graph[v].push_back(u);return 0;
}

并查集

#include<iostream>
#include<vector>
using namespace std;
int father[1000];
void InitDisjointSet(int n){for(int i=0;i<n;i++){father[i]=i;}
}
int FindDisjointSet(int u){if(u==father[u]){return u;}else{father[u]=FindDisjointSet(father[u]);return father[u];}
}
void UnionDisjointSet(int u,int v){int uroot=FindDisjointSet(u);int vroot=FindDisjointSet(v);father[vroot]=uroot;
}
int main(){//1234//567//08int n=9;InitDisjointSet(n);UnionDisjointSet(1,2);UnionDisjointSet(1,3);UnionDisjointSet(1,4);UnionDisjointSet(5,6);UnionDisjointSet(5,7);UnionDisjointSet(0,8);for(int i=0;i<9;i++){printf("NO=%d,root=%d\n",i,FindDisjointSet(i));}return 0;
}

畅通工程

#include<iostream>
#include<vector>
using namespace std;
int father[1000];
void InitDisjointSet(int n){for(int i=1;i<=n;i++){father[i]=i;}
}
int FindDisjointSet(int u){if(u==father[u]){return u;}else{father[u]=FindDisjointSet(father[u]);return father[u];}
}
int setCount;
void UnionDisjointSet(int u,int v){int uroot=FindDisjointSet(u);int vroot=FindDisjointSet(v);if(uroot!=vroot){setCount--;}father[vroot]=uroot;
}
int main(){int n;while(scanf("%d",&n)!=EOF){if(n==0)return 0;setCount=n;InitDisjointSet(n);int m;scanf("%d",&m);for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);UnionDisjointSet(u,v);}printf("%d\n",setCount-1);}return 0;
}

这是一棵树吗

#include<iostream>
#include<vector>
using namespace std;
int father[10001];
void InitDisjointSet(int n){for(int i=1;i<=n;i++){father[i]=i;}
}
int FindDisjointSet(int u){if(u==father[u]){return u;}else{father[u]=FindDisjointSet(father[u]);return father[u];}
}
void UnionDisjointSet(int u,int v){int uroot=FindDisjointSet(u);int vroot=FindDisjointSet(v);father[vroot]=uroot;
}
int main(){int u,v;InitDisjointSet(10001);int edgeCount=0;int vertexCount=0;vector<int> vertex(10001);vector<int> inDegree(10001);bool isOK=true;int CaseIdx=1;while(1){scanf("%d%d",&u,&v);if(u==-1&&v==-1){break;}else if(u==0&&v==0){if(vertexCount!=edgeCount+1){isOK=false;}if(vertexCount==0&&edgeCount==0){isOK=true;}if(isOK){printf("Case %d is a tree.\n",CaseIdx);}else{printf("Case %d is not a tree.\n",CaseIdx);}InitDisjointSet(10001);edgeCount=0;vertexCount=0;for(int i=0;i<10001;i++){vertex[i]=0;inDegree[i]=0;}isOK=true;CaseIdx++;}else{++edgeCount;if(vertex[u]==0){vertex[u]=1;++vertexCount;}if(vertex[v]==0){vertex[v]=1;++vertexCount;}if(FindDisjointSet(u)==FindDisjointSet(v)){isOK=false;}else{UnionDisjointSet(u,v);}++inDegree[v];if(inDegree[v]>=2){isOK=false;}}}return 0;
}

最小生成树 kruskal

还是畅通工程

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{int from;int to;int weight;Edge(int _from,int _to,int _weight){from=_from;to=_to;weight=_weight;}
};
int father[101];
void InitDisjointSet(int n){for(int i=1;i<=n;i++){father[i]=i;}
}
int FindDisjointSet(int u){if(u==father[u]){return u;}else{father[u]=FindDisjointSet(father[u]);return father[u];}
}
void UnionDisjointSet(int u,int v){int uroot=FindDisjointSet(u);int vroot=FindDisjointSet(v);father[vroot]=uroot;
}
bool compare(Edge lhs,Edge rhs){return lhs.weight<rhs.weight;
}
int main(){int n;while(scanf("%d",&n)!=EOF){if(n==0)return 0;InitDisjointSet(n);int edgeCount=0;int sumweight=0;vector<Edge> edgeVec;for(int i=0;i<n*(n-1)/2;i++){int from,to,weight;scanf("%d%d%d",&from,&to,&weight);Edge e(from,to,weight);edgeVec.push_back(e);}sort(edgeVec.begin(),edgeVec.end(),compare);for(int i=0;i<edgeVec.size();i++){if(FindDisjointSet(edgeVec[i].from)!=FindDisjointSet(edgeVec[i].to)){UnionDisjointSet(edgeVec[i].from,edgeVec[i].to);edgeCount++;sumweight+=edgeVec[i].weight;}if(edgeCount==n-1){break;}}printf("%d\n",sumweight);}return 0;
}

单源最短路径 dijkstra

畅通工程续

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Edge
{int u;int v;int weight;Edge(int _u,int _v,int _weight){u=_u;v=_v;weight=_weight;}
};
vector<Edge> graph[300];
struct pQueueNode{int u;int distance;pQueueNode(int _u,int _distance){u=_u;distance=_distance;}
};
bool operator < (pQueueNode lhs,pQueueNode rhs){return lhs.distance>rhs.distance;
}
int Dijkstra(int s, int t){priority_queue<pQueueNode> pqueue;int distance[300];bool isVisited[300];for(int i=0;i<300;i++){distance[i]=-1;isVisited[i]=false;}distance[s]=0;pQueueNode qnode(s,0);pqueue.push(qnode);while(!pqueue.empty()){int u=pqueue.top().u;pqueue.pop();if(isVisited[u]==true){continue;}isVisited[u]=true;for(int i=0;i<graph[u].size();i++){int v=graph[u][i].v;int weight=graph[u][i].weight;if(distance[v]==-1||distance[v]>distance[u]+weight){distance[v]=distance[u]+weight;pQueueNode next(v,distance[v]);pqueue.push(next);}}}return distance[t];
}
int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++){graph[i].clear();}for(int i=0;i<m;i++){int u,v,weight;scanf("%d%d%d",&u,&v,&weight);Edge e1(u,v,weight);graph[u].push_back(e1);Edge e2(v,u,weight);graph[v].push_back(e2);}int s,t;scanf("%d%d",&s,&t);printf("%d\n",Dijkstra(s,t));}return 0;
}

动态规划

跳台阶

#include<iostream>
using namespace std;
int main(){int dp[16]={0};dp[1]=1;dp[2]=2;int n;scanf("%d",&n);for(int i=3;i<n;i++){dp[i]=dp[i-1]+dp[i-2];}printf("%d\n",dp[n]);return 0; 
}

放苹果

#include<iostream>
#include<stdio.h>
using namespace std;
int main(){int dp[13][13]={0};int m,n;while(scanf("%d%d",&m,&n)!=EOF){memset(dp,0,13*13);for(int i=0;i<=m;i++){dp[i][1]=1;}for(int j=1;j<=n;j++){dp[1][j]=1;dp[0][j]=1;}for(int i=2;i<=m;i++){for(int j=2;j<=n;j++){if(i>=j){dp[i][j]=dp[i][j-1]+dp[i-j][j];}else{dp[i][j]=dp[i][i];}}}printf("%d\n",dp[m][n]);}return 0; 
}

最长公共子序列

int dp[1002][1002];//全局变量才不会栈溢出
int longestCommonSubsequence(string text1, string text2) {int m=text1.size();int n=text2.size();for(int i=0;i<=m;i++){dp[i][0]=0;}for(int i=0;i<=n;i++){dp[0][i]=0;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];
}

最长公共子串

#include<iostream>
#include<stdio.h>
using namespace std;
short dp[10002][10002];
int main(){char s1[10001];char s2[10001];scanf("%s%s",s1,s2);int n=strlen(s1);int m=strlen(s2);for(int j=0;j<=m;j++){dp[0][j]=0;}for(int i=0;i<=n;i++){dp[i][0]=0;}short curmax=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s1[i-1]>='a'&&s1[i-1]<='z'&&s1[i-1]==s2[j-1]){dp[i][j]=dp[i-1][j-1]+1;curmax=max(dp[i][j],curmax);}else{dp[i][j]=0;}}}printf("%d\n",curmax);return 0; 
}

最大序列和

#include<iostream>
#include<stdio.h>
using namespace std;
long long s[1000001];
long long dp[1000002];
int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lld",&s[i]);}dp[1]=s[0];long long curmax=dp[1];for(int i=2;i<=n;i++){if(dp[i-1]<=0){dp[i]=s[i-1];}else{dp[i]=s[i-1]+dp[i-1];}curmax=max(dp[i],curmax);}printf("%lld\n",curmax);return 0; 
}

背包问题

点菜问题

#include<iostream>
#include<stdio.h>
using namespace std;int main(){int c,n;scanf("%d%d",&c,&n);int p[101];int v[101];int dp[1002][102];for(int i=0;i<n;i++){scanf("%d%d",&p[i],&v[i]);}for(int i=0;i<=c;i++){dp[i][0]=0;}for(int i=0;i<=n;i++){dp[0][i]=0;}for(int i=1;i<=c;i++){for(int j=1;j<=n;j++){if(i-p[j-1]<0){dp[i][j]=dp[i][j-1];}else{dp[i][j]=max(dp[i-p[j-1]][j-1]+v[j-1],dp[i][j-1]);}}}printf("%d\n",dp[c][n]);return 0; 
}

铺瓷砖

#include<iostream>
using namespace std;
int main(){int t;scanf("%d",&t);for(int i=0;i<t;i++){int n;scanf("%d",&n);int dp[32][5]={0};int dp_one[32][5]={0};dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){if(i-j>=0){for(int k=0;k<=3;k++){if(k!=j){dp[i][j]+=dp[i-j][k];dp_one[i][j]+=dp_one[i-j][k];}}if(j==1){dp_one[i][j]+=dp[i][j];}}}}printf("%d\n",dp[n][1]+dp[n][2]+dp[n][3]);printf("%d\n",dp_one[n][1]+dp_one[n][2]+dp_one[n][3]);}return 0;
}

数学问题

二进制数

#include<iostream>
#include<vector>
using namespace std;int main(){unsigned int u;while(scanf("%u",&u)!=EOF){if(u==0){printf("0\n");return 0;}vector<int> binVec;while(u>0){binVec.push_back(u%2);u/=2;}for(int i=binVec.size()-1;i>=0;i--){printf("%d",binVec[i]);}printf("\n");}return 0; 
}

质数

埃氏筛法（打表）

#include<iostream>
#include<vector>
using namespace std;
int main(){vector<int> num(10001);for(int i=2;i<=10000;i++){if(num[i]==0){printf("%d,\n",i);}for(int j=2*i;j<=10000;j+=i){num[j]=1;}}return 0; 
}

质数（每100里至少有一个整数）

#include<iostream>
#include<vector>
using namespace std;
int prime[]={2,
3,
5,
7,
11,
13,
17,
.......
9931,
9941,
9949,
9967,
9973
};
int main(){int t,x;scanf("%d",&t);for(int i=0;i<t;i++){scanf("%d",&x); for(int j=0;j<1229;j++){//10*x+1~10*x+9if(prime[j]>=10*x+1&&prime[j]<=10*x+9){printf("%d\n",prime[j]);break;}//100*x+10~100*x+99if(prime[j]>=100*x+10&&prime[j]<=100*x+99){printf("%d\n",prime[j]);break;}}}return 0;
}

快速幂

递推数列

#include<iostream>
using namespace std;
void MatrixMutiply(int m1[2][2],int m2[2][2],int res[2][2]){res[0][0]=m1[0][0]*m2[0][0]%10000+m1[0][1]*m2[1][0]%10000;res[0][0]%=10000;res[0][1]=m1[0][0]*m2[0][1]%10000+m1[0][1]*m2[1][1]%10000;res[0][1]%=10000;res[1][0]=m1[1][0]*m2[0][0]%10000+m1[1][1]*m2[1][0]%10000;res[1][0]%=10000;res[1][1]=m1[1][0]*m2[0][1]%10000+m1[1][1]*m2[1][1]%10000;res[1][1]%=10000;
}
void MatrixPower(int m1[2][2],int n,int res[2][2]){if(n==0){res[0][0]=1;res[0][1]=0;res[1][0]=0;res[1][1]=1;}else if(n%2==0){int temp[2][2];MatrixPower(m1,n/2,temp);MatrixMutiply(temp,temp,res);}else{int temp1[2][2];MatrixPower(m1,n/2,temp1);int temp2[2][2];MatrixMutiply(temp1,temp1,temp2);MatrixMutiply(temp2,m1,res);}
}
int main(){int matrix[2][2];matrix[1][0]=1;matrix[1][1]=0;int a0,a1,p,q,k;scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k);matrix[0][0]=p;matrix[0][1]=q;int res[2][2];MatrixPower(matrix,k-1,res);printf("%d\n",(res[0][0]*a1%10000+res[0][1]*a0%10000)%10000);return 0;
}