Peter_Matthew的博客

题解 CPPU第五届“精武杯”计算机算法设计网络赛

2021-05-20

本文共7,274字,大约需要阅读32分钟。

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

本次比赛我认为值得一提的是7-1、7-6、7-7、7-10、和7-15,可以考虑重点看看这几道题的代码。

7-1 连续因子

一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7,其中 5、6、7 就是 3 个连续的数字。给定任一正整数 N,要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。

输入格式

输入在一行中给出一个正整数 N($1$<N<$2^{​31}$)。

输出格式

首先在第 1 行输出最长连续因子的个数;然后在第 2 行中按 因子1*因子2*……*因子k 的格式输出最小的连续因子序列,其中因子按递增顺序输出,1 不算在内。

输入样例

1
630

输出样例

1
2
3
5*6*7

鸣谢用户 漏穿雪 补充数据!

题解

我们考虑从2开始枚举因子1,然后判断因子1开始的k在满足题目要求的连续时最长可以为多少,在出现更大的k时更新答案。
例如,针对630,我们从2开始枚举出了以下几种情况

  • 2*3
  • 3
  • 5*6*7
  • 6*7
  • 7
  • 9*10
  • 10
  • 14
  • 15
  • 18
  • 21

考虑我们只需要枚举到$\sqrt{N}$,这是因为其余的部分k只能为1。
由于 $13!=6,227,020,800 > 2^{31}$,故k最大不会超过11,又由于对于一个素数,我们判断的时间是$O(\sqrt{N})$,所以整体的时间复杂度就是$O(10\sqrt{N})$。

代码

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0,an,sqn;
int main()
{
cin>>n;sqn=sqrt(n);
for(int i=2;i<=sqn;i++)
{
m=n;
for(int j=i;;j++)
{
if(m%j!=0)
{
if(ans<j-i)
{
ans=j-i;
an=i;
}
break;
}
m/=j;
}
}
if(!ans)
ans=1,an=n;
printf("%d",ans);
for(int i=0;i<ans;i++)
{
printf("%c%d",i==0?'\n':'*',i+an);
}
return 0;
}

7-2 我也会加密

字符串加密可以理解为对字符串的一种固定方式的变形,现定义一种基于种子数字的加密方法,首先计算种子数字,计算方法为将该字符串的长度对5求余加1,以该数字为间隔,得到原字符串的子串并求逆得到最终的密码。

输入格式

原字符串

输出格式

加密后的字符串

输入样例

在这里给出一组输入。例如:

1
abcdefghijklmn

输出样例

在这里给出相应的输出。例如:

1
kfa

题解

按照题意模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
string s;
char sta[100005];
int l;
int main()
{
cin>>s;
int n=s.length()%5+1;
for(int i=0;i<s.length();i+=n)
{
sta[l++]=s[i];
}
for(int i=l-1;i>=0;i--)
{
printf("%c",sta[i]);
}
return 0;
}

7-3 骑车还是走路?

在校园里,没有自行车,上课办事会很不方便。但实际上,并非去办任何事情都是骑车快。因为骑车总要找车、开锁、停车、锁车等,这要耽误一些时间。假设找到自行车,开锁并骑上自行车的时间为27秒;停车锁车的时间为23秒;步行每秒行走1.2米,骑车每秒行走3.0米。 编写程序判断走不同的距离去办事,是骑车快还是走路快。

输入格式

输入一个数,表示距离

输出格式

如果输入的距离骑车快,输出”Bike”;如果是走路快,输出”Walk”;如果一样快,输出”All”。

输入样例

1
120

输出样例

1
Bike

题解

按照题意模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
double bike,walk,m;

int main()
{
cin>>m;
bike=27+23+m/3.0;
walk=m/1.2;
if(bike<walk)
printf("Bike");
else if(bike>walk)
printf("Walk");
else
printf("All");
return 0;
}

7-4 虫子吃苹果

你买了一箱n个苹果,很不幸的是买完时箱子里混进了一条虫子。虫子每x小时能吃掉一个苹果,假设虫子在吃完一个苹果之前不会吃另一个,那么经过y小时你还有多少个完整的苹果? 编写程序进行计算。

输入格式

在同一行输入n、x和y,以逗号隔开

输出格式

还剩下完整的苹果个数

输入样例

以下输入表示:一箱10个苹果,虫子每4个小时吃一个苹果,经过9小时

1
10,4,9

输出样例

以下输出表示:还剩下几个完整的苹果?

1
7

题解

按照题意模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n,m,k;

int main()
{
scanf("%d,%d,%d",&n,&m,&k);
n-=(k+m-1)/m;
cout<<n;

return 0;
}

7-5 纵横

莫大侠练成纵横剑法,走上了杀怪路,每次仅出一招。这次,他遇到了一个正方形区域,由n×n个格子构成,每个格子(行号、列号都从1开始编号)中有若干个怪。莫大侠施展幻影步,抢占了一个格子,使出绝招“横扫四方”,就把他上、下、左、右四个直线方向区域内的怪都灭了(包括抢占点的怪)。请帮他算算他抢占哪个位置使出绝招“横扫四方”能杀掉最多的怪。如果有多个位置都能杀最多的怪,优先选择按行优先最靠前的位置。例如样例中位置(1,2)、(1,3),(3,2),(3,3)都能杀5个怪,则优先选择位置(1,2)。

输入格式

首先输入一个正整数T,表示测试数据的组数,然后是T组测试数据。对于每组测试,第一行输入n(3≤n≤20),第二行开始的n行输入n×n个格子中的怪数(非负整数)。

输出格式

对于每组测试数据输出一行,包含三个整数,分别表示莫大侠抢占点的行号和列号及所杀的最大怪数,数据之间留一个空格。

输入样例

1
2
3
4
5
1
3
1 1 1
0 1 1
1 1 1

输出样例

1
1 2 5

题解

循环暴力求解即可。这里可以采用行列记录的方法优化一维的复杂度。

代码

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
#include<bits/stdc++.h>
using namespace std;
int T;
int n,a[25][25],col[25],rol[25];
pair<int,int>anp;
int ans=0;
int main()
{
cin>>T;
while(T-->0)
{
memset(a,0,sizeof(a));
memset(col,0,sizeof(col));
memset(rol,0,sizeof(rol));
ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
col[i]+=a[i][j];
rol[j]+=a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int nw=col[i]+rol[j]-a[i][j];
if(nw>ans)
{
ans=nw;
anp=make_pair(i,j);
}
}
}
printf("%d %d %d\n",anp.first,anp.second,ans);
}


return 0;
}

7-6 小明打字

小明正使用Microsoft Word打一篇文档,文档只包含a-z的小写字母和空格,在打字过程中可能会一次或多次按下Home键、End键、←方向键、→方向键、Insert键、Backspace键。请编写程序,给定小明在键盘上按键的序列,输出小明屏幕上最终显示的文本。 提示:Home键会将当前光标移至文本开始位置,End键当前光标移至文本尾,←键和→键会使当前光标左移或右移一个位置(如果光标在文档头则无法左移,光标在文档尾则无法右移),Insert键会在插入和替换文本间切换(默认是插入状态),Backspace键会删除当前光标前的一个字符。

输入格式

输入为不超过50000个字符,表示小明的按键序列。包含a-z的小写字母、空格以及字符[、]、{、}、-、=。其中字符“[”表示Home键,“]”表示End键,“{”表示←键,“}”表示→键,“-”表示Insert键,“=”表示Backspace键。

输出格式

输出为在小明屏幕上最终显示的文本。最后一个字母后没有回车或换行。

输入样例1

1
jilin[i lofe{{-v-} ] universiti=y

输出样例1

1
i love jilin university

输入样例2

1
abcd[c-de

输出样例2

1
cdecd

输入样例3

1
[[]][][]happy=birthday

输出样例3

1
happbirthday

输入样例4

1
efg[bbb}}=}}}}=[{{{{a

输出样例4

1
abbbe

题解

对于C++选手来说,此题是一道STL的模板题。
我们设定两个值,当前光标和是否插入状态,并将题目中给的几个操作进行转换:

  • [ 转换为 将光标移到开头
  • ] 转换为 将光标移到结尾
  • { 转换为 将光标左移一位,这里要注意如果光标已经在开头,就不要移动
  • } 转换为 将光标右移一位,这里要注意如果光标已经在结尾,就不要移动
  • - 转换为 切换插入和替换状态的标记值
  • = 转换为删除光标前一位字符,并将光标左移一位
  • 其他字符
    • 如果为插入状态,则在光标位置插入字符并将光标右移一位
    • 如果为替换状态,则将光标位置的字符替换并将光标右移一位

我们可以利用string类的如下函数

  • erase(pos=0,len=npos)
  • insert(pos,n,c)

代码

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
#include<bits/stdc++.h>
using namespace std;
string str,s;
char c;
int nw=0,ist=1;
int main()
{
getline(cin,str);
int l=str.length();
for(int i=0;i<l;i++)
{
c=str[i];
if(c=='-')ist^=1;
else if(c=='[')nw=0;
else if(c==']')nw=s.length();
else if(c=='{')nw=max(0,nw-1);
else if(c=='}')nw=min((int)s.length(),nw+1);
else if(c=='=')
s.erase(nw=max(0,nw-1),1);
else
{
if(ist)
s.insert(nw,1,c);
else
s[nw]=c;
nw++;
}
}
cout<<s;
return 0;
}

7-7 锯齿几何

锯齿是由严格的高低不同的刀片组成,而锯齿数组指的是数组中的相邻元素一高一低严格不同。一个元素和两个不同的元素是齿数较少的锯齿数组,因空集属于任何子集,我们规定,空数组也是锯齿数组。如{2,30,5,7}是锯齿数组,而{2,2,30,8,5,7}不是锯齿数组,但我们可以删除2和8,构成长度为4的新的锯齿数组。编写程序,对输入的整数数组,计算删除若干元素后,构成的最长的锯齿数组(可删除元素,但其它元素的相对位置保持不变)的长度。

输入样例1

第一行,数组长度N,第二行是空格分隔的N个整数。

1
2
9
18 45 30 50 10 17 8 25 19

输出样例1

输出构成的最长的锯齿数组(本例中数据就是锯齿数组,故长度就是9)。

1
9

输入样例2

1
2
13
18 19 20 45 30 50 10 17 10 9 8 25 19

输出样例2

输出构成的最长的锯齿数组(本例中数据,至少可删除成上例中的锯齿数组,故长度最大长度也是9)。

1
9

输入样例3

1
2
4
18 15 9 9

输出样例3

输出构成的最长的锯齿数组(最多只能够留下两个齿)。

1
2

题解

一道双状态dp题。
我们对于每个点,都设计两个状态,这个点到下一个点是变高up和这个点到下一个点是变低dw两个状态,状态的值表示从这个点开始往后符合要求的最长长度。
初始状态每个点的两个状态都是1,因为每个点都可以仅剩下自己。
转移的方法是从后向前转移,后面点的dw状态可以转移给前面点的up状态当且仅当后面的点的高度大于前面的点;后面点的up状态可以转移给前面点的dw状态当且仅当后面的点的高度小于前面的点。
方程为
$up_i=max(up_i,dw_j+1),i<j,a_i<a_j$
$dw_i=max(dw_i,up_j+1),i<j,a_i>a_j$
最终状态是$max(max(up_i,dw_i))$

代码

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
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005],up[1005],dw[1005];
int ans=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
up[i]=dw[i]=1;
for(int j=i+1;j<=n;j++)
{
if(a[j]>a[i])
up[i]=max(up[i],dw[j]+1);
else if(a[j]<a[i])
dw[i]=max(dw[i],up[j]+1);
}
ans=max(ans,max(up[i],dw[i]));
}
printf("%d",ans);
return 0;
}

7-8 秋天的第一杯奶茶

2020年入秋后,朋友圈和微博上疯狂转发着自己收到的“秋天的第一杯奶茶”。然而小明却什么也没有收到,但是学校举行了这样一场活动:通过5道编写程序题目中的3道即可获得一杯奶茶。小明也想喝到秋天的第一杯奶茶。下面就请你判断小明是否有机会拿到学校的奶茶。
cppusf2021-7-8

输入格式

两行,第一行给出一个整数N(1<=N<=100),随后N行,每行给出一个长度为5的字符串(仅包含Y和N,分别代表5个题目小明是否通过),Y代表本题通过,N代表本题未通过。

输出格式

可以拿到奶茶输出“YES”,否则输出“NO”(输出不含双引号)。

输入样例

1
2
3
4
3
NNNYN
NNYYY
YYYNN

输出样例

1
2
3
NO
YES
YES

题解

按照题意模拟即可

代码

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
#include<bits/stdc++.h>
using namespace std;
int n,ny,nn;
char c;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
ny=0,nn=0;
scanf("\n");
for(int j=1;j<=5;j++)
{
scanf("%c",&c);
if(c=='Y')
ny++;
if(c=='N')
nn++;
}
if(ny>nn)
printf("YES\n");
else
printf("NO\n");
}


return 0;
}

7-9 镇长修路

某地对偏远地区实行“村村通”工程,目标是使整个地区任何两个村落间都可以实现快速交通(但不一定有直接的快速道路相连,只要互相间接通过快速路可达即可)。现得到拟修建道路的费用,现请你编写程序,计算出全地区畅通需要的最低成本。

输入格式

输入的第一行给出村庄数目N (1≤N≤20)和拟修建的道路数M

接下来的M行对应修建每条村庄间道路的成本,每行给出3个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本。

输出格式

输出需修建的道路,每行输出一条道路,形式如:道路1编号,道路2编号,费用。(编号小的放前面,编号大的放后面,逗号为英文状态下的逗号)

修建时优先修建最短的路,如果有多条路最短,则优先修建道路1编号小的路,再如果两条路道路1编号相同,则优先输出道路2小的路

输入样例

在这里给出一组输入。例如:

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

输出样例

在这里给出相应的输出。例如:

1
2
3
1,2,1
1,4,1
2,3,3

题解

最小生成树模板题

代码

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[25];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void merge(int x,int y)
{
int fx=getfa(x),fy=getfa(y);
if(fx==fy)return ;
fa[fx]=fy;
}
struct edge
{
int u,v,w;
}e[10005];
bool cmp(edge a,edge b)
{
if(a.w!=b.w)
return a.w<b.w;
if(a.u!=b.u)
return a.u<b.u;
return a.v<b.v;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
if(e[i].u>e[i].v)
swap(e[i].u,e[i].v);
}
sort(e+1,e+m+1,cmp);
int added=0;
for(int i=1;i<=m&&added<n-1;i++)
{
int fu=getfa(e[i].u),fv=getfa(e[i].v);
if(fu==fv)continue;
merge(fu,fv);
added++;
printf("%d,%d,%d\n",e[i].u,e[i].v,e[i].w);
}
return 0;
}

7-10 装修

胡老师买了新房,正在搞装修,装修公司太坑了,于是胡老师就自己找装修师傅来干活,但是装修的很多环节是环环相扣的,比如,要先刷墙才能铺木地板,有些环节呢,又是互相不干扰的,比如厨房的装修和窗帘的安装。但是每个装修师傅的时间又受他接的单所限制。所以必须仔细安排才能把房子装修好。胡老师收到了若干种不同装修师傅的安排,他想尽快装修好了入住,你能帮他吗?

输入格式

第一行输入正整数T(T< 20),表示有T个方案,对于每一个方案,第一行输入两个正整数N(< 100)和M,其中N是装修时间点的个数,从0开始编号,M是装修环节的个数。随后M行,每行输入三个非负整数表示一个装修环节,Start End Delay,Start表示开始时间点编号,End表示结束时间点编号,Delay表示装修需要时间。

输出格式

对每一个方案,如果方案可行,则在一行里输入最早结束的时间,如果不可行,则输出Impossible!

输入样例

在这里给出一组输入。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
7 10
0 1 3
0 2 2
0 3 6
1 3 2
2 3 1
1 4 4
3 4 1
2 5 3
4 6 3
5 6 4
3 3
0 1 1
1 2 2
2 0 3

输出样例

在这里给出相应的输出。例如:

1
2
10
Impossible!

题解

拓扑题,记录每个点的入度,从无入度的点开始访问,访问到一条边减少到点的入度,每个点开始访问的时间为最后一条前边遍历完成的时间,答案为最后一个被遍历到的点的访问时间。

代码

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
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,cnt,ans;
int inc[105],head[105];
struct edge
{
int ne,to,w;
}e[200005];
queue<int>q;
bool vis[105];
int st[105];
void clea()
{
cnt=0,ans=0;
memset(inc,0,sizeof(inc));
memset(head,0,sizeof(head));
memset(e,0,sizeof(e));
memset(st,0,sizeof(st));
memset(vis,0,sizeof(vis));
while(!q.empty())q.pop();
}
void add(int u,int v,int w)
{
e[++cnt]=(edge){head[u],v,w};head[u]=cnt;
}
int main()
{
cin>>T;
while(T-->0)
{
clea();
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);u++;v++;
inc[v]++;
add(u,v,w);
}
for(int i=1;i<=n;i++)
{
if(!inc[i])
{
q.push(i);
}
}
while(!q.empty())
{
int x=q.front();q.pop();
vis[x]=1;
for(int i=head[x];i;i=e[i].ne)
{
int y=e[i].to;
inc[y]--;
st[y]=max(st[y],st[x]+e[i].w);
}
for(int i=1;i<=n;i++)
{
if(!vis[i]&&!inc[i])
q.push(i);
}
}
for(int i=1;i<=n;i++)
{
ans=max(ans,st[i]);
if(!vis[i])
{
printf("Impossible!\n");
goto nextloop;
}
}
printf("%d\n",ans);
nextloop:
0;
}


return 0;
}

7-11 人与神

跨界大神 L. Peter Deutsch 有一句名言:“To iterate is human, to recurse divine.”(迭代的是人,递归的是神)。本题就请你直接在屏幕上输出这句话。

输入格式

本题没有输入。

输出格式

在一行中输出 To iterate is human, to recurse divine.

输入样例

输出样例

1
To iterate is human, to recurse divine.

题解

签到题

代码

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;


int main()
{
cout<<"To iterate is human, to recurse divine.";


return 0;
}

7-12 强迫症

小强在统计一个小区里居民的出生年月,但是发现大家填写的生日格式不统一,例如有的人写 199808,有的人只写 9808。有强迫症的小强请你写个程序,把所有人的出生年月都整理成 年年年年-月月 格式。对于那些只写了年份后两位的信息,我们默认小于 22 都是 20 开头的,其他都是 19 开头的。

输入格式

输入在一行中给出一个出生年月,为一个 6 位或者 4 位数,题目保证是 1000 年 1 月到 2021 年 12 月之间的合法年月。

输出格式

在一行中按标准格式 年年年年-月月 将输入的信息整理输出。

输入样例 1

1
9808

输出样例 1

1
1998-08

输入样例 2

1
0510

输出样例 2

1
2005-10

输入样例 3

1
196711

输出样例 3

1
1967-11

题解

按照题意模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int y,m;
char s[10];
int main()
{
scanf("%s",s);
if(strlen(s)==4)
{
sscanf(s,"%2d%d",&y,&m);
if(y<22)y+=2000;
else y+=1900;
}
else
sscanf(s,"%4d%d",&y,&m);
printf("%04d-%02d",y,m);
return 0;
}

7-13 病毒溯源

cppusf2021-7-13
病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株,而这些变异的病毒又可能被诱发突变产生第二代变异,如此继续不断变化。

现给定一些病毒之间的变异关系,要求你找出其中最长的一条变异链。

在此假设给出的变异都是由突变引起的,不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来,并且不存在循环变异的情况。

输入格式

输入在第一行中给 出一个正整数 N(≤$10^​4$),即病毒种类的总数。于是我们将所有病毒从 0 到 N−1 进行编号。

随后 N 行,每行按以下格式描述一种病毒的变异情况:

1
k 变异株1 …… 变异株k

其中 k 是该病毒产生的变异毒株的种类数,后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒(0≤i<N)。题目保证病毒源头有且仅有一个。

输出格式

首先输出从源头开始最长变异链的长度。

在第二行中输出从源头开始最长的一条变异链,编号间以 1 个空格分隔,行首尾不得有多余空格。如果最长链不唯一,则输出最小序列。

注:我们称序列 ${a_1,\cdots,a_n}$比序列${b_1,\cdots,b_n}$“小”,如果存在 $1≤k≤n$ 满足 $a_i=b_i$ 对所有 $i<k$ 成立,且 $a_k<b_k$​​ 。

输入样例

1
2
3
4
5
6
7
8
9
10
11
10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1

输出样例

1
2
4
0 4 9 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
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
int n;
int head[10005],cnt,inc[10005];
struct edge{
int ne,to;
}e[10005];
void add(int u,int v)
{
e[++cnt]=(edge){head[u],v};head[u]=cnt;
}
int ans,an[10005];
int nw[10005];
void dfs(int x,int d)
{
if(!head[x])
{
if(d>ans)
{
ans=d;
for(int i=1;i<=d;i++)
{
an[i]=nw[i];
}
}
else if(d==ans)
{
bool flg=0;
for(int i=1;i<=d;i++)
{
if(nw[i]<an[i])
flg=1;
else if(nw[i]>an[i])
break;
}
if(flg)
{
for(int i=1;i<=d;i++)
an[i]=nw[i];
}
}
return;
}
for(int i=head[x];i;i=e[i].ne)
{
nw[d+1]=e[i].to;
dfs(e[i].to,d+1);
nw[d+1]=0;
}
}
int main()
{
scanf("%d",&n);
for(int i=1,k,l;i<=n;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%d",&l);
add(i,l+1);
inc[l+1]++;
}
}
for(int i=1;i<=n;i++)
{
if(!inc[i])
{
nw[1]=i;
dfs(i,1);
nw[1]=0;
}
}
printf("%d",ans);
for(int i=1;i<=ans;i++)
{
printf("%c%d",i==1?'\n':' ',an[i]-1);
}
return 0;
}

7-14 大大的叉

打印出n阶的“叉”,这个叉图案由字符‘+’和‘X’构成,n越大,这个图案也就越大

输入格式

一个正整数n,1<=n<=20

输出格式

一个n阶叉图案

输入样例1

1
1

输出样例1

1
X

输入样例2

1
3

输出样例2

1
2
3
4
5
6
7
8
9
X+++X

+X+X+

++X++

+X+X+

X+++X

输入样例3

在这里给出一组输入。例如:

1
7

输出样例3

在这里给出相应的输出。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
X+++++++++++X
+X+++++++++X+
++X+++++++X++
+++X+++++X+++
++++X+++X++++
+++++X+X+++++
++++++X++++++
+++++X+X+++++
++++X+++X++++
+++X+++++X+++
++X+++++++X++
+X+++++++++X+
X+++++++++++X

题解

按照题意模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n;

int main()
{
cin>>n;
for(int i=1;i<=2*n-1;i++)
{
for(int j=1;j<=2*n-1;j++)
{
if(i==j||i+j==2*n)
printf("X");
else
printf("+");
}
printf("\n");
}


return 0;
}

7-15 3824经典游戏

24点游戏,也叫3824游戏,是一款经典的心算数字游戏。给出区间[1,13]内的四个整数,验证能否用加、减、乘、除四则运算,将这四个整数组合成24。比如:(3,8,2,4) 可以算出 8*(4−3+2)=24或者(8−4)*(2*3)=24,而(1,1,2,2)无法算出24。注意整除必须除尽,即9/2+10+10=24这种计算无效。

输入格式

第一行给出正整数N(1≤N≤1000)。接下来N行数据,每行给出四个正整数$a_i b_i c_i d_i$,用空格分开。($\forall i\in{1,…,N}:1≤a_i b_i c_i d_i≤13$)

输出格式

输出N行数据,第i行对应输入数据($a_i b_i c_i d_i$),如果能算出24,则输出24,如果不能则输出0。

输入样例

1
2
3
4
5
4
1 1 1 1
1 2 3 4
3 9 11 2
13 3 5 7

输出样例

1
2
3
4
0
24
0
24

(1,1,1,1)和(3,9,11,2)都无法算出24,(1,2,3,4)和(13,3,5,7)可以算出:1*2*3*4=24和(13*5+7)/3=24。

题解

整理下求24点的思路,给定四个数字,不限定他们的排序,自己指定三个运算符和括号添加位置,让结果等于24。
于是我们将四个数读入后排序,并使用next_permutation函数得到这四个数的全排列。
接着我们枚举三个运算符,一共有$4^3$种情况。
然后我们指定括号,这里指定括号可以理解为指定运算符的运算顺序,也就是123,132,213,231,312,321这几种,其中132和312这两种是相同的结果,于是就只有五种运算顺序。
枚举完所有情况后我们计算结果并判断是否为24即可。
需要注意的是对于除法,由于必须整除,我们最好写浮点运算,同时排除下除数是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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
int T;
int a[5];
int ans=0;
char op[]="/*-+";
bool d(int x)
{
if(x==24)
{
ans=24;
return 1;
}
return 0;
}
int cal(int x,int y,int tp)
{
if(tp==0)return x/y;
if(tp==1)return x*y;
if(tp==2)return x-y;
if(tp==3)return x+y;
}
bool model1(int t1,int t2,int t3)
{
int nw=a[1];
if(!t1&&(!a[2]||nw%a[2]!=0))return false;
nw=cal(nw,a[2],t1);
if(!t2&&(!a[3]||nw%a[3]!=0))return false;
nw=cal(nw,a[3],t2);
if(!t3&&(!a[4]||nw%a[4]!=0))return false;
nw=cal(nw,a[4],t3);
return d(nw);
}
bool model2(int t1,int t2,int t3)
{
int nw,nw1=a[1],nw2=a[3];
if(!t1&&(!a[2]||nw1%a[2]!=0))return false;
nw1=cal(nw1,a[2],t1);
if(!t3&&(!a[4]||nw2%a[4]!=0))return false;
nw2=cal(nw2,a[4],t3);
if(!t2&&(!nw2||nw1%nw2!=0))return false;
nw=cal(nw1,nw2,t2);
return d(nw);
}
bool model3(int t1,int t2,int t3)
{
int nw=a[2];
if(!t2&&(!a[3]||nw%a[3]!=0))return false;
nw=cal(nw,a[3],t2);
if(!t1&&(!nw||a[1]%nw!=0))return false;
nw=cal(a[1],nw,t1);
if(!t3&&(!a[4]||nw%a[4]!=0))return false;
nw=cal(nw,a[4],t3);
return d(nw);
}
bool model4(int t1,int t2,int t3)
{
int nw=a[2];
if(!t2&&(!a[3]||nw%a[3]!=0))return false;
nw=cal(nw,a[3],t2);
if(!t3&&(!a[4]||nw%a[4]!=0))return false;
nw=cal(nw,a[4],t3);
if(!t1&&(!nw||a[1]%nw!=0))return false;
nw=cal(a[1],nw,t1);
return d(nw);
}
bool model5(int t1,int t2,int t3)
{
int nw=a[3];
if(!t3&&(!a[4]||nw%a[4]!=0))return false;
nw=cal(nw,a[4],t3);
if(!t2&&(!nw||a[2]%nw!=0))return false;
nw=cal(a[2],nw,t2);
if(!t1&&(!nw||a[1]%nw!=0))return false;
nw=cal(a[1],nw,t1);
return d(nw);
}
int main()
{
cin>>T;
while(T-->0)
{
ans=0;
for(int i=1;i<=4;i++)scanf("%d",&a[i]);
sort(a+1,a+5);
do
{
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
for(int k=0;k<4;k++)
{
if(model1(i,j,k))goto nextloop;
if(model2(i,j,k))goto nextloop;
if(model3(i,j,k))goto nextloop;
if(model4(i,j,k))goto nextloop;
if(model5(i,j,k))goto nextloop;
}
}
}
}while(next_permutation(a+1,a+5));
nextloop:
printf("%d\n",ans);
}
return 0;
}
标签: 题解
使用支付宝打赏
使用微信打赏

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

扫描二维码,分享此文章