笔试共150min，有单选，多选，填空和编程题。时间安排不当，导致填空题没做。这里只回忆编程题

编程题共四题，前三题通过了，最后一个通过20%，回想一下感觉自己知道最后一问最后一题是在哪出问题了，后面细说。

第一题

给定两维数组，数组中为0或1,1为障碍。给定初始坐标(x,y)，给目的地坐标(X,Y)，每一步可以上下左右移动，求出初始到结束的最短路径。

分析：这个问题是最短路问题，但可以四个方向移动，不太适合用dp，所以这里采用bfs。这里踩了点坑，就是给定的坐标x表示col的下标，y表示row。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mod 1000000007

int n;
int M, N;
int x,y;
int X,Y;
int A[105][105];
int visited[105][105];
#define PII pair<int,int>
#define fi first
#define se second
int minDist()
{
    memset(visited,0,sizeof(visited));
    queue<PII> Q;
    Q.push({x,y});
    visited[x][y]= 1;
    if(A[x][y]==1) return -1;
    int lv=1;
    while(!Q.empty())
    {
        for(int i=Q.size(); i>0; i--)
        {
            PII t = Q.front(); Q.pop();
            //cout<<t.fi<<" "<<t.se<<";";
            if(t.fi == X && t.se==Y) return lv;
            if(t.fi>0 && A[t.fi-1][t.se]==0 && visited[t.fi-1][t.se]==0)
            {
                Q.push({t.fi-1,t.se});
                visited[t.fi-1][t.se]=1;
            }
            if(t.se>0 && A[t.fi][t.se-1]==0 && visited[t.fi][t.se-1]==0)
            {
                Q.push({t.fi,t.se-1});
                visited[t.fi][t.se-1]=1;
            }
            if(t.fi+1<N && A[t.fi+1][t.se]==0 && visited[t.fi+1][t.se]==0)
            {
                Q.push({t.fi+1,t.se});
                visited[t.fi+1][t.se]=1;
            }
            if(t.se+1<M && A[t.fi][t.se+1]==0 && visited[t.fi][t.se+1]==0)
            {
                Q.push({t.fi,t.se+1});
                visited[t.fi][t.se+1]=1;
            }
        }
        //cout<<endl;
        lv++;
    }
    return -1;
}

int work()
{
    cin>>n;
    while(n--)
    {
        cin>>M>>N;
        cin>>y>>x;
        cin>>Y>>X;
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                cin>>A[i][j];
         cout<<minDist()<<endl;   
    }
    return 0;
}

#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
    fr("d:/tmp/input");
    fw("d:/tmp/output");
#endif
    ios::sync_with_stdio (false);
    cin.tie (nullptr);
    work();

    return 0;
}

第二题

类似于leetcode上的石子问题。给定n，每次从中减去1到m任意数，不能不减。然后看谁先全部取完。计算先手坑定能赢的次数。对于这种问题，我常用dp来做。遍历先手的所有选项，若有后手必定输的情况，则先手一定赢，否则一定输。但这里n,m都很大，需要用到数学上的一点归纳。这里看后手,采用策略：先手拿x,则后手拿m+1-x,这样一轮下来必定n到 n-(m+1)，若n%(m+1)==0, 则后手必赢。否则，先手取x，使得(n-x)%(m+1)==0, 这时先手采用同样的策略必定能赢。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mod 1000000007

#define PII pair<int,int>
#define fi first
#define se second

int t;
int m;
int n;

bool win()
{
    int x = n/m;
    if(x%2==0) return true;
    else return false;
}

int work()
{
    cin>>t;
    int ans=0;
    while(t--)
    {
        cin>>n>>m;
        if(win()) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
    fr("d:/tmp/input");
    fw("d:/tmp/output");
#endif
    ios::sync_with_stdio (false);
    cin.tie (nullptr);
    work();

    return 0;
}

第三题

这个问题中，需要将带评论的json字符串去掉评论返回。基本思路是找到“//”的话，跳过直至行尾;找到“/”的话，找下一个"/",并将这里中间的跳过。一个小坑是，对于getline读入的字符串，是不带有回车符的，需要读的时候手动加一下。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mod 1000000007
#define PII pair<int,int>
#define fi first
#define se second

string s;
string line;

string simplify()
{
    string ans;
    int i=0;
    while(i<s.size())
    {
        if(s[i]=='/')
        {
            if(i+1<s.size() && s[i+1]=='/')
            {
                i+=2;
                while(i<s.size() && s[i]!='\n') i++;
                ans+=s[i++];
            }
            else if(i+1<s.size() && s[i+1]=='*')
            {
                i+=2;
                while(i+1<s.size() && (s[i]!='*' || s[i+1]!='/')) i++;
                //cout<<"-->"<<s[i]<<s[i+1]<<"<---- "<<endl;
                i+=2;
            }
            else
                ans+=s[i++];
        }
        else
            ans+=s[i++];
    }
    return ans;
}

void work()
{
    while( getline(cin,line) )
    {
        s+=line+'\n';
    }
    cout<<s<<endl;
    cout<<simplify();
}

#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
    fr("d:/tmp/input");
    fw("d:/tmp/output");
#endif
    ios::sync_with_stdio (false);
    cin.tie (nullptr);
    work();

    return 0;
}

第四题

这个问题中给定一个n节点的树，gcd(x,y)表示树的x节点到y节点的一条路径上所有节点的最大公约数，dist(表示路径的长度（节点数）。求gcd(x,y)>1的所有路径中最大的dist(x,y)。n最大20w,范围也是1到20w.

从n个范围来看，最多只能采用nlog(n)的算法了。我最后的想法是，先算所有节点的质因数，然后对给定质因数p, dfs遍历，遍历时保证节点能被p整除。这样对给定p的情况，转化为树中最常路径了，这个问题有点像leetcode的二叉树的直径。我想我可能是下面少加了个1才搞错了。。当然这也只是我的个人事后猜测，也许不是这样，现在也无从验证了。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define mod 1000000007
#define PII pair<int,int>
#define fi first
#define se second

int n;
int A[200005];
int visited[200005];
unordered_map<int, vector<int>> G;
int ans = 0;

unordered_set<int> primes;
void addP(int x)
{
    int i=2;
    while(x>1)
    {
        if(x%i==0)
        {
            primes.insert(i);
            while(x>1 && x%i==0)
                x/=i;
        }
        i++;
    }
}

// find max path length
int dfs(int ni, int p)
{
    visited[ni] = 1;
    if(A[ni]%p!=0) return 0;
    priority_queue<int, vector<int>, greater<int>> maxLen;
    int maxL=0;
    for(int nj : G[ni])
    {
        if(visited[nj]==0)
        {
            int t = dfs(nj, p);
            maxL = max(t, maxL);
            if( maxLen.size()<2 ) maxLen.push(t);
            else if( t>maxLen.top() )
            {
                maxLen.pop();
                maxLen.push(t);
            }
        }
    }
    ans = max(ans, 1+maxL);
    if(maxLen.size()>=2) 
    {
        int t1 = maxLen.top(); maxLen.pop();
        int t2 = maxLen.top(); maxLen.pop();
        ans = max(ans, 1+t1+t2); //这里比赛时少加了个1
    }
    return 1+maxL;
}

int maxDist()
{
    for(int i=0; i<n; i++)
        addP(A[i]);

    for(int p : primes)
    {
        for(int i=0 ;i<n ; i++) visited[i] = 0;
        for(int i=0; i<n; i++)
            if(visited[i]==0 ) // 比赛时没加isOk
                dfs(i, p);
    }
    return ans;
}


void work()
{
    cin>>n;
    int a,b;
    memset(visited,0,sizeof(visited));
    for(int i=0; i<n; i++) cin>>A[i];
    for(int i=0; i<n-1; i++)
    {
        cin>>a>>b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }
    cout<<maxDist()<<endl;
}

#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
int main()
{
#ifdef LOCAL
    fr("d:/tmp/input");
    fw("d:/tmp/output");
#endif
    ios::sync_with_stdio (false);
    cin.tie (nullptr);
    work();

    return 0;
}

总结

问题其实还不是太难，还是自己太菜了。。。继续加油！