【解题报告】Codeforces Round #362 (Div. 2)

本文主要是介绍【解题报告】Codeforces Round #362 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

A. Pineapple Incident（Codeforces 697A）

思路

由于菠萝乱叫的时间点满足 $t + p \times s$ 或 $t + q \times s + 1$ ，其中 $p \geq 0，q > 0$ 。先判断 $x = t$ 和 $x = t + 1$ 是否满足，如果不满足的话，我们就可以将 $p, q$ 统一看成 $k$ ，判断是否存在 $k$ 使得 $t + k \times s = x$ 或 $t + k \times s + 1 = x，k \geq 0$ 。只要判断 $(x - t) \mod s = 0$ 或 $(x - t) \mod s = 1$ 是否满足即可。

代码

#include <bits/stdc++.h>
using namespace std;int t, s, x, tmp;int main() {cin >> t >> s >> x;tmp = (x - t) % s;if(x < t) {puts("NO");}else if(x == t + 1) {puts("NO");}else if(tmp == 0 || tmp == 1) {puts("YES");}else {puts("NO");}return 0;
}

B. Barnicle（Codeforces 697B）

思路

本题的逻辑如下：

如果 $d = 0$ 的话，直接在 $a$ 的末尾加 $b$ 个 $0$ 输出。
否则如果结果是整数的话在 $a$ 的末尾加上数量比 $b$ 小的 $0$ 输出。
否则将小数点移动后依次输出新的 $a$ ，小数点和新的 $d$ 。

代码

#include <bits/stdc++.h>
using namespace std;int b, p, q;
string l, r, s, sa, sd;
stringstream ss;int main() {cin >> s;p = s.find('.');q = s.find('e');s[p] = s[q] = ' ';ss << s;ss >> sa >> sd >> b;if(sd == "0") {for(int i = 0; i < b; i++) {sa.push_back('0');}cout << sa << endl;}else if(b >= sd.size()) {sa += sd;for(int i = 0; i < b - sd.size(); i++) {sa.push_back('0');}cout << sa << endl;}else {l = sa + sd.substr(0, b);r = sd.substr(b, sd.size() - b);cout << l << '.' << r << endl;}return 0;
}

C. Lorenzo Von Matterhorn（Codeforces 697C）

思路

修改 $u-v$ 路径的权值的时候暴力找到 $u$ 和 $v$ 的最近公共祖先，边找边用 $map$ 更新当前点的出边的权值。查找 $u-v$ 路径的权值的时候暴力找到 $u$ 和 $v$ 的最近公共祖先，边找边累加当前点的出边的权值。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
int q, o;
ll u, v, w, ans;
map <ll, ll> mp;int main() {cin >> q;while(q--) {cin >> o >> u >> v;if(u < v) {swap(u, v);}if(o == 1) {cin >> w;while(u != v) {mp[u] += w;u >>= 1;if(u < v) {swap(u, v);}}}else {ans = 0;while(u != v) {ans += mp[u];u >>= 1;if(u < v) {swap(u, v);}}cout << ans << endl;}}return 0;
}

D. Puzzles（Codeforces 697D）

思路

如果想以树的节点编号做状态来做树形动态规划的话，对于每个节点，都要枚举子节点的访问顺序。这样的复杂度太高了。所以我们转而用公式法或者贡献度法来解决。对于一个点 $v$ ， $strart_time[v]$ 显然等于先于 $v$ 访问的节点的个数加上 $1$ 。那么每个点 $u$ 对点 $start_time[v]$ 期望的贡献度就是 $u$ 先于 $v$ 访问的概率 $p_u$ 。那么 $start_time[v]$ 的期望为 $\sum p_u + 1$ 。下面就考察每个点先于 $v$ 访问的概率。首先对于 $v$ 的祖先 $u_1，p_{u_1} = 1$ ，其次对于 $v$ 的子树上的节点 $u_2，p_{u_2} = 0$ 。最后对于其它所有节点 $u_3，p_{u_3} = 0.5$ （因为在 $v$ 和 $u_3$ 的最近公共祖先的时候，往这两个节点所在的子树走的概率是相等的）。现在问题就转化成如何计算 $u_3$ 的数量。设 $v$ 在树中的深度为 $d[v]$ （根节点深度为 $0$ ）， $v$ 的子树的节点个数为 $c[v]$ ，那么 $u_3$ 的数量就是 $n - c[v] - d[v]$ 。因此答案就是 $\frac{n - c[v] - d[v]}{2} + d[v] + 1$

代码

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 10;
int n, p, ans, c[maxn], d[maxn];
vector <int> G[maxn];void dfs(int u) {c[u] = 1;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];d[v] = d[u] + 1;dfs(v);c[u] += c[v];}
}int main() {scanf("%d", &n);for(int i = 2; i <= n; i++) {scanf("%d", &p);G[p].push_back(i);}dfs(1);for(int i = 1; i <= n; i++) {ans = n - c[i] + d[i] + 2;printf("%d.", ans / 2);printf(ans & 1 ? "5 " : "0 ");}puts("");return 0;
}

E. PLEASE（Codeforces 697E）

思路

因为这是一个概率问题，所以先按照状态转移的思想来思考。如果将初始状态定义为 $(1, 2, 3)$ ，那么状态空间将只有 $6$ 个元素—— $(1, 2, 3)，(1, 3, 2)，(2, 1, 3)，(2, 3, 1)，(3, 1, 2)，(3, 2, 1)$ 。但是将状态转移图画好后又会发现没有什么我们需要的线索。那么换一种状态定义方式呢？假设状态 $i$ 为 $i$ 次交换后的状态，令 $d[i]$ 为 $i$ 次交换后初始状态下的中间的杯子（我们可以暂时称之为第 $2$ 个杯子）依然在中间的概率。我们试图寻找 $d[i]$ 与 $d[i-1]$ 的关系。不难发现，当状态为 $i-1$ 时第 $2$ 个杯子在中间的话，到了状态为 $i$ 的时候第 $2$ 个杯子就不可能在中间了。于是有如下关系

$d[i] = \frac{1 - d[i-1]}{2}$

因为要得到最最简分数形式的概率，因此光得到递推公式是不够的，我们要求一个能直接计算出结果的封闭形式。于是用待定系数法可以得到一个等比数列的递推公式

$d[i] - \frac{1}{3} = -\frac{1}{2}(d[i-1] - \frac{1}{3})$

解这个递推公式得

$d[n] = \frac{(-1)^n + 2^{n-1}}{3 \times 2^{n-1}}$

凑巧的是， $(-1)^n + 2^{n-1}$ 正好是 $3$ 的倍数（与 $2$ 的幂的相邻的两个数中一定有一个是 $3$ 的倍数）而且 $(-1)^n + 2^{n-1}$ 除以 $3$ 一定能得到奇数，这样就能与上式分母的偶数互质了。所以有

$p = \frac{(-1)^n + 2^{n-1}}{3}$

$q = 2^{n-1}$

题目就得解了。另外要注意的是，对分数取 $mod$ 的时候要对分母计算模逆元，也就是要算出 $3$ 的模逆元。计算 $2^{n-1}$ 的时候可以用快速幂算法来算。

最后，偶然发现像P这样的数被称为 $Jacobsthal \,\,\, numbers$ （维基百科）。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const ll mod = 1e9 + 7;
bool one = true;
int k, odd = 1;
ll a, p, q = 2;// 快速幂算法
ll modPow(ll a, ll n, ll mod) {ll ans = 1;for(; n > 0; n >>= 1) {if(n & 1) {ans = (ans * a) % mod;}a = (a * a) % mod;}return ans;
}// 求模逆元
ll modInv(ll a, ll mod) {return modPow(a, mod - 2, mod);
}int main() {scanf("%d", &k);for(int i = 0; i < k; i++) {scanf("%I64d", &a);odd &= (a & 1);q = modPow(q, a, mod);if(a > 1) {one = false;}}q = (q * modInv(2, mod)) % mod;if(one == true) {p = 0;}else {p = q;p += (odd ? -1 : 1);p = (p * modInv(3, mod)) % mod;}printf("%I64d/%I64d\n", p, q);return 0;
}