Dashboard - Codeforces Round 904 (Div. 2) - Codeforces

C. Medium Design

题意

给长度为m的数组a，初始均为0。$1\le m \le 10^9$

给出一些区间，请你选出其中某些区间。每选择一个区间，就令区间中的数都加一，问 数组中最大值$max(a)$ ,和最小值$ min(a)$ 的差，最大为多少。

思路

考虑以下贪心策略：如果我们确定了最终第$i$个数是最大的那个数，即$ a[i] = max(a)$ , 那么我们就可以选择所有的包含$i$的区间。然后摒弃所有不包含$i$的区间。（选上包含$i$的区间一定会令$max(a)++$) , 这样我们可以遍历所有的数组下标$i$。 计算假使$i$为最大数时的$ans$，最终选择最大的$ans$即可。

我们可以先对区间进行排序。 然后根据右端点从小到大维护优先队列$pq$。这样按顺序遍历区间数组，就可以引入所有左端点小于等于$ i $的区间。然后通过剔除优先队列中的右端点小于i的区间。 这样优先队列中就保存了所有的包含$i$的区间。 因此有 $max(a) = pq.size()$ ,

再考虑寻找最小值$min(a)$ , 如果我们使用 $cntl$ 左端点为1的区间的数量。同理使用 $cntr$记录右端点为$m$的区间的数量 。那么 $min(a) = min(cntl,cntr)$ 。

本题m较大。需要离散化处理。

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
struct cmp{
	bool operator()(PII x,PII y){return x.second > y.second;}
};
int main(){
	int t;
	cin>>t;
	cin.tie(0);cout.tie(0);
	while(t--){
		int n,m;
		cin>>n>>m;
		vector<int > vec(2 * n+5);//存储端点
		vector<PII> seq(2*n+5);//存储区间
		int l ,r;
		for(int i = 1;i<=n;i++){
			cin>>l>>r;
			seq[i] = make_pair(l,r);
			vec[2 * i - 1] = l;
			vec[2 * i] = r;
		}
		//离散化处理
		vec[0] = 1;//引入1和m两个端点
		vec[2 * n + 1] = m;
		sort(vec.begin(),vec.begin()+2+2*n);//排序
		int len = unique(vec.begin(),vec.begin()+2+2*n) - vec.begin();//去重
		// for(int i = 0;i<len;i++) cout<<vec[i] <<" ";
		// puts("");	
		unordered_map<int,int> mp;
		for(int i = 0;i<len;i++){
			mp[vec[i]] = i;
		}
		sort(seq.begin() + 1,seq.begin()+1+n);//对区间排序
		int ans = -1;
		int cntl = 0,cntr = 0;
		priority_queue<PII , vector<PII> ,cmp> pq; //优先队列
		int p = 1;
		for(int i = 0;i<len;i++){
			while(p<=n && seq[p].first <= vec[i]){//入队
				if(seq[p].first == 1) cntl ++;
				if(seq[p].second == m) cntr ++;
				pq.push(seq[p]);
				p++;
			}
			while(pq.size() && pq.top().second < vec[i]){//出队
				PII temp = pq.top();
				if(temp.first == 1) cntl--;
				pq.pop();
			}
			ans = max(ans,(int)pq.size() - min(cntl,cntr));
		}
		cout<<ans<<endl;
	}
	return 0;
}

D. Counting Rhyme

题意

给出有n个数的数组a，问有多少个$(i,j)$ 对（$(i,j)$与$(j,i)$ 视为同一个对）,满足 不存在 任何k，使得$a_k $是$ a_i,a_j$ 的公因子。

（$1 \le n \le 10^6, 1 \le a_i \le n$）

思路

dp，设$dp[i] $ 为以$i$为最大公因子的对有多少个。我们可以统计 有多少个数有i这个因子 ， 假设有cc个数，那么就会有$\frac{cc (cc - 1)}{2}$ 个以 $i$为公因子（不是最大公因子）的对。 我们要求最大公因子，就还需要令$ dp[i] = dp[i] - \sum _{t = 2} ^{i t <= n} {dp[t * i]}$ 。（即减去以$i$的倍数为最大公因子的对的数量）。

所以最终的$dp$状态转移方程为$ dp[i] = \frac{cc (cc - 1)}{2}- \sum _{t = 2} ^{i t <= n} {dp[t * i]}$ 。 同时注意，应该从n开始，逐渐转移到1 。

最后，我们需要求 不存在 任何k，使得$a_k $是$ a_i,a_j$ 的公因子。 因此需要标记a数组中所有的数以及他们的倍数 ，最后不被标记的dp值的总和就是答案。

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		vector<int> cnt(n+5);//cnt[i] 表示i这个数出现了几次
		vector<int> dp(n+5);//dp
		vector<bool> vis(n+5);//标记
		for(int i = 1;i<=n;i++){
			int num;
			scanf("%d",&num);
			vis[num] = 1;//先将a数组中的数标记
			cnt[num]++;
		}
		for(int i = n;i>=1;i--){
			int p = i * 2;//从i的2倍开始
			int cc = cnt[i];//cc表示对数
			while(p <= n){
				if(cnt[i]) vis[p] = 1;//p代表i的倍数，那么如果i在a数组中出现过，那么p就是数组中这个数的倍数
				cc += cnt[p];
				dp[i] -= dp[p];//
				p += i;

			}
			dp[i] += cc * (cc - 1) / 2;
		}
		int ans = 0;
		for(int i = 1;i<=n;i++){
			if(!vis[i]) ans += dp[i]; 
		}
		cout<<ans<<endl;
	}
	return 0;
}