快手2018春季校园招聘笔试试卷--算法A试卷编程题题解

第二题：矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000003
struct matrix{
    ll m[5][5];

    struct matrix operator *(const matrix &a){
        struct matrix ans;
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                long long sum = 0;
                for(int k=0;k<5;k++){
                    sum = (sum+m[i][k]*a.m[k][j])%mod;
                }
            ans.m[i][j] = sum;
            }
        }
        return ans;
    }

};

int main()
{
    long long n;
    while(cin>>n)
    {
        if(n<5)cout<<1<<endl;
        else{
            struct matrix a,b;
            memset(a.m,0,sizeof(a.m));
            memset(b.m,0,sizeof(b.m));
            a.m[0][0] = a.m[0][1] = a.m[0][2] = a.m[0][3] = a.m[0][4] = 1;
            b.m[0][0] = 2018;
            b.m[1][0] = 2017;
            b.m[2][0] = 2016;
            b.m[3][0] = 2015;
            b.m[4][0] = 2014;
            b.m[0][1] = b.m[1][2] = b.m[2][3] = b.m[3][4] = 1;
            n-=4;
            struct matrix ans;
            memset(ans.m,0,sizeof(ans.m));
            for(int i=0;i<5;i++)ans.m[i][i] = 1;
            while(n){
                if(n%2ll){
                    ans = ans*b;
                }
                b = b*b;
                n/=2ll;
            }

            a = a*ans;
            cout<<a.m[0][0]<<endl;
        }
    }

    return 0;
}



第三题：  首先bfs预处理所有情况，map标记步数  用string存超时，换成char数组过了

#include<bits/stdc++.h>
using namespace std;
int fx[4][2] = {1,0,-1,0,0,1,0,-1};
map<string,int>mp;

struct st{
    char str[10];
    int i,j;
    int step;
};
queue<st>q;
int main()
{
    st a;
    a.i = 2;
    a.j = 2;
    a.step = 1;
    a.str[0] = '8';
    a.str[1] = '7';
    a.str[2] = '6';
    a.str[3] = '5';
    a.str[4] = '4';
    a.str[5] = '3';
    a.str[6] = '2';
    a.str[7] = '1';
    a.str[8] = '0';
    a.str[9] = '\0';

    q.push(a);
    mp[a.str] = 1;

    while(!q.empty()){
        a = q.front();
        q.pop();
        int i = a.i;
        int j = a.j;
        int step = a.step;
        for(int k=0;k<4;k++)
        {

            int ii = i+fx[k][0];
            int jj = j+fx[k][1];
            if(ii>=0&&ii<3&&jj>=0&&jj<3)
            {
                swap(a.str[ii*3+jj],a.str[i*3+j]);
                if(!mp[a.str]){

                    a.i = ii;
                    a.j = jj;
                    a.step = step+1;
                    mp[a.str] = a.step;
                    q.push(a);
                }
                swap(a.str[ii*3+jj],a.str[i*3+j]);
            }

        }
    }
    int n;cin>>n;
    while(n--){
        char str[10];
        for(int i=0;i<9;i++)
        {
            int x;
            scanf("%d",&x);
            str[i] = ('0'+x);
        }
        str[9] = '\0';
        if(mp[str]){
            cout<<mp[str]-1<<endl;
        }
        else cout<<"impossible!"<<endl;
    }
    return 0;
}