Start：2021/4/15
试题A：组队
ANS=490
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>using namespace std;int Team[20][5];//20个球员，每人在1~5号位的评分
int arr[20];void Read(){for(int i=0;i<20;i++){int id;cin>>id;for(int j=0;j<5;j++)cin>>Team[i][j];}
}void printTeam(){for(int i=0;i<20;i++){cout<<"id="<<i+1<<" 评分："<<endl;for(int j=0;j<5;j++)cout<<Team[i][j]<<" ";cout<<endl;}
}void func1(){//全排列，枚举所有情况，求最优值memset(arr,0,sizeof(arr));for(int j=1;j<=5;j++)arr[14+j]=j;int MMax=0;do{int curMax=0;for(int i=0;i<20;i++){if(arr[i]>0)curMax+=Team[i][arr[i]-1];}MMax=max(MMax,curMax);}while(next_permutation(arr,arr+20));cout<<MMax<<endl;
}int main()
{Read();func1();return 0;
}试题B：年号字串
ANS=BYQ
调试代码：
#include <iostream>
#include <map>
#include <cmath>using namespace std;//A~Z:1~26,类 26进制
map<char,int> index;//<字母,对应数字>void init(){int cnt=0;for(char c='A';c<='Z';c+=1)index[c]=++cnt;map<char,int>::iterator it;for(it=index.begin();it!=index.end();it++){cout<<it->first<<":"<<it->second<<endl;}}long long LetterToNum(string letter){int len=letter.size();long long num=0;for(int i=0;i<len;i++){num+=index[letter[i]]*pow(26,len-i-1);}return num+1;
}int main()
{init();int LQ=index['L']*26+index['Q'];cout<<"LQ="<<LQ<<endl;cout<<LetterToNum("BYP")<<endl;cout<<LetterToNum("BYQ")<<endl;int BYQ=index['B']*26*26+index['Y']*26+index['Q'];cout<<"BYQ="<<BYQ<<endl;//ANS=BYQreturn 0;
}
试题C：数列求值
ans=4659
调试代码：
#include <iostream>using namespace std;int A,B,C;
int tmp;void simplify(int& num){if(num>1000000){int ws=num/1000000;num=num-ws*1000000;}
}void simp2(int & num){//num只看其后6位，所以num对10^6取余数num%=1000000;
}void move(){tmp=C+B;
// simplify(tmp);simp2(tmp);tmp+=A;
// simplify(tmp);simp2(tmp);A=B;B=C;C=tmp;}int main(int argc, char** argv) {A=3;B=5;C=9;for(long long i=7;i<=20190324;i++){move();}cout<<C<<endl;return 0;
}
试题D：数的分解
ans=40785
调试代码：
#include <iostream>
#include <algorithm>
#include <string.h>
#include <sstream>using namespace std;
//三重for循环string ItoS(int num){stringstream ss;ss<<num;return ss.str();
}bool check(int num){string snum=ItoS(num);for(int i=0;i<snum.size();i++)if(snum[i]=='2' || snum[i]=='4')return false;return true;
}void func1(){int cnt=0;for(int i=1;i<2019;i++){//i<j<k,依次递增，保证了不会重复if(!check(i))continue;for(int j=i+1;j+i<2019;j++){if(!check(j))continue;for(int k=j+1;i+j+k<=2019;k++){if( (i+j+k)==2019 && check(k) )cnt++;}}}cout<<cnt<<endl;
}int main()
{func1();//ans=40785return 0;
}
试题E：迷宫
最少步数=186
最短路径：
DDDDRRURRRRRRRDRRRDDDLDDRDDDDDDDDDDDDRDRDRRUUURRRRDDDDRDRRRRRURRRDRRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
调试代码：
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
#include <stack>using namespace std;
//优化代码：降低耦合性，增加可扩展性struct Position{int x,y;int pace;//走到改点所需步数int preX,preY;//该点路径上的前一个位置结点Position(){ }Position(int xx,int yy):x(xx),y(yy) {this->preX=x;this->preY=y;this->pace=0;}
};int maze[30][50];
int vis[30][50];
int dir[4][2]={
{-1,0},{0,1},{1,0},{0,-1}};//四个方向：0~3:上 右 下 左
char cdir[4]={'U','R','D','L'};
Position G[30][50];
int row,col;//解题思路：BFSvoid printMaze(){for(int i=0;i<30;i++){for(int j=0;j<50;j++){cout<<maze[i][j]<<" ";}cout<<endl;}
}char dirCurComparedToPre(Position P){for(int i=0;i<4;i++){if(P.preX+dir[i][0]==P.x && P.preY+dir[i][1]==P.y )return cdir[i];}
}void stackTrace(){Position Node=G[row-1][col-1];stack<char> res;while( !(Node.x==Node.preX && Node.y==Node.preY) ){char curDir=dirCurComparedToPre(Node);Node=G[Node.preX][Node.preY];res.push(curDir);}cout<<"路径顺序为："<<endl;while(!res.empty()){char V=res.top();res.pop();cout<<V;}cout<<endl;
}void BFS(int x,int y){memset(vis,0,sizeof(vis));vis[x][y]=1;queue<Position> Q;Position P0(x,y);G[x][y]=P0;Q.push(G[x][y]);while(!Q.empty()){Position V=Q.front();Q.pop();if(V.x==row-1 && V.y==col-1){cout<<V.pace<<endl;break;}for(int i=0;i<4;i++){int nextX=V.x+dir[i][0];int nextY=V.y+dir[i][1];if( (nextX>=0 && nextX<=row-1) && (nextY>=0 && nextY<=col-1) &&maze[nextX][nextY]==0 && vis[nextX][nextY]==0 ){Position next(nextX,nextY);next.preX=V.x;next.preY=V.y;next.pace=V.pace+1;G[nextX][nextY]=next;vis[nextX][nextY]=1;Q.push(G[nextX][nextY]);}}}
}void Read(){//输入30个字符串，每个字符串分解成50个字符cin>>row>>col;//row,col:行,列for(int i=0;i<row;i++){string line;cin>>line;for(int j=0;j<line.size();j++){if(line[j]=='0')maze[i][j]=0;elsemaze[i][j]=1;}}
}int main()
{Read();BFS(0,0);stackTrace();return 0;
}
试题F：特别数的和
草稿：
num=12345
curPos=12345%10=5; num/10=12345/10=1234;
curPos=1234%10=4; num/10=1234/10=123;
curPos=123%10=3; num/10=123/10=12;
curPos=12%10=2; num/10=12/10=1;
curPos=1%10=1; num/10=1/10=0;
AC代码：
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;//用整数法检测，是否含有2、0、1、9
#define n1 2
#define n2 0
#define n3 1
#define n4 9int n;
vector<int> arr;bool check(int num){bool isOk=false;while(num){int curPos=num%10;//定位到当前位置的数if(curPos==n1 || curPos==n2 ||curPos==n3 || curPos==n4 ){isOk=true;break;}num/=10;}return isOk;
}void getArr(){for(int i=0;i<=n;i++)if(check(i))arr.push_back(i);
}void getArrSum(){long long sum=0;for(int i=0;i<arr.size();i++)sum+=arr[i];cout<<sum<<endl;
}int main()
{cin>>n;getArr();getArrSum();return 0;
}
试题G：完全二叉树的权值
调试代码：
#include <iostream>
#include <cmath>using namespace std;//解题思路：层序遍历，求每层权值之和，再求最优值int CBT[100000];//Complete Binary Tree
int N;
long long level[100000];
//tips:第n个结点的深度为[log2 n]+1void Read(){cin>>N;for(int i=0;i<N;i++)cin>>CBT[i];
}int getLevel(int No){return floor(log(No)/log(2))+1;
}void LevelOrderTraversal(){int lev=1;for(int i=0;i<N;i++){lev=getLevel(i+1);level[lev-1]+=CBT[i];}int thisLev=0;long long Maxx=0;for(int i=0;i<lev;i++){int thisMax=level[i];if(thisMax>Maxx){Maxx=thisMax;thisLev=i;}}cout<<thisLev+1<<endl;
}int main()
{Read();LevelOrderTraversal();return 0;
}
试题H：等差数列
调试代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>using namespace std;//解题思路：from最大公差to最小公差，找最短等差数列
//输入数据，需排序
typedef long long LL;
int N;
vector<LL> arr;void Read(){cin>>N;LL num;for(int i=0;i<N;i++){cin>>num;arr.push_back(num);}sort(arr.begin(),arr.end());
}int getMaxDist(){int dist=1e9;for(int i=1;i<arr.size();i++){int curDist=arr[i]-arr[i-1];dist=min(curDist,dist);}return dist;
}void func1(){int MaxDist=getMaxDist();//cout<<MaxDist<<endl;//公差越大，等差数列越短int dist;for(dist=MaxDist;dist>=0;dist--){for(int i=1;i<N;i++){int curD=arr[i]-arr[i-1];if( curD%dist==0 && i==N-1 ){int cnt=(arr[N-1]-arr[0])/dist+1;cout<<cnt<<endl;return;}if(curD%dist!=0)break;}}}int main()
{Read();func1();return 0;
}
试题I：后缀表达式
N+M-M-1+1=N
调试代码：
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 前N+1个较大的正数 使用加法，后面较小的正数和负数使用减法
typedef long long LL;
int N,M;
vector<LL> arr;void Read(){cin>>N>>M;LL num;for(int i=0;i<N+M+1;i++){cin>>num;arr.push_back(num);}sort(arr.begin(),arr.end());
}void func(){LL sum=arr[arr.size()-1];for(int i=arr.size()-2;i>=M;i--){sum+=arr[i];}for(int i=0;i<M;i++){sum-=arr[i];}cout<<sum<<endl;
}int main()
{Read();func();return 0;
}
试题J：灵能传输
适用于前2个测试用例的
Codes：
#include <iostream>
#include <vector>
#include <cmath>using namespace std;typedef long long LL;
int T;
vector<vector<LL> > arr;//二维向量
//解题思路，寻找abs(ai)最大数，将其值分给它两旁相邻的数
//还要考虑分解后，不能产生更大的abs(ai)
vector<LL> res;void Read(){cin>>T;for(int i=0;i<T;i++){LL n;cin>>n;vector<LL> tmp;LL ai;for(int i=0;i<n;i++){cin>>ai;tmp.push_back(ai);}arr.push_back(tmp);}
}int getMaxAbsAiPos(vector<LL>& vkt){int pos=-1;LL maxAbs=-1;for(int i=0;i<vkt.size();i++){LL curAbs=abs(vkt[i]);if(curAbs>maxAbs){maxAbs=curAbs;pos=i;}}return pos;
}void stablize(vector<LL>& vkt){//稳定化 函数 ：减小 vkt中的 元素绝对值的最大值LL maxAbs=1e6;while(true){LL mPos=getMaxAbsAiPos(vkt);LL thisAbs=abs(vkt[mPos]);if(maxAbs<=thisAbs)break;if(maxAbs>thisAbs)maxAbs=thisAbs;if(mPos>0 && mPos<vkt.size()-1){if(vkt[mPos]*vkt[mPos-1]<0){vkt[mPos-2]+=vkt[mPos-1];vkt[mPos]+=vkt[mPos-1];vkt[mPos-1]-=2*vkt[mPos-1];}else if(vkt[mPos]*vkt[mPos+1]<0){vkt[mPos+2]+=vkt[mPos+1];vkt[mPos]+=vkt[mPos+1];vkt[mPos+1]-=2*vkt[mPos+1];}}if(mPos==0){if( (vkt[mPos]>0 && vkt[mPos+1]<0) || (vkt[mPos]<0 && vkt[mPos+1]>0) ){//+,- 和 -，+vkt[mPos]+=vkt[mPos+1];vkt[mPos+2]+=vkt[mPos+1];vkt[mPos+1]-=2*vkt[mPos+1];}}if(mPos==vkt.size()-1){if( vkt[mPos]*vkt[mPos-1]<0 ){vkt[mPos]+=vkt[mPos-1];vkt[mPos-2]+=vkt[mPos-1];vkt[mPos-1]-=2*vkt[mPos-1];}}}res.push_back(maxAbs);
}void func(){for(LL i=0;i<T;i++)stablize(arr[i]);for(LL i=0;i<res.size();i++)cout<<res[i]<<endl;
}void PrintArr(){for(int i=0;i<arr.size();i++){int len=arr[i].size();cout<<"a["<<len<<"]={";for(int j=0;j<len;j++)cout<<arr[i][j]<<" ";cout<<"}"<<endl;}
}int main()
{Read();func();return 0;
}
Complete：2021/4/17