牛客周赛 Round 50

A题：小红的最小最大

思路：

大水题

code：

inline void solve() {int a, b, c; cin >> a >> b >> c;if (min(a, b) + c > max(a, b)) cout << "YES\n";else cout << "NO\n";return;
}

B题：小红的四则运算（easy） 

思路：

大水题

code：

inline void solve() {int ans = 0;int a, b, c; cin >> a >> b >> c;int cur = a + b + c;ans = max(ans, cur);cur = a * b + c;ans = max(ans, cur);cur = a + b * c;ans = max(ans, cur);cur = a * b * c;ans = max(ans, cur);cur = a * (b + c);ans = max(ans, cur);cur = (a + b) * c;ans = max(ans, cur);cout << ans << endl;return;
}

C题：小红的四则运算（hard） 

思路：

大水题

code：

inline void solve() {int ans = 0;int a, b, c; cin >> a >> b >> c;int cur = a + b + c;ans = max(ans, cur);cur = a * b + c;ans = max(ans, cur);cur = a + b * c;ans = max(ans, cur);cur = a * b * c;ans = max(ans, cur);cur = a * (b + c);ans = max(ans, cur);cur = (a + b) * c;ans = max(ans, cur);cout << ans << endl;return;
}

D题：小红的因式分解 

思路：

十字相乘大法。

注意正的可以表示为两个负的相乘。

code：

inline void solve() {ll a, b, c;cin >> a >> b >> c;if (c == 0) {cout << 1 << ' ' << 0 << ' ' << a << ' ' << b << endl;return;}vector<PLL> l, r;function<void(ll, vector<PLL>&)> add = [&](ll x, vector<PLL>& e) {for (ll i = min(1ll, x); i < max(0ll, x + 1); i ++ ) {if (x % i == 0) {e.push_back({i, x / i});e.push_back({-i, -x / i});}}};add(a, l), add(c, r);bool ok = false;for (auto [l1, l2] : l) {for (auto [r1, r2] : r) {if (l1 * r1 + l2 * r2 == b) {ok = true;cout << l1 << ' ' << r2 << ' ' << l2 << ' ' << r1 << endl;break;}}if (ok) break;}if (!ok) cout << "NO\n";return;
}

E题：小红的树上移动 

思路：

学过期望和逆元应该就会做了。

期望等于各个值乘以它的概率的和，对于此题，我们只需统计下每层的叶节点数量和节点数量即可。

inline void solve() {mod = 998244353;int n; cin >> n;vector<vector<int>> e(n + 1);for (int i = 1; i < n; i ++ ) {int u, v; cin >> u >> v;e[u].push_back(v), e[v].push_back(u);}vector<int> dep(n + 1), cnt(n + 1), tot(n + 1);function<void(int, int)> dfs = [&](int u, int pre) {dep[u] = dep[pre] + 1;tot[dep[u]] += 1;if (e[u].size() == 1 && u != 1) cnt[dep[u]] += 1;for (auto v : e[u]) {if (v == pre) continue;dfs(v, u);}};dfs(1, 0);ll ans = 0, lv = 1;for (int i = 1; i <= n; i ++ ) {if (cnt[i]) {ll gai = lv * cnt[i] % mod * inv(tot[i]) % mod;ans = (ans + (i - 1) * gai % mod) % mod;lv = lv * (tot[i] - cnt[i]) % mod * inv(tot[i]) % mod;}}cout << ans << endl;return;
}