Peter_Matthew的博客

题解 CPPUAPA 2022年寒假第一次模拟赛

2022-01-09

本文共5k字，大约需要阅读20分钟。

本篇题解所使用的语言是C++，部分其他语言的选手可能需要理解做法后自行编写对应语言的代码。

L1-1 打个招呼

背景
这是寒假的第一次模拟赛（可能也是最后一次模拟赛。。），关系到咱们天梯赛等比赛的选拔，希望大家怀着淡淡的喜悦尽情发挥！
描述
首先打个招呼，在屏幕上输出“HELL0 CPPUAPA!”。

输入格式

本题无输入。

输出格式

一行一个字符串，为打招呼的内容

输入样例

1
2


输出样例

1
HELL0 CPPUAPA!

题解

直接输出原文即可，注意是 HELL0 ，不是 HELLO 。

代码

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"HELL0 CPPUAPA!";
    return 0;
}

L1-2 昊神的游戏

邓晨昊和张开昕因为某些不可抗拒的原因寒假不能回家，他们在李志老师的办公室中百般无聊，于是昊神发明了一个新游戏让开昕玩。

游戏是要在纸上画一列长度为n的正方形，每个正方形可以是白色或黑色（1表示白色，0表示黑色）。玩家可以选择任意两个相邻并且颜色相同的正方形，并将它们重新涂色（可以是两个白色、两个黑色，也可以是一白一黑），游戏的目标是要让这一列正方形中任意两个相邻的正方形颜色都不同。

开昕觉得这个题目太简单了于是将它丢给了你，现在请你帮开昕计算一下，他至少需要几次操作才能达成目标？

输入格式

输入总共两行。

第一行包括一个数字n(1<=n<=1000)。n表示这列正方形的个数。

第二行包括n个数字0或1，表示每个正方形的颜色。

输出格式

输出一行，即开昕操作的最少次数。

输入样例 1

1
2
6
111010

输出样例 1

1
1

输入样例 2

1
2
7
1100010

输出样例 2

1
2

题解

我们考虑当一列正方形任意两个相邻的正方形颜色都不同时，一定是 010101... 或者 101010... 的排列。
若初始状态不是刚好满足排列时，则必定存在两个相邻正方形颜色相同的情况。显然，我们不会将两个相邻正方形颜色重新涂色成两个颜色相同的，而会是涂成一白一黑。
我们假设要将 001010 变为 010101 ，则需要先将序列变为 011010 ，然后变为 010010 、 010110 、 010100 ，最后变成 010101 。
可以看出来序列变换的次数是原序列和目标序列中数字不同的个数。

对于一整个序列来说，可以将序列划分成一小段一小段，每一小段分为需要按照上方给出的方法变换和已经满足排列两种，最后拼合答案即为整个序列中与目标序列中数字不同的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n,a,ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%1d",&a);
        if(a==(i&1))ans++;
    }
    ans=min(ans,n-ans);
    printf("%d",ans);
    return 0;
}

L1-3 懒羊羊的压岁钱

马上就要过年啦，懒羊羊又可以收压岁钱了，他非常开心，但他不愿意告诉他的父母他到底收了多少压岁钱，因为懒夫和懒母经常会以各种名义扣下这笔钱，他只想存下这笔钱作为和他的挚友喜羊羊的购房基金(呜呜呜喜懒szd!)。于是他给喜羊羊写信时进行了加密，信的内容是一串字符串，他今年收到的压岁钱的数量就是这个字符串中对称子串的数量，这样就算这封信件在通信过程中被懒夫懒母截获，他们也不知道这封信件的真正内容。

对称串是一个正读和反读都一样的字符串，比如”baaab”或者”non”再或者”a”这样的就是对称串；如果在这个字符串中能找到几个连续的字符构成一个对称串，则称这几个字符为这个字符串的对称子串。值得注意的是，具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

现在告诉你懒羊羊的信件内容，你能知道他今年一共收到了多少压岁钱吗？

输入格式

输入一个字符串

输出格式

输出一个整数，为字符串中对称子串的数量

输入样例 1

1
abc

输出样例 1

1
3

输入样例 2

1
oops

输出样例 2

1
5

提示

字符串长度len<=1000

题解

寻找回文串的题，可以使用Manacher或者PAM解题。
然而本题题目中字符串长度仅为1000，暴力枚举子串，然后判断是不是回文串即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
char s[1005];
int len,ans=0;
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    for(int l=1;l<=len;l++)
    {
        for(int i=1;i<=len-l+1;i++)
        {
            bool tag=true;
            for(int j=0;j<=l/2;j++)
            {
                if(s[i+j]!=s[i+l-1-j])
                {
                    tag=false;
                    break;
                }
            }
            if(tag)ans++;
        }
    }
    printf("%d",ans);
    return 0;
}

L1-4 这是一道水题

–Background

看了一眼大家出的题目，也太难了。

于是心地善良的好学长决定出一道水题让大家放松一下~

–Description

天梯赛马上就要到了，APA的同学们又要开始纠结起什么队名了。

李志老师一般都把起名字的权利交给大家。但老师也有一些不喜欢的词汇，是不可以出现在队伍名称里的。例如，老师不喜欢毛毛虫，于是2019年的天梯队名“飘起来的毛毛虫”就让老师看着很不舒服。

现在我们罗列出了老师不喜欢的N个词汇。你需要在三个小组上报队伍名称之前进行一轮检查，若出现了老师不喜欢的词汇，则需要把相关词汇剔除后再上报

输入格式

第一行输入一个数字N，表示老师不喜欢的词汇数量。

接下来N行，每行包含一个没有空格的字符串，表示老师不喜欢的词汇。

再接下来3行，每行包含一个可能含有空格的字符串，表示三支队伍上报的队名。

输出格式

输出包含3行，依次为三个队名的判断结果。(区分大小写)

若队名没有问题，则输出“No problem!”，否则，请将老师不喜欢的词汇剔除后，输出新队名。

只需要删除词汇对应的字符即可，前后若有空格无需删除

输入样例

1
2
3
4
5
1
maomaochong
maomaochong on the keyboard
Piaoqilaidemaomaochong
Wo zhi xiang yao KFC

输出样例

1
2
3
 on the keyboard
Piaoqilaide
No problem!

提示

N≤100，所有字符串长度len≤100。

题目保证一个队名中最多包含一个老师不喜欢的词汇。

题解

一道字符串匹配的题，这道题有很多种做法，说一种比较简单的做法，这种做法会利用到C和C++的一个特性。字符串在数组中的结束是以到值为0的字符为标志，所以当我们找到问题词汇的时候，将问题词汇开始的那个字母归0，这样从开头输出就只会输出到这个字母之前的部分，然后我们从这个词汇之后的地方继续输出，就可以达到删除对应词汇的效果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int n,T=3;
char s[105][105],t[110];
int sl[105],tl;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("\n%s",s[i]+1);
        sl[i]=strlen(s[i]+1);
    }
    while(T-->0)
    {
        scanf("\n");
        cin.getline(t+1,105);
        tl=strlen(t+1);
        int ts=0;
        for(int j=1;j<=tl;j++)
        {
            for(int i=1;i<=n;i++)
            {
                if(t[j]==s[i][1])
                {
                    bool tag=true;
                    for(int k=2;k<=sl[i];k++)
                    {
                        if(t[j+k-1]!=s[i][k])
                        {
                            tag=false;
                            break;
                        }
                    }
                    if(tag)
                    {
                        t[j]=0;
                        ts=j+sl[i];
                        break;
                    }
                }
            }
            if(ts)
                break;
        }
        if((int)strlen(t+1)==tl)
            printf("No problem!\n");
        else
            printf("%s%s\n",t+1,t+ts);
    }
    return 0;
}

L2-1 军训

警察大学的军训开始了，小梁作为带训班长需要给他所带的班的新生排队列，以下是他凭借多年带训经验总结的排队列方法：

先给班里每个新生一个编号（1~n），然后让1号新生先站在队列里，然后通过目测身高，凭感觉将第i名新生安排在之前已经在队列里的某位新生的旁边。

某次训练中，教员让带训班长们训练新生的出列动作，梁班长在让m（m<n）名同学出列后，想知道这时队列从左到右新生的编号

输入格式

第1行为新生人数

第2~n行，第i行包含一个整数a和一个字符b，其中a为小于i的正整数，b为z或者y。若b为z，则表示将i号新生插入到a号新生的左边，b为y则表示插入到右边。

第n+1行为新生的同学。

接下来m行，每一行一个数，代表出列的新生的编号（如果该新生已经出列就是梁班长记性不好，不用管这个出列的指令）。

输出格式

若干个正整数，数与数之间用空格隔开，表示从左到右新生的编号，行末换行且无空格。

输入样例

1
2
3
4
5
6
7
4
1 z
2 y
1 z
2
3
3

输出样例

1
2 4 1

提示

1<n,m<=100000

题解

一道链表的裸题，唯一需要注意的就是加入一个已经被清除的标记。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct stu
{
    int l,r;
    bool er;
}s[100005];
int main()
{
    scanf("%d",&n);
    s[0].l=s[0].r=1;
    for(int i=2;i<=n;i++)
    {
        int x;char c;
        scanf("\n%d %c",&x,&c);
        if(c=='z')
        {
            s[i].r=x;
            s[i].l=s[x].l;
            s[s[x].l].r=i;
            s[x].l=i;
        }
        if(c=='y')
        {
            s[i].l=x;
            s[i].r=s[x].r;
            s[s[x].r].l=i;
            s[x].r=i;
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("\n%d",&x);
        if(s[x].er)continue;
        s[s[x].l].r=s[x].r;
        s[s[x].r].l=s[x].l;
        s[x].er=true;
    }
    for(int i=s[0].r;i;i=s[i].r)
    {
        printf("%d%c",i,s[i].r?' ':'\n');
    }
    return 0;
}

L2-2 大大大卡车

警察大学新研究生宿舍楼正在如火如荼地建设中，大卡车不停地穿梭在校园间运送货物。他们总共需要运送两种类型的货物，记为A和B。类型A的货物重量为1，类型B的货物重量为2，每个货物都有一个编号和价值。

为了能让研究生学长学姐们更快地住上新宿舍，工程师在校园中找到了会设计算法的你，请你帮他计算大卡车一次运送货物的最大价值。

输入格式

第一行，包含两个整数 n 和 v。表示有 n 个物品（1 ≤ n ≤ 10^5）， 大卡车的载重量为 v （1 ≤ v ≤ 10^9）。

接下来 n 行， 每行两个整数，第i行表示编号为i的货物的重量 ti （1 ≤ ti ≤ 2）和价值 pi（1 ≤ pi ≤ 10000）。

输出格式

第一行为一个整数， 表示大卡车单次能运送的最大价值。

第二行为构成最大价值的全部物品编号。

输入样例 1

1
2
3
4
3 2
1 2
2 7
1 3

输出样例 1

1
2
7
2

输入样例 2

1
2
3
4
5
6
5 3
1 9
2 9
1 9
2 10
1 6

输出样例 2

1
2
24
1 3 5

提示

输出时注意：优先输出类型A的货物编号，并按货物的价值从大到小排序输出，以空格分隔。

题解

本题看上去是一个动态规划题，但我们看数据范围会发现用动态规划会超时。实际上，这个题就是一个排序的题目。
我们将物品分两种分别记录并降序排序，然后枚举可能的排列情况，比如5的时候，可能是 122 、 1112 和 11111 这三种，枚举情况判断价值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
int n,v;
int l1,l2,ans,an1,an2;
int s1[100005],s2[100005];
struct wp
{
    int p,id;
}v1[100005],v2[100005];
bool cmp(wp a,wp b)
{
    return a.p>b.p;
}
int main()
{
    scanf("%d%d",&n,&v);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d",&v1[++l1].p);
            v1[l1].id=i;
        }
        if(x==2)
        {
            scanf("%d",&v2[++l2].p);
            v2[l2].id=i;
        }
    }
    sort(v1+1,v1+l1+1,cmp);
    sort(v2+1,v2+l2+1,cmp);
    for(int i=1;i<=l1;i++)
        s1[i]=s1[i-1]+v1[i].p;
    for(int i=1;i<=l2;i++)
        s2[i]=s2[i-1]+v2[i].p;
    for(int i=0,sum;i<=min(v,l1);i++)
    {
        sum=s1[i]+s2[min((v-i)/2,l2)];
        if(sum>ans)
        {
            ans=sum;
            an1=i;
            an2=min((v-i)/2,l2);
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=an1;i++)
        printf("%d ",v1[i].id);
    for(int i=1;i<=an2;i++)
        printf("%d ",v2[i].id);
    return 0;
}

L2-3 LF市规划

LF市要重新规划城市建筑了，现在LF市有n个给建筑物预留的位置，LF市政府决定只建设n-1条长度为1的双向道路，每条道路连接两个位置，且任意两个位置可以通过这些道路相互到达。

LF市政府决定在其中的k个位置建设LF市的核心建筑物，这些建筑物往往是市政府、市检察院、市法院、市监察委等；在其余的n-k个位置建设其他的非核心建筑物。为了让核心建筑物更好的服务人民，这k个位置需要在建成城市以后让对应的k个核心建筑物满足以下条件：

  1. 这k个核心建筑物之间可以直接通过核心建筑物之间的道路相互到达，而不需要经过非核心建筑物。
  2. 一个非核心建筑物到这k个核心建筑物的距离，为其与这k个核心建筑物的距离的最小值，也就是其与其最近的核心建筑物的距离。所有非核心建筑物到这k个核心建筑物的距离的最大值需要最小。

现在，你需要求出建成城市以后，所有非核心建筑物到这k个核心建筑物的距离的最大值。

输入格式

输入共n行。

第一行有两个正整数n和k。

接下来的n-1行，每行有两个正整数u和v，表示第u个位置和第v个位置之间有一条长度为1的双向道路。

输出格式

输出共一行一个整数，表示答案。

输入样例

1
2
3
4
5
6
7
7 4
1 4
7 3
7 4
2 1
5 4
6 5

输出样例

1
1

提示

数据范围

1≤k<n≤ $10^5$ 。

1≤u,v≤n，且u≠v。

保证任意两个位置可以通过这些道路相互到达。

样例#1说明

在1,4,5,7这4个位置建设核心建筑物，这样2,3,6的3个非核心建筑物与4个核心建筑物的距离均为1，答案为1。

题解

一道树的性质的题。
首先，我们不难看出题中的图给的是一棵树。
根据核心建筑物的性质1，我们可知，所有的核心建筑物都是直接相连的，中间不会有非核心建筑物。
所以我们可以找出核心建筑物里最核心的那一个，将其作为树的根节点，向下延伸选择最优的k-1个节点即可。
根据性质2，我们知道这个最核心建筑物就是树的重心。
因此思路就是求出树的重心，按照节点距离排序剩下的节点，选择前k-1个即可。节点选择的时候，选择一个节点会减少最下方节点到核心区的距离，于是我们选择了到核心区距离最大的节点的祖辈节点，即可减小全局最大距离。
然后算出所求的距离。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
int n,k,dm,rt,hf;
int head[100005],cnt;
int d[100005],to[100005],fa[100005];
int dis[100005],ans;
struct edge
{
    int ne,to;
}e[200005];
void add(int u,int v)
{
    e[++cnt]=(edge){head[u],v};head[u]=cnt;
    e[++cnt]=(edge){head[v],u};head[v]=cnt;
}
void dfs1(int x,int f)
{
    if(d[x]>dm)
    {
        dm=d[x];
        rt=x;
    }
    for(int i=head[x];i;i=e[i].ne)
    {
        int y=e[i].to;
        if(y==f)continue;
        d[y]=d[x]+1;
        fa[y]=x;
        dfs1(y,x);
    }
}
void dfs2(int x,int f)
{
    to[x]=d[x];
    for(int i=head[x];i;i=e[i].ne)
    {
        int y=e[i].to;
        if(y==f)continue;
        d[y]=d[x]+1;
        dfs2(y,x);
        to[x]=max(to[x],to[y]);
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,u,v;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs1(1,0);
    memset(d,0,sizeof(d));
    memset(fa,0,sizeof(fa));
    dm=0;
    dfs1(rt,0);
    hf=rt;
    for(int i=1;i<=(d[rt]+1)/2;i++)
        hf=fa[hf];
    memset(d,0,sizeof(d));
    dfs2(hf,0);
    for(int i=1;i<=n;i++)
        dis[i]=to[i]-d[i];
    sort(dis+1,dis+n+1,greater<int>());
    for(int i=k+1;i<=n;i++)
        ans=max(ans,dis[i]+1);
    printf("%d",ans);
    return 0;
}

L3-1 dyd的好奇心

众所周知，dyd身高有两米所以总是被安排在队列的排头，队列是由学生组成的N×N的方阵。然而dyd是个好奇心重的少年会在队列的一角向周围望去并数清他所能看到的学生人数。善于思考的dyd已经摸清了随着N变化他所能看到人数的规律，然而为了考考你，希望你告诉他能看到的学生人数。

输入格式

一行，一个正整数 N。

输出格式

输出一行一个数，即 dyd应看到的学生人数。

输入样例

1
4

输出样例

1
9

提示

对于 100% 的数据，1≤N≤10000。

题解

我们将这些坐标从(0,0)编号到(n-1,n-1)，我们不难发现，可以被dyd看到的学生坐标都满足坐标的两个数字互质，因此dyd可以看到的学生数量是 $\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}\left [ \gcd (i,j)=1\right ]$ 再补上(0,1)和(1,0)两种情况。
同时，我们发现，可以利用对称性，让 $i>j$ ，变成 $\sum_{i=2}^{n-1}\sum_{j=1}^{i-1}\left [ \gcd (i,j)=1\right ]$ 在乘以2的同时除了(0,1)和(1,0)再补上(1,1)一共三种情况。
不难发现， $\sum_{j=1}^{i-1}\left [ \gcd (i,j)=1\right ]$ 即为欧拉函数 $\varphi (i)$ ，得到的答案是 $2\sum_{i=2}^{n-1}\varphi (i)+3$ ，考虑 $i=1$ 的情况，则最终答案就是 $2\sum_{i=1}^{n-1}\varphi (i)+1$ ，注意n为1时答案为0的特判即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int phi[10005];
void calcphi(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
    	if(!phi[i])
    	{
    		for(int j=i;j<=n;j+=i)
    		{
    			if(!phi[j])
    				phi[j]=j;
    			phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    if(n==1)
    {
        printf("0");
        return 0;
    }
    calcphi(n);
    for(int i=1;i<n;i++)
        ans+=phi[i];
    ans=ans*2+1;
    printf("%d",ans);
    return 0;
}
当前页共有次阅读，条评论。
标签: 题解
← 【宝塔面板使用心得】L01 宝塔面板的安装 【宝塔面板使用心得】L02 认识界面与配置 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏