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

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

时间:2024-09-28 18:45:14浏览次数:6  
标签:26 fu int 结点 cin 2024 MAXN 怪物 初秋

C. 牛半仙的妹子 Tree

题目描述

给定一棵树,当一个结点上打了标记,那么下一个单位时间这个标记就会扩散到其相邻的结点上,你有以下三种操作:

  • 给一个结点打上标记。
  • 清除所有标记。
  • 查询一个结点是否有标记。

思路

考虑根号分治。

我们对两次二操作之间的操作一数进行分治:

  • 当操作一数 \(\le \sqrt N\) 时,对于每次查询直接暴力枚举之前每一个打了标记的结点并计算其距离,总时间复杂度 \(O(N\sqrt N \log N)\)。
  • 否则,我们使用 bfs 求解,总时间复杂度 \(O(N\sqrt N)\)。

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

代码

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

const int MAXN = 100001, MAXM = 100001, B = 317;

struct query {
  int op, x;
}s[MAXM];

int n, m, dep[MAXN], f[18][MAXN];
bool ans[MAXM], vis[MAXN];
vector<int> e[MAXN];

void dfs(int u, int fa) {
  f[0][u] = fa, dep[u] = dep[fa] + 1;
  for(int i = 1; i <= 17; ++i) {
    f[i][u] = f[i - 1][f[i - 1][u]];
  }
  for(int v : e[u]) {
    if(v != fa) {
      dfs(v, u);
    }
  }
}

int LCA(int u, int v) {
  if(dep[u] < dep[v]) {
    swap(u, v);
  }
  int d = dep[u] - dep[v];
  for(int i = 17; i >= 0; --i) {
    if((d >> i) & 1) {
      u = f[i][u];
    }
  }
  if(u == v) {
    return u;
  }
  for(int i = 17; i >= 0; --i) {
    if(f[i][u] != f[i][v]) {
      u = f[i][u], v = f[i][v];
    }
  }
  return f[0][u];
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for(int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  for(int i = 1; i <= m; ++i) {
    cin >> s[i].op >> s[i].x;
  }
  dfs(1, 0);
  for(int i = 1, j = 1, cnt = 0; i <= m; i = ++j) {
    for(; j <= m && s[j].op != 2; cnt += (s[i].op == 1), ++j) {
    }
    if(cnt <= B) {
      vector<pii> pos;
      for(int k = i; k < j; ++k) {
        if(s[k].op == 1) {
          pos.emplace_back(s[k].x, k);
        }else {
          for(auto [x, id] : pos) {
            if(dep[s[k].x] + dep[x] - 2 * dep[LCA(s[k].x, x)] <= k - id) {
              ans[k] = 1;
              break;
            }
          }
        }
      }
      pos.clear();
    }else {
      queue<int> que;
      for(int k = i; k < j; ++k) {
        queue<int> q;
        for(; !que.empty(); q.push(que.front()), que.pop()) {
        }
        for(; !q.empty(); ) {
          int u = q.front();
          q.pop();
          for(int v : e[u]) {
            if(!vis[v]) {
              vis[v] = 1;
              que.push(v);
            }
          }
        }
        if(s[k].op == 1) {
          que.push(s[k].x);
          vis[s[k].x] = 1;
        }else {
          ans[k] = vis[s[k].x];
        }
      }
      for(int i = 1; i <= n; ++i) {
        vis[i] = 0;
      }
    }
  }
  for(int i = 1; i <= m; ++i) {
    if(s[i].op == 3) {
      cout << (ans[i] ? "wrxcsd\n" : "orzFsYo\n");
    }
  }
  return 0;
}

D. 牛半仙的魔塔 II

题目描述

有 \(N\) 个结点,第 \(i\) 个结点上有一只怪物。一开始你在结点 \(1\),结点 \(1\) 上没有怪物。当你第一次到达一个不为 \(1\) 的结点,你会与上面的怪物战斗,每次战斗你和怪物轮流攻击,你先攻击,每次攻击的伤害为你的攻击减敌人的防御。当你的血量 \(\le 0\) 时你就死了。打死一只怪物之后你的防御会增加。求把所有的怪物打死最后的最大剩余血量。

思路

我们可以求出将哪个怪物优先打更优,但这个怪物不一定能直接打到,不过我们能确定当它的父亲被打死之后下一个一定来打它。也就是可以看作它和它父亲是连在一起的,所以可以把它们合并。我们可以先不考虑你的防御增加,求出最中有多少血。然后在合并时统计能让你少扣多少血。合并用并查集维护,求哪个怪物优先打使用优先队列维护。

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

代码

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

const int MAXN = 100001;

struct Node {
  ll u, a, b;
}s[MAXN];

struct cmp {
  bool operator()(const Node &a, const Node &b) const {
    return 1ll * a.a * b.b > 1ll * b.a * a.b;
  }
};

int n, f[MAXN], _f[MAXN];
ll HP, ATK, DEF;
vector<int> e[MAXN];
priority_queue<Node, vector<Node>, cmp> pq;

int getfa(int u) {
  return (f[u] == u ? u : f[u] = getfa(f[u]));
}

void dfs(int u, int fa) {
  _f[u] = fa;
  for(int v : e[u]) {
    if(v != fa) {
      dfs(v, u);
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  iota(f + 1, f + n + 1, 1);
  for(int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  dfs(1, 0);
  cin >> HP >> ATK >> DEF;
  for(int i = 2, hp, atk, def; i <= n; ++i) {
    cin >> hp >> atk >> def >> s[i].b;
    s[i].u = i;
    s[i].a = (hp + ATK - def - 1) / (ATK - def) - 1;
    HP -= 1ll * s[i].a * atk;
    pq.push(s[i]);
  }
  for(; pq.size(); ) {
    auto [u, a, b] = pq.top();
    pq.pop();
    if(f[u] != u || u == 1 || a != s[u].a || b != s[u].b) {
      continue;
    }
    int fu = getfa(_f[u]);
    HP += 1ll * s[fu].b * a;
    s[fu].a += a, s[fu].b += b;
    f[u] = _f[u];
    pq.push({fu, s[fu].a, s[fu].b});
  }
  cout << (HP > 0 ? HP : -1ll);
  return 0;
}

标签:26,fu,int,结点,cin,2024,MAXN,怪物,初秋
From: https://www.cnblogs.com/yaosicheng124/p/18438266

相关文章

  • 学期2024-2025-1 学号20241401《计算机基础与程序设计》第一周学习总结
    班级的链接2024计算机基础与程序设计作业要求的链接第一周作业作业的目标1、参考教程安装Linux系统;2、快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解决的问题并在期末回答这些问题作业正文本博客教材学习内容总结快速浏览......
  • 团队练习记录2024.9.28
    B-MagicalSubsequencehttps://codeforces.com/gym/103447/problem/B桶+stack,这里用map会TLEstack用一次时间复杂度\(O(1)\)\(156ms/1000ms\)#include<iostream>#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;voidfio(){ ios::sync_wit......
  • 2024-2025全网最全计算机软件毕业设计选题大全:不要踩坑了✅
    博主介绍:✌全网粉丝60W+,csdn特邀作者、Java领域优质创作者、csdn/掘金/哔哩哔哩/知乎/道客/小红书等平台优质作者,计算机毕设实战导师,目前专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌技术栈范围:SpringBoot、Vue、SSM、Jsp、HLMT、Nodejs......
  • 【训练记录】香港城市大学(东莞)2024新生排位赛
    https://ac.nowcoder.com/acm/contest/91116#questionA题:操作1的时候增加代码行数,每次操作1、2的时候更新一下答案,操作2输出答案即可#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;voidsolve(){ intn,q;cin>>n>>q; intnow=0; intans=0; ......
  • CSP-S 2024 第六次
    A排序之后只会选相邻的,直接DP。B从前往后考虑每个数\(a_i\)要不要删。若不删\(a_i\):若\(a_i\ne0\),则\(a_i\)已经确定。若\(a_i=0\),则\(a_i\)可取所有没出现过的数,以及\(i\)后最小的数(先删掉它再把\(a_i\)赋成它)若删掉\(a_i\):若\(a_{i+1}\ne0\),则\(a......
  • 2024初秋集训——提高组 #27
    B.抉择题目描述给定\(N\)个数\(A_1,A_2,\dots,A_N\),求一个\(A\)的子序列\(B\)的\(\sum\limits_{i=1}^{k-1}B_i\operatorname{AND}B_{i+1}\)的最大值。思路令\(dp_i\)表示最后一个数是\(A_i\)的最大答案。我们很明显有转移\(dp_i\leftarrowdp_j+A_j\opera......
  • 20240925 随机训练
    LinkUpdateMax将总贡献拆成每个位置单独的贡献。假设一共有\(m\)个数未确定。如果\(a_i\neq-1\),那么产生贡献的条件就是:前面每个\(a_j<a_i\)。前面填充的\(cnt\)个空的数都要小于\(a_i\)。第一个条件可以直接判断,第二个考虑使用组合数学。由于只能使用那些小......
  • [DMY]2024 CSP-S 模拟赛 Day 6
    前言离A掉一道题最近的一次。过程看完T1以后,想先构一个\(\mathcal{O}(n^3)\)的暴力,但是发现只有10pts,而且算法复杂度接近\(\mathcal{O}(n^4)\),所以果断放弃。把链的限制写了(然后亏大了),然后开始在CS上面画画。画了一会发现一个简单的dp思路,但是是\(\mathcal{O}(n^......
  • SolidWorks.2024.SP3.1图文安装教程及下载
    SOLIDWORKS2024引入了一系列新功能和性能改进,‌旨在提升用户在设计、‌仿真、‌数据管理和制造等方面的效率和创新能力。‌安装前准备工作:【rjqjf.com】首先检查一下NETFramework3.5和4.0是否已安装。如果未安装.NETFramework3.5(包括.NET2.0和3.0),请转到“控制面板”->“......
  • NOIP2024集训Day37 DP
    NOIP2024集训Day37DPA.[CQOI2011]放棋子设\(f_{i,j,k}\)表示前\(k\)种棋子放了任意\(i\)行、\(j\)列。决策是:在哪些位置填同种颜色的棋子。于是美剧上一个状态的\(i,j\)(表示为\(l,r\)),上一状态\(k_1=k-1\)。设\(g_{i,j,k}\)表示\(k\)个同种颜色的......