首页 > 其他分享 >AT_keyence2019_e Connecting Cities 题解

AT_keyence2019_e Connecting Cities 题解

时间:2024-09-06 14:52:33浏览次数:13  
标签:begin int 题解 200010 fa Connecting Cities first

B 算法萌萌题。

题解

看到完全图求最小生成树,必然是要考虑一下 B 算法能不能做的。

发现这个题的联通块最小值是可以维护的。

我们发现。

假如我们钦定 \(i\) 往前面连。

那么前面的最小权值必然是一个固定的值。

我们一定会连到 \(\min (a_j-j\times D)\) 上。

由于不能连到自己在的联通块上。

所以我们可以维护每一个联通块的最小值。

只需要从前往后扫一遍,用 set 维护即可。

往后面连是同理的。

使用并查集维护联通性即可。

时间复杂度:\(O(n\log n\log n)\)。

Code

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

#define int long long

int n, D, ans;
int a[200010], f[200010];
int v[200010], s[200010];
int fa[200010];

inline int gf(int x) {
  return (fa[x] == x ? x : fa[x] = gf(fa[x]));
}
inline bool chk() {
  for (int i = 1; i <= n; i++) {
    if (gf(i) != gf(1)) return 1;
  }
  return 0;
}

signed main() {
  cin >> n >> D;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], fa[i] = i;
  }
  while (chk()) {
    multiset<pair<int, int>> q;
    for (int i = 1; i <= n; i++) s[i] = 0, v[i] = 1e18;
    for (int i = 1; i <= n; i++) f[i] = 1e18;
    q.clear();
    for (int i = 1; i <= n; i++) {
      int x = gf(i);
      if (f[x] < 1e18) q.erase(q.find({f[x], x}));
      if (q.empty() == 0) {
        if (v[x] > q.begin()->first + a[i] + i * D) {
          v[x] = q.begin()->first + a[i] + i * D;
          s[x] = q.begin()->second;
        }
      }
      if (f[x] > a[i] - i * D) {
        f[x] = a[i] - i * D;
      }
      q.insert({f[x], x});
    }
    for (int i = 1; i <= n; i++) f[i] = 1e18;
    q.clear();
    for (int i = n; i >= 1; i--) {
      int x = gf(i);
      if (f[x] < 1e18) q.erase(q.find({f[x], x}));
      if (q.empty() == 0) {
        if (v[x] > q.begin()->first + a[i] - i * D) {
          v[x] = q.begin()->first + a[i] - i * D;
          s[x] = q.begin()->second;
        }
      }
      if (f[x] > a[i] + i * D) {
        f[x] = a[i] + i * D;
      }
      q.insert({f[x], x});
    }
    vector<int> r;
    for (int i = 1; i <= n; i++)
      if (s[i]) {
        int x = gf(i), y = gf(s[i]);
        if (x != y) fa[x] = y, ans += v[i];
      }
  }
  cout << ans << "\n";
}

标签:begin,int,题解,200010,fa,Connecting,Cities,first
From: https://www.cnblogs.com/JiaY19/p/18400234

相关文章

  • AT_aising2019_e Attack to a Tree 题解
    挺有意思的树型dp。思路发现直接求解很难对限制下手。但我们可以注意到答案最多为\(n\)。考虑将答案记录dp状态。我们可以记\(dp_{i,j}\)为子树\(i\)合法并且断了\(j\)条边的状态。由于合法状态有两种,并且不好一起考虑,所以可以再在dp状态中加一维。令\(dp_{i,......
  • P8139 [ICPC2020 WF] Sweep Stakes 题解
    思路容易发现,题目要求我们动态维护这样一个多项式。\[\prod_{i}(1-p_i+p_ix)\]如何维护。由于精度问题,我们很难去进行一个多项式除法将其暴力求出。考虑\(p_i\le0.2\)。可以得知,我们的多项式的数的增减是比较大的。那么在一定数量后,一些可能有值的系数在当前精度下是可以......
  • ORCLE数据库语言设置原因查询不出数据的问题解决
    问题现象:oracle数据库视图中存在数据,但是jdbc查询视图查询不出来,后发现视图中有根据默认语言的过滤,如下图: 客户端查询环境语言为 web服务器查询环境语言为US,所以数据查询不出来。解决方案:修改应用端的NLS_LANG的配置与SQL保持一致linux执行下面代码exportNLS_LANG="......
  • CF1469D Ceil Divisions题解
    CF1469DCeilDivisions感觉是很巧妙的一题?一开始想到,对于任何小于$n$的数$x$,直接对它除以$n$可以得到$1$。那么对$3\simn-1$做完此操作后,还剩下$1$、$2$、$n$。将$n$变成$1$要花费$logn$次,显然总操作次数超过了$n+5$次。进一步地,发现瓶颈在于把$n$变成$1$,于是利用根号,用$\sqr......
  • 9.6 上午 becoder 模拟赛总结&题解
    T1语言水题不多说,很容易发现NP需要满足的只是最后一个单词为N,前面是A或N都可以随意放。所以用两个数组,\(v1_i\)记录以\(i\)结尾的前缀是否可以构成NP,\(v2_i\)记录以\(i\)为开头的后缀是否可以构成NP。最后for循环扫一遍是否有同时满足\(v1_{i-1}=true\)和......
  • CF381B题解
    我们先理解题意,大致意思是:给你一个序列让你组成一个中间有一个数,左侧递增右侧递减的数列。从这道题的题意来看,大概思路是:1.我们要将最大值设为中间的数,然后左右两端尽可能的小。2.跑两遍循环,分别为左边的递增边的递减。3.还有,因为一个数可以出现很多次,我们需要一个vis......
  • 2024 年高教社杯全国大学生数学建模竞赛B题解题思路(第一版)
    原文链接:https://www.cnblogs.com/qimoxuan/articles/18399372赛题:问题1:抽样检测方案设计分析:抽样检测方案需要在保证决策准确性的同时,尽量减少检测成本。需要考虑抽样误差对决策的影响,以及如何设置抽样大小和接受/拒绝标准。解题思路:1.确定抽样方法:采用属性抽样,......
  • 【洛谷 P1449】后缀表达式 题解(栈+分支)
    后缀表达式题目描述所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。如:对应的后缀表达式为:。在该式中,@为表达式的结束符号。.为操作数的结束符号。输入格式输入一行......
  • CodeForces 2009G Yunli's Subarray Queries 题解
    云璃!高质量Div.4,吊打某些Div.2Only/Edu/Div.3。本题是下面四道题目的有机结合,优雅且经典。LuoguP4168[Violet]蒲公英|LuoguP1997faebdc的烦恼|LuoguP3203[HNOI2010]弹飞绵羊|LuoguP3246[HNOI2016]序列建议先完成这四题。(必须指出:用蒲公英的分块方......
  • P3688 [ZJOI2017] 树状数组 题解
    P3688[ZJOI2017]树状数组题解记录一下做这道题的心路历程,说明在没有事先知道“九条是求成了后缀和”的情况下如何发现,以及解释一些部分分的做法。sub1,18pts:暴力搜索无脑枚举,复杂度\(\mathcalO(n^m)\)。代码:#include<bits/stdc++.h>#defineintlonglong#defineloop......