2022_牛客多校训练 round1 A, C, D, G, I
A. Villages: Landlines
题目描述：数轴上有 $n$ 个点，给出 $n$ 个点的坐标 $x_i$ 和控制范围 $r_i$，可以在数轴上放置电线以延长点的控制范围，求出电线的最小长度，使所有点相连。
思路：排序后模拟即可。
#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> a[200010];
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; ++i) {
int x, y;
cin >> x >> y;
a[i].first = x - y, a[i].second = x + y;
}
sort(a + 1, a + 1 + n);
int maxn = a[1].second;
long long res = 0;
for(int i = 2; i <= n; ++i) {
if(a[i].first > maxn) {
res += a[i].first - maxn;
}
if(a[i].second > maxn) maxn = a[i].second;
}
cout << res << endl;
return 0;
}
C. Grab the Seat!
题目描述：给定一二维平面，屏幕是 $(0,1) \sim (0,m)$ 的一条线段，有 $n$ 行 $m$ 列的座位在屏幕前面，是坐标范围为 $1 \leq x \leq n, 1 \leq y \leq m$ 的整点。有 $k$ 个座位已经有人，求出到屏幕的视线不被任何人挡住的座位数量。$q$ 个询问，每次修改一个人的坐标后求出答案。
思路：首先，对于每一排而言，只需要考虑第一个坐人的位置，因为第一个坐人的位置与屏幕构成的折线的范围一定包含这一排后面的其他点与屏幕构成的范围。
其次，对于 $y=1, y=m$ 两种情况，这两排坐的所有人只会影响到这一排后面的人，不会影响到其他排的人，可以单独进行考虑。除此之外的其他情况中，假设一个人的坐标为 $(x,y)$，那么他将挡住直线 $(0,1) \sim (x,y)$ 和直线 $(0,m) \sim (x,y)$ 构成的右半平面，有 $k$ 个人的情况下，那么将会构成由 $2k$ 条线段组成的折线图，可以将这些线段分为斜率为正（从 $(0,1)$ 出发）和斜率为负（从 $(0,m)$ 出发）两类。
分成两类之后，根据线段的两个端点，分别更新到给定的点的斜率和斜率对应的横坐标即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k, q;
pair<int, int> a[200010];
int neary[200010];
int res[200010];
signed main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m >> k >> q;
for (int i = 1; i <= k; ++i) {
cin >> a[i].first >> a[i].second;
}
for (int _ = 1; _ <= q; ++_) {
int id, x, y;
cin >> id >> x >> y;
a[id] = {x, y};
for (int i = 1; i <= m; ++i) {
neary[i] = n + 1;
}
for (int i = 1; i <= k; ++i) {
auto [p, q] = a[i];
neary[q] = min(neary[q], p);
}
int dx = 1, dy = 0;
for (int i = 1; i <= m; ++i) {
if (i == 1) {
res[i] = neary[i] - 1;
} else {
int p = neary[i], q = i;
if (dx * (q - 1) >= dy * p) {
dx = p, dy = q - 1;
}
res[i] = ((i - 1) * dx + dy - 1) / dy - 1;
}
}
dx = 1, dy = m;
for (int i = m; i >= 1; --i) {
if (i == m) {
res[i] = min(res[i], neary[i] - 1);
} else {
int p = neary[i], q = i;
if (dx * (q - m) <= dy * p) {
dx = p, dy = q - m;
}
res[i] = min(res[i], ((i - m) * dx + dy + 1) / dy - 1);
}
}
long long ans = 0;
for (int i = 1; i <= m; ++i) {
ans += res[i];
}
cout << ans << '\n';
}
return 0;
}
D. Mocha and Railgun
题目描述：给定一个圆和圆内一点 $P$，以 $P$ 为中点，以任意角度向圆上发射一长度为 $2d$ 的电磁炮，该电磁炮两端也一定位于圆内，求发射的电磁炮能覆盖的圆的弧长最大值。
思路：
见下图。
由此，问题等价于将 $P$ 点对坐标轴进行投影后找最大值。不难发现 $P$ 尽可能远离原点 $O$ 时，答案最大。
G. Lexicographical Maximum
题目描述：给定 $n$，将 $1, 2, \dots, n$ 视为字符串，求其中字典序最大的字符串。
思路：直接特判即可。
I. Chiitoitsu
题目描述：开始时手中有 $13$ 张麻将牌，相同的牌不超过 $2$ 张，每次从牌堆中抽一打一（若抽一后得到的 $14$ 张牌组成七对则不打且游戏结束）。给定初始手牌，求最优策略下游戏结束的抽牌次数期望。
思路：由于题目限制开始游戏时相同的牌不超过 $2$ 张，因此只会有成对和单牌两种情况。成对的牌显然不该再打出，每次抽牌之后若组成一对则打出另外一张单牌，若不能组成一对则直接将这张牌打出就是最优的策略。
直接进行 $dp$，设 $f(a,b)$ 是当前已经有 $a$ 对，还剩 $b$ 张牌的状态的期望抽牌次数，可以直接预处理出所有的情况，然后 $O(1)$ 回答每个询问。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int dp[8][130], res[8];
int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1)
res = (ll)res * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return res;
}
void work() {
for (int cnt = 0; cnt < 7; ++cnt) {
memset(dp, 0, sizeof dp);
dp[cnt][123] = 1;
for (int i = cnt; i <= 7; ++i) {
for (int j = 123; j >= 1; --j) {
if (i != 7 && i != 0) {
dp[i][j - 1] = (((ll)(13 - 2 * (i - 1)) * 3 * dp[i - 1][j] % mod) + ((ll)(j - (13 - 2 * i) * 3) * dp[i][j]) % mod) % mod;
} else if (i == 7) {
dp[i][j - 1] = (ll)(13 - 2 * (i - 1)) * 3 * dp[i - 1][j] % mod;
} else {
dp[i][j - 1] = (ll)(j - (13 - 2 * i) * 3) * dp[i][j] % mod;
}
dp[i][j - 1] = (ll)dp[i][j - 1] * qmi(j, mod - 2) % mod;
}
}
ll ans = 0;
for (int i = 123; i >= 1; --i) {
ans = (ans + (ll)dp[7][i] * (123 - i)) % mod;
}
res[cnt] = ans;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
work();
int T;
cin >> T;
for (int i = 1; i <= T; ++i) {
string s;
cin >> s;
map<string, int> mp;
int cnt = 0;
for (int i = 0; i < s.length(); i += 2)
{
string tmp = s.substr(i, 2);
if (mp[tmp])
cnt++;
mp[tmp]++;
}
cout << "Case #" << i << ": " << res[cnt] << '\n';
}
return 0;
}
2022_牛客多校训练 round2 G, I, J, K
G. Link with Monotonic Subsequence
题目描述：构造一个 $1\sim n$ 的排列，使得这个排列中最长上升子序列的长度和最长下降子序列的长度的最大值最小。
思路：考虑 $n=7$ 的原排列：$1, 2, 3, 4, 5, 6, 7$，我们可以考虑令 $len$ 为一个连续有序区间的长度，若 $len=3$，一个显然的排列是：$3, 2, 1, 6, 5, 4, 7$，其中，$[3, 2, 1]$ 和 $[6, 5, 4]$ 作为两个有序序列，它们的内部是严格下降的。
若我们从每个序列中选出一个数字，那么由这个序列的构造方法，我们会发现这个选出的数字会是严格上升的，如从 $[3, 2, 1]$ 中选择 $3$，$[6, 5, 4]$ 中选择 $5$，最后选择 $7$，这样的构造显然是上升的。因此，最长上升子序列的长度为：$\lceil \frac{n}{len} \rceil$。由前面的分析，最长下降子序列长度为 $len$，不难发现当 $len = \lceil \frac{n}{len} \rceil$ 时就是我们要求的长度(Dilworth’s theorem)。对边界情况特判后按照上述方法构造即可。
I. let fat tension
题目描述：给定 $n$ 个 $k$ 维向量 $X_{i}$，$n$ 个 $d$ 维向量 $Y_i$，有下列公式：
\[\begin{aligned} le(i,j) &= \frac{X_i \cdot X_j}{\mid X_i \mid \cdot \mid X_j \mid} \\ res_i &= \sum_{j=1}^n le(i,j) \cdot Y_j \end{aligned}\]求 $res_i(1 \leq i \leq n)$。
思路：暴力计算显然超时，由余弦相似度的性质（也可以根据 $le(i,j)$ 的定义直接推出），$res_i$ 构成的答案矩阵等价于：
\[\begin{aligned} res &= X_{norm} \cdot X^{T}_{norm} \cdot Y_j \end{aligned}\]通过矩阵乘法的结合律，先计算后两项，再计算 $X_{norm}$ 与后两项的乘积，这样的复杂度为 $O(nkd + knd)$。
J. Link with Arithmetic Progression
题目描述：给定一个整数序列 $a_1, a_2, \dots, a_n$, $a_i$ 被改变为 $a_i^{\prime}$ 的代价为 $(a_i - a_i^{\prime})^2$，最小化改变每个数的代价之和，使得这个序列变为等差数列（改变后的序列不需要保持整数）。
思路：此即为最小二乘法，直接套用最小二乘法的计算公式即可，此外此题也可三分代价。
K. Link with Bracket Sequence I
题目描述：给定一个长度为 $n$ 的括号序列 $A$， 它是一个长为 $m$ 的括号序列的子序列。求这个长为 $m$ 的括号序列 $B$ 的所有合法方案数量。
思路：一眼dp。
令 $f[i][j][k]$ 表示枚举到 $A$ 的第 $i$ 位，$B$ 的第 $j$ 位，还剩下 $k$ 个括号没有匹配的方案的数量，直接讨论 $A_i$ 和 $B_j$ 的括号情况即可。