「JSOI2014」学生选课

2021-04-20 07:27

阅读：559

标签：int ons print har stdin struct ref stdout lse

「JSOI2014」学生选课

传送门
看到这题首先可以二分。
考虑对于当前的 \(mid\) 如何 \(\text{check}\)
我们用 \(f_{i,j}\) 来表示 \(i\) 对 \(j\) 的好感度排名，那么对于两个人 \(i\)，\(j\) 如果有 \(\max\{f_{i, j}, f_{j, i}\} > mid\) 那么显然这两个人是不能上同一个老师的课的。
而且每个人可以上的课只有两种，我们记为 \(a_{i, 0 / 1}\)
假设 \(i\)，\(j\) 对于当前的 \(mid\) 而言不能分在一起，其中 \(a_{i, 0} = a_{j, 0}\)，那么我们可以发现：

\(i\) 上 \(a_{i, 0}\) 的课，则必须有 \(j\) 上 \(a_{j, 1}\) 的课
\(j\) 上 \(a_{j, 0}\) 的课，则必须有 \(i\) 上 \(a_{i, 1}\) 的课

可以发现这就是一个裸的 \(\text{2-SAT}\)
所以我们每次 \(\text{check}\) 都建图跑一遍 \(\text{2-SAT}\) 就好了。
参考代码：

#include 
#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template  inline T min(T a, T b) { return a  inline T max(T a, T b) { return a > b ? a : b; }
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' > 1;
        if (check(mid)) r = mid; else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

「JSOI2014」学生选课

标签：int ons print har stdin struct ref stdout lse

原文地址：https://www.cnblogs.com/zsbzsb/p/12260562.html

上一篇：MVC初体验-EF简介（16）

下一篇：《ASP.NET Core 高性能系列》ASP.NET Core的启动过程(1)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：「JSOI2014」学生选课
文章链接：http://soscw.com/essay/77029.html

亲，登录后才可以留言！

「JSOI2014」学生选课

「JSOI2014」学生选课

评论

热门文章

推荐文章

最新文章

置顶文章