FQR_的博客

FQR_的博客

0%

P7633 BRODOVI 题解

题目传送门

双倍经验

思路

遍历除 11 以外的“娱乐日”。

如果这个“娱乐日”暂时未被标记，那么就创建一个长度为 ai−1a_i-1 的间隔，并将答案加一。

遍历其它的“娱乐日”。如果这一天属于这个间隔，即这个数减 11 是 ai−1a_i-1 的倍数，就将这个数标记。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int a[5050];
map<int,bool> mp;//mp[i]表示i是否被标记过
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int ans=0;
	for(int i=2;i<=n;i++)//遍历除1以外的娱乐日
	{
		if(mp[i]) continue;//判断是否被标记过
		ans++;//需要创建新的间隔，将答案加一
		for(int j=1;j<=n;j++) 
            if((a[j]-1)%(a[i]-1)==0) 
                mp[j]=1;//标记属于这个间隔内的数字
	}
	cout<<ans;
	return 0; 
}