牛客编程巅峰赛S1第2场 - 黄金&钻石

A-牛牛的Fib序列
链接：https://ac.nowcoder.com/acm/contest/6357/A
来源：牛客网

牛牛重新定义了斐波那契数列，牛牛定义f(n) = f(n-1)+f(n+1); f(1)=a, f(2)=b， 现在给定初始值 a, b，现在求第n项f(n)%1000000007的值。
其中 1<=|x|, |y|, n<=10^9

示例1
输入

1,2,3

输出

1

说明

f(2)=f(3)+f(1), 所以f(3) = f(2)-f(1)=2-1=1

示例1
输入

-1,-2,3

输出

1000000006

说明

同样例1：f(3)=-1%1000000007=1000000006

备注

最终的答案应是一个非负整数，如-1 % 1000000007 = 1000000006

C++

class Solution {
public:
    /**
     *
     * @param a int整型
     * @param b int整型
     * @param n int整型
     * @return int整型
     */
     int f[20];
      
    int solve(int a, int b, int n) {
       int mod=1e9+7;
        f[1]=(a+mod)%mod;
         f[2]=(b+mod)%mod;
         for( int i=3;i<=10;i++ )
         {
            f[i]=(f[i-1]-f[i-2]+mod)%mod;
         } 
         return f[(n-1)%6+1];
    }
};

B-破译密码
链接：https://ac.nowcoder.com/acm/contest/6357/B
来源：牛客网
牛牛收到了一个任务，任务要求牛牛破译一个密码。牛牛将被给予两个字符串s1和s2，均由四个小写字母构成。需要破译的密码为从s1变换到s2最少需要的变换次数。
变换的方式是这样：每次变换可以选择当前字符串中的一个位置，然后剩下的三个位置的字符从左到右分别加上2，3，5，若是超出’z’，则重新从’a’开始，例如：对于字符串"abcd"，我们选择’c’的位置进行变换，则变换之后的字符串为"ceci";对于字符串"qyzr",我们选择’r’位置进行变换，则变换之后的字符串为"sber"。

HINT
以下四个公式成立，即可说明这种情况下可以从 s1 变换到 s2：
$2 * (b + c + d) \mod 26 = dis[0]$2∗(b+c+d)mod26=dis[0]

$(2 * a + 3* (c + d)) \mod 26 = dis[1]$(2∗a+3∗(c+d))mod26=dis[1]

$(3 * (a + b) + 5 * d) \mod 26 = dis[2]$(3∗(a+b)+5∗d)mod26=dis[2]

$5 * (a + b + c) \mod 26 = dis[3]$5∗(a+b+c)mod26=dis[3]
C++

class Solution {
public:
    /**
     * 返回最终的答案
     * @param s1 string字符串 表示初始的字符串
     * @param s2 string字符串 表示目标的字符串
     * @return int整型
     */
    int solve(string s1, string s2) {
        // write code here
        int a=(s2[0]-s1[0])%26+26; a%=26;
        int b=(s2[1]-s1[1])%26+26; b%=26;
        int c=(s2[2]-s1[2])%26+26; c%=26;
        int d=(s2[3]-s1[3])%26+26; d%=26;
        int ans=400;
        for(int x=0;x<=100;x++) {
            for(int y=0;y<=100;y++) {
                for(int z=0;z<=100;z++) {
                    for(int w=0;w<=100;w++) {
                        if(2*(y+z+w)%26==a&&(2*x+3*z+3*w)%26==b&&(3*x+3*y+5*w)%26==c&&5*(x+y+z)%26==d) {
                            ans=min(ans,x+y+z+w);
                        }
                    }
                      
                }
            }
        }
        return ans;
    }
};

c++（bfs）

class Solution
{
public:
    /**
     * 返回最终的答案
     * @param s1 string字符串 表示初始的字符串
     * @param s2 string字符串 表示目标的字符串
     * @return int整型
     */
    int vis[27][27][27][27];
    struct node
    {
        int x,y,z,d,s;

    };
    int bfs(string s1,string s2)
    {
        queue<node>q;
        int a=s1[0]-'a';
        int b=s1[1]-'a';
        int c=s1[2]-'a';
        int d=s1[3]-'a';
        int aa=s2[0]-'a';
        int bb=s2[1]-'a';
        int cc=s2[2]-'a';
        int dd=s2[3]-'a';
        q.push(node{a,b,c,d,0});
        vis[a][b][c][d]=1;
        while(!q.empty())
        {
            node xx=q.front();
            q.pop();
            if(xx.x==aa&&xx.y==bb&&xx.z==cc&&xx.d==dd)
            {
                return xx.s;
            }
            node ans=node{xx.x,(xx.y+2)%26,(xx.z+3)%26,(xx.d+5)%26,xx.s+1};
            if(!vis[ans.x][ans.y][ans.z][ans.d])
            {
                q.push(ans);
                vis[ans.x][ans.y][ans.z][ans.d]=1;
            }
            ans=node{(xx.x+2)%26,xx.y,(xx.z+3)%26,(xx.d+5)%26,xx.s+1};
            if(!vis[ans.x][ans.y][ans.z][ans.d])
            {
                q.push(ans);
                vis[ans.x][ans.y][ans.z][ans.d]=1;
            }
            ans=node{(xx.x+2)%26,(xx.y+3)%26,xx.z,(xx.d+5)%26,xx.s+1};
            if(!vis[ans.x][ans.y][ans.z][ans.d])
            {
                q.push(ans);
                vis[ans.x][ans.y][ans.z][ans.d]=1;
            }
            ans=node{(xx.x+2)%26,(xx.y+3)%26,(xx.z+5)%26,xx.d,xx.s+1};
            if(!vis[ans.x][ans.y][ans.z][ans.d])
            {
                q.push(ans);
                vis[ans.x][ans.y][ans.z][ans.d]=1;
            }
        }
        return 0;
    }
    int solve(string s1, string s2)
    {
        memset(vis,0,sizeof(vis));
        return bfs(s1,s2);
    }
};