神崎兰子

2023-11-28 15:58 已编辑牛客网_在线教育部_课程讲师

关注

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

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

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

初赛共8题：ABCDEFGH，其中B组6题：ABDEFG，A组6题：BCEFGH。

A 字符串拼接

题目来源：经典语法题

知识点：基本语法

键盘输入两个字符串，将这两个字符串进行拼接后输出。

思路：按题意直接操作即可。

参考标程：

#include <iostream>
#include <string>
using namespace std;

int main() {

	string s1, s2;
	getline(cin, s1);
	getline(cin, s2);

	cout << s1 + s2 << endl;

	return 0;
}

B 差值

题目来源：校招公共题库

知识点：排序、贪心

alt

题意整理：给一个数组，任选两个元素，最小化它们的差值。

思路：排序之后，枚举相邻的元素，维护差的最小值即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int a[202020];
int main()
{
    int n,i,mi=1e9;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(i=1;i<n;i++)mi=min(mi,a[i]-a[i-1]);
    cout<<mi;
}

C 删除公共字符

题目来源：经典语法题

知识点：字符串

alt

思路：可以先用map存取第二个字符串中的字母，然后遍历第一个字符串时check一下是否在map中存在。另外本地的数据较小，直接 $O(n^2)$ 暴力枚举也是可以通过的。

参考代码（map做法）：

#include <iostream>
#include <string>
using namespace std;
string a, b;
int main() {
    getline(cin, a);
    cin >> b;
    map<char,int>m;
    for(auto i:b)m[i]++;
    for(auto i : a) {
        if (!m.count(i)) cout << i;
    }
    return 0;
}

参考代码（暴力做法）：

#include <iostream>
#include <string>
using namespace std;
string a, b;
int main() {
    getline(cin, a);
    cin >> b;
    for (auto &i : a) {
        bool flag = false;
        for (auto &j : b) {
            if (i == j) {
                flag = true;
            }
        }
        if (flag == false) cout << i;
    }
    return 0;
}

D 红色和紫色

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

知识点：博弈

alt

思路：

可以证明：当且仅当 $n$ 和 $m$ 都是奇数时，小红可以获胜。否则一定是紫获胜。

证明如下：

如果 $n$ 和 $m$ 都是奇数，那么 $n∗m$ 是奇数，存在一个中心的方格。小红只需要第一步给中间染色，之后紫在任意地方染色，小红只需要在紫染色的方格中心对称的位置染上和紫上次操作相同的颜色即可。这样一定是紫最先无法行动。

如果 $n$ 和 $m$ 不全是奇数，说明不存在中心的方格。紫只需要在每次小红染色后，在中心对称的位置上染上和小红上次操作不同的颜色（显然，这样一定是合法的）。如此最后不能操作的一定是小红。

参考代码（python）：

n,m=map(int,input().split())
if n*m%2==1:print("akai")
else:print("yukari")

E abb

题目来源：牛客题霸动态规划精选：abb

知识点：前缀和

alt

思路：

提示 1：对于每个字母 ch，找到后面和 ch 不等的两个相等字母的个数 cnt 即可，贡献为

$C_{cnt}^2=cnt*(cnt-1)/2$

提示 2：快速得出每个 cnt 的方式：开一个后缀和数组 $sum[n][26]$ ， $sum[i][j]$ 代表 $j$ 对应的字母，在坐标 $i$ 到 $n$ 出现的次数。这样就能 $O(1)$ 查询到每个字母后缀的出现次数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
long long sum[101010][26];
int main(){
    int n,i,j;
    string s;
    cin>>n>>s;
    for(i=n-1;i>=0;i--){
        for(j=0;j<26;j++)sum[i][j]=sum[i+1][j];
        sum[i][s[i]-'a']++;
    }
    long long res=0;
    for(i=0;i<n;i++){
        for(j=0;j<26;j++){
            if(j!=s[i]-'a'){
                res+=sum[i+1][j]*(sum[i+1][j]-1)/2;
            }
        }
    }
    cout<<res;
}

F kotori和素因子

题目来源：牛客竞赛题库：https://ac.nowcoder.com/acm/problem/50042

知识点：dfs

alt

思路：

观察到本题数据范围很小，因此直接dfs暴力搜索所有选择方案即可。

参考代码：

#include<stdio.h>
#define N 1010
int prime[168] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
bool st[168];        //第几个素数被用过了
int f[10][100];        //第i个数的质因子有第几个素数
int n,cnt[10];        //第i个数有几个质因子

int ans = 0x3f3f3f3f;
void dfs(int num, int sum)
{
    if(num == n){
        if(sum < ans)  ans = sum;
        return;
    }else{
        for(int i = 0; i < cnt[num]; i ++)
        {
            if(!st[f[num][i]]){
                st[f[num][i]] = true;
                dfs(num + 1, sum + prime[f[num][i]]);
                st[f[num][i]] = false;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        int a;
        scanf("%d",&a);
        for(int j = 0; a != 1; j ++)
        {
            if(a % prime[j] == 0)
            {
                f[i][cnt[i]++] = j;        //质因子有第几个素数
                while(a % prime[j] == 0)
                    a /= prime[j];
            }
        }
    }
    dfs(0,0);
    if(ans == 0x3f3f3f3f)  ans = -1;
    printf("%d",ans);
    return 0;
}

G 红和蓝

题目来源：牛客题霸动态规划精选：红和蓝

2021年牛客寒假训练营：红和蓝

知识点：树形dp

alt

思路：

可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：

若当前节点 $x$ 与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。
若当前节点 $x$ 与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。 $x$ 的“奇数大小子树”的那个子节点颜色和 $x$ 相同，其他都和 $x$ 不同。

参考代码：

#include<bits/stdc++.h>
using namespace std;
vector<int>g[200020];
int dp[200020];
int su(int x,int pr){
    int i,sum=1;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            sum+=su(g[x][i],x);
        }
    }
    return dp[x]=sum;
}
char out[200020];
int jud=0;
char f(char c){
    if(c=='R')return 'B';
    return 'R';
}
void dfs(int x,int pr,char c){
    if(jud)return;
    out[x]=c;
    int cnt=0,i;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            cnt+=dp[g[x][i]]&1;
        }
    }
    if(out[x]==out[pr]){
        if(cnt!=0){jud=1;return;}
        for(i=0;i<g[x].size();i++){
            if(g[x][i]!=pr){
                dfs(g[x][i],x,f(c));
            }
        }
    }
    else {
        if(cnt!=1){jud=1;return;}
        for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            if(dp[g[x][i]]&1)dfs(g[x][i],x,c);
                else dfs(g[x][i],x,f(c));
            }
        }
    }
}
int main(){
    int n,i;
    cin>>n;
    for(i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp[1]=su(1,-1);
    out[0]='B';
    dfs(1,0,'R');
    if(jud)cout<<-1;
    else for(i=1;i<=n;i++)cout<<out[i];
}

H 简单的三角形构造

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

知识点：计算几何，贪心，构造

alt

思路：

我们可以先这么想，假设没有“点 $P$ 在三角形外”的限制，可以构造的三角形面积最大是多少？

显然答案是圆内接正三角形。那么这道题首先就是要判断，能否构造一个圆内接正三角形满足 $P$ 在三角形外部。

观察下图：

图片说明

可以发现，只要 $P$ 到圆心 $O$ 的距离不小于 $\frac{1}{2}r$ 即可。

如果 $|OP|<\frac{1}{2}r$ 怎么办呢？观察下图：

图片说明

只需要构造一个等腰三角形，使得三角形的高为 $PO$ 的延长线即可。是否能构造成功取决于该三角形面积与 $S$ 的大小比较。

因此三角形的构造方式如下：

若 $|OP| \geq \frac{1}{2}r$ ，那么连接 $PO$ 并延长，交圆于点 $A$ ，构造等边三角形即可。

否则，延长 $PO$ 交圆于点 $A$ ，以 $PA$ 为高构造等腰三角形。

参考代码：

#include<bits/stdc++.h>
using namespace std;
struct point
{
    /* data */
    double x,y;
    point(){}
    point(double x,double y):x(x),y(y){}
};
double dis(point a){
    return sqrt((a.x)*(a.x)+(a.y)*(a.y));
}
double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
point AB(point a,point b){
    return point(b.x-a.x,b.y-a.y);
}
point dwh(point a){
    double d=dis(a);
    return point(a.x/d,a.y/d);
}
int main(){
    double r,s;
    point p,p0;
    cin>>r>>p.x>>p.y>>s>>p0.x>>p0.y;
    double d=dis(p,p0);

    double maxs=3.0/4*sqrt(3)*r*r;
    if (p0.x == p.x && p0.y == p.y) {
        maxs = r * r;
        if(maxs<s){cout<<-1;return 0;}
        point p1(p.x - r, p.y);
        point p2(p.x + r, p.y);
        point p3(p.x, p.y + r);
        printf("%.7f %.7f %.7f %.7f %.7f %.7f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
        return 0;
    }
    if(d*2<r){
        double dd=sqrt(r*r-d*d);
        maxs=(r+d)*dd;

    }

    if(maxs<s){cout<<-1;return 0;}
    point vt=AB(p0,p);
    point dvt=dwh(vt);
    point p1(p.x+dvt.x*r,p.y+dvt.y*r);
    double dd;
    point dv1(dvt.y,-dvt.x);
    point dv2(-dvt.y,dvt.x);
    if(d*2<r){
        dd=sqrt(r*r-d*d);

        point p2(p0.x+dv1.x*dd,p0.y+dv1.y*dd);
        point p3(p0.x+dv2.x*dd,p0.y+dv2.y*dd);

        printf("%.7f %.7f %.7f %.7f %.7f %.7f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);

    }
    else{
        dd=sqrt(3)*r/2;

        point pp(p.x+0.5*(p.x-p1.x), p.y+0.5*(p.y-p1.y));
        point p2(pp.x+dv1.x*dd,pp.y+dv1.y*dd);
        point p3(pp.x+dv2.x*dd,pp.y+dv2.y*dd);

        printf("%.7f %.7f %.7f %.7f %.7f %.7f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);

    }
   
}

#传智杯#