首页 > 其他分享 >GYM 104114 F

GYM 104114 F

时间:2024-09-11 21:49:26浏览次数:12  
标签:sz 比赛 Min int GYM MAXN getfa 104114

题目描述

有 \(N\) 个参赛选手,将进行 \(N-1\) 场比赛,第 \(i,j\) 个选手进行比赛有 \(P_{i,j}\) 的激烈程度。每当选手 \(i\) 打败选手 \(j\) 时,\(P_{i,x}\leftarrow\max(P_{i,x},P_{j.x})\)。

在这些比赛中,编号小的选手总是打败编号大的选手。求最终 \(N-1\) 场比赛的激烈程度之和的最大值并给出方案。

思路

由于打败对手后激烈程度会取最大值,所以可以看作是两个集合 \(S_1,S_2\) 在打比赛,其激烈程度为 \(\min \limits_{x\in S_1,y\in S_2} \{P_{x,y}\}\)。

这实际上就是最小生成树。

但这道题要输出方案,也很好解决。两个集合 \(S_1,S_2\) 打比赛就是 \(\min \limits_{x\in S_1}\{x\},\min \limits_{x\in S_2}\{x\}\) 在打比赛。

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

代码

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

const int MAXN = 1001;

struct Edge {
  int u, v, w;
}e[MAXN * MAXN], edge[MAXN];

int n, f[MAXN], sz[MAXN], Min[MAXN], tot;
ll ans;

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

void Merge(int u, int v) {
  u = getfa(u), v = getfa(v);
  if(u != v) {
    if(sz[u] > sz[v]) {
      swap(u, v);
    }
    f[u] = v, sz[v] += sz[u], Min[v] = min(Min[v], Min[u]);
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    sz[i] = 1, f[i] = Min[i] = i;
    for(int j = 1, w; j <= n; ++j) {
      cin >> w;
      e[(i - 1) * n + j] = {i, j, w};
    }
  }
  sort(e + 1, e + n * n + 1, [](const Edge &a, const Edge &b) {
    return a.w > b.w;
  });
  for(int i = 1; i <= n * n; ++i) {
    auto [u, v, w] = e[i];
    if(getfa(u) != getfa(v)) {
      ans += w;
      edge[++tot] = {Min[getfa(u)], Min[getfa(v)], w};
      Merge(u, v);
    }
  }
  cout << ans << "\n";
  for(int i = 1; i < n; ++i) {
    cout << edge[i].u << " " << edge[i].v << "\n";
  }
  return 0;
}

标签:sz,比赛,Min,int,GYM,MAXN,getfa,104114
From: https://www.cnblogs.com/yaosicheng124/p/18409040

相关文章

  • OpenAI Gym ProcGen - Getting Action Meanings
    题意:OpenAIGymProcGen-获取动作含义问题背景:IntheOpenAIProcGengym,Iamnotgettingaway togetthemeaningsoftheactionvalues,Icanseethatthereare15actionsforthecoinrunenvironmentusing env.action_space.n.IhavetriedboththeG......
  • GYM 105264 E
    题目描述给定一个\(N\)个点的树,你要从中选出一个大小为\(k\)的子树出来,求这个子树的最小直径。思路由于此题允许\(O(N^2)\)的时间复杂度,所以考虑枚举子树的中心。接着以该中心为根向下搜出深度为\(i\)的结点数\(cnt_i\),接着枚举直径长度除\(2\)。由于这里直径可能长......
  • GYM 105264 C
    题目描述给定一个长度为\(N\)的数组\(A\),每次你可以令\(A_i\leftarrowA_i+1\)或\(A_i-1\)。求进行至多\(k\)次操作后\(A\)中最少不同元素数量。思路首先对\(A\)进行排序。令\(dp_{i,j}\)表示考虑前\(i\)个数,有\(j\)个不同的值时最多还能剩余几次操作。很......
  • OpenAI Gym custom environment: Discrete observation space with real values
    题意:OpenAIGym自定义环境:具有实数值的离散观测空间问题背景:Iwouldliketocreatecustomopenaigymenvironmentthathasdiscretestatespace,butwithfloatvalues.Tobemoreprecise,itshouldbearangeofvalueswith0.25step:10.0,10.25,10.5,10......
  • Start OpenAI gym on arbitrary initial state
    题意:“在任意初始状态下启动OpenAIGym”问题背景:AnybodyknowsanyOpenAIGymenvironmentswherewecansettheinitialstateofthegame?Forexample,IfoundtheMountainCarContinuous-v0candosuchthingsothatwecanselectatwhichpointthecarst......
  • gym创建环境、自定义gym环境
    环境:half_cheetah.pyfromosimportpathimportnumpyasnpfromgymnasiumimportutilsfromgymnasium.envs.mujocoimportMujocoEnvfromgymnasium.spacesimportBoxDEFAULT_CAMERA_CONFIG={"distance":4.0,}classMOHalfCheetahEnv(Mujoc......
  • gym序列化、EzPickle类
    EzPickle是一个用于强化学习环境的类,它重写了__getstate__和__setstate__方法,以便通过构造函数参数(*args,**kwargs)进行序列化和反序列化。这个设计允许那些无法直接用pickle库处理的对象,如数据库连接和网络套接字,也能在保存和恢复时保持其状态。"""Classforpicklingandun......
  • mujoco gymnasium 环境
    本文简要介绍gynasium中基于mujoco的环境搭建。参照gynasium.envs.mujoco。1.gynasium.Env简介在gynasium中,环境基类为gynasium.Env,其中定义了step,reset,render,close等方法以及action_space,observation_space,reward_range,spec,metadata,np_random......
  • Why unwrap an openAI gym?
    题意:为什么要“解开”OpenAIGym?问题背景:I'mtryingtogetsomeinsightsintoreinforcementlearningwhileusingopenAIgymasalearningenvironment.Idothisbyreadingthebook Hands-onreinforcementlearningwithPython.Inthisbook,somecodeisp......
  • Gym102788,B - Rectangles题解
    水水水~题目链接戳我分析首先根据题目条件可得式子=>\((x-2)(y-2)=n(2x+2y-4)\)化简式子可得\[\begin{align}(x-2)(y-2)=&n(2x+2y-4)\\xy-2x-2y+4=&2nx+2ny-4n\\x(y-2n-2)=&2ny-4n-4+2y\\x=&\frac{2ny-4n-4......