题解 CPPU第五届“精武杯”计算机算法设计网络赛 | 我有昕想法

本篇题解所使用的语言是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
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})$ 。

代码

#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`

输出样例

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

kfa

题解

按照题意模拟即可

代码

#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”。

输入样例

输出样例

Bike

题解

按照题意模拟即可

代码

#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小时

10,4,9

输出样例

以下输出表示：还剩下几个完整的苹果？

题解

按照题意模拟即可

代码

#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 5

题解

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

代码

#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

cdecd

输入样例3

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

输出样例3

`1`	`happbirthday`

输入样例4

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

输出样例4

abbbe

题解

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

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

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

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

代码

#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）。

输入样例2

1
2

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

输出样例2

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

输入样例3

1
2

4
18 15 9 9

输出样例3

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

题解

一道双状态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))$

代码

#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”（输出不含双引号）。

输入样例

3
NNNYN
NNYYY
YYYNN

输出样例

1
2
3

NO
YES
YES

题解

按照题意模拟即可

代码

#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

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

题解

最小生成树模板题

代码

#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

10
Impossible!

题解

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

代码

#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.`

题解

签到题

代码

#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

1998-08

输入样例 2

输出样例 2

2005-10

输入样例 3

输出样例 3

1967-11

题解

按照题意模拟即可

代码

#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

4
0 4 9 1

题解

本题是一道搜索题，写搜索记录最长链即可。

代码

#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

输入样例2

输出样例2

X+++X

+X+X+

++X++

+X+X+

X+++X

输入样例3

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

输出样例3

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

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

题解

按照题意模拟即可

代码

#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,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的情况即可。

代码

#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;
}