蓝桥杯练习（四）-蒲公英云

蓝桥杯练习（四）

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

小计算器

问题描述
　　模拟程序型计算器，依次输入指令，可能包含的指令有
　　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;
}

参考博客

蓝桥杯练习（一）
蓝桥杯练习（二）
蓝桥杯练习（三）

蓝桥杯练习（四）