C - Grab the Seat!
有一个竖直的屏幕位于 (0,1)−(0,m)，有 n 行 m 列座位，有 k 个座位有人。q 次询问，这 k 个人其中一个会离开座位，坐到 (x,y)。对于每次询问，求不被人遮挡整个屏幕的座位数。
画一个图，从(0,1)、(0,m) 向某个座位连两条射线。射线后面的所有座位都不是答案。
维护线段可以用李超树，但这题有一些单调的性质。
- 很显然同一行的人，我们只用考虑最靠前的人能挡住的面积是多少。因为如果最前面的人被挡住，被包含在某个区域内，后面的人也会包含在其内。
- 从 (0,1) 做射线，越靠前的人斜率越大，挡住的区域越大。他唯一挡不住的就是 (0,1),(x,y) 确定的这条直线左边的人。
- 从 (0,m) 做射线，越靠前的人斜率的绝对值越大。同 2 。
所以我们实际上只需要维护一个斜率最大的直线，每次计算一下他往后的交点，看一下这个交点是否能包含它所在行的所有点，如果不能，说明有一个更靠前的座位不会被挡住，这时候我们就维护更靠前的这个座位直线的斜率。
从下往上扫一遍，再从上往下扫一遍。求出每行第一个被挡住的人的位置，答案为这些人前面人数的和。
复杂度 O(nq)
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
constexpr long long inf = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k, q;
cin >> n >> m >> k >> q;
vector<int> x(k), y(k);
for (int i = 0; i < k; i++) {
cin >> x[i] >> y[i];
}
while (q--) {
int id;
cin >> id;
id--;
cin >> x[id] >> y[id];
vector<int> xs(m + 1, n + 1);
for (int i = 0; i < k; i++) {
xs[y[i]] = min(xs[y[i]], x[i]);
}
vector<long long> last(m + 1);
for (int i = 1; i <= m; i++) {
last[i] = xs[i] - 1;
}
{
long long bestx = inf, besty = 1;
for(int yi = 2; yi <= m; yi++) {
int py = yi - 1;
if (bestx != inf) {
last[yi] = min(last[yi], (bestx * py - 1) / besty);
}
if (py * bestx >= xs[yi] * besty) {
bestx = xs[yi];
besty = py;
}
}
}
{
long long bestx = inf, besty = 1;
for(int yi = m - 1; yi >= 1; yi--) {
int py = m - yi;
if (bestx != inf) {
last[yi] = min(1ll * last[yi], 1ll * (bestx * py - 1) / besty);
}
if (py * bestx >= xs[yi] * besty) {
bestx = xs[yi];
besty = py;
}
}
}
long long ans = accumulate(last.begin() + 1, last.end(), 0ll);
cout << ans << '\n';
}
return 0;
}
I - Chiitoitsu
初始手牌有 13 张麻将牌，相同牌至多出现 2 张，每轮可以从牌堆摸牌，若达成七对子则自摸胡牌，若不然则选择手牌中某张牌并丢弃之。给定初始手牌，求最优策略下达成七对子的期望轮数。多组数据，数据组数不超过 105 组
首先要搞清楚什么是最优策略：能组成一对的早组成了，打出去的牌以后不会再摸回来，手里的单牌以后一定能组成一对（牌堆里一定还剩三张匹配的）。
概率 dp 的状态表示一般为：当前状态下结束游戏需要多少轮；初始化已经知道的能结束游戏的状态。
答案是 dp[初始状态…]
遵循最优策略，我们的目标只有胡牌，手里的对子一定留着不用管，所以考虑的就是我手里有多少张单牌，由于外面一定有三张单牌，所以概率和剩多少牌有关。
dp(i,j):手里有i张单牌，外面有j张牌的情况下胡七对子需要多少轮
当摸了一张牌起来，现在 14 张，接下来要么胡牌游戏结束，要么打出去一张牌。考虑两种情况：
- 摸进来的牌没用，再打出去。手里有 i 张单牌，没用的牌有 j−3×i 张。
dp(i,j)=1+dp(i,j−1)×j−3×ij
- 摸进来的牌有用，打一张别的单牌出去，此时手里的一个单牌组成了一对，又打出去了一张，所以单牌减少两张。有用的牌是剩下来 j 张牌中的 3×i 张。
dp(i,j)=1+dp(i−2,j−1)×3×ij
注意边界。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
const int n = 13, m = 123;
vector<vector<Mint>> dp(n + 1, vector<Mint>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j < 3 * i) {
continue;
}
if (i >= 2) {
dp[i][j] = dp[i - 2][j - 1] * (3 * i) / j;
}
dp[i][j] += 1 + dp[i][j - 1] * (j - 3 * i) / j;
}
}
int tt;
cin >> tt;
for (int qq = 1; qq <= tt; qq++) {
string s;
cin >> s;
map<string, int> mp;
for (int i = 0; i < n; i++) {
auto x = s.substr(i * 2, 2);
mp[x]++;
}
int beg = 0;
for (auto &[_, v] : mp) {
beg += (v % 2);
}
cout << "Case #" << qq << ": " << dp[beg][123] << '\n';
}
return 0;
}
J - Serval and Essay
有一张 n 个点 m 条边的无重边无自环的有向图，初始时可以选择一个点染黑，其余点均为白点 若某个点所有前驱点均为黑点，则该点可以被染黑，最大化图中黑点数量。
直觉是：找入度为 1 的点，把他的前驱染黑，那么这个点自然黑了，在此基础上一直迭代下去，会有一个集合被染黑。
也就是说每个集合有一个“导火索”就是入度为 1 的那个点。
考虑暴力两两合并集合：如果集合 A 有 k 条边的入点都是集合 B 中的一个点的话，这 k 条边实际上可以缩成一条边，因为他们的出点在 A 里 ，全部都是黑的。所以就可以合并 A 和 B 了。
这个做法很暴力，但是启发式合并跑得快，利用 set 来维护每个集合的出边。多条集合间的，出点不同入点相同的边只会被访问一次。先合并集合间边少的那个，访问边的复杂度是 log 的。set 自带一个 log，所以复杂度是 Θ(mlog2m)。
答案自然是最大的那个集合。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
class DSU {
public:
vector<int> p;
int n;
DSU(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int find(int x) {
return (x == p[x] ? x : (p[x] = find(p[x])));
}
inline bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
for (int qq = 1; qq <= tt; qq++) {
int n;
cin >> n;
vector<set<int>> nv(n), pv(n);
for (int i = 0; i < n; i++) {
int k;
cin >> k;
while (k--) {
int v;
cin >> v;
v--;
pv[i].insert(v);
nv[v].insert(i);
}
}
DSU d(n);
vector<int> sz(n, 1);
function<void(int, int)> Dfs = [&](int x, int y) {
x = d.find(x), y = d.find(y);
if (x == y) {
return;
}
if (nv[x].size() < nv[y].size()) {
swap(x, y);
}
sz[x] += sz[y];
assert(sz[x] >= sz[y]);
d.unite(y, x);
vector<pair<int, int>> block;
for (auto &to : nv[y]) {
nv[x].insert(to);
pv[to].erase(y);
pv[to].insert(x);
if (pv[to].size() == 1) {
block.emplace_back(to, x);
}
}
for (auto &[xx, yy] : block) {
Dfs(xx, yy);
}
};
for (int i = 0; i < n; i++) {
if (pv[i].size() == 1) {
Dfs(i, *pv[i].begin());
}
}
int ans = *max_element(sz.begin(), sz.end());
cout << "Case #" << qq << ": " << ans << '\n';
}
return 0;
}
