首页 > 其他分享 >[PA2024] Modernizacja Bajtocji 题解

[PA2024] Modernizacja Bajtocji 题解

时间:2024-11-04 10:09:21浏览次数:1  
标签:cnt Bajtocji int 题解 电脑 Byteasar PA2024 居民 op

Description

Byteland 正在走向现代化。最新的政府项目旨在为那些没有电脑的村镇居民提供电脑。Byteasar 正在监督该计划中的一个村庄——Bytetown——的现代化进程,目前那里没有一个居民拥有电脑。

Bytetown 有 \(n\) 个居民,为了简单起见,Byteasar 将他们用 \(1\) 到 \(n\) 的整数编号。最初没有一个居民拥有电脑。Byteasar 的任务是处理三种形式的事件:

  • \(\texttt{+}\ a_i\ b_i\):将一台电脑送给 Bytetown 的居民。然而,Byteasar 并不知道电脑是送给了编号为 \(a_i\) 还是 \(b_i\) 的居民。可能会出现 \(a_i = b_i\) 的情况——在这种情况下,电脑肯定送给了编号为 \(a_i\) 的居民。可以确定的是,电脑被送到了目前还没有电脑的居民手中。
  • \(\texttt{-}\ c_i\):编号为 \(c_i\) 的居民的电脑坏了。可以肯定的是,该居民曾经拥有一台电脑(但现在不再拥有,因此将来可能会收到一台新电脑)。
  • \(\texttt{?}\ d_i\):Byteasar 需要(利用迄今为止获得的所有信息)确定编号为 \(d_i\) 的居民:肯定有电脑,肯定没有电脑,还是不确定他是否有电脑。

请编写一个程序,帮助 Byteasar 回答所提出的问题!

注:在居民的电脑坏掉的前一刻,Byteasar 不一定可以确定这个居民是否有电脑。换句话说,在某居民电脑坏掉之前,不一定可以从之前的事件中确定他是否有电脑。

Solution

首先没有 \(-\) 操作是好做的,如果把 \(+\) 操作的两个居民连一条边,则一定会连成树/基环树。对于一个连通块,如果大小为 \(1\),则一定没电脑,否则如果为树,则全部无法确定,基环树则每个人都有。

加上 \(-\) 操作后就把操作的点从其所在连通块删掉,原连通块如果为基环树则还是,否则如果删掉后只有一个点就看成单点,否则还是个树。

但是暴力删是做不了的,考虑把删点看成加点,即删掉点 \(a\) 时,只将原连通块的状态更新但不删点,然后新建一个点 \(a'\) 并把 \(a\) 放到 \(a'\) 上。

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

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1.3e6 + 5;
const char kC[] = "0?1";

int n, q, cnt;
int id[kMaxN], fa[kMaxN], sz[kMaxN], op[kMaxN];

// 0 : 单点,1 : 树,2 : 基环树

int find(int x) {
  return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void unionn(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx == fy) op[fx] = 2;
  else fa[fx] = fy, op[fy] = ((op[fx] == 2 || op[fy] == 2) ? 2 : 1), sz[fy] += sz[fx];
}

void dickdreamer() {
  std::cin >> n >> q;
  cnt = n;
  for (int i = 1; i <= n; ++i) id[i] = fa[i] = i, sz[i] = 1;
  for (int i = 1; i <= q; ++i) {
    std::string s;
    int a, b;
    std::cin >> s;
    if (s[0] == '+') {
      std::cin >> a >> b;
      unionn(id[a], id[b]);
    } else if (s[0] == '-') {
      std::cin >> a;
      int f = find(id[a]);
      if (op[f] == 1 && --sz[f] == 1) op[f] = 0;
      id[a] = ++cnt;
      fa[cnt] = cnt, sz[cnt] = 1;
    } else {
      std::cin >> a;
      std::cout << kC[op[find(id[a])]];
    }
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:cnt,Bajtocji,int,题解,电脑,Byteasar,PA2024,居民,op
From: https://www.cnblogs.com/Scarab/p/18524587

相关文章

  • Codeforces Round 984 (Div. 3) 题解
    CodeforcesRound984(Div.3)题解CodeforcesRound984(Div.3)Problem-A-Codeforces解题思路n很小,直接枚举即可#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;inta[100];voidsolve(){ intn;cin>>n; for(inti=1;i<=n;i......
  • SP30785 ADAAPPLE - Ada and Apple 题解
    洛谷题目传送门博客园可能食用更佳题目大意:给定一棵权值为000或11......
  • P11244 吻秋 题解
    洛谷题目传送门博客园可能食用更佳题目大意:给你mmm个长度为nn......
  • CSP-S 2024 题解
    CSP-S2024题解决斗发现一张卡只有和小的配对才能有贡献,所以sort一遍维护一下比当前小,没被击败的卡的数量就好了其实可以证明答案就是\(n-众数个数\),大概就是贪心的选择一条升序的序列,之后它们有\(len-1\)的贡献(即链头没有贡献),发现一共正好有众数个数条链超速检测挂得最......
  • P11244 吻秋 题解
    洛谷题目传送门博客园可能食用更佳题目大意:给你\(m\)个长度为\(n\)的序列\(a\),\(Q\)次操作:1xy将\(a_x\)与\(a_y\)的所有元素取出至长度为\(2n\)的序列\(b\),将\(b\)升序重排后\(a_x\getsb_{1\dotsn},a_y\getsb_{n+1\dots2n}\);2ij询问\(a_{......
  • 2024秋季赛部分题解(A,E,F,I,J)
    J 螺旋塔思路:一眼签到题直接写#include<iostream>#include<map>#include<vector>#include<stack>#include<queue>#include<cmath>#include<algorithm>#include<cstring>#include<string>#include<set>usingname......
  • 牛客周赛ROUND66-C题题解
    牛客周赛ROUND66-C题题解题目描述:小苯有一个正整数n,他想让n尽可能小,为此他可以做如下的操作任意次:将n的第一个数位放在最后一位。(例如n=123,则操作完后n=231)。小苯想知道他最小可以将n变为多少,请你帮他算一算吧。输入描述:每个测试文件内都包含多组测试数据。第一......
  • 新生赛题解(最大的最短或子段)
    \(题解:\)\(我们考虑到其最大值是固定的\)\(所以我们优先求出其最大值\)\(考虑到其答案肯定是一个固定的区间\)\(对于每个区间如果将其范围缩小它的取值或值只会单调不增\)\(那么对于每个区间首先选定其左端点然后我们向右不断拓展区间长度\)\(一直到其区间或值为最大值......
  • P11229 [CSP-J 2024] 小木棍 题解
    算法一,dp首先对于\(10^5\)的数据,很明显,如果用longlong是绝对会爆炸的,所以使用string类型进行dp.定义状态\(f_i\),表示用\(i\)根木棍能拼出的最小数字.显然,可以先初始化1~7的情况.状态转移:\(f_i=cmp(f_i,f_{i-stk_j}+j).\),其中,cmp为比较函数,j为0~9......
  • 「NOIP2022」建造军营 题解
    前言题目链接:洛谷。题意简述yzh送你一张\(n\)个点\(m\)条边的无向连通图,你可以决定选择\(n\)个点中若干个、\(m\)条边中若干条,方案数为\(2^n2^m\)。在你操作后,yzh会任意挑选一条边,如果这条边没有被你选中,那么就要断开这条边,否则什么事也没发生。你需要保证无论yzh......