| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1694 人关注过本帖
标题:求子数组中任意两数之和能整除k的最大元素个数
只看楼主 加入收藏
下节啥课
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2021-11-16
结帖率:0
收藏
已结贴  问题点数:20 回复次数:10 
求子数组中任意两数之和能整除k的最大元素个数
题目描述
一个长度大于等于2的数列,且其中任
意两个元素Ai和Aj(i≠j)的和Ai+Aj都能整除K,我们称其为K型好数列。
现在输入一个长度为N的数列A=[A1,A2,...AN]以及一个整数K,请你找出A的最长的K型好数列B,输出B的长度。
如果这样的子数组不存在,输出-1.
输入格式
第一行包含两个整数N和K.
第二行包含N个整数A1,A2,...AN.
1≤N≤100000
1≤Ai, K≤1000000000
输出格式
一个整数,表示答案。

搜索更多相关主题的帖子: 元素 数列 整数 整除 数组 
2021-11-16 20:42
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:7 
程序代码:
#include <stdio.h>
int goodSeries(int *a, int n, int s)
{
    int i, len=0, b=-1, t=-1;
    for (i=0; i<n-1; i++)
    {
        if (((a[i]+a[i+1])%s) == 0)
        {
            b = 2;
            break;
        }
    }
    if (s&1)
    {
        for (i=0; i<n; i++)
        {
            if ((a[i]%s) == 0)
            {
                len++;
            }
            else
            {
                if (len > b)
                {
                    b = len;
                }
                len = 0;
            }
        }
        if (len > b)
        {
            b = len;
        }
    }
    else
    {
        for (i=0; i<n; i++)
        {
            if ((a[i]%s) == t)
            {
                len++;
            }
            else
            {
                if (len > b)
                {
                    b = len;
                }
                t = -1;
                len = 0;

                if ((a[i]%s) == 0)
                {
                    t = 0;
                    len++;
                }
                else if ((a[i]%s) == (s>>1))
                {
                    t = s>>1;
                    len++;
                }
            }
        }
        if (len > b)
        {
            b = len;
        }
    }
    return b;
}

void main()
{
    int a[100000];
    int n, k, i, b;
    char tmp;
    scanf("%d%d", &n, &k);

    for (i=0; i<n; )
    {
        if (scanf("%d", a+i) == 0)
        {
            scanf("%c", &tmp);
            continue;
        }
        i++;
    }
    b = goodSeries(a, n, k);
    printf("%d\n", b);
}
2021-11-17 12:59
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:7 
回复 2楼 diycai
    for (i=0; i<n-1; i++)
    {
        if (((a[i]+a[i+1])%s) == 0)
        {
            b = 2;
            break;
        }
    }

这一段的思路应该是错的
你准备挑选出两个和能整除s
作为其他情况不满足的最后可选
但是 只检查连续不合理呀
比如
序列
1 5 6 100
s是7
结果序列应该是 [1 6] 或者[5 100] 不连续的
那你的这个循环就错过了正确选项了

https://zh.
2021-11-17 17:05
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:0 
回复 3楼 lin5161678
你再看一下题目,是任意两个都满足,而不是任选两个满足即可。
2021-11-17 18:26
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
回复 4楼 diycai
我说的是 对于数列 [1, 5, 6, 100] s == 7的情况
选出子数列 [1, 6] 满足 任意两个加起来整除7的要求

我看明白了 你以为子数组是连续的?
不是的 从数组里面删除任意多的元素得到的都是这个数组的子数组

https://zh.
2021-11-18 08:56
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:7 
这题目连个示例都不肯给,纯属浪费时间。

@diycai
按照 lin5161678 所言,我输入 4 7 1 5 6 100,你的程序输出 0,但正确的结果应该是 2 呀!

我简单思考了一下,
假设 K型好数列 有三个数,那么这三个数必然是 { x,a*k-x,(b+2*x/k)*k-x },
也就是 2x 可以被 k 整除,
也就是 这些数要么全是k的倍数,要么全是 k的倍数 + k的半数
以上是三个及三个以上的情况。
程序代码:
#include <stdio.h>

int main( void )
{
    int a[] = { 1, 5, 6, 100 };
    int k = 7;

    size_t maxlen = 0;
    const size_t n = sizeof(a)/sizeof(*a);
    for( size_t i=0; i!=n; ++i ) // 统计k的倍数
        maxlen += a[i]%k == 0;
    if( k%2 == 0 ) // 统计k的 ?.5倍 的数
    {
        size_t half = 0;
        for( size_t i=0; i!=n; ++i )
            half += a[i]%k == k/2;
        if( maxlen < half )
            maxlen = half;
    }
    if( maxlen < 2 ) // 考虑两个的情况
    {
        for( size_t i=0; maxlen!=2 && i!=n; ++i )
            for( size_t j=i+1; maxlen!=2 && j!=n; ++j )
                if( (a[i]+a[j])%k == 0 )
                    maxlen = 2;
    }

    printf( "%zu\n", maxlen ); // 我没有按照题目要求在小于2时输出-1,因为我觉得这要求无聊
}

2021-11-18 09:28
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:0 
回复 5楼 lin5161678
子数组

子数组的定义:一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素)
2021-11-18 09:57
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
以下是引用diycai在2021-11-18 09:57:21的发言:

子数组

子数组的定义:一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素)

看吧 你果然对子数组 子序列的理解出错了
子序列不要求连续的 可能还会要求顺序一致(不过这个题目顺序无关 不管是否一致 结果不变)
你可以找找其他带子序列的题目对比一下 比如 最长递增子序列

你说的连续的子序列 一般会描述为 子串 比如 最长回文子串

比如
https://blog.
这文章 刚刚好是在讲解 最长回文子串 & 最长回文子序列
你可以比较一下其中的区别


https://zh.
2021-11-18 14:39
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:0 
回复 8楼 lin5161678
不是我理解的,是标准定义的。题目要求的是子数组。
图片附件: 游客没有浏览图片的权限,请 登录注册
2021-11-18 14:54
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:0 
回复 8楼 lin5161678
再来看 数组的定义:
    数组是逻辑上连续的一系列元素。

那么子数组也要符合这个定义。

在逻辑学上,叫做 数组 蕴含 子数组。
2021-11-18 15:14
快速回复:求子数组中任意两数之和能整除k的最大元素个数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.052490 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved