Maison >interface Web >tutoriel HTML >Codeforces Round #245 (Div. 1)??Tricky Function_html/css_WEB-ITnose

Codeforces Round #245 (Div. 1)??Tricky Function_html/css_WEB-ITnose

WBOY
WBOYoriginal
2016-06-24 12:04:421084parcourir

题目链接

  • 题意:
    n个数a[i],f(i, j) = (i - j) ^ 2 + sigma(a[k]) ^ 2, i n (2?≤?n?≤?100000).(?-?104?≤?a[i]?≤?104)
  • 分析:
    关键在于题意的转换。简单的考虑,需要知道每个区间的信息,复杂度难以降下来,应该将题目的f函数进行化简。既然考虑区间是不可行的,那么就尝试是否能将区间分成两个短点的计算。这里用到了一个常用的转换:区间和转化为前缀和的差。转换后就得到f(i, j) = (i - j) ^ 2 + (presum[j] - presum[i]) ^ 2,做过几何的都能看出来,就是平面最近点对
  • 总结:
    如果以区间为问题的单位,那么复杂度难以下降,所以问题的考虑单位往往是点,如果能转化为点,复杂度将可以下降
    区间和往往需要转化为前缀和:这样的话,对于区间的两个点,需要求得值就只和当前点有关,也就是完成了上一个(区间转化为点)的任务

  • const double EPS = 1e-10;const int MAXN = 100100;inline int dcmp(double x){	if(fabs(x) > 1;	double d1 = Closest_Pair(left, mid);	double d2 = Closest_Pair(mid + 1, right);	d = min(d1, d2);	int k = 0;	//分离出宽度为d的区间	FE(i, left, right)	{		if(sqr(point[mid].x - point[i].x)  d3)				d = d3;		}	return d;}LL ipt[MAXN];int main(){	//freopen("input.txt", "r", stdin);	int n;	while (~RI(n) && n)	{		FE(i, 1, n)		{			cin >> ipt[i];			ipt[i] = ipt[i - 1] + ipt[i];		}		FE(i, 1, n)		{			point[i - 1].x = i;			point[i - 1].y = ipt[i];		}		sort(point, point + n, cmpxy);		LL ans = Closest_Pair(0, n - 1);		cout   <br>  <p></p> 
    Déclaration:
    Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn