第十届蓝桥杯大赛个人赛省赛（软件类本科B组）做题笔记Partial
试题A：组队
题目略
Ans=490
解题思路：全排列解题：arr【20】数组，生成5个元素分别赋值为1，2，3，4，5 表示作为首发坑位编号，其余全为0：表示不选择作为首发。
全排列 遍历所有可能的首发阵容：若arr[i]!=0 则选择(i+1) 【因为 i 从 0~19 】号球员 作为 坑位 arr[i] 对应的球员；反之，continue ；得到对应的分值之和，不断比较，求出最大值。
Codes:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int Pnts[20][5]={
{97,90,0,0,0},{92,85,96,0,0},{0,0,0,0,93},{0,0,0,80,86},
{89,83,97,0,0},{82,86,0,0,0},{0,0,0,87,90},{0,97,96,0,0},
{0,0,89,0,0},{95,99,0,0,0},{0,0,96,97,0},{0,0,0,93,98},
{94,91,0,0,0},{0,83,87,0,0},{0,0,98,97,98},{0,0,0,93,86},
{98,83,99,98,81},{93,87,92,96,98},{0,0,0,89,92},{0,99,96,95,81}
};
int arr[20];
int maxPnt=0;
int player[5];
int res[5];
void check(){
int thisPnt=0;
for(int i=0;i<5;i++){
int Plr=player[i];//选手Pos
thisPnt+=Pnts[Plr-1][i];
}
maxPnt=max(thisPnt,maxPnt);
}
int main(int argc, char** argv) {
for(int i=0;i<20;i++){
if(i<5)
arr[i]=i+1;
else
arr[i]=0;
}
sort(arr,arr+20);
do{
for(int i=0;i<20;i++){
int num=arr[i];
if(num!=0){
player[num-1]=i+1;
}
}
check();
}while(next_permutation(arr,arr+20));
cout<<maxPnt<<endl;
return 0;
}
试题B：年号子串
题目略
Excel 解题
Ans=BYQ
试题C：数列求值
Ans=4659
Codes:
#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 move(){
tmp=C+B;
simplify(tmp);
tmp+=A;
simplify(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：数的分解
in thought。。。
试题E：迷宫
题目略
一共186步
Ans=DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUUULLLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
Codes:
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;
struct Point{
int val;
int X,Y;//Point的坐标：行X,列Y
int FX,FY;//BFS遍历得到最短路径 上 当前节点的 上一个节点 :行FX,列FY
int steps;// BFS遍历到当前节点时，走过的步数
Point(){ }
Point(int xx,int yy,int fx=0,int fy=0,int stp=0){
this->X=xx;
this->Y=yy;
this->FX=fx;
this->FY=fy;
this->steps=stp;
}
}G[502][502];//图
int N,M;//N行，M列
int vis[502][502];
int dir[][2]={ {-1,0},{0,1},{1,0},{0,-1} };//顺时针 四个方向：上、右、下、左
queue<Point> Q;
char dir2[4]={'U','R','D','L'};
stack<char> way;
void Read(){
cin>>N;
string samp;
for(int i=1;i<=N;i++){
cin>>samp;
for(int j=1;j<=samp.size();j++){
G[i][j].X=i;//初始化每个 坐标
G[i][j].Y=j;
G[i][j].val=samp[j-1]-'0';
}
}
M=samp.size();
memset(vis,0,sizeof(vis));
}
void PrintG(){
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++)
cout<<G[i][j].val<<" ";
cout<<endl;
}
}
void moveOn(Point P){
for(int i=0;i<4;i++){
int toX=P.X+dir[i][0];
int toY=P.Y+dir[i][1];
if(toX>=1 && toX<=N && toY>=1 && toY<=M && vis[toX][toY]==0 && G[toX][toY].val==0 ){
vis[toX][toY]=1;
Point tmp(toX,toY,P.X,P.Y,P.steps+1);
G[toX][toY]=tmp;
Q.push(G[toX][toY]);
}
}
}
Point BFS(Point S){
vis[S.X][S.Y]=1;
Q.push(S);
while(!Q.empty()){
Point V=Q.front();
Q.pop();
if(V.X==N && V.Y==M)
return V;
moveOn(V);
}
}
char getDir(Point P){//=> 当前节点的上一个节点 相对于 当前节点的方向
for(int i=0;i<4;i++){
if(P.FX+dir[i][0]==P.X && P.FY+dir[i][1]==P.Y){
return dir2[i];
}
}
return 'X';
}
int main(int argc, char** argv) {
Read();
// PrintG();
G[1][1].steps=0;
Point Final=BFS(G[1][1]);
cout<<"Final.steps: "<<Final.steps<<endl;
Point tmp=Final;
while( !(tmp.X==1 && tmp.Y==1) ){
way.push(getDir(tmp));
tmp=G[tmp.FX][tmp.FY];
}
while(!way.empty()){
char c=way.top();
cout<<c;
way.pop();
}
return 0;
}
试题F：特别数的和
题目略
Codes：
#include <iostream>
#include <sstream>
#include <string.h>
using namespace std;
int n;//n<=10000
//数字中 包含 2、0 、1、9 的
string ItoS(int x){
ostringstream is;
is<<x;
return is.str();
}
bool check(int num){
string sn=ItoS(num);
int len=sn.size();
for(int i=0;i<len;i++){
if(sn[i]=='2' || sn[i]=='0' || sn[i]=='1' || sn[i]=='9')
return true;
}
return false;
}
int main(int argc, char** argv) {
cin>>n;
long long sum=0;
for(int i=1;i<=n;i++){
if(check(i))
sum+=i;
}
cout<<sum<<endl;
return 0;
}
试题G：完全二叉树的权值
题目略
Codes:
#include <iostream>
#include <cmath>
using namespace std;
//深度为k的二叉树，最多有节点 2^k -1 个
int tree[100006];
int n;
int level(int nodes){
return ceil( log(nodes+1)/log(2) );
}
int KthTotalNodes(int lvl){
return pow(2,lvl)-1;
}
int main(int argc, char** argv) {
cin>>n;
for(int i=1;i<=n;i++)
cin>>tree[i];
int lvl=level(n);
int amt[lvl+1];
for(int i=1;i<=lvl;i++){//完全二叉树 ，每层最多2^(k-1)个 节点
if(i<lvl){
for(int j=KthTotalNodes(i)+1;j<=pow(2,i-1)+KthTotalNodes(i);j++){
amt[i]+=tree[j];
}
}
else{
for(int j=KthTotalNodes(i)+1;j<=n;j++){//最后一层
amt[i]+=tree[j];
}
}
}
int thismax=0;
int pos=-1;
for(int i=1;i<=lvl;i++){
if(amt[i]>thismax){
thismax=amt[i];
pos=i;
}
}
cout<<pos<<endl;
return 0;
}
试题H：等差数列
题目略
Codes:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
LL N;
vector<LL> arr;
LL mind=1e9;//最小公差
int main(int argc, char** argv) {
cin>>N;
for(LL i=0;i<N;i++){
LL x;
cin>>x;
arr.push_back(x);
}
sort(arr.begin(),arr.end());
for(LL i=1;i<N;i++){
LL thisd=arr[i]-arr[i-1];
mind=min(mind,thisd);
}
LL cnt=0;
for(LL i=arr[0];;i+=mind){
cnt++;
if(i==arr[N-1])
break;
}
cout<<cnt<<endl;
return 0;
}
试题I：后缀表达式
题目略
Codes：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
LL N,M;//N各加号，M个减号，以及N+M+1个整数
vector<LL> arr;
int main(int argc, char** argv) {
cin>>N>>M;
for(int i=1;i<=N+M+1;i++){
LL x;
cin>>x;
arr.push_back(x);
}
sort(arr.begin(),arr.end());
LL sum=0;
LL cnt=-1;
for(LL i=arr.size()-1;i>=0;i--){
sum+=arr[i];
cnt++;
if(cnt==N)
break;
}
for(LL i=0;i<M;i++){
sum-=arr[i];
}
cout<<sum<<endl;
return 0;
}