【CodeForces】Lyft Level 5 Challenge 2018 - Elimination Round (Div. 1 + Div. 2) 题解

【比赛链接】

点击打开连接

【题解链接】

点击打开链接

**【A】**King Escape

【思路要点】

皇后会攻击到 $8$ 条直线，其中 $4$ 条斜向的可以跨过，因此可以忽略。判断起始点和目标点是否在其余 $4$ 条线分割出的同一个联通块内即可。时间复杂度 $O(1)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, ax, ay, bx, by, cx, cy; int f(int x, int y) { int ans = 0; ans += x < ax; ans *= 2; ans += y < ay; return ans; } int main() { read(n); read(ax), read(ay); read(bx), read(by); read(cx), read(cy); if (f(bx, by) == f(cx ,cy)) printf("YES\n"); else printf("NO\n"); return 0; }

**【B】**Square Difference

【思路要点】

由题，我们要判断 $a^2-b^2$ 是否是质数。由于 $a^2-b^2=(a+b)(a-b)$ ，若 $a-b>1$ ， $a^2-b^2$ 显然不是质数。否则则判断 $a+b$ 是否为质数即可。时间复杂度 $O(\sqrt{a+b})$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } bool prime(ll x) { for (int i = 2; 1ll * i * i <= x; i++) if (x % i == 0) return false; return true; } int main() { int T; read(T); while (T--) { ll a, b; read(a), read(b); if (a == b + 1 && prime(a + b)) printf("YES\n"); else printf("NO\n"); } return 0; }

**【C】**Permutation Game

【思路要点】

按照权值从大到小暴力博弈 $dp$ 即可。时间复杂度 $O(NLogN)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, a[MAXN], p[MAXN]; bool dp[MAXN]; bool cmp(int x, int y) { return a[x] > a[y]; } int main() { read(n); for (int i = 1; i <= n; i++) read(a[i]), p[i] = i; sort(p + 1, p + n + 1, cmp); for (int i = 1; i <= n; i++) { int pos = p[i]; for (int j = pos + a[pos]; j <= n; j += a[pos]) if (a[j] > a[pos]) dp[pos] |= !dp[j]; for (int j = pos - a[pos]; j >= 1; j -= a[pos]) if (a[j] > a[pos]) dp[pos] |= !dp[j]; } for (int i = 1; i <= n; i++) if (dp[i]) putchar('A'); else putchar('B'); putchar('\n'); return 0; }

**【D】**Divisors

【思路要点】

有 $3$ 至 $5$ 个因数的数应当形如 $p^2,p^3,p^4,pq$ ，其中 $p,q$ 为质数。其中形如 $p^2,p^3,p^4$ 的较容易分解，可以先用 $pow$ 函数估算方根，再微调以消除误差，即可检查该数是否为完全 $4,3,2$ 次方数，从而分解该数。剩余的形如 $pq$ 的数可以通过计算 $gcd$ 进行试探分解，若仍然无法分解，则说明该数对应的 $p,q$ 不在不与其相等的数中出现，因此单独计算对答案的贡献即可，即若有 $x$ 个该数，则贡献为 $(x+1{)}^2$ 。时间复杂度 $O(N^{2}LogV)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 5005; const double eps = 1e-9; const int P = 998244353; typedef long long ll; typedef long double ld; typedef pair <ll, int> info; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } ll ans, n, m, tot, a[MAXN]; vector <info> b; ll gcd(ll x, ll y) { if (y == 0) return x; else return gcd(y, x % y); } int main() { read(m); for (int i = 1; i <= m; i++) { ll x, tmp; read(x); tmp = pow(x, 1.0 / 4.0); while (tmp * tmp * tmp * tmp < x) tmp++; while (tmp * tmp * tmp * tmp > x) tmp--; if (tmp * tmp * tmp * tmp == x) { b.push_back(make_pair(tmp, 4)); continue; } tmp = pow(x, 1.0 / 3.0); while (tmp * tmp * tmp < x) tmp++; while (tmp * tmp * tmp > x) tmp--; if (tmp * tmp * tmp == x) { b.push_back(make_pair(tmp, 3)); continue; } tmp = pow(x, 1.0 / 2.0); while (tmp * tmp < x) tmp++; while (tmp * tmp > x) tmp--; if (tmp * tmp == x) { b.push_back(make_pair(tmp, 2)); continue; } a[++n] = x; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) if (a[i] != a[j]) { ll tmp = gcd(a[i], a[j]); if (tmp != 1) b.push_back(make_pair(tmp, 0)); } sort(b.begin(), b.end()); ll ans = 1; while (!b.empty()) { ll x = b.back().first; int cnt = b.back().second; b.pop_back(); while (!b.empty() && x == b.back().first) { cnt += b.back().second; b.pop_back(); } for (int i = 1; i <= n; i++) if (a[i] % x == 0) { cnt++; b.push_back(make_pair(a[i] / x, 1)); a[i] = 1; } ans = ans * (cnt + 1) % P; sort(b.begin(), b.end()); } sort(a + 1, a + n + 1); for (int i = 1, nxt; i <= n; i = nxt) { nxt = i; while (a[nxt] == a[i]) nxt++; int cnt = nxt - i; if (a[i] == 1) continue; ans = ans * (cnt + 1) % P * (cnt + 1) % P; } cout << ans << endl; return 0; }

**【E】**Hidden Bipartite Graph

【思路要点】

首先，我们可以使用 $3$ 次操作算出不相交的点集 $A$ 和 $B$ 之间的边数，即 $query(A+B)-query(A)-query(B)$ 。由于图是联通的，我们可以通过 $LogN$ 次上述操作二分出一个与当前点集有边相连的一个点，再通过 $LogN$ 次上述操作可以二分出它与当前点集的一条边，如此重复 $N-1$ 次，我们可以得到一棵原图的生成树。上述做法使用了 $6NLogN$ 次操作，但实际上许多操作询问的是相同的点集，因此不妨将询问进行记忆化。有了生成树，我们能够确定如果图是二分图，两边的点集，因此再询问一下两边的点集即可判断图是否为二分图。若图不是二分图，再二分出任意一条在某一侧的边即可，这里用到的操作数为 $O(LogN)$ ，几乎可以忽略不计。时间复杂度 $O(N^{2}LogN)$ ，使用操作至多 $4NLogN$ 次，实测至多使用 $16139$ 次。

【代码】

//Max Operation Use : 16139 #include<bits/stdc++.h> using namespace std; const int MAXN = 605; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, fa[MAXN], depth[MAXN]; bool vis[MAXN], col[MAXN]; vector <int> a[MAXN], part[2]; map <vector <int>, int> mem; int query(vector <int> a) { if (a.size() <= 1) return 0; sort(a.begin(), a.end()); if (mem.count(a)) return mem[a]; printf("? %d", a.size()); cout << endl; for (auto i : a) printf("%d ", i); cout << endl; int ans; read(ans); return mem[a] = ans; } int query(vector <int> a, vector <int> b) { vector <int> tmp; for (auto i : a) tmp.push_back(i); for (auto i : b) tmp.push_back(i); return query(tmp) - query(a) - query(b); } void dfs(int pos) { vis[pos] = true; part[col[pos]].push_back(pos); for (auto dest : a[pos]) if (!vis[dest]) { fa[dest] = pos; depth[dest] = depth[pos] + 1; col[dest] = !col[pos]; dfs(dest); } } void answer(int x, int y) { vector <int> a, b; if (depth[x] < depth[y]) swap(x, y); while (depth[x] > depth[y]) { a.push_back(x); x = fa[x]; } while (x != y) { a.push_back(x); x = fa[x]; b.push_back(y); y = fa[y]; } a.push_back(x); while (!b.empty()) { a.push_back(b.back()); b.pop_back(); } printf("N %d", a.size()); cout << endl; for (auto i : a) printf("%d ", i); cout << endl; exit(0); } void work(vector <int> a) { if (a.size() == 2) answer(a[0], a[1]); while (true) { random_shuffle(a.begin(), a.end()); vector <int> b, c; for (unsigned i = 0; i < a.size(); i++) if (i & 1) b.push_back(a[i]); else c.push_back(a[i]); if (query(b)) work(b); if (query(c)) work(c); } } int main() { read(n); vector <int> now, lft; now.push_back(1); for (int i = 2; i <= n; i++) lft.push_back(i); while (lft.size() != 0) { vector <int> rem = lft, pa, pb; while (rem.size() > 1) { unsigned mid = rem.size() / 2; pa.clear(); pb.clear(); for (unsigned j = 0; j < rem.size(); j++) if (j < mid) pa.push_back(rem[j]); else pb.push_back(rem[j]); if (query(now, pa)) rem = pa; else rem = pb; } vector <int> bak = rem; int pos = rem.back(); rem = now; while (rem.size() > 1) { unsigned mid = rem.size() / 2; pa.clear(); pb.clear(); for (unsigned j = 0; j < rem.size(); j++) if (j < mid) pa.push_back(rem[j]); else pb.push_back(rem[j]); if (query(pa, bak)) rem = pa; else rem = pb; } int dest = rem.back(); a[pos].push_back(dest); a[dest].push_back(pos); now.push_back(pos); for (unsigned j = 0; j < lft.size(); j++) if (lft[j] == pos) { lft.erase(lft.begin() + j); break; } } dfs(1); if (query(part[0]) + query(part[1]) == 0) { printf("Y %d", part[0].size()); cout << endl; for (auto i : part[0]) printf("%d ", i); cout << endl; return 0; } if (query(part[0])) work(part[0]); else work(part[1]); return 0; }

**【F】**Boolean Computer

【思路要点】

对于一个询问，枚举其中一个操作数，另一个操作数的某些数位将由此确定，某些数位仍然取 $0/1$ 均可，也有可能某一位上不存在相匹配的数。本质上，我们需要回答形如“ $1?0?$ 的数有多少个”的问题，可以在 $O(4^w)$ 的时间内暴力预处理出上述问题的答案。通过合适的预处理，时间复杂度 $O(N+M\ast 2^w+4^w)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 531441; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int w, n, m, bit[15], zero[MAXN], one[MAXN]; int bnt[MAXN], cnt[MAXN], mask[MAXN], two[MAXN]; int main() { read(w), read(n), read(m); for (int i = 1; i <= n; i++) { int x; read(x); bnt[x]++; } int goal = (1 << w) - 1; bit[0] = 1; for (int i = 1; i <= w; i++) bit[i] = bit[i - 1] * 3; for (int i = 0; i <= goal; i++) { for (int j = 0; j <= w - 1; j++) { mask[i] += bit[j] * ((i & (1 << j)) != 0); if (i & (1 << j)) two[i] += bit[j] * 2, one[i] += 1 << j; else zero[i] += 1 << j; } } for (int i = 0; i <= goal; i++) { if (bnt[i] == 0) continue; for (int j = 0; j <= goal; j++) cnt[mask[i & j] + two[goal ^ j]] += bnt[i]; } for (int i = 1; i <= m; i++) { char str[15]; scanf("\n%s", str); reverse(str, str + w); ll ans = 0; int opt[2][3] = {{0, 0, 0}, {0, 0, 0}}; for (int j = 0; j <= w - 1; j++) { if (str[j] == 'A') { opt[0][2] += 1 << j; opt[1][0] += 1 << j; } if (str[j] == 'O') opt[0][0] += 1 << j; if (str[j] == 'X') { opt[0][0] += 1 << j; opt[1][1] += 1 << j; } if (str[j] == 'a') opt[1][1] += 1 << j; if (str[j] == 'o') { opt[0][1] += 1 << j; opt[1][2] += 1 << j; } if (str[j] == 'x') { opt[0][1] += 1 << j; opt[1][0] += 1 << j; } } for (int s = 0; s <= goal; s++) { if (bnt[s] == 0) continue; int tmp[3]; tmp[0] = (zero[s] & opt[0][0]) + (one[s] & opt[1][0]); tmp[1] = (zero[s] & opt[0][1]) + (one[s] & opt[1][1]); tmp[2] = (zero[s] & opt[0][2]) + (one[s] & opt[1][2]); if (tmp[0] + tmp[1] + tmp[2] == goal) ans += 1ll * cnt[mask[tmp[1]] + two[tmp[2]]] * bnt[s]; } writeln(ans); } return 0; }

**【G】**Chip Game

【思路要点】

首先，我们来解决：若固定一对 $(a,b)$ ，游戏的胜负性。若 $a=b$ ，判断 ${\sum }_{i=1}^N\lfloor \frac{v_i}{a}\rfloor$ 的奇偶性即可。不妨设 $a<b$ ， $Alice$ 对应 $a$ ， $Bob$ 对应 $b$ 。引理：若令 $v_i^{\prime }=v_i\%(a+b)$ ，游戏的胜负情况不变。证明： 以下我们说明在 $v^{\prime }$ 对应的游戏中获胜的玩家同样可以在 $v$ 对应的游戏中获胜，由于没有平局，这两个命题是等价的。 以下是在 $v^{\prime }$ 对应的游戏中获胜的玩家在新游戏中的必胜策略： 若获胜玩家走第一步，那么按照 $v^{\prime }$ 对应的游戏中的第一步走； 若上一步对方走的一步存在于 $v^{\prime }$ 对应的游戏中，那么按照游戏中的方式应对； 否则，对对方上一步操作的石子堆进行的操作，两次操作的总和为 $a+b$ ，相当于在 $v^{\prime }$ 对应的游戏中没有变化。以下我们令 $v_i=v_i\%(a+b)$ 。存在以下四种游戏： $1$ 、 $0\le v_i<a$ ，无用的游戏，双方都无法操作。 $2$ 、 $a\le v_i<b$ ，只有 $Alice$ 可以操作，只要存在此类游戏，则 $Alice$ 必胜。 $3$ 、 $b\le v_i<2a$ ，双方都只能操作一次的游戏。 $4$ 、 $max\{2a,b\}\le v_i<a+b$ ，只要 $Alice$ 能够对该游戏操作一次，即可将其转化为 $2$ 类游戏，因此若存在 $\ge 2$ 个此类游戏，则 $Alice$ 必胜。剩余的情况如下： $1$ 、 $4$ 类游戏有 $1$ 个， $3$ 类游戏有奇数个， $Alice$ 必胜。 $2$ 、 $4$ 类游戏有 $1$ 个， $3$ 类游戏有偶数个， 先手必胜。 $3$ 、 没有 $4$ 类游戏， $3$ 类游戏有奇数个， 先手必胜。 $4$ 、 没有 $4$ 类游戏， $3$ 类游戏有偶数个， 后手必胜。因此，若我们枚举 $a,b$ ，可以到一个 $O(M^{2}N)$ 的做法。考虑优化，枚举 $a+b$ ，计算 $v_i=v_i\%(a+b)$ 。令 $f(x,i)$ 表示当 $a=x,b=(a+b)-x$ 时游戏 $i$ 的类型， $f(\ast ,i)$ 的取值将分成 $O(1)$ 段，分别计算出其变化的位置，排序即可在 $O(NLogN)$ 的时间内计算出 $a+b$ 对答案的贡献。时间复杂度 $O(M\ast NLogN)$ 。

【代码】

#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; typedef long long ll; typedef long double ld; typedef unsigned long long ull; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } int n, m; ll ans[4], b[MAXN]; int a[MAXN]; void solve(int sum) { if (sum % 2 == 0) { int tmp = sum / 2, cnt = 0; for (int i = 1; i <= n; i++) cnt += a[i] / tmp; if (cnt & 1) ans[2]++; else ans[3]++; } int Min = max(1, sum - m), Max = (sum - 1) / 2; vector <pair<int, int>> res; for (int i = 1; i <= n; i++) { if (a[i] + 1 <= Max) { res.emplace_back(max(a[i] + 1, Min), 1); res.emplace_back(Max + 1, -1); } int tmp = min(a[i], sum - a[i] - 1); if (tmp >= Min) { res.emplace_back(Min, 2); res.emplace_back(min(tmp, Max) + 1, -2); } tmp = max(sum - a[i], a[i] / 2 + 1); if (tmp <= Max) { res.emplace_back(max(tmp, Min), 3); res.emplace_back(Max + 1, -3); } } res.emplace_back(Min, 0); res.emplace_back(Max + 1, 0); sort(res.begin(), res.end()); int now[5] = {0, 0, 0, 0, 0}; for (unsigned i = 1; i < res.size(); i++) { int delta = res[i].first - res[i - 1].first; if (res[i - 1].second < 0) now[-res[i - 1].second]--; else now[res[i - 1].second]++; now[4] = n - now[1] - now[2] - now[3]; if (now[2] != 0 || now[4] >= 2) ans[0] += delta, ans[1] += delta; else if (now[4] == 0) { if (now[3] & 1) ans[2] += delta * 2; else ans[3] += delta * 2; } else { if (now[3] & 1) ans[0] += delta, ans[1] += delta; else ans[2] += delta * 2; } } } int main() { read(n), read(m); for (int i = 1; i <= n; i++) read(b[i]); for (int i = 2; i <= 2 * m; i++) { for (int j = 1; j <= n; j++) a[j] = b[j] % i; solve(i); } cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << ' ' << ans[3] << endl; return 0; }