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

~~本蒟蒻的第一篇题解~~

题目描述

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

n

个有船只来到的日子，求最少有多少只船。

思路

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

Code

CPP

#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;
}

~~第一篇题解祭~~

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

文章操作

题目描述

思路

Code

相关推荐

评论

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