首页 > 其他分享 >CF538H Summer Dichotomy 题解

CF538H Summer Dichotomy 题解

时间:2024-07-30 20:10:06浏览次数:14  
标签:std Summer int 题解 kMaxN CF538H n1 n2 col

Description

有 \(T\) 名学生,你要从中选出至少 \(t\) 人,并将选出的人分成两组,可以有某一组是空的。

有 \(n\) 名老师,每名老师要被分配到两个小组之一,对于第 \(i\) 名老师,要求所在的小组中的学生人数 \(\in [l_i, r_i]\)。

此外,有 \(m\) 对老师不能在同一个小组中。

你需要判断能否满足所有要求,如果可以,请给出一种方案。

\(t \le T \le 10^9\),\(n,m \le 10^5\)。

Solution

先不考虑人数为 \([t,T]\) 的限制,只考虑怎么取出 \(n_1\) 和 \(n_2\) 使答案尽可能合法。

注意到如果 \(\max\{l_i\}\leq\min\{r_i\}\) 那么 \(n_1\) 和 \(n_2\) 取这个区间里的任意一个数均可行。

否则不妨让 \(n_1=\min\{r_i\},n_2=\max\{l_i\}\),则一定有 \(n_1<n_2\),此时如果让 \(n_1\) 增大则必然会使 \(r\) 最大的那个区间两个组都选不上,而让 \(n_1\) 减少则一定会让 \(n_1\) 这边能放的区间变为原来的子集,一定不优。对于 \(n_2\) 同理,所以此时的 \(n_1,n_2\) 一定是最优解。

现在考虑上 \([t,T]\) 的限制,如果 \(n_1+n_2\in [t,T]\) 则不需要调整。如果 \(n_1+n_2>T\),注意到 \(n_2\) 不能减少,所以让 \(n_1\) 减少,\(n_2\) 不变最优。如果 \(n_1+n_2<t\) 则让 \(n_1\) 不变,\(n_2\) 增大最优。

确定了 \(n_1,n_2\) 后只需要对于每个区间判断其能放到哪个组,如果只能放一个组则已经确定,否则不管它。

然后对于不能放在一个组的两个区间连一条边,跑二分图染色即可。

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

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int L, R, n, m;
int l[kMaxN], r[kMaxN], col[kMaxN];
bool vis[kMaxN];
std::vector<int> G[kMaxN];

bool dfs(int u) {
  vis[u] = 1;
  for (auto v : G[u]) {
    if (!col[v]) {
      col[v] = 3 - col[u];
      dfs(v);
    } else if (col[v] == col[u]) {
      return 0;
    }
  }
  return 1;
}

void dickdreamer() {
  std::cin >> L >> R >> n >> m;
  int n1 = 1e9, n2 = 0;
  for (int i = 1; i <= n; ++i) {
    std::cin >> l[i] >> r[i];
    n1 = std::min(n1, r[i]), n2 = std::max(n2, l[i]);
  }
  if (n1 + n2 > R) n1 = R - n2;
  if (n1 + n2 < L) n2 = L - n1;
  if (n1 < 0 || n2 < 0) return void(std::cout << "IMPOSSIBLE\n");
  for (int i = 1; i <= n; ++i) {
    int o1 = (l[i] <= n1 && n1 <= r[i]), o2 = (l[i] <= n2 && n2 <= r[i]);
    if (!o1 && !o2) return void(std::cout << "IMPOSSIBLE\n");
    if (o1 && !o2) col[i] = 1;
    else if (!o1 && o2) col[i] = 2;
  }
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    if (!vis[i] && col[i] && !dfs(i))
      return void(std::cout << "IMPOSSIBLE\n");
  }
  for (int i = 1; i <= n; ++i) {
    if (!vis[i] && !col[i]) {
      col[i] = 1;
      if (!dfs(i)) return void(std::cout << "IMPOSSIBLE\n");
    }
  }
  std::cout << "POSSIBLE\n" << n1 << ' ' << n2 << '\n';
  for (int i = 1; i <= n; ++i) std::cout << col[i];
}

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;
}

标签:std,Summer,int,题解,kMaxN,CF538H,n1,n2,col
From: https://www.cnblogs.com/Scarab/p/18333247

相关文章

  • SP8099 TABLE - Crash´s number table 题解
    题目传送门前置知识一般的积性函数|数论分块|莫比乌斯反演解法令\(n\lem\)。考虑莫比乌斯反演,推式子,有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\operatorname{lcm}(i,j)\\&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\frac{ij}{\gcd(i,j)......
  • 题解:Pinely Round 4 (Div. 1 + Div. 2) A
    A.MaximizetheLastElementtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)of\(n\)integers,where\(n\)isodd.Inoneoperation,youwillremovetwoa......
  • P4449 于神之怒加强版 (题解)
    题目链接P4449于神之怒加强版题目大意:求\[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\]\(数据范围n,m\leq5e6\)\(二话不说,先开导式子(假定n<m):\)\begin{aligned}ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\\\end{aligned}\[先套路地枚举d=gcd(i,j)\]\begin{align......
  • 题解 - Alice
    题目描述Alice和Bob在玩游戏,游戏规则如下:有两堆石子,每堆石子有非负整数个Alice与Bob轮流操作,Alice先手,每次可以从任意一堆石子中取出若干个取出的石子个数应满足为另一堆石子个数的因数(此处规定任何数均为0的因数)将石子取完的玩家获胜给定一个初始状态,现......
  • [POI2007] OSI-Axes of Symmetry 题解
    给出一个多边形,求对称轴数量。考虑对于一个多边形,其是对称的当且仅当对于若干个边(角),其左右的角与边都是对称的。考虑如果我们对于内角构造出一种单射,映射为一个整数,将边映射为它的边长,那么我们按照角,边,角,边,……的顺序将他们加入数组中,能构造出一个长度为\(2n\)的数组,将这个......
  • 旅行 题解
    题目id:20300题目描述鱼大大计划环华夏自驾游游玩一圈,在他的计划中,这次旅行将在\(m\)天内完成,预计游玩\(n\)个城市,每个城市游玩\(x\)天,然后赶路开车以均速去到下一个城市,现鱼大大从海洋城市出发,按游玩顺序先后给出每个城市和上一个城市之间的距离(\(km\)),问鱼大大每天至少赶路多......
  • 质数差列 题解
    题目id:20315题目描述驰骋宇宙的鱼大大找到了一个古遗迹,稍作研究后发现这是一个来着远古的质数星球文明遗迹,这个文明的特点是所有事物都和质数息息相关。于是,鱼大大赶紧列出了一堆的质数,以方便自己的研究。这天鱼大大找到了质数星球文明的一个遗迹仓库大门,正准备破解密码的同时......
  • [POI2008] POC-Trains 题解
    前言题目链接:洛谷。时间复杂度和输入同阶的做法。题意简述有\(n\)(\(n\leq10^3\))个长\(m\)的字符串,\(q\)(\(q\leq10^5\))次操作,交换两个字符串的两个字符。问每个字符串在所有时刻,最多有几个和它相等。题目分析套路做法看到字符串相等,想到使用哈希。但是要支持修改,怎么......
  • 题解:[ABC363D] Palindromic Number
    提示特定位数的回文数数量是可以快速计算出来的,对于特定的位数\(n\),第一位由于不能有前导\(0\),共有\(9\)种选择,而从第\(2\)位到第\(\frac{n+1}{2}\)位都有\(10\)种选择(一个回文数完全由它的前半部分确定)。所以\(n\)位数中共有\(S(n)=9*10^\frac{n-1}{2}......
  • P3811 【模板】模意义下的乘法逆元 题解
    【模板】模意义下的乘法逆元题目背景这是一道模板题题目描述给定n,pn,pn,p求......