刷题记录（NC202589 魔法数字，NC235247 Sramoc问题）

NC202589 魔法数字

题目链接

关键点:

1、题目要求求的是最小的步数，因此我们采用bfs，对每一次的n可以转换的步数存下来，然后看是否等于m

2、如何判断当前数字肯定不行？对于2*m-n为变换数目的上限，因为当当前数为2*m-n，那么再经过m-n次，就变为m，那还不如直接从n一直加一变成m，也为m-n次。所以对于每一步得出的数，我们可以判断当前数是否小于2*m-n，然后再插入队列

完整代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    int vis[3000];
    struct step{
        int d, s;
    };
    queueq;
    int solve(int n, int m) {
        memset(vis, 0, sizeof(vis));
        return bfs(n, m);
    }
    int bfs(int n, int m)
    {
        if (n>=m)
            return n-m;
        q.push({n, 0});
        int maxx = 2*m-n;
        int ans;
        while (!q.empty())
        {
            step st = q.front();
            int x = st.d;
            int ste = st.s;
            vis[x] = 1;
//             cout<<"x = "<
            q.pop();
            if (x == m)
            {
                ans = ste;
                return ste;
            }
            int x1 = x+1;
            int x2 = x-1;
            int x3 = x*x;
            if (x1<=maxx && !vis[x1])
                q.push({x1, ste+1});
            if (x2<=maxx && !vis[x2])
                q.push({x2, ste+1});
            if (x3<=maxx && !vis[x3])
                q.push({x3, ste+1});
        }
        return -1;
    }
};

NC235247 Sramoc问题

题目链接

关键点：

1、同样的求最小的步数，采用bfs，对于每一步选则0-k的一个数，组成后插入队列

2、可以发现对于每次求出的余数，如果出现重复余数，那么该重复余数就不用再继续算下去了，肯定也为重复，因此我们可以用余数是否重复来筛选入队的数

3、对于组成的数，可能会有很多位，那么采用int来存肯定不行，用字符串来存

4、对于每个数对于m的取余计算，有以下公式

(a+b)%m = (a%m+b%m)%m;

a*b%m = ((a%m)*(b%m))%m;

那么比如对于

100011%m = 3

1000111%m = (3*10+1)%m;

完整代码：

# include 
using namespace std;
int k, m;
int vis[1010];
struct step{
    string s;
    int yu;
};
queue q;
string bfs()
{
    step st;
    for (int i=1; i
    {
        st.s = i+'0';
        st.yu = i%m;
        vis[i%m] = 1;
        q.push(st);
    }
    while (!q.empty())
    {
        step tmp = q.front();
        q.pop();
        if (tmp.yu == 0)
            return tmp.s;
        for (int i=0; i
        {
            int y = tmp.yu*10+i;
            if (!vis[y%m])
            {
                step s1 = tmp;
                s1.s += i+'0';
                s1.yu = y%m;
                vis[y%m] = 1;
                q.push(s1);
            }
        }
    }
    return "-1";
}
int main()
{
    cin>>k>>m;
    cout<<bfs();
    
    
    return 0;
}