自动搬运

查看原文

来自洛谷，原作者为

	yiLIUyi 不屈的江油人民终会迎来光明|看主页：F12删除“display: none;”|互关条件luogu.com.cn/paste/x54efpmj 满足可私信|准九年级|山东|可以加微信/qq聊天

搬运于2025-08-24 22:31:44，当前版本为作者最后更新于2025-08-10 08:25:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门：P7633 [COCI 2010/2011 #5] BRODOVI。
双倍经验：SP8349 BRODOVI - BRODOVI。

题意

有一些船只，从第一天开始每隔固定的时间就会来到港口。现在给出 $n$ 个有船只来到的日子，求最少有多少只船。

思路

首先我们在题目中看到：

例如，长度为 $3$ 的间隔表示某艘船在第 $1$ 天、第 $4$ 天、第 $7$ 天、第 $10$ 天等时间访问港口。

观察它，我们就能得出几句废话：

• 这四个数字是一个等差数列，差为 $3$。
• 靠后的数字减去靠前的数字，结果可以被 $3$ 整除。即都是 $3$ 的倍数。如果是相邻两数相减，结果正好是 $3$。
• 数列中，任意一个数字减去第一个数字（也就是 $1$），结果都可以被 $3$ 整除，即都是 $3$ 的倍数。第二个数减去一，正好是 $3$。

从这些废话中，我们就可以得出题目解法：

• 维护一个数组 $vis$，记录每一条船的间隔时间；
• 对于每一个 $a_i$，查询 $vis$ 数组，如果存在 $vis_j$ 使得 $vis_j \mid a_i-1$，说明 $a_i$ 对应的船已经记录过了，不用进行操作；
• 否则，说明这是一条新船，我们把 $a_i-1$ 添加至 $vis$ 中（刚刚已经说过，数列中第二个数减去 $1$ 正好是这个数列的差）；
• 继续处理下一个数。

还有一点，上面之所以要减一，只是因为第一位是 $1$。如果第一位是 $2$ 就会减二。那如果第一位是 $0$，是不是就不用减了？所以我们在输入时就顺手把所有数字都减一，就把第一位变成了 $0$。显然这样不会影响我们的答案。

参考代码

//241ms / 844.00KB / 392B C++14 O2
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll n,a[5010];
bool flag;
vector<ll>v;//vis 数组
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        a[i]--;//减一
    }for(ll i=2;i<=n;i++){
        flag=false;//记录这条船在 vis 中能不能找到
        for(ll j:v)//提示：c++98 可能用不了这种写法
            if(a[i]%j==0){//找到了
				flag=true;
				break;//跳出
			}
        if(!flag)//没找到
			v.push_back(a[i]);//加入数组
    }cout<<v.size();//数组长度，也就是船的个数
    return 0;//好习惯
}//喜欢就点个赞呗~ QAQ