头条笔试部分答案

第一题BFS

#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory>
#include<cstring>
using namespace std;
typedef long long ll;
int mp[15][15],vis[15][15];
int dirx[4]={ 1,-1,0,0 };
int diry[4]={ 0,0,1,-1 };
struct Node
{
    Node(int a=0,int b=0):x(a),y(b){ }
    int x,y;
};

int main ()
{
    //freopen("in.txt","r",stdin);
    memset(vis,0x3f,sizeof(vis));
    queue<Node>pro;
    char str[15];
    int c=0,len;
    while(gets(str))
    {
        int cur=0;
        len=strlen(str);
        for(int i=0;i<len;i++)
        {
            if(str[i]!=' ')
            {
                mp[c][cur]=str[i]-'0';
                if(str[i]=='2')
                {
                    pro.push(Node(c,cur));
                    vis[c][cur]=0;
                }
                cur++;
            }
        }
        c++;
    }
    while(!pro.empty())
    {
        Node cur=pro.front();
        pro.pop();
        for(int i=0;i<4;i++)
        {
            Node now;
            now.x=cur.x+dirx[i];
            now.y=cur.y+diry[i];
            if(now.x<c&&now.x>=0&&now.y<len&&now.y>=0)
            {
                if(mp[now.x][now.y]==1&&vis[now.x][now.y]==0x3f3f3f3f)
                {
                    vis[now.x][now.y]=min(vis[cur.x][cur.y]+1,vis[now.x][now.y]);
                    pro.push(now);
                }
            }
        }
    }
    int res=0;
    for(int i=0;i<c;i++)
        for(int j=0;j<len;j++)
            if(mp[i][j]==1)
                res=max(res,vis[i][j]);
    cout<<(res==0x3f3f3f3f?-1:res)<<endl;
}

第二题哈希

#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory>
#include<unordered_map>
using namespace std;
typedef long long ll;
struct Nodemes
{
    int lasttime;
    int cur;
    int ma;
};
struct Node
{
    int x,y;
};
struct keyhash
{
    size_t operator()(const Node&k)const
    {
        return hash<int>()(k.x)^hash<int>()(k.y);
    }
};
struct keyequal
{
    bool operator()(const Node&a,const Node&b)const
    {
        return a.x==b.x&&a.y==b.y;
    }
};
int main ()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        unordered_map<Node,Nodemes,keyhash,keyequal>hs;
        int n;
        scanf("%d",&n);

        for(int i=0;i<n;i++)
        {
            int m;
            scanf("%d",&m);
            for(int j=0;j<m;j++)
            {
                Node now;
                scanf("%d %d",&now.x,&now.y);
                unordered_map<Node,Nodemes,keyhash,keyequal>::iterator it=hs.find(now);
                if(it==hs.end())
                {
                    hs[now].cur=1;
                    hs[now].lasttime=i;
                    hs[now].ma=1;
                }
                else
                {
                    if(it->second.lasttime==i-1)
                    {

                        it->second.cur++;
                        it->second.ma=max(it->second.cur,it->second.ma);
                        it->second.lasttime=i;
                    }
                    else
                    {
                        it->second.cur=1;
                        it->second.lasttime=i;
                    }
                }
            }
        }
        int res=0;
        for(auto it=hs.begin();it!=hs.end();it++)
            res=max(res,it->second.ma);
        cout<<res<<endl;

    }
}

第三题本来想是二分水题nlogn结果只过了8%，求大神讲讲思路啊

这是我的代码

#include <iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<memory>
#include<unordered_map>
using namespace std;
typedef long long ll;
int k[100005];
int n;
bool judge(ll x)
{
    ll cur=x;
    for(int i=0;i<n;i++)
    {
        if(cur>k[i])
            cur+=(cur-k[i]);
        else
        {
            cur-=(k[i]-cur);
            if(cur<0)
                return false;
        }
    }
    return true;
}
int main ()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&k[i]);
    ll l=0,r=100005,mid,res=r;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(judge(mid))
        {
            r=mid-1;
            res=min(res,mid);
        }
        else
            l=mid+1;
    }
    cout<<res<<endl;
}

第四题应该是个TSP板子题，手头没有现成的，也没好意思上网搜

第五题没看