字节8.21客户端笔试题解

第一题：

贪心，摩天轮转动一次相当于可以多上4个人，题目要求转动尽可能少，那么自然想到尽可能的让互为朋友的4个人上去同一个摩天轮。

由于必须至少两个朋友一起上同一个摩天轮，如果余下了1个，那么就不能上4个，只能上3个，剩下2个人可以和其他2个人拼；如果余下了2个，那么也可以和其他2个人拼；如果剩3个，那么就拼不了了。

代码（这题代码忘记存了，实现的话就取一下模，然后记录剩下了多少个两人组就好了）

第二题：

问有哪些点到达不了终点，其实就是总点数减去能到达终点的点数。直接从终点出发进行BFS，按照题目模拟即可。

代码（C++）：

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 1e+5;
vector<string> mp;
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
char op[4] = {'U','L','D','R'};
map<int,map<int,int> > vis;
int main()
{
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    string s;
    for(int i = 0; i < n; i++)
    {
        cin>>s;
        mp.push_back(s);
    }
    int ex = -1,ey = -1;
    queue<pii> q;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(mp[i][j] == 'O')
                ex = i,ey = j;
        }
    q.push({ex,ey});
    vis[ex][ey] = 1;
    int ans = n*m;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        ans--;
        for(int i = 0; i < 4; i++)
        {
            int x = t.fi+dir[i][0],y = t.se+dir[i][1];
            if(x>=0&&y>=0&&x<n&&y<m&&!vis[x][y]&&(mp[x][y]==op[i]||mp[x][y]=='.'))
            {
                vis[x][y] = 1;
                q.push({x,y});
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

第三题：

题目有点难懂，其实把一个花括号当成一个整体，那么这题就是一个简单的小正则匹配，记忆化搜索就好了。

代码（C++）（这里把花括号直接换成一个题目中没有的字符@，简化逻辑）：

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 105;
string s,ns = "";
int n,m,ok = 0,must = 0;
string p;
bool vis[105][105];
//p1->s,p2->p
void dfs(int p1,int p2,int must)
{
    if(vis[p1][p2])
        return;
//    cout<<p1<<" "<<p2<<endl;
    vis[p1][p2] = 1;
    if(p2 >= m && !must)
    {
        ok = 1;
        return;
    }
    if(ok)
        return;
    if(p1 >= n)
        return;
    if(p2 >= m)
        return;
    if(ns[p1] == '@')
    {
        dfs(p1+1,p2,must);
        dfs(p1,p2+1,must);
    }
    else if(ns[p1] == p[p2])
        dfs(p1+1,p2+1,must-1);
}
int main()
{
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    cin>>s;
    n = s.length();
    int flg = 0,tt = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == '{')
        {
            flg = 1;
            ns += '@';
            tt++;
            continue;
        }
        else if(s[i] == '}')
        {
            flg = 0;
            continue;
        }
        if(!flg)
            ns += s[i];
    }
//    cout<<ns<<endl;
    must = ns.length()-tt;
    n = ns.length();
//    cout<<ns<<endl;
    while(T--)
    {
        cin>>p;
        m = p.length();
        memset(vis,0,sizeof(vis));
        ok = 0;
        dfs(0,0,must);
        puts(ok?"True":"False");    
    }
    return 0;
}

第四题：

思维题，不难发现只有把1移动到字符串的头部或者尾部的时候（头部/尾部一开始不为1），答案才会减少，移动到头部相当于少了1，尾部相当于少了10，那么自然优先移动到尾部。

代码（C++）：

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 1e+5;
int main()
{
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        int ans = 0,fi = -1,la = -1;
        for(int i = 0; i < n-1; i++)
            ans += (s[i]-'0')*10+s[i+1]-'0';
        for(int i = 0; i < n; i++)
        {
            if(fi == -1 && s[i] == '1')
                fi = i;
            if(s[i] == '1')
                la = i;
        }
        if(la != -1 && la != n-1 && n-1-la <= k)
        {
            k -= n-1-la;
            ans -= 10;
        }
        if(fi != -1 && fi != 0 && fi <= k)
            ans--;
        cout<<ans<<'\n';
    }
    return 0;
}