codeforces #365 div2ABC题解

A题

水题防止爆零的，不解释了，比较大小的水题

B题

B题是一个数学容斥题，因为数据量比较大，需要用前缀和+容斥的思想来做

题意：n个点，1，2,3,4，……n初始化的时候成环形连边，也就是1-2,2-3,3-4……，n-1

然后，有k个重要城市，每个重要城市与其他所有城市都有一条边

任意两个城市之中，最多有一条边相连

每个点有自己的价值ci，每条边的价值是所连两个点i，j的价值乘积ci*cj

如何容斥？

特殊情况：相邻的！记得特判

如何减小时间复杂度：利用前缀和：两个前缀和

第一个前缀和，是所有的ci之和，需要算进来，每当有一个重要城市的时候，先把重要城市的价值*该前缀和

第二个前缀和，是重要城市的价值ci之和，因为，对于第M+1个重要城市来说，前M个重要城市已经和自己连过边了，那么需要减掉

特殊情况：相邻的，特判！

如果当前的重要城市和前一个是相邻的，那么需要加回来

如果重要城市中包括1和n的话，那么需要加回来

因为，题目中强调了，给定的重要城市序号是按照升序给定的

那么不需要用数组记录，如果1和n的组合存在，那么一定是第一个和最后一个

如果出现相邻的，那么需要记录前一个重要城市的序号

另外，一定要记得初始化！

因为在第一个重要城市之前，是没有重要城市的，那么初始化需要一个跟第一个重要城市无关的值

代码如下：

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=100050;
int n,k,x;
__int64 a[maxn];
__int64 ans,sum;
__int64 desc;
int Start;
int End;
int before;
int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&k)!=EOF){
		sum=0;
		ans=0;
		desc=0;
		for(int i=0;i<n;i++){
			scanf("%I64d",&a[i]);
			sum=sum+a[i];
		}
		for(int i=0;i<n;i++)
			ans+=a[i]*a[(i+1)%n];
		//cout<<ans<<endl;
		x=-99999;
		for(int Case=1;Case<=k;Case++){
			before=x;
			scanf("%d",&x);
			x--;
			if (Case==1) Start=x;
			else if (Case==k) End=x;
			ans+=a[x]*sum;//ALL POINT
			ans=ans-(a[x]+a[(x+1)%n]+a[(x+n-1)%n])*a[x];
			
			ans=ans-desc*a[x];
			if (before+1==x) ans+=a[before]*a[x];
			desc+=a[x];
		}
		if (End==n-1&&Start==0) ans+=a[0]*a[n-1];
		cout<<ans<<endl;
		//cout<<endl;
	}
	return 0;
}

C题

首先知道这个题，是个计算几何

然后呢，肯定需要特判：到底能不能冲过去，是吧

如果对二分熟悉的呢，这个题就过了：因为可以对时间二分，再次判断：人在原点等待一段时间之后，到底能不能冲过去！

思路很连续，代码也很好写，列出一个比例式子，比较大小就好了

代码如下：

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-9;
const int maxn=10050;

int zero(double x){
	if (x>eps) return 1;
	else if (x<-eps) return -1;
	else return 0;
}

double u,w,v;
int n;
struct node{
	double x,y;
}p[maxn];

bool judge1(){
	/*
	
	u     p[i].y
   --- ? --------
	v     p[i].x
	
	*/
	for(int i=0;i<n;i++)
		if (zero(u*p[i].x-v*p[i].y)<0) return 0;
	return 1;
}

bool judge2(double t){
	/*
	
	u        p[i].y
       --- ? -------------
	v      p[i].x-v*t
	
	*/
	for(int i=0;i<n;i++)
		if (zero(u*p[i].x-v*p[i].y-u*v*t)>0) return 0;
	return 1;
}

int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%d%lf%lf%lf",&n,&w,&v,&u)!=EOF){
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		if (judge1()) printf("%.10lf\n",w/u);
		else{
			double l=0,r=2e9;
			for(int i=0;i<100;i++){
				double mid=(l+r)/2;
				if (judge2(mid)) r=mid;
				else l=mid;
			}
			printf("%.10lf\n",w/u+(l+r)/2.0);
		}
	}
	return 0;
}

D题

看到就知道是线段树或者树状数组的搞法

贴个链接以后来学习

D题题解