神崎兰子

2023-12-13 15:29 已编辑偶像大师灰姑娘女孩后端

关注

【题解】2023年第六届传智杯初赛第二场题解

补题链接： https://ac.nowcoder.com/acm/contest/72369

本次初赛第二场的题目也来源于牛客公共题库，基本是校招/竞赛原题或者经典题。考察的知识较为基础。

初赛第二场共8题：ABCDEFGH，其中B组6题：ACDEFG，A组6题：BDEFGH。

A 字符逆序

题目来源：牛客公开经典题目

alt

知识点：字符串

思路：直接调用系统自带函数，或者倒序遍历输出都可以。

参考代码（python）：

print(input()[::-1])

参考代码（c++）：

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

int main() {
    string s;
    getline(cin,s);
    reverse(s.begin(),s.end());
    cout<<s;
}

B 喵

题目来源：牛客小白月赛37：https://ac.nowcoder.com/acm/contest/11214/J

alt

知识点：字符串

忽略字符串最后三个字符，输出即可。

参考代码（python）：

a=input()
print(a[:-3])

参考代码（c++）：

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

int main() {
    string s;
    getline(cin,s);
    cout<<s.substr(0,s.length()-3);
}

C 小红的ABC

题目来源：牛客小白月赛41：https://ac.nowcoder.com/acm/contest/11218/B

知识点：字符串，枚举

思路：首先回文串有个性质：如果存在长度超过1的回文子串，那么最短回文子串的长度要么是2要么是3（因为如果存在一个长度为 $k$ 的回文子串，那么去掉首尾一定能得到一个长度为 $k-2$ 的回文子串）。因此直接特判这两种情况即可。（该做法复杂度 $O(n)$ ）

当然本题数据范围较小，直接暴力枚举每个子串判回文，然后维护合法最小长度也是可以通过的。纯暴力的复杂度为 $O(n^3)$ ，可以通过剪枝优化到 $O(n^2)$ 或者 $O(n)$ 。

参考代码：

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

int main() {
    string s;
    cin>>s;
    int i;
    for(i=1;i<s.length();i++)if(s[i]==s[i-1])return cout<<2,0;
    for(i=2;i<s.length();i++)if(s[i]==s[i-2])return cout<<3,0;
    cout<<-1;
}

D 小红取数

题目来源：牛客题霸-动态规划专项练习：小红取数

alt

知识点：动态规划

思路：我们计 $dp[i][j]$ 为：取前 $i$ 个数，模 $k$ 为 $j$ 的限制下的最大和，那么可以 $O(nk)$ 转移全部情况。

参考代码：

#include <bits/stdc++.h>
using namespace std;
long long dp[1010][1010];
int main() {
    long long n,k,i,x,j;
    cin>>n>>k;
    for(i=1;i<k;i++)dp[0][i]=-1e17;
    for(i=1;i<=n;i++){
        cin>>x;
        for(j=0;j<k;j++)dp[i][j]=dp[i-1][j];        //不取x
        for(j=0;j<k;j++){
            dp[i][(j+x)%k]=max(dp[i][(j+x)%k],dp[i-1][j]+x);    //取x
        }
    }
    cout<<(dp[n][0]>0?dp[n][0]:-1);
}

E 憧憬

题目来源：牛客小白月赛39：https://ac.nowcoder.com/acm/contest/11216/A

alt

知识点：枚举，计算几何

思路：我们直接 $O(n^2)$ 枚举所有情况即可。注意判向量平行可以把除法转化为乘法来规避可能存在的精度问题。

参考代码：

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

#define ll long long
int dis[4000040],vis[404040];
int a[1010][7];
int main(){
    ll t=1;
    //cin>>t;
    while(t--){
        ll n,i,k,j;
        cin>>n;
        for(i=0;i<n;i++)cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3],a[i][4]=a[i][2]-a[i][0],a[i][5]=a[i][3]-a[i][1];
        int x,y,xx,yy;
        cin>>x>>y>>xx>>yy;
        xx-=x,yy-=y;
        int jud=0;
        for(i=0;i<n;i++){
            for(j=i+1;j<n;j++){
                ll x4=a[i][4]+a[j][4],y4=a[i][5]+a[j][5];
                if(x4*yy==y4*xx)jud=1;
            }
        }
        if(jud)cout<<"YES";
        else cout<<"NO";
    }
}

F 加减

题目来源：牛客小白月赛37：https://ac.nowcoder.com/acm/contest/11214/I

alt

知识点：排序、前缀和、双指针/二分

思路：显然优先变化尽量接近的数。所以可以先对数组进行排序。

引理：一个数组每次操作可以让一个数加一或者减一，使所有数都相等的操作最小次数的方式是所有数都变成中位数（或两个中间的数的任意一个，若共有偶数个数）。

证明：一个数组有 $k$ 个数比中位数小， $k$ 个数（或 $k+1$ 个数，若共有偶数个数）比中位数大，假设把所有数都变成中位数的总操作次数为 $cnt$ 。这时如果让所有数变成比中位数更小的数，相当于对于 $x$ 个数而言 $(x<k)$ ，操作次数变少了，但对于 $y$ 个数而言 $(y>k)$ ，操作次数变多了同样的数值。总体来说操作次数一定是变多的。如果让所有数变成比中位数更大的数同理。证毕。

通过以上引理，我们只需要求出最大的一个区间，令其所有数都变成中位数的次数不超过 $k$ 即可。区间内部的操作次数可以通过前缀和达成 $O(1)$ 查询。

如何求这个最大区间呢？有两个方法：二分答案或者双指针。

方法一：二分答案

很明显，一定存在一个数 $x$ ，满足至少存在一个长度为 $x$ 的区间满足其所有数都变成中位数的次数不超过 $k$ 次，且不存在一个长度为 $x+1$ 的区间使得其所有数都变成中位数的次数不超过 $k$ 次。那么这个 $x$ 就满足可以用二分答案来求的性质。复杂度：二分单次判断的复杂度为 $O(n)$ ，总复杂度为 $O(nlogn)$

方法二：双指针

当固定左端点 $l$ 时，我们可以找到右边第一个不合法的右端点 $r$ ，当 $l$ 向右移动时， $r$ 也向右移动，移动到最新的第一次不合法的位置。维护 $r-l$ 的最大值即可。双指针复杂度为 $O(n)$ ，但还有排序的 $O(nlogn)$ ，总复杂度为 $O(nlogn)$

本题参考代码如下（双指针法）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100010],k,n;
ll sum[100010];
int main(){
    ll i,j,temp;
    cin>>n>>k;
    ll s=0;
    
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n;i++)sum[i+1]=s+=a[i];
    
    i=j=temp=0;
    ll res=0;
    for(i=0;i<n;i++)res+=abs(a[i]-a[n/2]);
    if(res<=k){
        cout<<n;
        return 0;
    }
    ll ma=0;
    for(i=0;i<n;i++){
        j--;
        do {
            j++;
            temp=(i+j)/2;
            res=(temp-i)*a[temp]-(sum[temp]-sum[i]);
            res+=sum[j+1]-sum[temp+1]-(j-temp)*a[temp];
        } while (j<n&&res<=k);
        ma=max(ma,j-i);
    }
    cout<<ma;
}

G 白魔法师

题目来源：牛客小白月赛25：https://ac.nowcoder.com/acm/contest/5600/C

alt

知识点：树，dfs，并查集

思路：如果将一个黑色点染成白色，那么将得到一个白色连通块，这个连通块由和这个黑色点连结的所有白色连通块组成。

如果将一个白色点染成白色，那么不会有任何变化。

所以我们可以先并查集预处理一下，把所有白色连通块的大小求出来，并把所有白色点对应的连通块表示一下。连通块的大小可以dfs或者统计并查集根的孩子总数得出。

然后统计所有黑色点的邻点连通块大小即可。要注意特判全部是白色点的情况。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>g[200020];
string s;
ll fa[200020],kdm[200020],sz[200020];
ll f(ll x){
    if(fa[x]==x)return x;
    return f(fa[x]);
}
void uni(ll x,ll y){
    ll p=f(x),q=f(y);
    if(p!=q){
        if(kdm[p]<kdm[q]){
            fa[p]=q;
            kdm[q]+=kdm[p]+1;
        }
        else{
            fa[q]=p;
            kdm[p]+=kdm[q]+1;
        }
    }
}
int main(){
    ll n,i,j,k,x,y;
    cin>>n>>s;
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=1;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
        if(s[x-1]=='W'&&s[y-1]=='W')uni(x,y);
    }
    for(i=1;i<=n;i++)
        if(s[i-1]=='W')sz[i]=kdm[f(i)]+1;
    ll ma=0;
    for(i=1;i<=n;i++){
        if(s[i-1]=='B'){
            ll sum=1;
            for(j=0;j<g[i].size();j++)
                if(s[g[i][j]-1]=='W')sum+=sz[g[i][j]];
            ma=max(ma,sum);
        }
    }
    if(ma==0)cout<<n;
    else cout<<ma;
}

H 紫妹永不服输

题目来源：牛客小白月赛37：https://ac.nowcoder.com/acm/contest/11214/E

alt

知识点：构造

思路：

引理：由 $x$ 个 R 、 $y$ 个 P 组成的字符串，其中 'RP' 子序列的数量和 'PR' 子序列的数量之和为 $x*y$ 。

证明：

一个字符串共有 $x$ 个 R 、 $y$ 个 P ，那么在这些 R 和 P 中各选一个，方案数共有 $x*y$ 种，要么构成 'PR' ，要么构成 'RP'。其必为原串的一个子序列。因此 'RP' 子序列的数量和 'PR' 子序列的数量之和为 $x*y$ 。证毕。

因此我们需要构造一个由 $x$ 个 R 、 $y$ 个 P 组成的字符串，其中 $x$ 和 $y$ 满足 $x*y=m+n$ 。也就是说，我们需要找到 $Q=m+n$ 的两个因子，它们的乘积等于 $Q$ 且和不大于100000。

所以我们可以采取贪心的策略，取尽可能接近 $\sqrt q$ 的两个因子即可。

关于具体的构造方法：

如果构造成 RR..RRPP...PP （ $x$ 个R， $y$ 个P），此时共有 $x*y$ 个 'RP' 。

这时我们如果把最后一个 R 向右移动一为，则可以转化一个 'RP' 为 'PR' 。如果把最后一个 R 放到所有 P 的后面，那么转化了 $y$ 个 PR。以此类推，我们可以找到最终字符串的形态。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,m;
    cin>>n>>m;
    long long sum=n+m;
    int x=1,i;
    for(i=2;i*i<=sum;i++){
        if(sum%i==0)x=i;
    }
    if(x+sum/x>=100000){
        cout<<-1;
        return 0;
    }
    int y=sum/x;
    int left=n/y,right=m/y;
    if(n%y==0){
        while(left--)cout<<'R';
        while(y--)cout<<"P";
        while(right--)cout<<'R';
    }
    else{
        int yu=n%y;
        while(left--)cout<<'R';
        while(y--){
            
            cout<<"P";
            if(y==yu)cout<<'R';
            
        }
        while(right--)cout<<'R';
    }
}