字节跳动秋招 2023.09.03 机试题目与题解

发表于 2023-09-04 分类于笔试阅读次数：本文字数： 4.1k 阅读时长 ≈ 4 分钟

1、小红的字符串

小红希望你构造一个字符串，满足以下两个条件：

字符串仅由小写字母构成，且每种小写字母都出现了至少\(2\)次。
对于任意小写字母，该字母在字符串中出现下标的最短距离恰好等于\(k\)。

输入

一个正整数\(k\)。

\(1\le k\le 25\)

输出

合法的字符串。请保证输出的字符串长度不超过\(10^5\)，有多解时输出任意合法解即可。

样例

输入：
1

输出：
qqwweerrttyyuuiiooppaassddffgghhjjkkllzzxxccvvbbnnmm

输入：
2

输出：
qwqwewerertrtytyuyuiuioiopopapasasdsdfdfgfghghjhjkjklklzlzxzxcxcvcvbvbnbnmnm

解答

我们考虑分两步构造这个字符串。

首先从小到大枚举这\(26\)个字母之一，并且在字符数组\(s\)中找到第一个未被填上字母的下标\(i\)，并将\(s[i]\)和\(s[i+k]\)填上该字母。

按照这种填充方式，我们可以看到这个字符串可以看成是多块长度为\(k\)的字符串拼接而成，一共有\(2\cdot\lceil(26/k)\rceil\)块。因此这个字符串的长度为\(2k\cdot \lceil(26/k)\rceil\)。

可以发现，字符串\(s\)仍然有一些位置仍然未被填上字符。假设这些位置为\(i\)，那么为了满足题目中的条件2，我们可以选择将\(s[i-k],s[i-2k],s[i-3k],\dots\)中的一个字符填入\(s[i]\)，可以发现这些位置\(s[i-k],s[i-2k],s[i-3k],\dots\)必定存在一个位置已经被填上了字符。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
char s[N];
int main(){
    int n,k;
    scanf("%d",&k);
    int m=(26+(k-1))/k;
    for(char ch='a';ch<='z';ch++){
        int j;
        for(j=0;islower(s[j]);++j);
        s[j]=s[j+k]=ch;
    }
    for(int i=0;i<k;i++){
        char ch='0';
        for(int j=i;j<m*2*k;j+=k){
            if(islower(s[j]))
                ch=s[j];
            else
                s[j]=ch;
        }
    }
    puts(s);
}

2、小红的矩阵

有一个无穷大的\(01\)矩阵，满足任意两个相邻的字符都不同。即矩阵形状如下：

010101......
101010......
010101......
............

现在小红希望取出一个大小为太的连通块，满足\(cnt_1-cnt_0\)尽可能大。你能帮帮她吗？

\(cnt_1\)代表字符\(1\)的数量，\(cnt_0\)代表字符\(0\)的数量。

连通块的定义:若两个字符在矩阵里是相邻的（上/下左/右/方向），则它们被视为一个连通块。即两个字符连通当且仅当它们的坐标(\(x_1,y_1),(x_2,y_2)\)满足\(|x_1-x_2|+|y_1-y_2|=1\)。

输入

一个正整数\(k(1\le k\le10^{14})\)。

输出

一行一个整数\(cnt_1-cnt_0\)的最大值。

样例

输入：
1

输出：
1

输入：
2

输出：
0

输入：
5

输出：
3

提示：
.1.
101
.1.
如上图，选择这样的连通块，1的数量比0的数量多3个。

解答

按照题目的意思，可见这题我们需要选择尽可能多的\(1\)，尽可能少的\(0\)。

在每次扩展连通块时，如果实在没办法选\(1\)了，那么才选\(0\)；否则必定选\(1\)。

怎么样扩展才能最优呢？首先一开始我们选定了一个\(1\)，那么不失一般性，我们向右选择一个\(0\)，这时又多出了\(3\)个\(1\)可供选择，之后扩展时选上这\(3\)个\(1\)后，又只能选\(0\)。只要选上右边的\(0\)，又可以多出\(3\)个\(1\)提供选择，由此把这个操作继续进行下去，得到的一定是个最优解。整个图形的大致形状如下：

1
2
3

.1.1.1.1.1.1.1.1.1.1.1.1. ...
1010101010101010101010101 ...
.1.1.1.1.1.1.1.1.1.1.1.1. ...

为什么这样最优呢？因为每次拓展一个位置，都至多有\(3\)个新位置可以被拓展。而在上面提供的策略中，当拓展一次格子\(0\)时，就可以拓展\(3\)次\(1\)。

因此，最终拓展的序列一定是形如这个样子\(1,0,1,1,1,0,1,1,1,0,1,\dots\)，即除去了第一个元素，是一个周期为4的序列。

对于这个序列的前\(k\)个元素，一共有\(\lceil(k-1)/4\rceil\)个\(0\)，有\(k-\lceil(k-1)/4\rceil\)个\(1\)，因此最终答案为\(k-2\cdot \lceil(k-1)/4\rceil\)。

代码

1 2	k = int(input()) print(k - (k - 1 + 4 - 1) // 4 * 2)

3、小红的连通块

小红拿到了一个无向图，初始每个节点是白色，其中有若干个节点被染成了红色。

小红想知道，若将\(i\)号节点染成红色，当前的红色连通块的数量是多少？你需要回答\(i\in[1,n]\)的答案。

我们定义，若干节点组成一个红色连通块，当且仅当它们都是红色节点，且在该图上可以通过无向边互相到达，这些可以连通的节点构成的最大集合为一个连通块。

输入

第一行输入两个正整数\(n,m\)，代表无向图的节点数和边数。

第二行输入一个长度为\(n\)的字符串，第\(i\)个字符为'R'代表节点\(i\)被染成红色，'w'代表节点\(i\)被染成白色。

接下来的\(m\)行，每行输入两个正整数\(u,v\)，代表节点\(u\)和节点\(v\)有一条无向边连接。

请注意，无向图不保证是连通的，而且可能有重边和自环。

\(1\le n\le 10^5\)
\(1\le u,v\le n\)

输出

输出\(n\)行，每行输出一个正整数，代表若将\(i\)号节点染红，当前的红色连通块数量。

样例

输入：
4 4
WRWR
1 2
2 3
3 4
1 4

输出：
1
2
1
2

解答

整个过程可以分成两步进行。

第一步，先通过并查集求出目前的图中红色连通块的数量为\(c\)；也可以使用搜索完成这个过程。

第二步，对每一个\(i\)求解答案。如果\(i\)已经被染成红色了，那么答案显然为\(c\)。否则，接下来\(i\)将要从白色染成红色，这个过程有可能讲相邻的多个红色连通块连接成一个。具体过程是，枚举i的每一个邻居\(v\)，如果\(v\)是一个红色顶点，那么将\(v\)的红色连通块编号插入集合\(S\)。

将\(i\)这个白色节点染成红色是将\(S\)中的所有红色连通块相连成一个。因此，这时答案为\(c-|S|+1\)。可以注意到，当\(i\)没有红色节点邻居时，它将自成一个连通块，结果为\(c+1\)，这对应了\(S=\varnothing\)时的情况。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int fa[N],n,m;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
unordered_set<int>g[N];
char s[N];
int cnt=0;
int main(){
    scanf("%d %d %s",&n,&m,s+1);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++){
        if(s[i]=='R'){
            ++cnt;
        }
    }
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        if(x!=y){
            g[x].insert(y);
            g[y].insert(x);
            if(s[x]=='R'&&s[y]=='R'&&find(x)!=find(y)){
                merge(x,y);
                --cnt;
            }
        }
    }
    for(int u=1;u<=n;u++){
        if(s[u]=='R'){
            printf("%d\n",cnt);
        }
        else{
            unordered_set<int>st;
            for(int v:g[u]){
                if(s[v]=='R'){
                    st.insert(find(v));
                }
            }
            printf("%d\n",cnt-st.size()+1);
        }
    }
}

4、小红的游戏

小红正在玩一个死斗游戏，一共有\(n\)个怪物\(a_1,a_2,\dots,a_n\)，第\(i\)个怪物的血量是\(a_i\)。她可以安排任意两个怪物进行决斗，如果这两个怪物血量分别是\(x\)和\(y\)，那么血量高的怪物获胜失败的怪物死亡，获胜的怪物血量变成\(|x-y|\)。特殊的，如果两个怪物血量相同，那么它们同归于尽。

小红可以任意安排怪物的决斗，直到最终只剩一个怪物（或者所有怪物全部死亡）。小红希望最终剩余的怪物血量尽可能小（如果所有怪物死亡则更好）。请你帮小红设计一个决斗的方案。

输入

第一行输入一个正整数\(n\)，代表怪物的数量。

第二行输入\(n\)个正整数\(a_i\)，代表每个怪物的血量。

\(1\le n,a_i\le 100\)

输出

第一行输出一个整数\(h\)，代表剩余的怪物血量。

第二行输出一个正整数\(k\)，代表决斗的次数。

接下来的\(k\)行，每行输入两个正整数\(i\)和\(j\)，代表小红安排第\(i\)个怪物和第\(j\)个怪物进行一场决斗。

请务必保证，每场决斗的两个怪物的血量都大于\(0\)。且\(k\)次决斗之后，存活的怪物不超过\(1\)只。

如果有多个决斗方案，请输出任意方案。但你必须保证最终剩余的怪物血量尽可能小。

样例

输入：
3
1 2 3

输出：
0
2
1 3
2 3

提示：
第一轮，第一个怪物和第三个怪物决斗，第三个怪物获胜，剩余血量为2。此时三个怪物的血量为[0,2,2]
第二轮，第二个怪物和第三个怪物决斗，同归于尽。

解答

每场战斗结束后，活下来的怪物血量要么是\(x-y\)，要么是\(y-x\)，哪怕\(x\)和\(y\)并不是它们原本的血量。

因此，最终战斗结束后，活下来的怪物的剩余血量可以表示为：\(\displaystyle{r=\sum_{i=1}^n f_ia_i}\)，其中\(f_i\in\{-1,1\}\)（代表了要将每个\(a_i\)串成一个加法和剑法表达式，\(a_i\)前面要么是一个加号，要么是一个减号）。也有可能有没有活下来的怪物，这时\(r=0\)。

那么，怎么才能保证在\(r\ge 0\)的基础上，保证\(r\)最小呢？

我们考虑将\(f_i=-1\)的怪物放入集合\(S\)，将\(f_i=1\)的怪物放入集合\(T\)，这相当于是要求\(S\)中的怪物血量之和不超过\(T\)的情况下，保证集合\(S\)和\(T\)中的怪物血量之和尽可能接近。

最终这个问题我们可以使用动态规划解决。令状态\(f(i,j)\)表示前\(i\)个怪物中，是否存在一个子集，使得怪物的血量之和为\(j\)，如果存在，那么\(f(i,j)=1\)；否则\(f(i,j)=0\)。那么，可以写出\(f(i,j)\)的状态转移方程：

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0\land j=0 \\ &0 & & \text{if}\quad i=0\land j>0 \\ &f(i-1,j) & & \text{if}\quad i>0\land j<a_i\\ &f(i-1,j)|f(i-1,j-a_i) & & \text{if}\quad i>0\land j\ge a_i\\ \end{aligned}\right.\)

其中状态转移方程第\(4\)行表示了\(f(i,j)\)有两种选择：一种是\(a_j\)被选择了，从\(f(i-1,j-a_i)\)转移过来；一种是没被选择，直接从\(f(i-1,j)\)转移过来。

令\(s=\displaystyle{\sum_{i=1}^n a_i}\)。最终我们可以找到一个最大的\(k\)使得\(k\le \lfloor s/2\rfloor \land f(n,k)=1\)，那么我们可以通过对\(f(n,k)\)进行状态转移跟踪，来找到对应的集合\(S\)，并求出\(T\)，这时\(S\)和\(T\)的怪物血量之和是最接近的。

接下来的步骤就非常简单了，只需要操作将\(S\)和\(T\)中的怪物相互进行战斗，直到\(S\)中的怪物被清空为止，整个过程就可以结束了。

由于每一次战斗过后，\(S\)和\(T\)损失的血量都是相同的，因此最终剩下的怪物的血量和一开始\(S,T\)中怪物的所有血量和之差相同，为\(|k-(s-k)|=|s-2k|\)。

这里考虑使用\(O(s)\)空间复杂度的方法实现求解\(f(k,\cdot)\)。在实现的时候，为了避免构造方案时，同一只怪物多次出现，因此\(f(k,\cdot)\)最多只会从一个策略转移而来。并且，用于跟踪状态转移的数组和\(f\)放在了一起。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;
const int N=104;
int a[N],n;
int f[N*N/2];
int vis[N];
int main(){
    scanf("%d",&n);
    int s=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s+=a[i];
    }
    f[0]=n+1;
    int m=s/2;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=a[i];j--){
            if(f[j]==0&&f[j-a[i]]!=0){
                f[j]=i;
            }
        }
    }
    vector<int>pos,neg;
    int k;
    for(k=m;f[k]==0;--k);
    for(int i=k;i>0;i-=a[f[i]]){
        neg.push_back(f[i]);
        vis[f[i]]=1;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            pos.push_back(i);
        }
    }
    vector<pi>ans;
    while(!neg.empty()&&!pos.empty()){
        int x=neg.back(),y=pos.back();
        int loss=min(a[x],a[y]);
        a[x]-=loss;
        a[y]-=loss;
        if(a[x]==0) neg.pop_back();
        if(a[y]==0) pos.pop_back();
        ans.push_back(pi(x,y));
    }
    printf("%d\n%d\n",abs(s-k-k),ans.size());
    for(auto [x,y]:ans)
        printf("%d %d\n",x,y);
}