蓝桥杯初步C++（小计算器+合根植物）

程序员文章站 2022-06-08 22:22:20

...

文章目录

前言
一、小计算器
二、合根植物
总结

前言

蓝桥杯练习第一天，练习题目【小计算器】【合根植物】

一、小计算器

1.题目详情

题目链接
模拟程序型计算器，依次输入指令，可能包含的指令有
　　1. 数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
　　2. 运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
　　3. 进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
　　4. 输出指令：‘EQUAL’，以当前进制输出结果
　　5. 重置指令：‘CLEAR’，清除当前数字
指令按照以下规则给出：
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
　　运算指令后出现的第一个数字，表示参与运算的数字。
　　且在该运算指令和该数字中间不会出现运算指令和输出指令
　　重置指令后出现的第一个数字，表示基础值。
　　且在重置指令和第一个数字中间不会出现运算指令和输出指令
　　进制转换指令可能出现在任何地方
　　运算过程中中间变量均为非负整数，且小于2^63。
　　以大写的’A’—Z’表示10~35
输入格式
　　第1行：1个n，表示指令数量
　　第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR‘作为开始，满足指令规则
输出格式
　　依次给出每一次’EQUAL'得到的结果
样例输入

7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL

样例输出

2.问题分析

此题目为经典的进制转换，但是需要注意的是需要有两个进制转化函数，分别为changeten目的是将n进制形式的字符串转换为10进制的数，以便于之后的运算。changea目的是将运算完的十进制再转换为字符串形式的n进制，以便于之后的EQUAl输出结果，下面附上完整AC代码，以及注释。
题目上的坑我在注释中已经解释

3.详细代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int caozuo=1;//默认为
long long int changeten(int n,string b)//用来转换成10进制的数
{
    long long int ans=0;
    for(int i=0; i<b.size(); i++)
    {
        char t=b[i];
        if(t>='0'&&t<='9') //0-9的情况，直接减去'0'就是它的”绝对值“
            ans=ans*n+t-'0';
        else//其他情况就是A-Z的情况了，这个情况需要减去A来获得数的”绝对值“
            ans=ans*n+t-'A'+10;
    }
    return ans;
}
string changea(int n,long long int b)
{
    string res="";
    do
    {
        int t=b%n;//取出最后一位数
        if(t>=0&&t<=9)
            res+=t+'0';
        else
            res+=t-10+'A';
        b/=n;
    }
    while(b!=0); //使用do while 循环可以在只有一位数的情况下正确的赋值
    reverse(res.begin(),res.end());
    return res;
}

int main()
{
    string ch;
    int n;
    cin>>n;
    long long int a=0;
    int index=10;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>ch;
        if(ch=="CLEAR")
        {
            a=0;
            s="";
            caozuo=1;
            //此处有坑，每一次CLEAR之后后面的NUM一定等价于0+NUM，所以每次进行CLEAR之后要变更为ADD形式
            //index=10;
        }
        else if(ch=="NUM")
        {
            string str2;
            cin>>str2;
            long long int cnt=changeten(index,str2);
            //之后的步骤为各个操作
            if(caozuo==1)
            {
                a+=cnt;
            }
            else if(caozuo==2)
            {
                a-=cnt;
            }
            else if(caozuo==3)
            {
                a*=cnt;
            }
            else if(caozuo==4)
            {
                a/=cnt;
            }
            else if(caozuo==5)
            {
                a%=cnt;
            }
            //最后将a的结果转换为该进制下的字符串
            s=changea(index,a);
        }
        else if(ch=="ADD")//add 1
        {
            caozuo=1;

        }
        else if(ch=="SUB")
        {
            caozuo=2;
        }
        else if(ch=="MUL")
        {
            caozuo=3;

        }
        else if(ch=="DIV")
        {
            caozuo=4;

        }
        else if(ch=="MOD")
        {
            caozuo=5;

        }
        //改变进制，只需把s重新赋值
        else if(ch=="CHANGE")
        {
            cin>>index;
            s=changea(index,a);
        }
        else if(ch=="EQUAL")
        {
            cout<<s<<endl;
        }
    }
    return 0;
}

二、合根植物

题目链接

1.题目详情

问题描述
　　w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
　　这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
　　如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入格式
　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
　　接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
　　接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。
　　比如：5 * 4 的小格子，编号：
　　1 2 3 4
　　5 6 7 8
　　9 10 11 12
　　13 14 15 16
　　17 18 19 20
样例输入

样例输出

样例说明
　　其合根情况参考下图
蓝桥杯初步C++（小计算器+合根植物）

2.问题分析

此题目为经典的并查集问题，根据题目样例说明更能体现，这里不过多赘述，直接引入一个大佬的教程供大家学习一下吧！
并查集详解

3.详细代码

#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1000001;
int pre[maxn];
int m,n;
int total;
void init()
{
    for(int i=1; i<=m*n; i++)
        pre[i]=i;
}
int union_1(int root)//union_1函数起连接，并且最后返回此节点的根节点
{
    int son,tmp;
    son=root;
    //找到它的根节点
    while(root!=pre[root])
    {
        root=pre[root];
    }
    //把此路上的所有结点的根节点都指向最后的根
    while(son!=root)
    {
        //cout<<"111111"<<endl;
        tmp=pre[son];
        pre[son]=root;
        son=tmp;
    }
    //返回他们的老大
    return root;
}
//添加2个点
void join(int root1,int root2)
{
    int x,y;
    x=union_1(root1);
    y=union_1(root2);
    //如果两个点的老大不一样，那么就让y的老大变成x的老大
    if(x!=y)
    {
        pre[x]=y;
        total--;//整体的集体数-1
    }

}
int main()
{

    cin>>m>>n;
    total=m*n;//初始时，有m*n的集体
    int cnt;
    cin>>cnt;
    init();
    for(int i=0; i<cnt; i++)
    {
        int x,y;
        cin>>x>>y;
        join(x,y);
    }
    //最后输出多少个集体
    cout<<total<<endl;
    return 0;
}

总结

这两个题目都是备战蓝桥杯的必备算法，通过题目我们应该充分掌握这些知识点，查缺补漏，蓝桥杯大家加油！