题解九：P7633 [COCI 2010/2011 #5] BRODOVI

__yiLIUyi__ · 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