网易秋招 2023.10.15 编程题目与题解

发表于 2023-10-15 分类于笔试阅读次数：本文字数： 2.2k 阅读时长 ≈ 2 分钟

1、小红的字符串变换（easy）

小红有一个字符串\(s\)，她想把\(s\)变成\(t\)。

小红可以进行操作：选择两种不同的字母，然后将在\(s\)中的这两种字母按任意顺序排列。

小红想知道她是否可以恰好操作一次将\(s\)变成\(t\)。

输入

第一行输入一个字符串\(s\)。

第二行输入一个字符串\(t\)。

\(s\)和\(t\)长度相等，且都不超过\(10^6\)。

输出

若小红可以恰好操作一次将\(s\)变成\(t\)，则输出"YES"，再输出选择的两种字母，否则输出"NO"。

如果有多种方案，请输出字典序最小的方案（第一种字母 ASCII 码值尽可能小，若第一种字母 ASCII 码值相同，则第二种字母 ASCII 码值尽可能小）。

样例

输入：
abab
abba

输出：
YES
a b

提示：
选择字母 'a' 、 'b' ，即可使 "abab" 变成 "abba"
选择字母 'b' 、 'a' 也是答案，但此方案的字典序较大。

解答

对于任意一个下标\(i\)，如果\(s_i\neq t_i\)，那么我们只能选择这一对字符\((s_i,t_i)\)进行操作，如果只使用这一对字符进行操作仍然无法完成\(s=t\)的目的，那么说明肯定还存在另一对和\((s_i,t_i)\)不相同的字符串需要操作，这时肯定是无解的。如果能够达到\(s=t\)的目的，那么\((s_i,t_i)\)就是唯一解。

如果有多个解，那么唯有\(s=t\)才可以做到。此时最小字典序的解为\((\texttt{a,b})\)。

代码

def solve(s, t):
    n = len(s)
    v = []
    for i in range(n):
        if s[i] != t[i]:
            v = sorted([s[i], t[i]])
            break
    if not v:
        return ['a', 'b']
    s0 = set(i for i in range(n) if s[i] == v[0])
    s1 = set(i for i in range(n) if s[i] == v[1])
    t0 = set(i for i in range(n) if t[i] == v[0])
    t1 = set(i for i in range(n) if t[i] == v[1])
    if len(s0) == len(t0) and len(s1) == len(t1) and (s0 | s1) == (t0 | t1):
        return v
    else:
        return []


ans = solve(input(), input())
if ans:
    print("YES\n{} {}".format(ans[0], ans[1]))
else:
    print("NO")

2、小红的树上染色

小红有一棵\(n\)个点的树，\(1\)号点是根结点。树上的一些边需要被染色，小红每次可以选择一个点，将这个点到根结点的所有边染成红色。小红想知道，最少需要多少次操作，才能使得树上所有的边都被染成红色。

必须把所有需要染红的边染红，可以把一条边染色多次，也可以把不需要染色的边染成红色。

输入

第一行一个整数\(n\)，表示树上点的个数。

接下来\(n-1\)行，每行三个整数\(u,v,c\)，表示\(u\)和\(v\)之间有一条边，如果\(c=1\)，表示这条边需要被染色，否则表示这条边可以不被染色。

\(2 \leq n \leq 10^5\)
\(1 \leq u, v \leq n\)

输出

输出一个整数，表示最少需要的操作次数。

样例

输入：
5
1 2 1
1 3 0
2 4 1
2 5 0

输出：
1

提示：
选择 4 号结点，把 (1, 2)，(2, 4) 染红。

解答

基于贪心的思想，我们应该尽量选择深度足够深的节点进行染色。为了使得染色节点尽可能少，怎么做出这个选择呢？

如果一个节点\(u\)连向它的父节点这条边必须被染色，但是\(u\)的子树中，没有需要被染色的边，那么我们可以选择\(u\)，这样子将使得\(u\)到根中的所有边都会被进行染色。此外，选择\(u\)的后代是没有必要的，因为选择它们的效果和选择\(u\)相同。

由此我们只需要统计选择必须被选择的节点\(u\)即可。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;

const int N=100005;

vector<pi>g[N];
int n;
int ans=0;
int dfs(int u,int fa){
    int cnt=0;
    for(auto [v,w]:g[u]){
        if(v==fa) continue;
        int c=dfs(v,u);
        if(w&&c==0) ++ans;
        cnt+=w+c;
    }
    return cnt;
}
int main(){
    int u,v,w;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d %d %d",&u,&v,&w);
        g[u].push_back(pi(v,w));
        g[v].push_back(pi(u,w));
    }
    dfs(1,0);
    printf("%d\n",ans);
}

3、小红的mex查询

小红拿到了一个空集。她准备进行以下操作：将\([l,r]\)区间的每个整数添加进集合。

请你在每次操作后，输出当前集合的\(\text{mex}\)。我们定义，集合的\(\text{mex}\)为：集合中最小的未出现的非负整数。

输入

第一行输入一个正整数\(q\)，代表操作次数。接下来的\(q\)行，每行输入两个正整数\(l,r\)，代表一次操作。

\(1\leq q \leq 10^5\)
\(1\leq l \leq r \leq 10^9\)

输出

输出\(q\)行，每行输入一个整数，代表当前的集合\(\text{mex}\)。

样例

输入：
4
1 3
7 8
0 5
3 6

输出：
0
0
6
9

提示：
第一次操作后，集合为[1,2,3]，mex 为 0。
第二次操作后，集合为[1,2,3,7,8]，mex 仍然是 0。
第三次操作后，集合为[0,1,2,3,4,5,7,8]，mex 为 6。
第四次操作后，集合为[0,1,2,3,4,5,6,7,8]，mex 为 9。

解答

令第\(i\)次操作表示为区间\([l_i,r_i]\)。按照\(\text{mex}\)的覆盖性质可以发现，一个候选的\(\text{mex}\)值必定为集合\(U=\{r_i+1\mid i\in[1,n]\}\cup\{0\}\)，因为对于一个数\(k\)，如果不存在\(i\)使得\(r_i+1=k\)，那么有两种情况：

\(k\)不被任何一个区间所覆盖，但是\(k-1\)也将不会被任何一个区间所覆盖。因此\(k\)必定不是一个\(\text{mex}\)值。
\(k\)被任何一个区间所覆盖，因此\(k\)必定不是一个\(\text{mex}\)值。

因此，每对一个区间\([l_i,r_i]\)进行操作后，将原本集合\(U\)中区间\([l_i,r_i]\)内的所有元素删除即可。最终输出\(S\)中的最小值即可。

代码

# include <bits/stdc++.h>
using namespace std;

const int N=100004;

int l[N],r[N],n;
int main(){
    set<int>st{0};
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&l[i],&r[i]);++r[i];
        st.insert(r[i]);
    }
    for(int i=1;i<=n;i++){
        while(true){
            auto it=st.lower_bound(l[i]);
            if(it==st.end()||*it>=r[i]) break;
            st.erase(it);
        }
        printf("%d\n",*st.begin());
    }
}

4、小红的字符串回文值

小红有一个字符串\(s\)，她想知道这个字符串中字典序最大的后缀、字典序最小的后缀的回文值分别是多少。

字符串的回文值定义为：字符串的最长回文子串长度。

输入

第一行输入一个字符串，字符串长度不超过\(2 \times 10^5\)。

输出

输出两个整数表示答案。

样例

输入：
abc

输出：
1 1

提示：
字典序最大的后缀为"c"，回文值为1
字典序最小的后缀为"abc"，回文值为1

输入：
ababa

输出：
3 1

提示：
字典序最大的后缀为"baba"，回文值为3（最大回文子串为 "bab" 或 "aba" ）
字典序最小的后缀为"a"，回文值为1

解答

本题将分为两个部分进行求解。

第一部分是找到两个字典序最大和最小的后缀。这题可以直接使用后缀数组进行解决，不过这不在考察范围内。对于一对后缀\((i,j)\)，我们可以使用字符串哈希，通过二分找到最小的正整数\(l\)使得\(s_{i+l-1}\neq s_{j+l-1}\)，并比较\(s_{i+l-1}\)和\(s_{j+l-1}\)的顺序，从而比较出这两个后缀的字典序大小。如果不存在\(l\)，那么说明\(i,j\)中其中一个是另一个的前缀，因此长度较小的那个后缀字典序比较小。

最终通过哈希算法求解字典序最大和最小的后缀。

第二部分是找到一个字符串的最长回文字符串长度，这个问题可以使用Manachar算法直接解决。也可以使用二分法和哈希法完成，具体做法是预处理出这个字符串的前缀哈希值和后缀哈希值，使用中心扩展法进行二分即可。

代码

# include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const int N=200004;
char s[N];
int n;

ull pw[N],hs[N],B=131;
ull geths(int l,int r){
    return hs[r]-hs[l-1]*pw[r-l+1];
}
bool lt(int x,int y){
    int m=n-y+1;
    int l=1,r=m+1;
    while(l<r){
        int mid=(l+r)>>1;
        if(geths(x,x+mid-1)!=geths(y,y+mid-1)) r=mid;
        else l=mid+1;
    }
    if(l==m+1) return 0;
    else return s[x+l-1]<s[y+l-1];
}
int solve(string t){
    string s="#";
    for(char ch:t){
        s+=ch;s+='#';
    }
    int n=s.size();
    vector<int>d(n);
    for(int i=0,l=0,r=-1;i<n;i++){
        int k=(i>r?1:min(d[l+r-i],r-i+1));
        for(;0<=i-k&&i+k<n&&s[i-k]==s[i+k];k++);
        d[i]=k--;
        if(i+k>r){
            l=i-k;
            r=i+k;
        }
    }
    int k=*max_element(d.begin(),d.end());
    return k-1;
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    pw[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*B;
        hs[i]=hs[i-1]*B+s[i];
    }
    int mx=1,mn=1;
    for(int i=2;i<=n;i++){
        if(!lt(mn,i)) mn=i;
        if(lt(mx,i)) mx=i;
    }
    printf("%d %d\n",solve(string(s+mx,s+n+1)),solve(string(s+mn,s+n+1)));

}