文远知行 8-30号 算法笔试

AC了前两道，最后一道因为写的太慢了没调试成功，写了个思路做参考吧，然后我正好是文远知行的校园大使，所以有意向加入的话可以私信我哦

第一道 AC

#include<iostream>
#include<vector>


using namespace std;

void dfs(int x, int y, vector<vector<int> > &dp, vector<vector<int> > &cost, vector<vector<int> > &gain, int cur_gain, int &max_gain)
{
    if(x == 0 && y == 0)
    {

        max_gain = max(cur_gain + gain[0][0], max_gain);
        return;
    }

    int pre_cost = dp[x][y] - cost[x][y];
    if(x-1 >= 0 && pre_cost == dp[x-1][y])
    {
        cur_gain += gain[x][y];
        dfs(x-1, y, dp, cost, gain, cur_gain, max_gain);
        cur_gain -= gain[x][y];
    }

    if(y-1>=0 && pre_cost == dp[x][y-1])
    {
        cur_gain += gain[x][y];
        dfs(x, y-1, dp, cost, gain, cur_gain,max_gain);
        cur_gain += gain[x][y];
    }
}
void solver(vector<vector<int> > &cost, vector<vector<int> > &gain, int n, int m)
{
    int min_cost = 0, max_gain = 0;

    //第一步用DP得到最小的消耗
    vector<vector<int> > dp(n, vector<int>(m,0));
    dp[0][0] = cost[0][0];
    for(int i = 1; i < n; i++)
    {
        dp[i][0] = dp[i-1][0] + cost[i][0];
    }
    for(int i = 1; i < m; i++)
    {
        dp[0][i] = dp[0][i-1] + cost[0][i];
    }


    for(int i = 1; i< n; i++)
    {
        for(int j = 1; j < m; j++)
        {

            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j];
        }
    }
    min_cost = dp[n-1][m-1];
    //第二步从后往前找路径，计算增益
    int cur_gain = 0;
    dfs(n-1, m-1, dp, cost, gain, cur_gain, max_gain);
    cout<<min_cost<<" "<<max_gain<<endl;
}
int main()
{
    int n, m;
    cin>>n>>m;
    vector<vector<int> > cost(n, vector<int>(m));
    vector<vector<int> > gain(n, vector<int>(m));
    for(int i = 0; i< n; i++)
    {

        for(int j = 0; j<m;j++)
        {
            cin>>cost[i][j];
        }
    }
    for(int i = 0; i< n; i++)
    {

        for(int j = 0; j<m;j++)
        {
            cin>>gain[i][j];
        }
    }
    solver(cost,gain, n, m);
    return 0;
}

第二道 AC

这个题注意一下溢出的问题哦
可以看成是0-25范围的一个数x， 与一个 k* t的数相加，最后再把它归一化到0-25范围内
即 (x + k * t) % 26 , 因为 k* t都特别大，所以先取模再相乘
(x + k * t) % 26 = (x + (k%26) *(t%26)%26) % 26

#include<iostream>
#include<string>
#include<vector>

using namespace std;

void solver( vector<char>& A, vector<long>& K, vector<long>& T, int n)
{
    for(int i = 0; i< n; i++)
    {
        int c = int(A[i]) - 97;
        K[i] = K[i] % 26;
        T[i] = T[i] % 26;
        int y = (c + (K[i] * T[i]) % 26) % 26 + 97;
        char res = char(y);
        cout<<res<<endl;

    }
}
int main()
{

    int n;
    cin>>n;
    vector<char> A(n);
    vector<long> K(n);
    vector<long> T(n);
    for(int i = 0; i<n; i++)
    {
        cin>>A[i]>>K[i]>>T[i];
    }
    solver(A, K, T, n);
    return 0;
}

第三道 线下调试没啥问题

#include<iostream>
#include<vector>

using namespace std;

bool dfs(int S, int E, vector<vector<int> > &mat, vector<int>& visit, int &cost, int &len)
{

    if(S == E)
    {
        return true;
    }

    visit[S] = 1;
    for(int i = 0; i < mat[S].size(); i++)
    {
        if(mat[S][i] ==0 || visit[i] == 1)
            continue;

        visit[i] = 1;
        cost += mat[S][i];
        len += 1;
        //cout<<"visit: "<<i <<" " <<cost<<" "<<len<<endl;
        if(dfs(i, E, mat, visit, cost, len) == true)
        {
            return true;
        }

        cost -= mat[S][i];
        len -= 1;
        visit[i] = 0;

    }
    visit[S] = 0;
    return false;
}
void solver(int N, int Q, vector<vector<int> >&paths, vector<vector<int> > & schedule)
{
    vector<vector<int> > mat(N, vector<int>(N, 0));
    //建立邻接矩阵
    for(int i = 0; i < N-1;i++)
    {
        int U = paths[i][0] - 1;
        int V = paths[i][1] - 1;
        mat[U][V] = paths[i][2];
        mat[V][U] = paths[i][2];
    }

    for(int i = 0; i < Q; i++)
    {
        int S = schedule[i][0] - 1;
        int E = schedule[i][1] - 1;
        int C = schedule[i][2];
        if(mat[S][E] != 0)
        {
            cout<<mat[S][E] / C<<endl;
            continue;
        }
        int cost = 0;
        int len = 0;
        vector<int> visit(N, 0);
        //dfs寻找路径
        dfs(S, E, mat, visit,cost, len);

        cout<<cost / C + len -1<<endl;
    }
}
int main()
{

    int N, Q;
    cin>>N>>Q;
    vector<vector<int> > paths(N-1, vector<int>(3)), schedule(Q, vector<int>(3));
    for(int i = 0; i< N-1; i++)
    {
        cin>>paths[i][0]>>paths[i][1]>>paths[i][2];
    }
    for(int i = 0; i< Q; i++)
    {
        cin>>schedule[i][0]>>schedule[i][1]>>schedule[i][2];
    }
    solver(N, Q, paths, schedule);
    return 0;
}