A. 困难数学题
题意
求 n xor n xor n xor n
大概思路
求 n xor n xor n xor n
参考代码
求 n xor n xor n xor n
void solve(){
int n;
std::cin >> n;
std::cout << (n ^ n ^ n ^ n);
}
其实当时想到了可以直接输出0，但是为了保险一点就按照题目说的模拟了
B. 构造序列
题意
给你 nn 个正数和 mm 个负数，请你使用这些数字，构造一个序列。
序列需要满足：正数不能和正数相邻，负数不能和负数相邻。
那么，最多能构造多长的序列？
大概思路
贪心，选择较少的，乘2，然后判断较多的能不能补一个
参考代码
void solve(){
int n, m;
std::cin >> n >> m;
std::cout << 2 * std::min(n, m) + (n != m);
}
C. 连点成线
题意
小红有一个 n×n 大小的格子棋盘，我们使用 (i,j) 表示棋盘中从上往下数第 i 行和从左往右数第 j 列的单元格。棋盘上有 m 个棋子，第 i 个棋子的坐标是 (xi,yi) 。
对于一对棋子 i 和 j ，如果满足 xi=xj 或者 yi=yj ，则两个棋子之间可以连线。
小红有点无聊，于是她把能连的线都连上了。现在，她想知道，最长的那条线，长度是多少。
特别地，如果连线数量为 0 ，则输出 0 。
大概思路
暴力map，统计每行最左，每行最右，每列最上面，每列最下面的，然后动态更新答案即可
参考代码
void solve(){
int n, m;
std::cin >> n >> m;
std::map<int, int> L, R, U, D;
int ans = 0;
while (m--) {
int x, y;
std::cin >> x >> y;
if (L.count(y)) {
L[y] = std::min(L[y], x);
R[y] = std::max(R[y], x);
} else {
L[y] = R[y] = x;
}
if (U.count(x)) {
D[x] = std::min(D[x], y);
U[x] = std::max(U[x], y);
} else {
D[x] = U[x] = y;
}
ans = std::max(ans, R[y] - L[y]);
ans = std::max(ans, U[x] - D[x]);
}
std::cout << ans;
}
D. 我们N个真是太厉害了
题意
给你 n 个数，问你对于1 到 n任意一个数i，是否都存在一个子集和为i。
大概思路
sort一下，从小到大一个个更新MEX，如果当前的数a[i]大于MEX，那么没法再更新了（因为MEX覆盖不到），直接输出MEX；否则更新MEX为MEX + a[i]。
参考代码
void solve(){
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto &i : a) std::cin >> i;
std::sort(a.begin(), a.end());
int MEX = 1;
for (auto &i : a) {
if (i > MEX) {
std::cout << MEX << "\n";
return;
} else {
MEX = std::min(n + 1, MEX + i);
}
if (MEX == n + 1) {
std::cout << "Cool!\n";
return;
}
}
std::cout << MEX << "\n";
}
E. 折返跑
题意
笔直的跑道可以看作是一条数轴。跑道上有 n 个点位，其中，老师在 1 点和 n 点处各放了两根杆子，称为左杆和右杆，作为折返跑的折返点。
老师规定，今天一共需要跑 m 趟。我们认为，从一根杆子开始，跑到另一根杆子结束为一趟，显然，一共需要进行 m−1 次折返。Zaoly偶然发现，杆子是可推动的，所以他有了一个大胆的想法——
-
每次跑至右杆折返后，都需要把右杆向左推动一段距离（大于 0），但仍保证右杆位于整数点，且在左杆的右边（不能与左杆重合）；
-
每次跑至左杆折返后，都需要把左杆向右推动一段距离（大于 0），但仍保证左杆位于整数点，且在右杆的左边（不能与右杆重合）；
现在，给出整数 n 和 m 的值，请问Zaoly一共有多少种不同的推杆方法？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。注意，每次折返时都需要推杆，如果某一轮无法推动，则这一轮推杆非法。
大概思路
纸上分析一下样例 “4 3” 和 “5 3”，很容易发现答案就是 $C_{n - 2}^{m - 1}$。
参考代码
constexpr int M = 1e9 + 7;
i64 powp(i64 a, i64 n) {
i64 ans = 1;
while (n) {
if (n & 1) (ans *= a) %= M;
(a *= a) %= M;
n >>= 1;
}
return ans;
}
i64 inv(i64 x) {
return powp(x, M - 2);
}
constexpr int N = 1e6 + 1;
i64 fac[N], invfac[N];
void pre() {
fac[0] = invfac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i % M;
invfac[N - 1] = inv(fac[N - 1]);
for (int i = N - 2; i >= 1; i--) invfac[i] = invfac[i + 1] * (i + 1) % M;
}
i64 C(i64 n,i64 m) {
if (m > n) return 0;
return fac[n] * invfac[n - m] % M * invfac[m] % M;
}
void solve(){
int n, m;
std::cin >> n >> m;
std::cout << C(n - 1 - 1, m - 1) << "\n";
}
F. 口吃
题意
Zaoly要讲一句话，这句话有 n 个字，他要一个字一个字讲出来。奈何 Zaoly 口吃：
- 讲到第 1 个字时，下一个要讲的字有 $\frac{a_1}{a_1+b_1}$ 的概率前进到第 2 个字，有 $\frac{b_1}{a_1+b_1}$ 的概率仍是第 1 个字。
- 讲到第 i（2≤i≤n−1）个字时，下一个要讲的字有 $\frac{a_i^2}{a_i^2 + 2a_ib_i + b_i^2}$ 的概率前进到第 i+1 个字，有 $\frac{2a_ib_i}{a_i^2 + 2a_ib_i + b_i^2}$ 的概率仍是第 i 个字，有 $\frac{b_i^2}{a_i^2 + 2a_ib_i + b_i^2}$ 的概率倒退到第 i−1 个字。
- 讲到第 n 个字时，讲话完毕，停止讲话。
直到讲话完毕，Zaoly总共讲出的字数的期望是多少？
大概思路
一眼带环的期望dp（为什么带环？因为可以从后面的状态转移到之前的状态），所以不能用普通的期望dp一直往后推，而是要用高斯消元的方法。
注意到第一项只有一个自环和向前推进。列出转移方程：
$$ E[1] = \frac{a_1}{a_1 + b_1}E[2] + \frac{b_1}{a_1 + b_1}E[1] + 1$$
移项整理有：
$$ E[1] = E[2] + \frac{a_1 + b_1}{a_1}$$
设 $ E[i] = P[i]E[i + 1] + Q[i] $，则 $P[1] = 1$，$Q[1] = \frac{a_1 + b_1}{a_1}$
对 $i (i \ge 2)$ 有如下转移方程：
$$ E[i] = \frac{a_i^2}{a_i^2 + 2a_ib_i + b_i^2}E[i + 1] + \frac{2a_ib_i}{a_i^2 + 2a_ib_i + b_i^2}E[i] + \frac{b_i^2}{a_i^2 + 2a_ib_i + b_i^2}E[i - 1] + 1 $$
将 $ E[i] = P[i]E[i + 1] + Q[i] $ 代入到上式的 $E[i - 1]$ 中并移项整理有：
$$ E[i] = \frac{a_i^2}{a_i^2 + b_i^2 - b_i^2P[i - 1]}E[i + 1] + \frac{b_i^2Q[i - 1] + (a_i + b_i)^2}{a_i^2 + b_i^2 - b_i^2P[i - 1]} $$
也就是说：
$$ P[i] = \frac{a_i^2}{a_i^2 + b_i^2 - b_i^2P[i - 1]} $$ $$ Q[i] = \frac{b_i^2Q[i - 1] + (a_i + b_i)^2}{a_i^2 + b_i^2 - b_i^2P[i - 1]} $$
其和 $E[i]$ 无关，那么我们可以预处理出所有的 $P[i]$, $Q[i]$，再用 $E[i] = P[i]E[i + 1] + Q[i] $倒序推出 $E[1]$ 即可，易知 $E[n] = 1$
参考代码
constexpr int M = 1e9 + 7;
i64 powp(i64 a, i64 n) {
i64 ans = 1;
while (n) {
if (n & 1) (ans *= a) %= M;
(a *= a) %= M;
n >>= 1;
}
return ans;
}
i64 inv(i64 x) {
return powp(x, M - 2);
}
void solve(){
int n;
std::cin >> n;
std::vector<i64> a(n), b = a;
for (int i = 1; i < n; i++) std::cin >> a[i];
for (int i = 1; i < n; i++) std::cin >> b[i];
std::vector<i64> p(n), q = p;
p[1] = 1; q[1] = (a[1] + b[1]) * inv(a[1]) % M;
for (int i = 2; i < n; i++) {
i64 fm = (a[i] * a[i] % M + b[i] * b[i] % M - b[i] * b[i] % M * p[i - 1] % M + M) % M;
fm = inv(fm);
p[i] = (a[i] * a[i] % M) * fm % M;
q[i] = (b[i] * b[i] % M * q[i - 1] % M + ((a[i] + b[i]) % M) * ((a[i] + b[i]) % M) % M) % M * fm % M;
}
std::vector<i64> E(n + 1);
E[n] = 1;
for (int i = n - 1; i >= 1; i--) {
E[i] = (p[i] * E[i + 1] % M + q[i]) % M;
}
std::cout << E[1];
}