第十届蓝桥杯大赛个人赛省赛（软件类本科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;
}