求助求助 k型好数列

chenwhccc · 发表于 2021-11-21 00:49:00

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

如题，求一个思路？
一个长度大于等于2的数列，且其中任意两个元素 A;和4;（2+j）的和 4;十 A;都能整除飞，我们称其为区
型好数列。
现在输入一个长度为 N 的数列 A=[Ai,As,…AN 以及一个整数不，请你找出 A 的最长的区型好数列 B，输
出B的长度。
如果这样的子数组不存在，输出一1.
输入格式
筆一行包含两个整数 N 和区。
第二行包含 N 个整数 Ai, A2, ...AN。
1 ≤N≤100000
1≤4,5≤1000000000
例：输入53
输出13236

jhq999 · 发表于 2021-11-21 07:56:39

看不明白题目？

chenwhccc · 发表于 2021-11-21 10:31:12

是的，希望大佬给点思路和方法

jhq999 · 发表于 2021-11-21 10:35:01

chenwhccc 发表于 2021-11-21 10:31
是的，希望大佬给点思路和方法

我看不明白你的题目。
“A;和4;（2+j）的和 4;十 A;都能整除飞”这是啥意思，没看明白

chenwhccc · 发表于 2021-11-21 10:49:01

一个长度大于等于2的数列，且其中任意两个元素Ai和Aj的和能够整除K，则称K为K型好数列。
现在输入一个长度为N的数列A={A1 A2 …An}以及一个整数K，找出A的最好K型好数列B，输出B的长度
这是原题目

chenwhccc · 发表于 2021-11-21 11:26:29

jhq999 发表于 2021-11-21 10:35
我看不明白你的题目。
“A;和4;（2+j）的和 4;十 A;都能整除飞”这是啥意思，没看明白

还在吗？😶

jhq999 · 发表于 2021-11-21 11:27:41

本帖最后由 jhq999 于 2021-11-21 11:46 编辑

不知道我理解的对不对？

//数列A,int len=A的大小
int begin=0,end=0,i=0,j=0,flag=0,K=0;
cin>>K;
for(begin=0;begin<len-1;begin++)
{
    for(end=begin+1;end<len;end++)//在A中截取元素数量>=2的数列
    {
        flag=0;//初始化flag=0
        for(i=beging;i<end;i++)
        {
            for(j=i+1;j<=end;j++)//在截取的数列中取得任意两个数相加
            {
                if((A[i]+A[j])%K)//如果有一组相加不能整除K，跳出，并且让flag=1
                {
                  flag=1;
                  break;
                 }
             }
             if(flag)break;
         }
        if(flag)//如果flag=1
        {
          //A[begin]——A[end]不是K型好数列
         }
        else//如果flag=0，说明这组数列两两相加都能够整除K
          {
          //A[begin]——A[end]是K型好数列
         }
        
    }

}

chenwhccc · 发表于 2021-11-21 11:36:32

jhq999 发表于 2021-11-21 11:27
不知道我理解的对不对？

这个意思是三种情况吗？

jhq999 · 发表于 2021-11-21 11:37:51

chenwhccc 发表于 2021-11-21 11:36
这个意思是三种情况吗？

刚才应该是(A[i]+A[j])%K
已经改过来了

chenwhccc · 发表于 2021-11-21 11:41:51

jhq999 发表于 2021-11-21 11:37

cin>>K 是什么意思？

jhq999 · 发表于 2021-11-21 11:42:53

chenwhccc 发表于 2021-11-21 11:41
cin>>K 是什么意思？

输入数值给K,"整除K"

jhq999 · 发表于 2021-11-21 11:44:27

chenwhccc 发表于 2021-11-21 11:41
cin>>K 是什么意思？

输入数值给K

chenwhccc · 发表于 2021-11-21 11:49:19

jhq999 发表于 2021-11-21 11:44
输入数值给K

最终是要求得数列的长度，最后三行是不是错了？

jhq999 · 发表于 2021-11-21 11:52:52

chenwhccc 发表于 2021-11-21 11:49
最终是要求得数列的长度，最后三行是不是错了？

既然知道两两相加都能够整除K数列{A[begin]到A[end]},长度不就是end-begin+1

jhq999 · 发表于 2021-11-21 11:58:07

靠！不会是在A里面找出条件是两两相加能够整除K的所有元素吧

chenwhccc · 发表于 2021-11-21 12:00:08

jhq999 发表于 2021-11-21 11:58
靠！不会是在A里面找出条件是两两相加能够整除K的所有元素吧

对所有元素的集合长度

chenwhccc · 发表于 2021-11-21 12:05:31

chenwhccc 发表于 2021-11-21 12:00
对所有元素的集合长度

最大子列存在于：1全部是k的倍数2当k为偶数时全部是k/2的倍数3两数模k之和等于k（如果存在该情况，结果只能是2）。取三者最大
我现在基本思路是这样但是第三种情况不知道怎么实现

jhq999 · 发表于 2021-11-21 12:07:27

本帖最后由 jhq999 于 2021-11-21 12:11 编辑

又想错了，唉

jhq999 · 发表于 2021-11-21 13:09:43

本帖最后由 jhq999 于 2021-11-21 13:10 编辑

看看这个思路怎么样
末位淘汰制，直到大家整除的数量一样，且数量=剩下的-1

chenwhccc · 发表于 2021-11-21 13:11:37

jhq999 发表于 2021-11-21 13:09
看看这个思路怎么样
末位淘汰制，直到大家整除的数量一样，且数量=剩下的-1

能具体一点吗？属实想不明白

账号		自动登录	找回密码
密码			立即注册