首页 > 其他分享 >2024初秋集训——提高组 #32

2024初秋集训——提高组 #32

时间:2024-10-07 19:33:38浏览次数:8  
标签:史莱姆 int 32 ll 2024 初秋 max 0ll dp

B. 序列删除

题目描述

有一个长度为 \(2N\) 的序列 \(A\),其中 \(1\) 到 \(N\) 恰好出现两次。你每次可以选择两个相同的数 \(A_l,A_r(l<r)\) 并花费 \(r-l\) 的代价将其删除。求将整个序列删空的最小代价。

思路

有一个很显然的贪心就是:每次取代价最小的两个数删除。所以我们按照代价排序,用树状数组维护区间中未被删除的数的数量即可。

空间复杂度 \(O(N)\),时间复杂度 \(O(N\log N)\)。

代码

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

const int MAXN = 200001, MAXV = (1 << 20);

struct Node {
  int l, r;
}s[MAXN];

int n, a[MAXN], l[MAXN], tr[MAXN];
ll ans;

void update(int p, int x) {
  for(; p <= 2 * n; tr[p] += x, p += (p & -p)) {
  }
}

int Getsum(int p) {
  int sum = 0;
  for(; p; sum += tr[p], p -= (p & -p)) {
  }
  return sum;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= 2 * n; ++i) {
    cin >> a[i];
    if(!l[a[i]]) {
      l[a[i]] = i;
    }else {
      s[a[i]] = {l[a[i]], i};
    }
  }
  sort(s + 1, s + n + 1, [](const Node &a, const Node &b) -> bool {
    return a.r - a.l < b.r - b.l;
  });
  for(int i = 1; i <= n; ++i) {
    ans += s[i].r - s[i].l - Getsum(s[i].r) + Getsum(s[i].l);
    update(s[i].l, 1), update(s[i].r, 1);
  }
  cout << ans;
  return 0;
}

C. 史莱姆融合

题目描述

在一棵 \(N\) 个结点的树上,有 \(k\) 只史莱姆,一开始在结点 \(id_i\),体积为 \(v_i\)。它们会如下行动:

  • 如果一只史莱姆通过了边权为 \(w\) 的边,则其体积减 \(w\)。若其体积变为非正数,则其消失。
  • 如果多只史莱姆待在同一个结点,则它们将会合并为体积为其体积之和的史莱姆。
  • 史莱姆最终都要到达一个结点 \(c\),但它们会按最优方案行动。

有 \(q\) 次查询,每次查询如果史莱姆要到达 \(c\),且你一开始可以让 \(num(num\in \{0,1\})\) 个史莱姆消失时最终史莱姆的最小体积。

思路

我们先只考虑 \(c=1\) 的情况,那么我们可以令 \(dp_{0/1,u}\) 表示在 \(u\) 子树内删除了 \(0/1\) 个史莱姆,最终子树内的史莱姆到达 \(u\) 的体积。对于 \(dp_{0,u}\),显然有转移 \(dp_{0,u}=\sum \limits_{(v,w)\in son_u} \max(0,dp_{0,v}-w)\)。而对于 \(dp_{1,u}\),我们可以选择删掉这个结点本身的,也可以选择一个儿子子树删,也就是 \(dp_{1,u}=\min (\max(0,dp_{0,u}-w),\min\limits_{v_0\in son_u} \{\max(0,dp_{1,v_0})+\sum \limits_{v\in son_u\and v\ne v_0}\max(0,dp_{0,v})\})\)。

接着我们考虑换根,\(dp_{0,u}\) 的换根很简单,但 \(dp_{1,u}\) 比较麻烦。如果 \(v\) 不是 \(dp_{1,u}\) 转移时最小的那个 \(v_0\),那么可以直接转移。否则必须从次小值转移过来,所以这里还需要记录次小值。

空间复杂度 \(O(N)\),时间复杂度 \(O(N+K+Q)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 100001;
const ll INF = (ll)(1e18);

int n, k, q, a[MAXN], son[MAXN];
ll dp[3][MAXN];
vector<pii> e[MAXN];

void dfs(int u, int fa) {
  dp[0][u] = a[u];
  for(pii g : e[u]) {
    int v = g.first, w = g.second;
    if(v != fa) {
      dfs(v, u);
      dp[0][u] += max(0ll, dp[0][v] - w);
    }
  }
  dp[1][u] = dp[0][u] - a[u], dp[2][u] = INF, son[u] = u;
  for(pii g : e[u]) {
    int v = g.first, w = g.second;
    if(v != fa) {
      ll x = dp[0][u] - max(0ll, dp[0][v] - w) + max(0ll, dp[1][v] - w);
      if(x < dp[1][u]) {
        dp[2][u] = dp[1][u], dp[1][u] = x, son[u] = v;
      }else if(x < dp[2][u]) {
        dp[2][u] = x;
      }
    }
  }
}

void DFS(int u, int fa) {
  for(pii g : e[u]) {
    int v = g.first, w = g.second;
    if(v != fa) {
      ll v0 = dp[0][v], u0 = dp[0][u] - max(0ll, v0 - w);
      dp[0][v] += max(0ll, u0 - w);
      dp[1][v] += max(0ll, u0 - w);
      dp[2][v] += max(0ll, u0 - w);
      if(son[u] != v) {
        ll x = dp[0][v] - max(0ll, u0 - w) + max(0ll, dp[1][u] - max(0ll, v0 - w) - w);
        if(x < dp[1][v]) {
          dp[2][v] = dp[1][v], dp[1][v] = x, son[v] = u;
        }else if(x < dp[2][v]) {
          dp[2][v] = x;
        }
      }else {
        ll x = dp[0][v] - max(0ll, u0 - w) + max(0ll, dp[2][u] - max(0ll, v0 - w) - w);
        if(x < dp[1][v]) {
          dp[2][v] = dp[1][v], dp[1][v] = x, son[v] = u;
        }else if(x < dp[2][v]) {
          dp[2][v] = x;
        }
      }
      DFS(v, u);
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k >> q;
  for(int i = 1, u, v, w; i < n; ++i) {
    cin >> u >> v >> w;
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
  }
  for(int i = 1, u; i <= k; ++i) {
    cin >> u >> a[u];
  }
  dfs(1, 0);
  DFS(1, 0);
  for(int i = 1, u, v; i <= q; ++i) {
    cin >> u >> v;
    cout << dp[v][u] << "\n";
  }
  return 0;
}

标签:史莱姆,int,32,ll,2024,初秋,max,0ll,dp
From: https://www.cnblogs.com/yaosicheng124/p/18450473

相关文章

  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反,脑瘫了没敢用bitset(复杂度擦边但卡常能过),T2空间开大了挂了\(100pts\),\(T3\)是原。T1五彩斑斓部分分\(20pts\):\(O(n^4)\)暴力。部分分\(20+?pts\):进行一些优化,极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\):bitset优化一下,\(O(\f......
  • 团队训练记录2024.10.7
    赛时依然和本校强队差两题比赛链接:https://codeforces.com/gym/104901A.ManyManyHeads这里先用栈处理好第一个状况,然后根据层数进行第二个状况是否存在判断#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;llgcd(llx,lly){if(y==0)retu......
  • 多校A层冲刺NOIP2024模拟赛03
    多校A层冲刺NOIP2024模拟赛03还有一个半小时结束才来,题基本没打,全口胡。T1五彩斑斓(colorful)直接统计答案难做,考虑统计四个顶点都一样的。知道\(n\)行\(m\)列的矩阵有\(\frac{n\times(n+1)\timesm\times(m+1)}{4}\)个子矩阵,这个想成选择矩阵的边界就可以证明。如何统计四......
  • 20241002 模拟赛
    这场爆零了。(惨先把题目发上来吧。A.躲避技能难度:绿机房大佬又给出解法:对于每个账号的位置,我们+1;而关键点,我们-1。(这里其实可以不必考虑正负,最后取abs就行了)然后遍历一遍整棵树,将每个节点(除了根节点)作为根的子树点权和算出来,乘上该节点与其父亲连的边的边权,每个节......
  • Photoshop2024下载安装包(附安装教程)
    Photoshop2024安装包:Photoshop2024安装包百度网盘下载PS2024安装教程:1、右击【PS2024.zip】,选择【解压到PS2024】2、右击【Set-up.exe】,选择【以管理员身份运行】3、点击右下角灰色的小文件夹图标,选择【更改位置】4、选择安装路径后,点击【确定】,然后点击【继......
  • 20222315 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    1.实验内容1.掌握反汇编与十六进制编程器2.能正确修改机器指令改变程序执行流程3.能正确构造payload进行bof攻击2.实验过程1.直接修改程序机器指令,改变程序执行流程将pwn1文件下载至kali中并将pwn1文件改名为pwn20222315,并将其内容复制到pwn2反汇编文件objdump-dpwn2022231......
  • EGOI2024 简单题解
    Day1T1InfiniteRace由于只有重复超过一个人才肯定是跑过一圈的,所以只用用一个数组做标记就可以了,每超过一次就打上标记,否则去掉标记。T2Bouquet定义\(dp[i]\)为,以第\(i\)种郁金香结尾的选法中最大可选的郁金香数量,易得状态转移方程为:\(dp[i]=max{dep[j]}+1(j<l_i\le......
  • 中国大学生程序设计竞赛(秦皇岛)正式赛东北大学秦皇岛分校(SMU Autumn 2024 Team Round 1
    中国大学生程序设计竞赛(秦皇岛)正式赛东北大学秦皇岛分校(SMUAutumn2024TeamRound1)ProblemA.贵校是构造王国吗I思路官方题解很清晰明了。代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineendl'\n'#definePIIpair<int,int>cons......
  • 多校 A 层冲刺 NOIP2024 模拟赛 03
    多校A层冲刺NOIP2024模拟赛03T1五彩斑斓(colorful)签到题直接暴力枚举是\(O(n^4)\),考虑使用\(bitset\)优化,对每个点开个\(bitset\),预处理它所在一行它及它之前相同颜色的位置,这样就只用枚举另一个点所在列,时间复杂度为\(O(n^3+\frac{n^4}{w})\)。T2错峰旅行(travel)......
  • HO引擎近况20241007
    又好几个月没更新,原因是感觉人生有点迷茫了6月这被公司裁员了8月才找到工作,还是原同事推荐的,只凭简历的话根本没可能新的公司又让我长见识了,完全不考虑程序的设计和日后的扩展及维护,只求快速出东西,俩月出一个DEMO,次留好就继续,不好就砍掉项目继续也不是重新正式开发,它没有一个......