首页 / HTML / CodeforcesRound#245(Div.1)??TrickyFunction_html/css_WEB-ITnose

CodeforcesRound#245(Div.1)??TrickyFunction_html/css_WEB-ITnose

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#245(Div.1)??TrickyFunction_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2080字，纯文字阅读大概需要3分钟。

内容图文

题目链接

  • 题意：
    n个数a[i]，f(i, j) = (i - j) ^ 2 + sigma(a[k]) ^ 2, i < k <= j，求最小的f值
    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) < EPS) return 0;	else return x < 0 ? -1 : 1;}struct Point{	LL x, y;};//最近点对Point point[MAXN];LL tmpt[MAXN], Y[MAXN];inline bool cmpxy(Point a, Point b){	if(a.x != b.x)		return a.x < b.x;	return a.y < b.y;}inline bool cmpy(int a, int b){	return point[a].y < point[b].y;}inline LL dist(int x, int y){	Point& a = point[x], &b = point[y];	return sqr(a.x - b.x) + sqr(a.y - b.y);}LL Closest_Pair(int left, int right){	LL d = 1e18;	if(left == right)		return d;	if(left + 1 == right)		return dist(left, right);	int mid = (left + right) >> 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) <= d)			tmpt[k++] = i;	}	sort(tmpt, tmpt + k, cmpy);	//线性扫描	REP(i, k)		for(int j = i + 1; j < k && sqr(point[tmpt[j]].y-point[tmpt[i]].y) < d; j++)		{			LL d3 = dist(tmpt[i],tmpt[j]);			if(d > 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 << ans << endl;	}	return 0;}

    内容总结

    以上是互联网集市为您收集整理的CodeforcesRound#245(Div.1)??TrickyFunction_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#245(Div.1)??TrickyFunction_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

    内容备注

    版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

    内容手机端

    扫描二维码推送至手机访问。

    本文链接：https://qyyshop.com/info/398024.html

    来源：【匿名】