蓝桥赛题BASIC

title: 蓝桥赛题BASICdate: 2021-1-20 1：07：41
tags: C++
categories: 蓝桥赛练习

求1+2+3+…+n的值

long long result = (1 + n) * n / 2 //避免数据规模过大

求Fibonacci数列%10007

F[i] = (F[i - 1] + F[i - 2]) % 10007  //直接求余数而不先求数值再求余数

杨辉三角形

#include <iostream>
using namespace std;
/*杨辉三角形 
1  i = 0  j = /0
1 1  i = 1  j = /0
1 2 1  i = 2  j = 1~1
1 3 3 1  i = 3 j = 1~2
1 4 4 4 1
*/
const int N = 40; 
int main(){
    int n;
    cin>>n;
    int i,j;
    int a[N][N];
    for(i = 0;i < n;i++){
        a[i][0] = a[i][i] = 1;
        for(j = 1;j < i;j++){
            a[i][j] = a[i-1][0] + a[i-1][1];
        }
    }
    for(i = 0;i < n;i++){
        cout<<a[i][0];
        for(j = 1;j <= i;j++){
            cout<<" "<<a[i][j];
        }
        cout<<endl;
    }
    return 0;
}

16进制转10进制

#include <iostream>
#include <string>
using namespace std;
/*
16进制转10进制  
10 11 12 13 14 15
A  B  C  D  E  F
*/
int main(){
    string s;
    cin>>s;
    int len = s.length();
    int i;
    long long sum = 0;
    for(i = 0;i < len;i++){
        if('A' <= s[i] && s[i] >= 'F'){
            sum = sum * 16 + s[i] - 'A' + 10;
        }else{
            sum = sum * 16 + s[i] - '0';
        }
    }
    cout<<sum<<endl;
    return 0;
}

10进制转16进制

#include <iostream>
using namespace std;
const int N = 40;
int main(){
    int n;
    cin>>n;
    char a[N];
    int i = 0;
    if(n == 0){
        cout<<"0";
    }else{
        while(n){
            if(n % 16 >= 10){
                a[i++] = 'A' + n % 16 - 10;
            }else{
                a[i++] = '0' + n % 16;
            }
            n /= 16;
        }
    }
    for(i -= 1;i >= 0;i--)
        cout<<a[i];
    return 0;
}

数列排序

问题描述

给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200
输⼊格式
　　第一行为一个整数n。
　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。
样例输入
5
8 3 6 4 9
样例输出
3 4 6 8 9

#include <iostream>
#include <algorithm>
using namespace std;
int cmp(int a,int b){
    return a < b;
}
int main(){
    int n;
    cin>>n;
    int a[201];
    int i;
    for(i = 0;i < n;i++){
        cin>>a[i];
    }
    sort(a,a+n,cmp);
    i = 0;
    cout<<a[i];
    for(i = 1;i < n;i++)
        cout<<" "<<a[i];
    return 0;
}

心得：< algorithm >里的sort函数

时间转换

#include <iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    int m,h,s;
    m = h = s = 0;
    h = t / 3600;
    t = t % 3600;
    m = t / 60;
    s = t % 60;
    cout<<h<<":"<<m<<":"<<s<<endl;
    return 0;
}

心得：位运算就是权运算

字符串对比

#include <iostream>
#include <string>
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    int lena = a.length();
    int lenb = b.length();
    //1：两个字符串长度不等。
    if(lena != lenb){
        cout<<1;
        return 0;
    }
    //2：两个字符串不仅长度相等，且相应位置上的字符完全一致(区分大小写)
    if(a == b){
        cout<<2;
        return 0;
    }
    //4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。
    int i;
    for(i = 0;i < lena;i++){
        a[i] = tolower(a[i]);
        b[i] = tolower(b[i]);
        if(a[i] != b[i]){
            cout<<4;
            return 0;
        }
    }
    //3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致
    cout<<3;
    return 0;
}

分解质因数

问题描述

求出区间[a,b]中所有整数的质因数分解。
输入格式
输出两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1_a2_a3…(a1<=a2<=a3…，k也是从小到大的)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=2_2_2
9=33
10=25
思路来自

#include<iostream>
using namespace std;
void divide(int x){
    cout<<x<<"=";
    int i;
    bool flag = 1;
    for(i = 2;i <= x;i++){
        while(x % i == 0){
            if(flag){cout<<i;flag = 0;}
            else{
                cout<<"*"<<i;
            }
            x /= i;
        }
    }
    cout<<endl;
}
int main(){
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        divide(i);
    }
    return 0;
}

心得：跟进制转换类似

矩阵乘法

问题描述

给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
　　例如：
　　A =
　　1 2
　　3 4
　　A的2次幂
　　7 10
　　15 22
输入格式
　　第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
　　接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值
输出格式
　　输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开
样例输入
2 2
1 2
3 4
样例输出
7 10
15 22

#include<iostream>
using namespace std;
int main(){
    long long int a[40][40];
    long long int t[40][40];
    int i,j,n,m;
    cin>>n>>m;
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            cin>>a[i][j];
            t[i][j] = 0;
        }
    }
    //矩阵的0次幂输出单位矩阵
     for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            if(i == i) cout<<1<<' ';
            else cout<<0<<' ';
        }
        cout<<endl;
    }
    //非0次幂
    int k;
    long long sum = 0;
    while(--m){
        for(i = 0;i < n;i++){
            for(j = 0;j < n;j++){ 
                for(k = 0;k < n;k++){
                    t[i][j] += a[i][k] * a[k][j];
                }
            }
        }    
    } 
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            cout<<t[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

完美的代价

问题描述

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。
现在给你两个串，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (完美！)
输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N，只包含小写字母
输出格式
如果可能，输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
分析：
1.impossible的情况：
串的长度为偶数，且有一个或一个以上的字符为唯一字符
串的长度任意，有两个或两个一以上的字符为唯一字符
2.在n为奇数，且只有一个字符是唯一字符的情况下，当然这种情况是要计算最小交换次数的，
但是在检测到该唯一字符时，不对它进行移位（移动到字符串的中心位置）操作，而对它先忽视，直到其他的字符都检测处理完毕
因为若是把它移动到中间位置，继续计算时，假设有两个相同的字符位于中间该字符的两边，利用冒泡排序的过程中会把该字符后移，
这会消耗交换数，而且还可能带来重复检测到该字符再重复位移处理的问题，在顺序存储中，由于可以根据下标随机访问，所以先无
视该字符，计算的最后再把它冒泡位移到中间位置才能求得最短的交换数

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    int N;
    cin>>N;
    cin>>s;
    int len = s.length();  //这个len计算过程中会变化 
    int num = 0;  //0表示未检测到唯一字符 
    int i,j,k;
    int cnt = 0;
    for(i = 0;i < len-1;i++){
        for(j = len-1;j >= i;j--){
            if(i == j){
                num++;
                if(N % 2 == 0 || num > 1){  //两种Impossible的情况
                    cout<<"Impossible"<<endl; 
                    return 0;
                }else{  //只有一个唯一字符，且串长度为奇数 
                    cnt += N / 2 - i;
                } 
            }else if(s[i] == s[j]){
                for(k = j;k < len-1;k++){
                    s[k] = s[k + 1];
                    cnt++;
                    cout<<"第"<<cnt<<"次:"<<s<<endl;
                }
                s[len-1] = s[i];
                cout<<"结果："<<s<<endl;
                len--;  //冒泡法固定了一个末尾字符的位置 
                break;
            }
        }
    }    
    cout<<"总共交换次数："<<cnt;
    return 0;
}

心得：这道题是我苦手的字符串问题，把串变为回文串的过程是冒泡法从串的尾端固定字符的过程，每固定一个字符，要处理的串就少了两位（i++&&len—），此外检测到唯一字符的处理也有点技巧

数的读法

问题描述

给定一个阿拉伯数字串，你帮他按照中文读写的规范转为汉语拼音字串
注意必须严格按照规范，比如说“10010”读作“yi wan ling yi shi”而不是“yi wan ling shi”，“100000”读 作“shi wan”而不是“yi shi wan”，“2000”读作“er qian”而不是“liang qian”。
输入格式
字符串，数值大小不超过2,000,000,000。
输出格式
是一个由小写英文字母，逗号和空格组成的字符串，表示该数的英文读法。
样例输入
1234567009
样例输出
shi er yi san qian si bai wu shi liu wan qi qian ling jiu

#include <iostream>
#include <string> 
using namespace std;
string num[10] = { "ling ","yi ","er ","san ","si ","wu ","liu ","qi ","ba ","jiu " };
string levels[3] = { "ge","wan ","yi " };
string basic[3] = { "shi ","bai ","qian " };
int main() {
    string s;
    cin >> s;
    string ans;
    int i, j;
    int len = s.length();
    int zeroFlag = 0;  //处理读连续0问题 
    int level = 0;  //数据量级 
    int basciCount;  //分段处理进度 
    int headCount = 0;  //区分"shi "与"yi "的情况 
    //判断数据量级 
    if (len >= 9) level = 2;
    else if (len >= 5) level = 1;
    else level = 0;
    //全局处理进度 
    int process = 0;
    //分段处理 
    while (level >= 0) {
        zeroFlag = 0;  //默认前面不是0   
        if(len <= 4) j = len;
        else{
            j = len - (4 * level);
            len -= j;
        } 
        basciCount = j;
        for (i = process; i < process + j; i++) {
            if (s[i] - '0' == 0) {  //是0 
                zeroFlag = 1;  //记录为0字符 
            }
            else {   //不是0 
                if(zeroFlag == 1) 
                    ans += "ling ";
                if(s[i] - '0' == 1 && headCount == 0 && j == 2){  //是1 是首字符 是shi 
                    ans += "shi ";
                }else{   
                    ans += num[s[i] - '0'];
                    if (basciCount >= 2) {
                        ans += basic[basciCount - 2];  //单个字符单位 shi bai qian 
                    }
                }
                headCount = 1;  //表示已处理头字符 
                zeroFlag = 0;  //记录为非0字符 
            }
            basciCount--;  //处理完一个字符更新进度 
        }
        process += j;  //处理完一个基础段更新总进度 
        if (level >= 1) ans += levels[level];  //每个量级的单位:ge(不计) wang yi  
        level--;  //处理完一个量级更新进度 
    }
    cout<<ans<<endl;
    return 0;
}

心得：

1. 分别判断读取 字符本身num 单个字符单位 每个量级单位

2. 分段处理，basciCount记录在段中的处理进度，process记录总的处理进度

3. 0问题：遇到0不读，用zeroFlag记录前一个字符，若读到非0字符，根据前一个字符读入”ling “

4. 位于首的10读”shi “,反之，读”yi shi “;

FJ的字符串

问题描述

FJ在沙盘上写了这样一些字符串：
A1 = “A”
A2 = “ABA”
A3 = “ABACABA”
A4 = “ABACABADABACABA”
输入格式
仅有一个数：N ≤ 26。
输出格式
请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

#include <iostream>
#include <string> 
using namespace std;
string func(int n){
    if(n == 1) return "A";
    else{
        return func(n-1) + (char)('A' + n - 1) + func(n-1);
    }
}
int main() {
    string s;
    int n;
    cin>>n;
    s = func(n);
    cout<<s;
    return 0;
}

心得：(char)(‘A’ + n - 1)

BASIC-23. 芯片测试

#include <iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int i,j,sum;
    int a[20][20];
    for(i = 0;i < n;i++){
        sum = 0;
        for(j = 0;j < n;j++){
            cin>>a[i][j];
            if(i != j && a[i][j]) sum++;
        }
        if(sum >= n/2) cout<<i + 1<<' ';
    }
    return 0;
}

BASIC-24. 龟兔赛跑预测

#include <iostream>
using namespace std;
int main() {
    int v1,v2,t,s,l;
    int i;
    int ra = 0,te = 0;
    int t1 = 0,t2 = 0;
    cin>>v1>>v2>>t>>s>>l;
    while(1){
        if(ra >= l && te < l) {cout<<"R "<<endl<<t1;break;}
        else if(te >= l && ra < l) {cout<<"T "<<endl<<t2;break;}
        else if(ra >= l && te >= l){cout<<"D "<<endl<<t1;break;}
        while((ra - te) >= t){
            te  = te + s * v2;
            t2 += s;
            t1 += s;
        }
        if(ra >= l && te < l) {cout<<"R "<<endl<<t1;break;}
        else if(te >= l && ra < l) {cout<<"T "<<endl<<t2;break;}
        else if(ra >= l && te >= l){cout<<"D "<<endl<<t1;break;}
        ra += v1;
        te += v2;
        t1++;
        t2++;
    }
    return 0;
}

BASIC-25. 回形取数

#include <iostream>
using namespace std;
int main() {
    int m,n,i,j;
    int a[201][201] = {-1};
    cin>>m>>n;
    for(i = 0;i < m;i++){
        for(j = 0;j < m;j++){
            cin>>a[i][j];
        }
    }
    //打印 
    for(i = 0;i < m;i++){
        for(j = 0;j < m;j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
    int total = 0;
    i = 0; j = 0;
    while(total < m*n){
        //down
        while(i <= m-1 && a[i][j] != -1){
            cout<<a[i][j]<<' ';
            a[i][j] = -1;
            total++;
            i++;
        }
        i--;
        j++;
        //right
        while(j <= n-1 && a[i][j] != -1){
            cout<<a[i][j]<<' ';
            a[i][j] = -1;
            total++;
            j++;
        }
        j--;
        i--;
        //up
        while(i >= 0 && a[i][j] != -1){
            cout<<a[i][j]<<' ';
            a[i][j] = -1;
            total++;
            i--;
        }
        i++;
        j--;
        //left
        while(j >= 0 && a[i][j] != -1){
            cout<<a[i][j]<<' ';
            a[i][j] = -1;
            total++;
            j--;
        }
        j++;
        i++;
    }
    return 0;
}

心得：一开始用四个标识表示读取方向，并且为第一个数的打印发愁，跟上述做法比起来武德不充沛！

BASIC-26. 报时助手

问题描述

输入格式
　　输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。
输出格式
　　输出时间时刻的英文

#include <iostream>
#include <string>
using namespace std;
int main() {
    string num[24] = {
    "zero", "one", "two", "three", "four", "five",
    "six", "seven", "eight", "nine", "ten", "eleven",
    "twelve", "thirteen","fourteen", "fifteen", "sixteen", "seventeen",
    "eighteen", "nineteen", "twenty", "twenty one", "twenty two", "twenty three"
    };
    int h,m;
    cin>>h>>m;
    cout<<num[h]<<' ';
    if(m == 0)
        cout<<"o’clock";
    else{
        int t = m % 10;
        m = m / 10;
        switch(m){
            case 0:
                cout<<num[t];  //已排除t = 0的情况 
                break;
            case 1:
                cout<<num[10 + t];break;
            case 2:
                cout<<"twenty ";
                if(t) cout<<num[t];
                break;
            case 3:
                cout<<"thirty ";
                if(t) cout<<num[t];
                break;
            case 4:
                cout<<"forty ";
                if(t) cout<<num[t];
                break;
            case 5:
                cout<<"fifty ";
                if(t) cout<<num[t];
                break;
        }
    }
    return 0;
}

心得：主要注意分离出分钟数的个位数t后，对t = 0进行区别处理

BASIC-27. 2n皇后问题

问题描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，
使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int cnt = 0;
//issafe
bool issafe(vector<int> pos,int row){
    int i;
    for(i = 0;i < row;i++){
        if(pos[i] == pos[row] || abs(i - row) == abs(pos[i] - pos[row]))
            return false;
    }
    return true;
}
//blackdfs
void blackdfs(vector<vector<int> > blackMap,vector<int> blackPos,int n,int blackRow){
    if(blackRow == n){
        cnt++;
        return;
    }
    for(blackPos[blackRow] = 0;blackPos[blackRow] < n;blackPos[blackRow]++){
        if(blackMap[blackRow][blackPos[blackRow]] == 1 && issafe(blackPos,blackRow))
            blackdfs(blackMap,blackPos,n,blackRow + 1);  //黑皇后递归
    }
    return; 
}
//dfs
void dfs(vector<vector<int> > map,vector<int> pos,int n,int row){
    if(row == n){
        int i,j;
        vector<vector<int> > blackMap(n,vector<int>(n));
        vector<int> blackPos(n);
        for(i = 0;i < n;i++){
            for(j = 0;j < n;j++){
                blackMap[i][j] = map[i][j];  
            } 
        }
        for(i = 0;i < n;i++){
            blackMap[i][pos[i]] = 0;
        }
        blackdfs(blackMap,blackPos,n,0);  //引用黑皇后递归 
        return;
    }
    for(pos[row] = 0;pos[row] < n;pos[row]++){
        if(map[row][pos[row]] == 1 && issafe(pos,row))
            dfs(map,pos,n,row + 1);  //白皇后递归 
    }
    return;
}
//main
int main(){
    int n;
    cin>>n;
    int i,j;
    vector<vector<int> > map(n,vector<int>(n));
    vector<int> pos(n);
    for(i = 0;i < n;i++){
        for(j = 0;j < n;j++){
            cin>>map[i][j];
        }
    }
    dfs(map,pos,n,0);  //引用白皇后递归
    cout<<cnt;
    return 0;
}

心得：如果会单个N皇后的问题这道题就明朗了，做法是dfs完白皇后，将初始棋盘赋值给新建的黑皇后棋盘，再将白皇后的位置标示为0，再调用黑皇后的dfs。此外，在之前做单皇后问题时，我的做法是：下棋时改变棋盘Map，用栈存储已经下在棋盘上的棋子，判断函数issafe要传入棋盘，棋子，棋盘大小三种参数，比较复杂，且之前的做法在递归方面也繁琐，现在的做法显然更优，repeat加深理解

BASIC-29. 高精度加法

问题描述

　输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

#include <iostream>
#include <string>
using namespace std;
void printArry(int t[],int len){
    for(int i = len - 1;i >= 0;i--){
        cout<<t[i];
    }
    cout<<endl;
}
int main(){
    string a,b;
    int A[100];
    int B[100];
    int C[101];
    int temp = 0;
    cin>>a>>b;
    int i,j;
    int lena = a.length();
    int lenb = b.length();
    for(i = lena - 1,j = 0;i >= 0;i--){
        A[j++] = a[i] - '0';
    }
    //printArry(A,lena);
    for(i = lenb - 1,j = 0;i >= 0;i--){
        B[j++] = b[i] - '0';
    }
    //printArry(B,lenb);
    for(i = 0;i < lena && i < lenb;i++){
        C[i] = (A[i] + B[i] + temp) % 10;
        temp = (A[i] + B[i] + temp) / 10;
    }
    while(i < lena){
        C[i] = (A[i] + temp) % 10;
        temp = (A[i] + temp) / 10;
    }
    while(i < lenb){
        C[i] = (B[i] + temp) % 10;
        temp = (B[i] + temp) / 10;
    }
    if(temp)
        C[i] = temp;
    for(i = i - 1;i >= 0;i--){
        cout<<C[i];
    }
    return 0;
}

心得：旧题重刷，之前我用< algorithm >里的reverce(a,a + lena);函数来倒置字符串，这次用倒叙输入，其实更加简便

BASIC-30. 阶乘计算

问题描述

输入一个正整数n，输出n!的值。
其中n!=12_3…_n。
输入格式
　　输入包含一个人正整数n，n<=1000。
输出格式
　　输出n!的准确值。
样例输入
10
样例输出
3628800

#include <iostream>
using namespace std;
int main() {
    int a[10000] = { 1 };  
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {  //每个数位上的数都乘一次i 
        for (int j = 0; j < 10000; j++) {
            a[j] *= i;
        }
        for (int i = 0; i < 10000; i++) {  //为避免每个位上的数值过大，每乘一次就相加进位整理一次 
            if (a[i] > 9) {
                a[i + 1] += a[i] / 10;
                a[i] = a[i] % 10;
            }
        }
    }
    int i = 999;
    while(a[i] == 0) --i;
    for(;i >= 0;i--){
        cout<<a[i];
    }
    return 0;
}

心得:之前也做过大数阶乘，但是做法相当繁琐，此次用柳大的方法做，类似的大数处理题，或是类似的，利用数组处理庞大数据的题目也要多留意解题思路