P8027 题解

yeshubo_qwq · 2022-01-20 15:25:12 · 题解

题意

给你 n 个数，要求选出一段，可以令其分成 k 个完全相同的小段。

如果有符合的选取方式，请输出任意一种符合的选取方式一小段的颜色情况；否则输出 -1。

思路

这道题范围很小，只有 50，考虑 O\left(n^4\right) 暴力枚举，寻找符合的选取方式。

具体实现：第一个循环枚举长度，第二个循环枚举起点，第三个循环枚举每一个小段，第四个循环枚举小段的第几个位置并进行判断。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,l,i,j,t,flag,a[55];
int main(){
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(l=1;l<=n/k;l++)//枚举长度
        for(i=1;i+l*k-1<=n;i++){//枚举起点
            flag=1;//默认此解符合 
            for(j=2;j<=k;j++)//枚举每一个小段
                for(t=1;t<=l;t++)//枚举小段的第几个位置
                    if(a[i+t-1]!=a[i+l*(j-1)+t-1]){//与第一小段进行判断
                        flag=0;//此解不符合
                        break;
                    }
            if(flag==1){//输出任意一种符合的选取方式 
                printf("%d\n",l);
                for(j=1;j<=l;j++)
                    printf("%d ",a[i+j-1]);
                return 0;
            }
        }
    printf("-1");//无解输出-1 
    return 0;
}