cf&at&hiho杂选二

自用笔记算法

cf&at&hiho杂选二

hihocoder152周_hiho

题目要求

参考AC代码

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
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define maxn 400050 
#define LL long long
using namespace std;
struct node{
	LL x;
	int flag;
	node(LL x,int flag):x(x),flag(flag){}
};
bool cmp(node a,node b){
	return a.x<b.x;
}
vector<node>e;
LL cnta[maxn],cntb[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=2*n;i++){
		LL data;
		cin>>data;
		if(i&1) e.push_back(node(data,1));
		else e.push_back(node(data,2));
	}
	for(int i=1;i<=2*m;i++){
		LL data;
		cin>>data;
		if(i&1) e.push_back(node(data,3));
		else e.push_back(node(data,4));
	}
	sort(e.begin(),e.end(),cmp);
	LL sum=0,st=0;
	memset(cnta,0,sizeof(cnta));
	memset(cntb,0,sizeof(cntb));
	for(int i=0;i<e.size();i++){
		if(e[i].flag==1){
			cnta[i]=(i==0?0:cnta[i-1]);
			cntb[i]=(i==0?0:cntb[i-1]);
			cnta[i]++;
		}
		else if(e[i].flag==2){
			cnta[i]=(i==0?0:cnta[i-1]);
			cntb[i]=(i==0?0:cntb[i-1]);
			cnta[i]--;
		}
		else if(e[i].flag==3){
			cnta[i]=(i==0?0:cnta[i-1]);
			cntb[i]=(i==0?0:cntb[i-1]);
			cntb[i]++;
		}
		else{
			cnta[i]=(i==0?0:cnta[i-1]);
			cntb[i]=(i==0?0:cntb[i-1]);
			cntb[i]--;
		}
	}
	for(int i=0;i<e.size();i++){
		if(!(cnta[i]>0 && cntb[i]==0)){
			if(st!=i) sum+=(e[i].x-e[st].x),st=i+1;
			else st++;
		}
	}
	cout<<sum<<endl;
	return 0;
}

思路

这道题是一类区间问题的变体，我们先来看一道最基础的区间问题：
给定N个区间[S1, E1], [S2, E2], … [SN, EN]，求这些区间并集的长度。
这道题通常的解法是，我们把这N个区间的2N个端点从左到右排列在数轴上P1, P2, … P2N。
并且如果一个点Pi是原区间的左端点，我们就把它标记成绿色；如果是右端点，就标记成蓝色。

值得注意的是这2N个点中可能存在重合的点。比如假设有两个区间[1, 3]和[3, 5]，那么在3这个位置上
就同时存在一个绿点(左端点)和蓝点(右端点)。某些情况下我们在排序时需要特别处理重合的点，例如要
保证蓝点都排在绿点之前。不过本题我们无需特殊处理，重合的点无论谁在前谁在后都不影响结果。
这2N个点把数轴分成了2N+1段，(-INF, P1), (P1, P2), (P2, P3) … (P2N-1, P2N), (P2N, +INF)。
每一段内部被原来区间集合覆盖的情况都是相同的。换句话说，不会出现(Pi, Pi+1)的左半部分被第1、3、5号
区间覆盖，而右半部分只被第1、3号区间覆盖这种情况。
所以我们可以从左到右扫描每一段，令cnt计数器初始值=0。当扫过一个绿点时，cnt++；扫过一个蓝点时cnt–。
我们可以发点对于(Pi, Pi+1)这一段，处理完Pi时的cnt值恰好代表了这一段被几个原来的区间同时覆盖。
有了每一段的cnt值，我们可以做很多事情。例如要求区间并集的长度，我们可以找出所有cnt值大于0的段
(Pi, Pi+1)，并把这些段的长度(Pi+1 - Pi)求和。我们还可以知道哪段被覆盖了最多次：自然是cnt值最大的段。
对于给定的坐标X，我们可以在O(logN)的时间内求出X这个点被覆盖多少次：我们只需要在P1, P2, … P2N中二分
查找出X的位置，即Pi < X < Pi+1，那么(Pi, Pi+1)这一段的cnt值就是答案。(当X恰好是端点时需要特判，取决于
给出的区间是开区间还是闭区间)
好了，我们回到《区间求差》这道题目。我们可以把A和B集合中2N+2M个端点都从左到右排列在数轴上。并且用4种颜色
标记出每个点是A的左端点、A的右端点、B的左端点、B的右端点。然后我们用两个计数器cntA和cntB来分别维护每一段
被A集合中的区间覆盖多少次、以及被B集合的区间覆盖多少次。那么如果某一段(Pi, Pi+1)满足cntA>0且cntB=0，
那么它一定是A-B的一部分。我们对于这些段的长度求和即可。
整个算法对于端点排序的部分复杂度是O(NlogN)的，对于从左到右扫描复杂度是O(N)的。总体复杂度是O(NlogN)。

atcoder_contest015_A

题目要求

在A到B的区间内取N个数字(A和B必取) 问求和后有多少种情况

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	LL n,a,b;
	cin>>n>>a>>b;
	if(n==1){
		if(a==b) cout<<"1"<<endl;
		else cout<<"0"<<endl;
	}
	else{
		if(a>b) cout<<"0"<<endl;
		else cout<<(n-2)*(b-a)+1<<endl;
	}
	return 0;
}

思路

除去最大值和最小值还需取n-2个 最大值为(n-2)A 最小值为(n-2)B 这之间的每个数字都能取到
所以最大值-最小值+1就是答案
注意特殊情况特判

cf_round416_c

题目要求

一个线段内选择若干个连续区间 满足每个区间内出现的所有数字只出现在该区间内 并且要求所有区间内出现的数字(重复数字只算一次)xor和最大
求sum

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5050;
int dp[maxn],L[maxn],R[maxn],arr[maxn];
int vis[maxn];
int main() {
//	freopen("input.txt","r",stdin);
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        x=arr[i];
        if(L[x]==0) L[x]=i;
        R[x]=i;
    }
    for(int i=1;i<=n;i++){
        int first=L[arr[i]],ret=0;
        dp[i]=dp[i-1];
        memset(vis,0,sizeof(vis));
        for(int j=i;j>=1;j--){
            x=arr[j];
            if(R[x]>i) break;
            first=min(first,L[x]);
            if(!vis[x]){
                vis[x]=1;
                ret^=x;
            }
            if(first==j){
            	dp[i]=max(dp[i],dp[j-1]+ret);
			}
        }
    }
    printf("%d\n",dp[n]);
	return 0;
}

思路

dp
预处理每个数字出现最左边和最右边的位置
外层循环遍历n次 内层循环从i逆序倒推 如果有某个数字超过该区间 即右边界越界 break
同时更新区间的最左端点 同时用vis数组记录区间内的xor值(hash思想避免了重复数字)
如果左端点等于j 那么改区间合法 更新dp[i]的值
主要每次外层循环vis数组要初始化 同时dp也初始化为前一位的值

本文标题:cf&at&hiho杂选二

文章作者:Hippopmonkey

发布时间:2017-05-29, 13:17:53

最后更新:2017-05-29, 15:33:36

原始链接:http://xuboming8.github.io/2017/05/29/cf-at-hiho杂选二/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. cf&at&hiho杂选二
    1. 1.1. hihocoder152周_hiho
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. atcoder_contest015_A
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. cf_round416_c
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|