poj2356:Find a multiple-阿里云开发者社区

开发者社区> 人工智能> 正文

poj2356:Find a multiple

简介: 题目链接: 【鸽巢原理+乱搞】 其实用不着开$map$ 一步最巧妙的转化是$……$前缀和。 反正本宝宝突发奇想就出来了。 首先,我们分类讨论。 1.当$∃i \in N_{+} $ 且 $i \in [1,n]$ 使 $a_{i} | n$ 则直接选这个数就好 2.没有以上那种特殊情况的话,我们记录前缀和$sum_{i}= \sum _{k=1}^{i} a_{k} (mod \ \ n)$ 然后又有两种情况。

题目链接:

【鸽巢原理+乱搞】

其实用不着开$map$

一步最巧妙的转化是$……$前缀和。

反正本宝宝突发奇想就出来了。

首先,我们分类讨论。

1.当$∃i \in N_{+} $ 且 $i \in [1,n]$ 使 $a_{i} | n$ 则直接选这个数就好

2.没有以上那种特殊情况的话,我们记录前缀和$sum_{i}= \sum _{k=1}^{i} a_{k} (mod \ \ n)$ 然后又有两种情况。

根据鸽巢抽屉原理,因为我们现在在$(mod \ \ n)$剩余系下,有$n$个数。所以只会有两种情况: 

  (1).当这$n$个数互不相等的时候,一定 $∃i \in N_{+} $ 且 $i \in [1,n]$ 使 $sum_{i} \equiv 0 \ \ (mod \  n)$

     则直接选$1 \thicksim n$ 就好。

  (2).如果有两个$sum$相等,假设为$sum_{i},sum_{j} \ ,j>i$,则$sum_{j}-sum_{i} \equiv 0 \ \ (mod \ n)$

    而$sum_{j}-sum_{i} =  \sum_{k=i}^{j} a_{k} $ 所以就可以选这 $j-i$ 个数了。

一开始$WA$掉3次因为集合大小输出错了2333……qwq

 上代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
int n;
int a[100100];
int sum[100010];
signed main()
{
    scanf("%dll",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]),sum[i]=(sum[i-1]+a[i])%n;
        if(a[i]%n==0) {printf("1\n%lld",a[i]);return 0;}
        if(sum[i]==0) {printf("%lld\n",i);for(int j=1;j<=i;j++) printf("%lld\n",a[j]);return 0;}
    }
    for(int i=1;i<=n;i++)
      for(int j=i+1;j<=n;j++)
        if(sum[i]==sum[j])
        {
            printf("%lld\n",j-i);
            for(int k=i+1;k<=j;k++)
              printf("%lld\n",a[k]);
            return 0;
        }
    return 0;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章