首页 > 其他分享 >SpainOI XXIV

SpainOI XXIV

时间:2024-09-26 12:01:45浏览次数:8  
标签:int Solve 复杂度 删掉 SpainOI 骨牌 XXIV MAXN

GYM 105325 B

题目描述

有 \(N\) 个站,站之间有 \(M\) 条单向道路。一条路径的代价为:

  • 令你经过的边权为 \(w_1,w_2,\dots,w_k\),则你的代价为 \(w_1\cdot k+w_2\cdot(k-1)+\dots+w_k\)。

求你从 \(0\) 到其他点的最少代价。

思路

令 \(dp_{i,u}\) 表示还要走 \(i\) 条边,当前在 \(u\) 的最小代价。

很明显有以下转移:\(dp_{i,u}+i\cdot w\rightarrow dp_{i-1,v}(i\ge 1,v\in d_u)\),\(d_u\) 是 \(u\) 的出边。

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

代码

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

const int MAXN = 1001, INF = int(1e9) + 1;

int T, n, m, dp[MAXN][MAXN];
vector<pii> e[MAXN];

void Solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    e[i].clear();
    for(int j = 0; j < n; ++j) {
      dp[j][i] = (i == 1 ? 0 : INF);
    }
  }
  for(int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w;
    u++, v++;
    e[u].emplace_back(v, w);
  }
  for(int i = n - 1; i >= 1; --i) {
    for(int u = 1; u <= n; ++u) {
      for(auto [v, w] : e[u]) {
        dp[i - 1][v] = min(dp[i - 1][v], dp[i][u] + i * w);
      }
    }
  }
  for(int i = 2; i <= n; ++i) {
    cout << (dp[0][i] == INF ? -1 : dp[0][i]) << " \n"[i == n];
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> T; T--; Solve()) {
  }
  return 0;
}

GYM 105325 B

题目描述

有 \(N\) 个骨牌,第 \(i\) 个骨牌位于位置 \(p_i\),高度为 \(h_i\)。对于 \(\forall 1\le i< N,p_i<p_{i+1}\)。

当骨牌 \(i\) 倒下时,它会击倒所有 \(j>i且p_i+h_i>p_j\) 的骨牌。

请你判断当前局面属于哪种情况:

  • 推倒最左边的骨牌后,最右边的骨牌不会倒。输出 Pep
  • 推到最左边的骨牌后,最右边的骨牌会倒下。但存在一个不是最左或最右的骨牌,使得抽走它以后,推倒最左边的骨牌后,最右边的骨牌不会倒。输出 Ivet
  • 推到最左边的骨牌后,最右边的骨牌会倒下。不存在一个不是最左或最右的骨牌,使得抽走它以后,推倒最左边的骨牌后,最右边的骨牌不会倒。输出 Cesc

思路

令 \(r_i\) 表示 \(i\) 最远能推倒的骨牌。

我们记 \(S_i=\max \limits_{j=1}^i \{r_j\}\),就是当前最远能推倒的骨牌。如果存在一个骨牌\(i\) 使得 \(i\ge S_{i-1}\),那么很明显答案为 Pep

否则的话,最劣情况下一定会抽走那个 \(r_j\) 的最大值,所以我们再记录一个次大值判断是否合法即可。

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

代码

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

const int MAXN = 20001;

int t, n, p[MAXN], h[MAXN], r[MAXN];

void Solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> p[i] >> h[i];
  }
  int Max = 1, Max2 = 0, pos = 0;
  for(int i = 1; i <= n; ++i) {
    r[i] = lower_bound(p + 1, p + n + 1, p[i] + h[i]) - p - 1;
    if(Max < i) {
      cout << "Pep\n";
      return;
    }
    Max = max(Max, r[i]);
  }
  Max = 1, Max2 = 1;
  for(int i = 1; i <= n; ++i) {
    if(i > 2 && (pos == 1 ? Max : Max2) < i) {
      cout << "Ivet\n";
      return;
    }
    if(r[i] > Max) {
      Max2 = Max, Max = r[i], pos = i;
    }else if(r[i] > Max2) {
      Max2 = r[i];
    }
  }
  cout << "Cesc\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}

GYM 105325 E

题目描述

给定一张图,其中有一个获胜顶点,接着两个玩家将轮流进行操作:

  • 在图中选择一个连通分量,删除该连通分量中编号最小的点和连接它的边。

先删除获胜顶点的玩家获胜。求哪些获胜顶点使得先手获胜。

思路

我们考虑对这张图建一个树,表示删掉树上某个点的父亲后就能删掉这个点。

我们可以把这个过程倒过来,看成从大到小加点。每次加入一个点,我们枚举它的出边,如果连接的点的编号小于当前点,那么交给后面处理。否则看对应的连通块,只要删掉了当前点,那么该连通块的最小值也可以被删掉,所以我们建立父子关系并合并连通块。这可以用并查集处理。

接着我们枚举每个点作为获胜点。如果当前点是连通块中的最小值,那么先手显然必胜。否则,两名玩家肯定不想删掉该点的父亲,因为只要删掉,那么另一位玩家就能立马删掉获胜点。所以两名玩家会先把除了该点的父亲的子树的所有点删掉,接下来进行操作的人必输,所以只有除了该点的父亲的子树的点数为奇数时,先手必胜。

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

代码

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

const int MAXN = 100001;

int T, n, m, f[MAXN], fa[MAXN], sz[MAXN];
vector<int> e[MAXN], g[MAXN];

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

void dfs(int u) {
  sz[u] = 1;
  for(int v : g[u]) {
    fa[v] = u;
    dfs(v);
    sz[u] += sz[v];
  }
}

void Solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    e[i].clear();
    f[i] = i;
  }
  for(int i = 0; i <= n; ++i) {
    g[i].clear();
  }
  for(int i = 1, u, v; i <= m; ++i) {
    cin >> u >> v;
    u++, v++;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  for(int i = n; i >= 1; --i) {
    for(int v : e[i]) {
      if(v > i && getfa(i) != getfa(v)) {
        g[i].emplace_back(getfa(v));
        f[getfa(v)] = i;
      }
    }
  }
  for(int i = 1; i <= n; ++i) {
    if(f[i] == i) {
      f[i] = 0;
      g[0].emplace_back(i);
    }
  }
  dfs(0);
  for(int i = 1; i <= n; ++i) {
    if(!fa[i] || (n - sz[fa[i]]) % 2 == 1) {
      cout << i - 1 << " ";
    }
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> T; T--; Solve()) {
  }
  return 0;
}

标签:int,Solve,复杂度,删掉,SpainOI,骨牌,XXIV,MAXN
From: https://www.cnblogs.com/yaosicheng124/p/18433179

相关文章