E - Roaming
题目链接： E - Roaming
题意：
有 $n$ 个房子，每个房子一开始有 $1$ 个人，每次操作可以将一个人移动到另一个房间，问操作 $k(k\geq 2)$ 次后，有多少种可能的情况。
解题思路：
可以从空房间的数量入手，最多有 $min(n-1,k)$ 个空房间，最少没有，因为总是可以形成一个长度为 $k$ 的环使得有一种方案最终和初始状态一样。
枚举空房间的数量 $i$ ，那么有人的房间就是 $n-i$ ，这时候就用隔板法，在 $n-1$ 个位置插入 $n-i-1$ 个隔板，即 $C_{n-i-1}^{n-1}$ ，这是有人的房间分配方案，再乘以空房间的分配方案，即 $C_{n}^{i}$ 。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010, mod = 1e9 + 7;
int n, k;
int fact[N], infact[N];
void init(int n)
{
fact[0] = fact[1] = 1;
infact[0] = infact[1] = 1;
for (int i = 2; i <= n; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[mod % i] * (mod - mod / i) % mod;
}
for (int i = 2; i <= n; i ++ ) infact[i] = (LL)infact[i] * infact[i - 1] % mod;
}
int C(int a, int b)
{
if (a < b) return 0;
else return (LL)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
init(N - 1);
int n, k;
cin >> n >> k;
int res = 0;
for (int i = 0; i <= min(n - 1, k); i ++ )
{
int s = C(n - 1, n - i - 1);
s = (LL)s * C(n, i) % mod;
res = (res + s) % mod;
}
cout << res << '\n';
return 0;
}
B. Present
题目链接： B. Present
题意：
给定 $n$ 个数，求所有数对的和的异或结果。
解题思路：
直接做的复杂度是 $O(n^2)$ ，肯定不行。求位运算的结果通常来说都是按位处理，那么就试试看。
假如当前在处理第 $bit$ 位，先将所有数高于 $bit$ 位的清楚掉，即对 $2^{bit+1}$ 取模。这时，两个数相加可以使得 $bit$ 位为 $1$ 的，这两个数的和一定是在 $[2^{bit},2^{bit+1}-1]∪[2^{bit+1}+2^{bit},2^{bit+2}-2]$ 这个范围内，因此对于每个数，就可以用二分找到与它的和落在这两个范围内的数都多少个，最后要记得除以 $2$ ，因为结果中每个数都重复算了一遍，看数对个数是否为奇数，如果为奇数，那么说明可以令第 $bit$ 位为 $1$ 。
代码如下：
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &u : a) cin >> u;
int res = 0;
for (int bit = 0; bit < 25; bit ++ )
{
vector<int> b(a);
for (auto &u : b) u %= (1 << (bit + 1));
sort(b.begin(), b.end());
int cnt = 0;
for (int i = 0; i < n; i ++ )
{
// [2^bit, 2^(bit+1)-1]
{
int L = (1 << bit);
int R = (1 << (bit + 1)) - 1;
int l = lower_bound(b.begin(), b.end(), L - b[i]) - b.begin();
int r = upper_bound(b.begin(), b.end(), R - b[i]) - b.begin() - 1;
cnt += (r - l + 1);
// 要将本身减去
cnt -= (i >= l && i <= r);
}
// [2^bit+2^(bit+1), 2^(bit+2)-2]
{
int L = (1 << bit) + (1 << (bit + 1));
int R = (1 << (bit + 2)) - 2;
int l = lower_bound(b.begin(), b.end(), L - b[i]) - b.begin();
int r = upper_bound(b.begin(), b.end(), R - b[i]) - b.begin() - 1;
cnt += (r - l + 1);
// 要将本身减去
cnt -= (i >= l && i <= r);
}
}
cnt /= 2;
if (cnt & 1) res |= (1 << bit);
}
cout << res << '\n';
return 0;
}
D. 3-Coloring
题目链接： D. 3-Coloring
题意：
交互题，相当于和电脑玩游戏，一共有三种颜色，每次玩家操作前电脑给出一种颜色，在这一次操作不能使用这种颜色，填完整个 $n\times n$ 矩阵，使得没有相邻的格子是同色的。
解题思路：
构造就没什么好说的了，按照对角线分组，相邻的两条对角线分别分在不同组，开始时每组填一种颜色，最多只能允许其中一组包含两种颜色。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
#define F first
#define S second
using namespace std;
typedef pair<int, int> PII;
int main()
{
int n;
cin >> n;
vector<PII> g[2];
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[(i + j) & 1].emplace_back(i, j);
auto answer = [&](int b, int x, int y)
{
cout << b + 1 << ' ' << x + 1 << ' ' << y + 1 << '\n';
};
auto ask = [&]() -> int
{
int x;
cin >> x;
return x - 1;
};
for (int i = 0; i < n * n; i ++ )
{
int c = ask();
int b = -1, t = -1;
if (c == 0)
{
if (g[1].size()) t = 1, b = 1;
else t = 0, b = 2;
}
else if (c == 1)
{
if (g[0].size()) t = 0, b = 0;
else t = 1, b = 2;
}
else if (c == 2)
{
if (g[0].size()) t = 0, b = 0;
else t = 1, b = 1;
}
answer(b, g[t].back().F, g[t].back().S);
g[t].pop_back();
}
return 0;
}
E. Travelling Salesman Problem
题目链接： E. Travelling Salesman Problem
题意：
有 $n$ 个地点，要求从 $1$ 出发，恰好走过所有点一次，最终回到 $1$ ，从 $i$ 点走到 $j$ 点的花费为 $max(c[i],a[j]-a[i])$ ，求最小花费。
解题思路：
其实我觉得这题是最难的一道题。
首先可以将花费改写成 $c[i]+max(0,a[j]-(a[i]+c[i])$ ，然后按照题意，每个点都出发恰好一次，每个点都到达恰好一次，因此每个 $c_i$ 都一定在结果中，对于每一个点 $j$ ，都找到它出发的点 $i$ ，使得所有 $max(0,a[j]-(a[i]+c[i]))$ 的和最小。
首先将 $a_i$ 按从小到大排序，可以发现从一个点走到前面的所有点都是 无代价 的，另外假如某个点的 $a_i+c_i$ 足够大，它走到它后面的某些点，也是 无代价 的。
做法是维护 $a+c$ 的最大值，对于每个点，假设它是由它前面的 $a+c$ 最大的点出发到达的，也就是说，从第二个点开始，统计 $max(0,a_i-mx)$ 的和。
从上面可以知道，每个点只能出发一次，为什么这样做是对的呢？假设有一种情况， $j,k(j<k)$ 点的前面 $a+c$ 最大值的点都是 $i$ 点，按照上面的分析，最优情况下，应该都从 $i$ 出发到 $j$ 和 $k$ 。但其实可以发现，因为 $a_i+c_i \geq a_j+c_j$ ，因此从 $i$ 走到 $j$ 其实是无代价的，因此上面的计算方法并不会影响最终结果。
代码如下：
#include <vector>
#include <cassert>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 2e9;
int main()
{
int n;
cin >> n;
vector<long long> a(n), c(n);
for (int i = 0; i < n; i ++ ) cin >> a[i] >> c[i];
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int x, int y)
{
return a[x] < a[y];
});
long long res = accumulate(c.begin(), c.end(), 0LL), mx = -INF;
for (int j = 0; j < n; j ++ )
{
if (j) res += max(0LL, a[i] - mx);
mx = max(mx, a[i] + c[i]);
}
cout << res << '\n';
return 0;
}
D. Trash Problem
题目链接： D. Trash Problem
题意：
维护若干个点，选择不多于两段线段覆盖所有点，求线段长度的和的最小值，有若干次操作，可以加入一个点，或取出一个点。
解题思路：
这题就比较简单了，直接用 set 维护所有点，以及所有线段即可。
输出答案时，如果没有线段，则输出 $0$ ，否则输出所有线段之和减去最大的线段。
加入一个点时，加入集合后，看它的左右两边是否有点，如果有，则加入与新点形成的线段，如果两边都有点，还要清除原有的两边的点形成的线段。
清除一个点时，看它左右两边是否有点，如果有，则清除与这个点形成的线段，如果两边都有点，则加入两边的点形成的新线段，最后将点从集合中删除。
代码如下：
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
set<int> S;
for (auto &u : a)
{
cin >> u;
S.insert(u);
}
sort(a.begin(), a.end());
multiset<int> seg;
int sum = 0;
// 加入初始线段
for (int i = 1; i < n; i ++ )
{
sum += a[i] - a[i - 1];
seg.insert(a[i] - a[i - 1]);
}
while (q -- )
{
int t, x;
cin >> t >> x;
if ((int)seg.size() == 0) cout << "0\n";
else cout << sum - *prev(seg.end()) << '\n';
if (t == 0)
{
auto it = S.find(x);
auto lit = prev(it), rit = next(it);
if (it != S.begin()) seg.erase(seg.find(*it - *lit)), sum -= (*it - *lit);
if (rit != S.end()) seg.erase(seg.find(*rit - *it)), sum -= (*rit - *it);
if (it != S.begin() && rit != S.end()) seg.insert(*rit - *lit), sum += (*rit - *lit);
S.erase(it);
}
else
{
S.insert(x);
auto it = S.find(x);
auto lit = prev(it), rit = next(it);
if (it != S.begin()) seg.insert(*it - *lit), sum += (*it - *lit);
if (rit != S.end()) seg.insert(*rit - *it), sum += (*rit - *it);
if (it != S.begin() && rit != S.end()) seg.erase(seg.find(*rit - *lit)), sum -= (*rit - *lit);
}
}
if ((int)seg.size() == 0) cout << "0\n";
else cout << sum - *prev(seg.end()) << '\n';
return 0;
}
C. World of Darkraft: Battle for Azathoth
题目链接： C. World of Darkraft: Battle for Azathoth
题意：
给定 $n$ 把武器， $m$ 件防御装， $q$ 个敌人，每把武器的攻击力为 $a_i$ ，花费为 $ca_i$ ，每件防御装的防御力为 $b_i$ ，花费为 $cb_i$ ，每个敌人的防御力、攻击力、奖励分别为 $x_i,y_i,z_i$ ，必须且只能选择一把武器以及一件防御装，当武器攻击力大于敌人防御力，且防御力大于敌人攻击力时，才能击败这个敌人并获得奖励，求可以获得的最大利润，即奖励之和减去武器和防御装的花费。
解题思路：
比较常规的想法可能是往贪心或者 DP 去想，但利润受到两个因素的影响，很难想到一个正确的思路。
这是一个二维偏序问题，很多时候都是用树状数组或者线段树来处理，其实遇到过这种题，就会变得比较简单了。看一下数据范围， $a$ 和 $b$ 都在 $10^6$ 以内，这就刚刚好了。
首先开两个桶，分别维护攻击力为 $i$ 的武器，花费最少为多少，以及防御力为 $i$ 的防御装，利润最大为多少。将怪兽的防御力从小到大排序
开一个线段树，线段树的每个点的编号表示防御装的防御力，初始化时，对于防御力为 $b$ ，最大利润为 $－cb$ ，那么就在 $b$ 号点，赋值为 $-cb$ ，那么其它没有防御装的点，就赋值为负无穷。
然后从前往后用双指针来遍历所有武器和敌人，对于当前的武器，找到所有可以击败的敌人，并将敌人的奖励加到线段树中，假如当前敌人的攻击力和奖励分别为 $y,z$ ，那么就在线段树 $[y+1,N-1]$ 的范围内加 $z$ ，表示防御力大于 $y$ 的所有防御装，都可以满足击败敌人的条件，又因为在遍历时保证了所有的敌人都可以被当前武器击败，因此当前遍历到的所有怪兽都是有可能被击败获得奖励的，这时用线段树中的最大值更新答案即可。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
const LL INF = 4e18;
int n, m, p;
LL a[N], b[N];
struct Mon
{
LL x, y, z;
bool operator<(const Mon &t) const
{
return x < t.x;
}
} mon[N];
struct Node
{
int l, r;
LL val, mx, lazy;
} tr[N << 2];
#define lson (u << 1)
#define rson (u << 1 | 1)
void pushup(int u)
{
tr[u].val = tr[lson].val + tr[rson].val;
tr[u].mx = max(tr[lson].mx, tr[rson].mx);
}
void pushdown(int u)
{
tr[lson].val += (tr[lson].r - tr[lson].l + 1) * tr[u].lazy;
tr[rson].val += (tr[rson].r - tr[rson].l + 1) * tr[u].lazy;
tr[lson].mx += tr[u].lazy;
tr[rson].mx += tr[u].lazy;
tr[lson].lazy += tr[u].lazy;
tr[rson].lazy += tr[u].lazy;
tr[u].lazy = 0;
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) tr[u].val = tr[u].mx = b[r], tr[u].lazy = 0;
else
{
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, LL v)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].val += (tr[u].r - tr[u].l + 1) * v;
tr[u].mx += v;
tr[u].lazy += v;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(lson, l, r, v);
if (r > mid) modify(rson, l, r, v);
pushup(u);
}
}
LL query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].mx;
else
{
pushdown(u);
LL res = -INF;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res = max(res, query(lson, l, r));
if (r > mid) res = max(res, query(rson, l, r));
return res;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> p;
for (int i = 0; i < N; i ++ ) a[i] = INF, b[i] = -INF;
for (int i = 1; i <= n; i ++ )
{
LL x, y;
cin >> x >> y;
a[x] = min(a[x], y);
}
for (int i = 1; i <= m; i ++ )
{
LL x, y;
cin >> x >> y;
b[x] = max(b[x], -y);
}
for (int i = 1; i <= p; i ++ )
{
LL x, y, z;
cin >> x >> y >> z;
mon[i] = {x, y, z};
}
sort(mon + 1, mon + p + 1);
build(1, 1, N - 1);
LL res = -INF;
for (int i = 1, j = 1; i < N; i ++ )
{
while (j <= p && mon[j].x < i)
{
modify(1, mon[j].y + 1, N - 1, mon[j].z);
j ++ ;
}
res = max(res, query(1, 1, N - 1) - a[i]);
}
cout << res << '\n';
return 0;
}
D. Discrete Centrifugal Jumps
题目链接： D. Discrete Centrifugal Jumps
题意：
有 $n$ 个点，当前在 $1$ 点，要跳到 $n$ 号点，当以下条件满足任意一个，可以从 $i$ 跳到 $j$ ：
- $i+1=j$
- $max(h_{i+1},\dots,h_{j-1})<min(h_i,h_j)$
- $max(h_i,h_j)<min(h_{i+1},\dots,h_{j-1})$
问最少需要跳多少次。
解题思路：
维护两个单调栈，用单调递增栈举例，单调递减栈就是反过来。
对于某个点 $i$ ，它可以从起点一步步跳到，也可以从 $i-1$ 跳到，那么就是 $min(f[i-1],i-1)$ 。
维护栈，如果栈不空，且 $h[i]>h[stk[top]]$ ，那么 $i$ 点其实也可以从 $stk[top]$ 跳到，因此就用 $f[stk[top]]+1$ 来更新答案。弹出栈中所有大于或等于 $h[i]$ 的元素，这里要注意，最后如果栈还有元素，而且前一个弹出的元素不等于 $h[i]$ ，那么此时的 $stk[top]$ 也可以跳到 $i$ 。
最后 $f[n]$ 就是答案。
代码如下：
#include <iostream>
using namespace std;
const int N = 300010;
int n;
int h[N];
int f[N];
int top1, top2;
int stk1[N], stk2[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> h[i];
stk1[ ++ top1] = 1;
stk2[ ++ top2] = 1;
f[1] = 0;
for (int i = 2; i <= n; i ++ )
{
f[i] = min(f[i - 1] + 1, i - 1);
int last = -1;
while (top1 && h[stk1[top1]] >= h[i])
{
last = stk1[top1];
f[i] = min(f[i], f[stk1[top1]] + 1);
top1 -- ;
}
if (top1 && last != -1 && h[i] != h[last]) f[i] = min(f[i], f[stk1[top1]] + 1);
stk1[ ++ top1] = i;
last = -1;
while (top2 && h[stk2[top2]] <= h[i])
{
last = stk2[top2];
f[i] = min(f[i], f[stk2[top2]] + 1);
top2 -- ;
}
if (top2 && last != -1 && h[i] != h[last]) f[i] = min(f[i], f[stk2[top2]] + 1);
stk2[ ++ top2] = i;
}
cout << f[n] << '\n';
return 0;
}
A. Matrix
题目链接： A. Matrix
题意：
给定一个数 $a$ ，以及一个长度为 $n$ 的序列 $s$ ，序列的数都是一位自然数，构成一个 $n\times n$ 矩阵 $b$ ，其中 $b_{ij}$ 为序列中第 $i$ 个数和第 $j$ 个数相乘的结果，问矩阵里有多少个子矩阵满足子矩阵中元素之和为 $a$ 。
解题思路：
首先要理解这个矩阵的形态，可以发现对于第 $i$ 行，其实就是原始序列的 $s[i]$ 倍，对于某个子矩阵，假如宽是 $[j,i]$ ，高是 $[k,l]$ ，它的和其实就是 $(s[j]+\dots s[i])\times (s[k]+\dots s[l])$ 。
分两种情况讨论：
- $a$ 为 $0$ ：那么就暴力枚举所有子段和，若某个子段和为 $0$ ，以它为子矩阵的宽，长任意，这样的子矩阵所有元素的和一定都是 $0$ ，因此给答案加上 $\frac{(n+1)\times n}{2} $ 。
- $a$ 不为 $0$ ：先统计所有子段和的个数，然后枚举所有子段和，如果 $a$ 可以被子段和 $d$ 整除，那么就给答案加上子段和为 $\frac{a}{d}$ 的个数即可。
注意事项：
这题坑有点多，很容易 RE ，尤其是要注意 $a$ 为 $0$ ，以及除 $0$ 的错误。
代码如下：
#include <map>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
int x;
string s;
cin >> x >> s;
int n = (int)s.size();
vector<int> a(n);
for (int i = 0; i < n; i ++ ) a[i] = s[i] - '0';
vector<int> sum(n + 1);
for (int i = 0; i < n; i ++ ) sum[i + 1] = sum[i] + a[i];
map<int, int> mp;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
mp[sum[i] - sum[j]] ++ ;
long long res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < i; j ++ )
{
int d = sum[i] - sum[j];
if (x)
{
if (d && x % d == 0) res += mp[x / d];
}
else
{
if (d == 0) res += (long long)(n + 1) * n / 2;
else res += mp[0];
}
}
cout << res << '\n';
return 0;
}
D. Let’s Play the Words?
题目链接： D. Let’s Play the Words?
题意：
给定若干 $01$ 串，它们两两不同，可以对其中一些串进行翻转操作，要求操作完以后所有串也都是两两不同的，判断是否可以将所有串首尾相连，形成一条链。
解题思路：
有一种情况是一定不能构造而成的，就是同时存在头尾都是 $0$ ，头尾都是 $1$ ，而且没有头尾不同的串，这时输出 $-1$ 。
否则首先统计头尾不同的串的个数，可以发现只要它们的个数绝对值不大于 $1$ ，就能满足题目要求。
假如 $0\dots 1$ 这样的串比 $1\dots 0$ 这样的串多，那么就遍历 $0\dots 1$ 这样的串，对于某个串 $s$ ，如果翻转之后不会和已经存在的串重复，那么就将它翻转，直到满足要求。
因为给定的字符串是两两不同的，设数量较少的那个集合大小为 $size_1$ ，另一个为 $size_2$ ，那么较少的集合最多只能限制 $size_1$ 个字符串，只需要从剩下的 $size_2-size_1$ 个串中选择即可，一定可以构造出答案。
代码如下：
#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T -- )
{
int n;
cin >> n;
set<string> S01, S10;
map<string, int> mp01, mp10;
int cnt00 = 0, cnt11 = 0;
for (int i = 0; i < n; i ++ )
{
string s;
cin >> s;
char st = s[0], ed = s.back();
if (st == '0' && ed == '1') S01.insert(s), mp01[s] = i;
else if (st == '1' && ed == '0') S10.insert(s), mp10[s] = i;
else if (st == '0') cnt00 ++ ;
else if (st == '1') cnt11 ++ ;
}
if (cnt00 && cnt11 && !S01.size() && !S10.size())
{
cout << "-1\n";
continue;
}
vector<int> res;
if ((int)S01.size() < S10.size()) S01.swap(S10), mp01.swap(mp10);
while ((int)S01.size() - S10.size() > 1)
{
string s = *S01.begin();
string t = s;
reverse(t.begin(), t.end());
if (S10.count(t))
{
S01.erase(s);
S10.erase(t);
}
else
{
res.emplace_back(mp01[s]);
S01.erase(s);
S10.insert(t);
}
}
cout << (int)res.size() << '\n';
for (auto &u : res) cout << u + 1 << ' ';
cout << '\n';
}
return 0;
}
D. Minimax Problem
题目链接： D. Minimax Problem
题意：
给定若干个序列，从中取出两个序列，对这两个序列的每一位进行比较，取出每一位的较大值，形成一个新的序列，记录这个序列的最小值，求这个新序列的最小值最大可以取多少。
解题思路：
这题有点像之前提到过的“屏蔽法”，而且看一下每个序列的规模，小得就很诡异，规模规模较小的题目一般可以考虑全排列、暴搜、位运算等等。
思路是二分最小值的最大值 $x$ ，然后处理所有序列，用一个二进制数表示每个序列，如果某个数大于或等于 $x$ ，则设为 $1$ ，否则设为 $0$ ，记录下每个二进制数对应的序列编号，枚举二进制数对，如果两个二进制数相或得到全 $1$ ，等价于这两个序列的每个位的最小值都大于等于 $x$ ，也就是形成的新序列的最小值大于等于 $x$ 。
注意事项：
这里有个坑点，就是二分的时候，最终答案不一定是上一次执行检查的 $x$ ，因此得到最终答案后，还要执行一次检查，获得两个序列的编号。
代码如下：
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> a[i][j];
pair<int, int> res{-1, -1};
auto check = [&](int x) -> bool
{
vector<int> idx(1 << m, -1);
for (int i = 0; i < n; i ++ )
{
int mask = 0;
for (int j = 0; j < m; j ++ )
if (a[i][j] >= x)
mask |= (1 << j);
idx[mask] = i;
}
for (int i = 0; i < 1 << m; i ++ )
for (int j = 0; j < 1 << m; j ++ )
if (idx[i] != -1 && idx[j] != -1 && (i | j) == (1 << m) - 1)
{
res = make_pair(idx[i], idx[j]);
return true;
}
res = {-1, -1};
return false;
};
int l = 0, r = 1e9 + 10;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
// 记得还要 check() 一次
check(r);
cout << res.first + 1 << ' ' << res.second + 1 << '\n';
return 0;
}
D. Dima and Trap Graph
题目链接： D. Dima and Trap Graph
题意：
有 $n$ 个点，每个点有一个权值范围 $[l,r]$ ，要从 $1$ 走到 $n$ ，初始时可以选择一个 $x$ ， $x$ 必须在路径中经过的所有点的权值范围的交集内，对于每条路径中， $x$ 可能有多种取法，求在所有路径中， $x$ 的取法最多有多少种。
解题思路：
这题很巧妙，首先对于任意一条从 $1$ 走到 $n$ 的路径，它的选法是路径上所有点的权值范围的交集，也就是最大的 $l$ 和最小的 $r$ 的交集。
可以对于每个左端点，规定它为某一条路径上对应 $x$ 的最终选法范围的左端点。从大到小选择所有的右端点，这其实是一个给点加边的过程，若加上一条边后， $1$ 和 $n$ 连通，那么就用此时维护的选法个数去更新答案。连通性则用并查集来维护。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 3010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge
{
int a, b, l, r;
bool operator<(const Edge &t) const
{
return r > t.r;
}
} e[M];
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++ )
{
int a, b, l, r;
cin >> a >> b >> l >> r;
e[i] = {a, b, l, r};
}
sort(e, e + m);
int res = 0;
for (int i = 0; i < m; i ++ )
{
int L = e[i].l, R = INF;
for (int i = 0; i <= n; i ++ ) p[i] = i;
for (int j = 0; j < m; j ++ )
{
int l = e[j].l, r = e[j].r;
// 规定 L 为最终路径上最大左端点
// 不考虑比 L 更大的边
if (l > L) continue;
int pa = find(e[j].a), pb = find(e[j].b);
R = min(R, r);
p[pa] = pb;
if (find(1) == find(n)) res = max(res, R - L + 1);
}
}
if (res) cout << res << '\n';
else cout << "Nice work, Dima!\n";
return 0;
}
