携程 秋招 2023.09.07 编程题目与题解

1、游游的排列统计

游游想知道，有多少个长度为\(n\)的排列满足任意两个相邻元素之和都不是素数，你能帮帮她吗？

我们定义，长度为\(n\)的排列值一个长度为\(n\)的数组其中\(1\)到\(n\)每个元素恰好出现了一次。

输入

一个正整数\(n\)。

\(2\le n\le 10\)

输出

满足条件的排列数量。

样例

输入：
5

输出：
4

提示：
共有以下4种合法排列：
[1,3,5,4,2]
[3,1,5,4,2]
[2,4,5,1,3]
[2,4,5,3,1]

解答

本题考查的是回溯法，并且需要剪支。尝试往第\(f\)个位置填入之前未被使用过的数\(x\)，并且判断当前填入\(a[f]\)的数\(x\)与前一个数之和\(x+a[f-1]\)是否是一个质数。如果是质数那么不填入，这相当于进行了一次剪支操作。

最终统计所生成的排列个数即可。

如果\(n\)再大一点（比如\(15\)），可以使用什么方法做呢？答案：状态压缩动态规划。

代码

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

const int N=24;
int is_prime[N];
vector<int>pr{2,3,5,7,11,13,17,19};
int a[N],vis[N],n;
int ans=0;
void dfs(int f){
    if(f==n+1){
        ++ans;
        return;
    }
    for(int x=1;x<=n;x++){
        if(vis[x]||f>1&&is_prime[a[f-1]+x]) continue;
        a[f]=x;
        vis[x]=1;
        dfs(f+1);
        vis[x]=0;
    }
}
int main(){
    scanf("%d",&n);
    for(int x:pr) is_prime[x]=1;
    dfs(1);
    printf("%d\n",ans);
}

2、游游的you矩阵

游游拿到了一个字符矩阵，她想知道有多少个三角形满足以下条件：

1. 三角形的三个顶点分别是'y', 'o', 'u' 字符。
2. 三角形为直角三角形，且两个直角边一个为水平、另一个为垂直。

输入

第一行输入两个正整数\(n,m\)，用空格隔开，代表矩阵的行数和列数。

接下来的\(n\)行，每行输入一个长度为m的字符串，代表游游拿到的矩阵。

\(1 \le n,m \le 1000\)

输出

输出一个整数，代表满足条件的三角形个数。

样例

输入：
2 3
you
our

输出：
3

提示：
y u     y       yo
o       ou       u

解答

首先对整个矩阵先进行预处理，具体过程是：

\(a_{ij}= \left \{\begin{aligned} &0 & & \text{if}\quad s_{ij}=\texttt{y} \\ &1 & & \text{if}\quad s_{ij}=\texttt{o} \\ &2 & & \text{if}\quad s_{ij}=\texttt{u} \\ &-1 & & \text{otherwise} \\ \end{aligned}\right.\)

其中\(1\le i\le n,1\le j\le m\)，由此去除无关信息。

由于我们需要枚举的是直角三角形，因此我们可以考虑枚举每个顶点\((i,j)\)作为直角顶点，然后在第\(i\)行中选择一个顶点，再在第\(j\)列中选择一个顶点，由此构成一个直角三角形。因此，我们可以统计每个顶点作为直角顶点时，它对总个数的贡献。

接下来，令\(r_{i,k}\)表示矩阵\(a\)的第\(i\)行中元素\(k\)的个数，令\(c_{j,k}\)表示矩阵\(a\)的第\(j\)列中元素\(k\)的个数，注意这里的\(k\)满足\(0\le k\le 2\)。如果\(a_{i,j}=k\)，那么假设\(x,y\)是除去\(k\)中，集合\(\{0,1,2\}\)中的另外两个元素。如果元素\(x\)在第\(i\)行中选择，那么\(y\)就要在第\(j\)列选择，这种方式产生了\(r_{i,x}\cdot c_{j,y}\)个直角三角形；类似的，如果元素\(x\)在第\(j\)列中选择，那么\(y\)就要在第\(i\)行选择选择，这种方式产生了\(r_{i,y}\cdot c_{j,x}\)个直角三角形。

最终，将如上统计出来的直角三角形个数累加起来即可。

代码

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

const int N=1004;
char s[N][N];
int r[N][3],c[N][3];
int n,m;
int mp[N][N];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char ch=s[i][j];
            int k=(ch=='y'?0:ch=='o'?1:ch=='u'?2:-1);
            mp[i][j]=k;
            if(k>=0){
                ++r[i][k];
                ++c[j][k];
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int k=mp[i][j];
            if(k!=-1){
                int x=(k==0?1:0);
                int y=3-x-k;
                ans+=r[i][x]*c[j][y]+r[i][y]*c[j][x];
            }
        }
    }
    printf("%lld\n",ans);
}

3、游游的元素修改

游游拿到了一个数组，她每次操作可以使得一个元素加\(1\)，另一个元素减\(1\)。

游游希望最终数组的每个元素大小都在\([l,r]\)范围内，她想知道自己最少多少次操作可以达成目标？

输入

第一行输入一个正整数\(t\)，代表用例的组数。

对于每组用例:

第一行输入三个正整数\(n,l,r\)。

第二行输入\(n\)个正整数\(a_i\)，代表游游拿到的数组。

• \(1\le t\le 1000\)
• \(2 \le n \le 200000\)
• \(1\le l\le r \le10^9\)
• \(1 \le a_i \le 10^9\)

输出

输出\(t\)行，每行一个整数，含义如下：

如果无法用有限次数的操作次数使得每个元系大小都在\([l,r]\)范围内，请输出\(-1\)。

否则输出一个整数，代表最少的操作次数。

样例

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

输出：
-1
1

提示：
第一组用例：显然无法用有限次数的操作使得所有元素范围都在[3,5]之间。
第二组用例：使第一个数加1，第三个数减1即可，数组变成[4,6,4]，满足所有元素不小于4，不大于6。

解答

本题只需要非常简单的贪心。可以发现，这个数组的和总是不变的，因此令\(\displaystyle{s=\sum_{i=1}^n a_i}\)。如果不满足\(ln\le s\le rn\)，那么答案为\(-1\)，这是显而易见的。

否则，由于\(1\)次操作可以同时将一个数加上\(1\)，将一个数减去\(1\)，因此我们需要充分利用每一次操作：在将已经下溢的所有数都加上\(1\)的同时，将上溢的数减去\(1\)。对于多余的操作，只需要将让区间\([l,r]\)内部的数消化即可，因为\(ln\le s\le rn\)，总存在一种方式将这\(n\)个数分配到区间\([l,r]\)中。

因此，令\(\displaystyle{s_1=\sum_{i=1}^n \max\{0,a_i-r\},s_2=\sum_{i=1}^n\max\{0,l-a_i\}}\)，那么\(\max\{s_1,s_2\}\)为最终答案。

代码

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

const int N=100004;
ll a[N],l,r;
int n;
ll solve(){
    scanf("%d %lld %lld",&n,&l,&r);
    ll sum=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    if(l*n<=sum&&sum<=r*n){
        ll pos=0,neg=0;
        for(int i=1;i<=n;i++){
            if(a[i]>r) pos+=a[i]-r;
            else if(a[i]<l) neg+=l-a[i];
        }
        return max(pos,neg);
    }
    else return -1;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        printf("%lld\n",solve());
    }
}

4、游游的好串

游游有一个只包含'0'和'1'的字符串，他想知道这个字符串有多少个好子串？

一个字符串如果是“好串”，那么该字符串的所有前缀，'0'的数量严格大于'1'的数量。

输入

输入一个只包含'0'和'1'的字符串，长度不超过\(100000\)。

输出

输出一个整数，代表答案。

样例

输入：
100

输出：
3

提示：
子区间[2,2], [2,3], [3,3]组成的子串都是一个好串。

输入：
10010

输出：
6

提示：
子区间[2,2], [3,3], [2,3], [2,4], [2,5], [5,5]组成的子串是一个好串。

解答

假设\(t\)是所输入的字符串。由于这题考虑的是子串间\(0,1\)之间个数的关系，因此我们不难想到将所有的\(1\)替换成\(1\)，将所有的\(0\)用\(-1\)代替，令\(a_i\)表示替换后的数组。令\(a\)的前缀和为\(\displaystyle{s_i=\sum_{j=1}^i a_j},s_0=0\)。那么对于\(t[i:j]\)这个子字符串，如果\(s_j-s_{i-1}\ge 0\)，那么说明这个子字符串中，\(1\)的数量比\(0\)多。

如果一个子字符串\(t[i:j]\)是好串，那么说明\(\forall k\in[i,j]\)，都有\(s_k-s_{i-1}<0\)；否则，必定\(\exists k\in[i,j],s_k-s_{i-1}\ge 0\)成立。按照这个性质的传递性，如果\(t[i:j]\)不是一个好串，那么\(t[i:j+k](0\le k\le n-j)\)必定也不是一个好串。

因此，对于每个\(i\)，我们可以找到一个最小的\(j(j\ge i-1)\)，使得\(s_j-s_{i-1}\ge 0\)（如果\(j\)不存在，那么为了方便后续计算，令\(j=n+1\)）。此时，对于\(\forall k\in [i,j)\)，字符串\(t[i:j]\)都是好串；对于\(\forall k\in[j,n],t[i:j]\)都不是好串。我们只需要将\(j-i\)添加到统计结果即可。

接下来问题就转化成了如下形式：对于\(1\le i\le n\)，找到一个最小的\(j(j\ge i-1)\)，使得\(s_j\ge s_{i-1}\)成立。并将\(j-i\)添加到答案中。

这个问题可以使用单调栈进行解决，它是Leetcode 496的原题，这个栈维护右边元素至少一样大的列表，从栈顶到栈底的元素是单调递增的。

为了方便，代码实现时，字符串的区间都是左开右闭的。

代码

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

const int N=100004;
char t[N];
int s[N];
int main(){
    scanf("%s",t);
    int n=strlen(t);
    for(int i=1;i<=n;i++){
        if(t[i-1]=='1') s[i]=1;
        else s[i]=-1;
        s[i]+=s[i-1];
    }
    ll ans=0;
    stack<int>st;
    for(int i=n;i>=0;i--){
        while(!st.empty()&&s[i]>s[st.top()]){
            st.pop();
        }
        int k=st.empty()?n+1:st.top();
        ans+=k-i-1;
        st.push(i);
    }
    printf("%lld\n",ans);
}