蓝桥杯练习（四）

超、凢脫俗 2023-07-18 14:17 15阅读 0赞

### 蓝桥杯练习（四） ###

*   *   *  小计算器
         *  兰顿蚂蚁
         *  带分数
         *  幸运数
         *  买不到的数目
         *  参考博客

### 小计算器 ###

**问题描述**  
　　模拟程序型计算器，依次输入指令，可能包含的指令有  
　　1. 数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数  
　　2. 运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余  
　　3. 进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)  
　　4. 输出指令：‘EQUAL’，以当前进制输出结果  
　　5. 重置指令：‘CLEAR’，清除当前数字

指令按照以下规则给出：  
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出  
　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令  
　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令  
　　进制转换指令可能出现在任何地方  
　　运算过程中中间变量均为非负整数，且小于263。  
　　以大写的’A’~'Z’表示10~35  
**输入格式**  
　　第1行：1个n，表示指令数量  
　　第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则  
**输出格式**  
　　依次给出每一次’EQUAL’得到的结果

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    /** * @brief 将radix进制的数字串a转换为10进制数字 */
    ll toD(string a, int radix){ 
        //cout<<a<<" :R "<<radix<<" ";
        ll sum  = 0;
        for(int i=0;i<a.size();++i){ 
            if(a[i]>='A')a[i]=a[i]-'A'+10+'0';
            sum = sum*radix+a[i]-'0';
        }
        //cout<<sum<<endl;
        return sum;
    }
    
    /** * @brief 将10进制数字num转换为radix进制的数字串 */
    string toX(ll num ,int radix){ 
        //cout<<num<<" X "<<radix<<" ";
        string a = "";
        int d;
        while(num){ 
            d = num%radix;
            if(d>9)a=char(d+'A'-10)+a;
            else a = char(d+'0')+a;
            num/=radix;
        }
        if(a.size()==0)a="0";
        //cout<<a<<endl;
        return a;
    }
    
    
    int main(){ 
       std::ios::sync_with_stdio(false);
       cin.tie(0);
       int n;
       cin>>n;
       string s,a;//指令，数字串
       ll num=0,d;//当前数字
       int radix=10;//当前进制
       int op=-1 ;// -1 无， 1 加 2 减 3 乘 4 除 5 余
       while (n--){ 
           //cout<<"n:"<<n<<":"<<num<<endl;
           cin>>s;
           if(s=="CLEAR")num=0;
           else if(s=="CHANGE")cin>>radix;
           else if(s=="EQUAL")cout<<toX(num,radix)<<endl;
           else if(s=="ADD") op = 1;
           else if(s=="SUB") op = 2;
           else if(s=="MUL") op =3;
           else if(s=="DIV") op = 4;
           else if(s=="MOD") op = 5;
           else if(s=="NUM"){ 
               cin>>a;
               d = toD(a,radix);
               switch (op){ 
                    case 1: num += d;  break;
                    case 2: num -= d;  break;
                    case 3: num *= d; break;
                    case 4: num /=d; break;
                    case 5: num%=d; break;
                    case -1:num=d; break;
               }
               op = -1;
           }
       }
    }

### 兰顿蚂蚁 ###

**问题描述**  
　兰顿蚂蚁，是于1986年，由克里斯·兰顿提出来的，属于细胞自动机的一种。

平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一只“蚂蚁”。  
　　蚂蚁的头部朝向为：上下左右其中一方。

蚂蚁的移动规则十分简单：  
　　若蚂蚁在黑格，右转90度，将该格改为白格，并向前移一格；  
　　若蚂蚁在白格，左转90度，将该格改为黑格，并向前移一格。

规则虽然简单，蚂蚁的行为却十分复杂。刚刚开始时留下的路线都会有接近对称，像是会重复，但不论起始状态如何，蚂蚁经过漫长的混乱活动后，会开辟出一条规则的“高速公路”。

蚂蚁的路线是很难事先预测的。

你的任务是根据初始状态，用计算机模拟兰顿蚂蚁在第n步行走后所处的位置。  
**输入格式**  
　　输入数据的第一行是 m n 两个整数（3 < m, n < 100），表示正方形格子的行数和列数。  
　　接下来是 m 行数据。  
　　每行数据为 n 个被空格分开的数字。0 表示白格，1 表示黑格。

接下来是一行数据：x y s k, 其中x y为整数，表示蚂蚁所在行号和列号（行号从上到下增长，列号从左到右增长，都是从0开始编号）。s 是一个大写字母，表示蚂蚁头的朝向，我们约定：上下左右分别用：UDLR表示。k 表示蚂蚁走的步数。

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 100;
    int g[MAXN][MAXN];
    int m,n;//表示正方形格子的行数和列数。
    int x,y,s,k;//蚂蚁所在行号和列号,上下左右(0,1,2,3),k表示蚂蚁走的步数。
    char S;//表示蚂蚁头的朝向 上下左右分别用：UDLR表示
    int pos[4][2]={ { -1,0},{ 1,0},{ 0,-1},{ 0,1}};//移动方向的坐标变化
    /** * @brief 将UDLR 转换成数字表示 */
    void f(){ 
        string str = "UDLR";
        for(int i=0;i<4;++i)if(str[i]==S)s=i;
    }
    
    void dfs(){ 
        f();
        int hei[]={ 3,2,0,1};//在黑色格子里的方向变化
        int bai[]={ 2,3,1,0};//在白色格子里的方向变化
        while(k--){ 
            //cout<<"k="<<k<<" x="<<x<<" y="<<y<<" s="<<s<<endl;;
            if(g[x][y]==1){ 
                g[x][y]=0;
                s = hei[s];  
            }else{ 
                g[x][y]=1;
                s=bai[s];
            }
            x += pos[s][0];
            y += pos[s][1];
        }
        cout<<x<<" "<<y;
    }
    
    
    int main(){ 
        std::ios::sync_with_stdio(false);
        cin.tie(0);
        
        cin>>m>>n;
        for(int i=0;i<m;++i){ 
            for(int j=0;j<n;++j)cin>>g[i][j];
        }
        cin>>x>>y>>S>>k;
        dfs();
        return 0;
    }

### 带分数 ###

**问题描述**  
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。  
还可以表示为：100 = 82 + 3546 / 197。  
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。  
类似这样的带分数，100 有 11 种表示法。  
**输入格式**  
从标准输入读入一个正整数N (N<1000\*1000)

#include <bits/stdc++.h>
    using namespace std;
    
    int main(){ 
        int a[9],n=9;
        for(int i=0;i<n;++i)a[i]=i+1;
        int x,ans=0;
        cin>>x;
        int a1,a2,a3;// x==a1+a2/a3
        do{ 
            for(int i=1;i<n;++i){ 
                a1=0;
                for(int j=0;j<i;++j)a1=a1*10+a[j];
                if(a1>=x)break;//优化
                for(int t=i+1;t<n;++t){ 
                    a2=a3=0;
                    for(int j=i;j<t;++j)a2=a2*10+a[j];
                    for(int j=t;j<n;++j)a3=a3*10+a[j];
                    if(a2%a3==0&&a1+a2/a3==x){ 
                        //cout<<a1<<"+"<<a2<<"/"<<a3<<endl;
                        ans++;
                    }
                }
            }
        } while (next_permutation(a,a+n));
        cout<<ans;
        return 0;
    }

### 幸运数 ###

**问题描述**  
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成

。  
首先从1开始写出自然数1,2,3,4,5,6,…

1 就是第一个幸运数。

我们从2这个数开始。把所有序号能被2整除的项删除，变为：

1 \_ 3 \_ 5 \_ 7 \_ 9 …

把它们缩紧，重新记序，为：

1 3 5 7 9 … 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, …

此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,…)

最后剩下的序列类似：

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …

**输入格式**  
输入两个正整数m n, 用空格分开 (m < n < 1000\*1000)

#include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e6;
    int a[MAXN/2+1];
    int main(){ 
        int k=1,L;//k筛选过程数组下标变化，L数组长度
        for(int i=1;i<MAXN;i+=2)a[k++]=i;
        int iter = 2; //iter迭代次数
        int cnt=0,T;//计数
        while(true){ 
            L = k;
            k = 1;
            T = a[iter++];
            cnt=0;//初始化
            for(int i=1;i<L;++i){ 
                cnt++;
                if(cnt==T)cnt=0;
                else a[k++]=a[i];
            }
            if(k==L)break;
           
        }
        // for(int i=1;i<20;++i)cout<<a[i]<<" ";
        // cout<<endl;
        int n,m;
        cin>>n>>m;
        int r=lower_bound(a+1,a+L,m)-a;
        if(a[r]>=m)r--;
        int l=lower_bound(a+1,a+L,n)-a;
        if(a[l]==n)l++;
        cout<<r-l+1<<endl;
    }

### 买不到的数目 ###

**问题描述**  
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

**输入格式**  
两个正整数，表示每种包装中糖的颗数(都不多于1000)

#include <bits/stdc++.h>
    using namespace std;
    
    int main(){ 
        int x,y;
        cin>>x>>y;
        cout<<x*y-x-y<<endl;
        return 0;
    }

### 参考博客 ###

*  [蓝桥杯练习（一）][Link 1]
 *  [蓝桥杯练习（二）][Link 2]
 *  [蓝桥杯练习（三）][Link 3]

[Link 1]: https://blog.csdn.net/qq_41146650/article/details/103479737
[Link 2]: https://blog.csdn.net/qq_41146650/article/details/105148589
[Link 3]: https://blog.csdn.net/qq_41146650/article/details/105155642