暑假欢乐赛

C 冒险

对于此题，我们的思想是 贪心。

对于以上的图，我们发现，我们需要找到尽量重叠的一部分，对于完全不重叠的，我们就要单独计一个数。

这个原理有点像区间覆盖问题，给出几个区间，求能覆盖0~len的整个区间的最小可选区间数。

那么对于所有区间，我们设每一个区间的左端点下标为l，右端点下标为r。

证明得出，如果两个区间是重叠的，那么后面那个区间的左端点在前面那个区间的右端点的左边，而右端点在前面那个区间的右端点的右边。

• 我们按照先右端点由小到大，再左端点由大到小对区间排序，为什么是右端点，因为假设两个区间，按左端点排，会出现这个情况。

• 

  这样是会对后面区间的判断造成影响。

  方法是遍历每一个区间，若满足以上条件，就不作为，否则它就是后面的不存在重合部分的区间，cnt+1，标志l和标志r分别改为该区间的l和r

  code：

  #include "bits/stdc++.h"
  using namespace std;
  struct node{
  	int l,r;
  }nd[100005];
  bool cmp(node a,node b){
  	if(a.r==b.r) return a.l<=b.l;
  	return a.r<=b.r;
  }
  int main(){
  	int len,n;
  	cin>>len>>n;
  	for(int i=1;i<=n;i++){
  		cin>>nd[i].l>>nd[i].r;
  	}
  	sort(nd+1,nd+1+n,cmp);
  	int u=nd[1].l,v=nd[1].r,cnt=1;
  
  	for(int i=2;i<=n;i++){
  		if(nd[i].l<=v&&nd[i].r>=v);
  		if(nd[i].l>v) cnt++,u=nd[i].l,v=nd[i].r; 
  	}
  	cout<<cnt;
  	return 0;
  }

H 计算三元组

暴力方法是直接遍历i和j然后根据条件选择正确的k（i，j，k都是下标，所以数可能相同，但是下标不一样是分不同情况的）

我们直接在输入a数组元素的时候用一个二维数组记录每一个元素出现的位置。因为它是由小到大顺序输入的，所以不用排序了。

然后遍历i和j ， i != j 且a[ i ] != a[ j ] , 那么ak就等于s - a[ i ] - a[ j ]用二分法找到k下标大于j的第一个k（如果有多个相同的ak）然后之后的全都是各一种情况。

• 二分法用upper_bound( v[k].begin() , v[k].end() , j )会很方便。直接得到大于j的第一个下标。

  code:

  #include "bits/stdc++.h"
  using namespace std;
  int a[5005];
  vector<int>v[100005];
  
  int main(){
  	int n,s;
  	cin>>n;
  	for(int i=1;i<=n;i++){
  		cin>>a[i];v[a[i]].push_back(i);
  	}
  	cin>>s;
  	
  	int cnt=0;
  	for(int i=1;i<=n;i++){
  		for(int j=i+1;j<=n;j++){
  			if(a[i]!=a[j]&&i<j){
  				int k=s-a[i]-a[j];
  				if(k>=0&&k!=a[i]&&k!=a[j]){
  					int tt = upper_bound(v[k].begin(),v[k].end(),j)-v[k].begin();
  					tt=v[k].size()-tt;  //计算满足条件的k数量
  					cnt+=tt;
  				}
  			}
  		}
  	}
  	cout<<cnt;
  	return 0;
  }

F 赛跑

首先我们的思路是对于每一个选手（数组中的每一个元素），查找他是所有元素中的第几名然后对于排名比他小的是可以都选的，对于排名比他大的可以选最多两个，因为规定是top3。

对于每一个人，我们假设前面有x个比它小的，后面有y个比它大的，那么可以选全部的x，而y部分最多只能选两个。有4种情况。

• 这个人排第一位，那么就选所有的x，除了只有它自己本身的那一个子集不选，那就是2^x-1
• 这个人排第二位，那么前面的x都可以选，然后从y中任意选一个。
• 这个人排第三位，那么前面x都可以选，然后从y中任意选两个。
• 这个人排第二位，但是就不选前面的x的部分了，相当于这个人就是最小的。则从后面y部分选一个。
• 这个人排第三位，但是就不选前面的x的部分了，相当于这个人就是最小的。则从后面y部分任意选两个。

那么要做到排序，首先要进行离散化过程。将数值映射成排名。

然后一些细节就是求2^x-1的时候要用快速幂，否则会被卡时间和空间。

离散化模板（实际上是根据不同需求做出修改）：

int C[MAXN], L[MAXN];
// 在main函数中...
memcpy(C, A, sizeof(A)); // 复制   A是投入的数组。
sort(C, C + n); // 排序
int l = unique(C, C + n) - C; // 去重
for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找

链接：算法学习笔记(19): 离散化 - 知乎 (zhihu.com)

快速幂模板

const long long m=1e9+7;
long long quickpow(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1)//与运算，可判断奇偶，详细见注释
		sum=sum*a%m;//取模运算
		a=a*a%m;
		b>>=1;//位运算，右移，相当于除以2
	}
	return sum;
}

code :

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 100005;
int A[MAXN],C[MAXN],L[MAXN];
int ans[MAXN];
const int md = 1e9+7;

//快速幂
long long quickpow(long long a,long long b){
	long long sum=1;
	while(b){
		if(b&1)//与运算，可判断奇偶，详细见注释
		sum=sum*a%md;//取模运算
		a=a*a%md;
		b>>=1;//位运算，右移，相当于除以2
	}
	return sum;
}


//typedef long long LL;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>A[i];
	}
    //离散化步骤
	memcpy(C, A, sizeof(A)); 
	sort(C, C + n); 
	int l = unique(C, C + n) - C;   //长度 
	for (int i = 0; i < n; ++i)
    L[i] = lower_bound(C, C + l, A[i]) - C + 1; 
    
    //乘法原理求解（分情况）
    for(int i=0;i<n;i++){
	
		long long sum=0;
		int x=L[i]-1,y=n-L[i];

		sum = ((long long)((long long)y*(y-1)/2)+y)%md;
		sum = (sum+((long long)((long long)y*(y-1)/2)+y)%md*((long long)(quickpow(2,x)-1))%md)%md;		
		sum = (sum+(long long)(quickpow(2,x)-1))%md;

		cout<<sum<<" ";

	}
	return 0;
}

Donate