简要题解
A
根据等差中项的定义,,所以 ,直接输出即可。
当然如果你 for 循环一个个找那也是能过的。
#include <bits/stdc++.h> using namespace std; int main() { int a, b; cin >> a >> b; cout << 2 * b - a << endl; return 0; }
B
我们按位考虑,注意到一共可操作 位(因为 ),然后对于每一位(设 的第 位为 ),若 ,则为了使最后按位与出来的结果一样, 必须为 ,否则 就为 (为了使 尽量大)。
当然实际上这就是 和 的同或运算,直接输出 LONG_LONG_MAX ^ a ^ b
也可。
#include <bits/stdc++.h> using namespace std; long long a, b, ans; int main() { cin >> a >> b; ans = LONG_LONG_MAX ^ a ^ b; cout << ans << endl; return 0; }
C
一开始可能大家会想二分,但是完全没有必要。
斐波那契数列增长的很快,事实上其只有不到 项是在 ll
范围的,直接暴力判断即可。
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std; using ll = long long; ll F[105]; int n; inline ll myabs(ll x) {return x >= 0 ? x : -x;} int main() { F[1] = 1, F[2] = 1; FOR(i, 3, 88) F[i] = F[i - 1] + F[i - 2]; cin >> n; while (n --) { ll a; cin >> a; int ans = 1; FOR(i, 1, 88) if (myabs(F[i] - a) < myabs(F[ans] - a)) ans = i; cout << ans << '\n'; } return 0; }
D
注意到两人可操作的次数一定是 ,所以算出总操作次数后,若其为奇数则一定是至至子胜(轮到苏苏子的时候他一定没办法操作),否则就是苏苏子胜。
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std; using ll = long long; const int maxn = 1e5 + 5; int n; ll a[maxn]; int main() { cin >> n; ll ret = 0; FOR(i, 1, n) cin >> a[i], ret += (a[i] - i); cout << ((ret & 1) ? "ZZZ" : "SSZ") << endl; return 0; }
E
注意到一条长链上的 值一定是 这样的形式,并且整棵树中最大的 值只能有一个,不难发现其为根节点。
于是构造流程如下:
- 先找到根节点,然后引出这条最长的长链。
- 然后从当前最大的 值开始(令其为 ),依次取出 构成一条长链,然后接到树上已有的任意合法节点上(即接上去之后原来的 值不会被破坏)。
- 重复第二步直到构造完这棵树为止。
如果中间的任意一步无法进行下去,报告无解即可。时间复杂度 或 ,取决于实现。
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std; const int maxn = 2e5 + 5; int n, h[maxn]; vector<int> vec[maxn]; void solve() { cin >> n; FOR(i, 0, n - 1) vector<int>().swap(vec[i]); int maxh = 0; FOR(i, 1, n) cin >> h[i], vec[h[i]].emplace_back(i), maxh = max(maxh, h[i]); vector<pair<int, int>> E; if (vec[maxh].size() > 1) return cout << "-1\n", void(); int root = vec[maxh].back(); while (E.size() < n - 1) { while (maxh >= 0 && vec[maxh].empty()) --maxh; if (maxh < 0) return cout << "-1\n", void(); int hm = maxh; for (int las = root, cur = hm; cur >= 0; --cur) { if (vec[cur].empty()) return cout << "-1\n", void(); int u = vec[cur].back(); if (u != las) E.push_back({las, u}); las = u; vec[cur].pop_back(); } } cout << root << '\n'; for (auto &p : E) cout << p.first << ' ' << p.second << '\n'; return; } int main() { int T; cin >> T; while (T--) solve(); return 0; }
F
首先不难发现每个公司都是一棵树。
然后只考虑一个公司的话,相当于要对这棵树的拓扑序进行计数(将其视为叶向树),考虑树形 dp。
设 为只考虑 子树的拓扑序个数,转移的话首先 必须在第一个,剩下的随缘归并一下就行,用多重组合数类似的想法就是
预处理阶乘和阶乘逆,按照上面的方式转移即可求出每棵树的方案数 。然后再归并一下啥的就是
(事实上你可以将其看作一个虚拟的根,然后转移跟上面是同构的)。
当然,对于一棵 个节点的树,其拓扑序数量还可以如下计算:
利用上面的 dp 式子,将 除到左边,设 ,则可以归纳得到下式,反正都可以过题。
为了不卡常,数据范围只开到了 ,时间复杂度 或 。
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); ++i) #define DEC(i, a, b) for (int i = (a); i >= (b); --i) using namespace std; const int maxn = 1e5 + 5, N = 1e5, mod = 1e9 + 7; int fa[maxn], n, tot, c; int fac[maxn], ifac[maxn], size[maxn], f[maxn]; int qPow(int base, int exp) { int ret = 1; for (base %= mod; exp; exp >>= 1, base = 1ll * base * base % mod) if (exp & 1) ret = 1ll * ret * base % mod; return ret; } inline int binom(int n, int m) {return n < m ? 0 : 1ll * fac[n] * ifac[m] * ifac[n - m] % mod;} vector<int> G[maxn]; void dfs(int u) { f[u] = size[u] = 1; for (auto &v : G[u]) { dfs(v); f[u] = 1ll * f[u] * f[v] % mod * ifac[size[v]] % mod; size[u] += size[v]; } f[u] = 1ll * f[u] * fac[size[u] - 1] % mod; return; } int solve(int n) { FOR(i, 1, n) vector<int>().swap(G[i]); FOR(i, 2, n) cin >> fa[i], G[fa[i]].push_back(i); dfs(1); return f[1]; } int main() { fac[0] = 1; FOR(i, 1, N) fac[i] = 1ll * fac[i - 1] * i % mod; ifac[N] = qPow(fac[N], mod - 2); DEC(i, N - 1, 0) ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod; int ans = 1; cin >> n; FOR(i, 1, n) { cin >> c; tot += c; ans = 1ll * ifac[c] * ans % mod * solve(c) % mod; } cout << 1ll * ans * fac[tot] % mod << endl; return 0; }
全部评论
(1) 回帖