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

· · 题解

本蒟蒻的第一篇题解

题目描述

题目传送门
题面可以简化如下：有很多船只，从第一天开始每隔一段固定的时间来到港口。已知 n 个有船只来到的日子，求最少有多少只船。

思路

先看数据范围，发现数据较小，可以直接暴力。由于船每隔一段固定时间就会来到，所以如果是同一艘船那必然是一个等差数列。观察题面说数据保证从一开始，我们就可以先把所有天数减一。然后我们用一个数组维护可能的船，枚举这艘船的倍数并标记，如果没有标记的就让答案加一，最后输出答案即可。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10010];
bool vis[10010];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] --;
    }
    int f = 1, bj = 2, ans = 0;
    for(int i = 2; i <= n; i ++){
        if(!vis[i]){
            ans ++;
            for(int j = i + 1; j <= n; j ++){
                if(vis[j] == 1) continue;
                if(a[j] % a[i] == 0) vis[j] = 1;
            }
        }
    }
    cout << ans;
    return 0;
}

第一篇题解祭