lly的数列询问(最小生成树 + 思维)
Description
这个问题很简单,lly lly lly给你一些提示,让你试着确定长度为n n n的数列A [1] A [2] ... A [n]的值,但是他想尽一切办法为大家降低难度:
因此lly lly lly会给定一些对你有用的m m m询问,每次询问lly lly lly会表明L,R,sum[L,R] L,R,sum [L,R] L,R,sum[L,R]:表示区间[L,R]的区间和(保证询问合法),让大家更好的解决这个问题,但是对于每个询问会有一个代价,代价就是(R−L)∗sum[L,R](R-L)* sum [L,R] (R−L)∗sum[L,R]。
那么问题就转化了,如何花费尽可能小的代价确定这个数列。
Input
输入第一行包括两个整数n,m(1≤n≤2∗105,0≤m≤5∗105)n,m(1 \leq n \leq 2*10^5,0 \leq m \leq 5*10^5)n,m(1≤n≤2∗105,0≤m≤5∗105)。
接下来有mmm行,每行包括三个整数,L,R,sum[L,R],(1≤L≤R≤n,sum[L,R]≤109)L,R,sum[L,R],(1 \leq L \leq R \leq n,sum[L,R] \leq 10^9)L,R,sum[L,R],(1≤L≤R≤n,sum[L,R]≤109)。
Output
输出包含一个整数,即最小花费,如果无论如何都无法确定这个数列就输出“lly tcl!”。
Source
nuoyanli
思路
题意:给我们一个长度为 n 的序列,但是我们不知道的它的元素是什么,之后给我们m个是提示,每次提示 给我一个们一个[L, R]区间 的元素和sum[L~R],每次提示有一个 最小的花费 (R−L)∗sum[L..R](R-L)*sum[L ..R](R−L)∗sum[L..R],问我们找出序列的n个元素是啥,需要的总共的最小花费是多少?
分析:这题真实令人脑洞大开,对于这种区间元素是啥的题竟然可以转化成求
最小生成树
的问题(可惜本巨弱竟毫无察觉 ),对于这一题要求出序列的n个元素是啥?就等价于求出每个位置的前缀和 sum[ i ] ,我们已知 sum[0] = 0, 如果对于序列中的1~n点都 0 点联通(应用最小生成树的地方
)的话,那么我们就能够求出所有的 sum[i],有了所有的sum[ i ] 之后我们通过相邻位置的前缀和相减就能够得到 n 个元素了,对于题目上的m次提示的条件我们就可以转化成 sum[R] - sum[L - 1], 以 L-1点 与R点之间建立一条 权值为 (R-L)* sum[L~R] 的边,这样根据m个条件建完图之后,用 Kruskal 或者 Prim 来跑一边最小生成树(在这个是时候我们要判断这个图能否全部连通),的出来的答案就是 总花费最后举个例子来证明可行,例如 1-3 的区间和为sum[3] - sum[0], 4 - 6的区间和为sum[6] - sum[4], 我们可以看到 如果 0与6联通 那么区间和 sum[ 6 ] - sum[0] == sum[6] - 0, 而在我们将 1-3、4-6区间,对应的 0 - 3 - 6 (
这样我们就使 0 与 6间接联通了
)联通的时候,那么这条边的边权和是 (sum[6] - sum[3]) + ( sum[3] - sum[0]) = sum[6] + sum[0], 这样我们就可以得到了 sum[6] 的值了。。。。。。。。。。。。。。。。。
题解
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int Len = 5e5 + 10;
int n,m;
struct Edge
{
ll u,v,w;
bool operator < (const Edge a) const { return w < a. w; }
} edge[Len];
int pre[Len];
ll find(ll x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
void init()
{
for(int i = 0; i <= n; i ++)
pre[i] = i;
}
int main()
{
/* freopen("A.txt","r",stdin); */
scanf("%d %d", &n, &m);
init();
ll l, r, sum;
for(int i = 0; i < m; i ++)
{
scanf("%lld %lld %lld", &l, &r, &sum);
edge[i] = (Edge){ l-1, r, (r - l)*sum };
}
sort(edge, edge + m);
int cnt = 0;
ll u, v, w, Sp = 0;
for(int i = 0; i < m; i ++)
{
u = edge[i].u, v = edge[i].v, w = edge[i].w;
int fu = find(u);
int fv = find(v);
if(fu != fv)
pre[fu] = fv, cnt ++, Sp += w;
}
if(cnt < n) printf("lly tcl!\n");
else printf("%lld\n", Sp);
return 0;
}
最新文章
- 模拟搭建Web项目的真实运行环境(四)
- android 获取应用的当前版本号&;获取当前android系统的版本号
- SAP abap 需找出口(BADI)的几种方法
- SQL Server 2008 数据库镜像部署实例之一 数据库准备
- 给MySQL官方提交的bug report备忘
- Winform开发框架之权限管理系统改进的经验总结(4)-一行代码实现表操作日志记录
- -fomit-frame-pointer 编译选项在gcc 4.8.2版本中的汇编代码研究
- 如何在Windows Server 2003中配置FTP站点服务
- 简单的oracle sql 语句
- 乐在其中设计模式(C#) - 抽象工厂模式(Abstract Factory Pattern)
- SQL注入(三)
- Mycat安装与使用
- COGS 144. [USACO Dec07] 魅力手镯【01背包复习】
- C++ enum用法小技巧
- [转]Android长度单位详解
- Linux下强制杀死进程的方法
- Loadrunner打开VU时候报错Critical error(cannot use Exceptiondialog)
- 程序媛计划——mysql外键
- linux挂载windows共享文件夹出错,提示mount error(13): Permission denied
- VR电竞游戏在英特尔&#174;架构上的用户体验优化