Educational Codeforces Round 138 (Rated for Div. 2) A-E

比赛链接

知识点：贪心。

注意到 m≥nm≥n 时，不存在某一行或列空着，于是不能移动。

而 m<nm<n 时，一定存在，可以移动。

时间复杂度 O(1)O(1)

空间复杂度 O(1)O(1)

#include <bits/stdc++.h>#define ll long long using namespace std; bool solve() { int n, m; cin >> n >> m; for (int i = 1;i <= m;i++) { int x, y; cin >> x >> y; } if (m >= n) return false; else cout << "YES" << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << '\n'; } return 0;}

知识点：贪心。

每次干掉两端 bb 最小的即可，能保证最大的 bb 没有增加花费，其他 bb 只增加花费一次。

时间复杂度 O(n)O(n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h>#define ll long long using namespace std; int a[200007], b[200007];bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; for (int i = 1;i <= n;i++) cin >> b[i]; ll sum = 0; for (int i = 1;i <= n;i++) sum += a[i]; int l = 1, r = n; while (l < r) { if (b[l] <= b[r]) sum += b[l++]; else sum += b[r--]; } cout << sum << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：博弈论，贪心，二分。

本来数据范围能暴力，但执着找规律推结论，结果推假了wwwwwwwwww，不如直接暴力QAQ。

显然二分 kk 可以，k∈[1,⌈n2⌉]k∈[1,⌈n2⌉]。二者选取的贪心策略也很明显，A尽量取大的，B取最小的，推到这一步可以直接模拟了。

但进一步可以推出，A取后 kk 个之后，B一定取了前 k−1k−1 个，那么我们把前 k−1k−1 个空出来，让A直接从 kk 开始取是最优的，正着取的第 ii 个是第 k−i+1k−i+1 回合，只要小于等于 ii 即可。

时间复杂度 O(nlogn)O(nlog⁡n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h>#define ll long long using namespace std; int n;int a[107];bool check(int mid) { bool ok = 1; for (int i = 1;i <= mid;i++) { ok &= a[mid + i - 1] <= i; } return ok;} bool solve() { cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); int l = 1, r = n + 1 >> 1; while (l <= r) { int mid = l + r >> 1; if (check(mid)) l = mid + 1; else r = mid - 1; } cout << r << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：数论，筛法。

注意到，我们要求的是每个元素不超过 mm 的正整数，长度 [1,n][1,n] 的每个长度的不明确的序列个数之和。我们先考虑长度为 nn 的情况，其他长度可以同理。

所有序列天生有一组 [1,1,1,1,⋯][1,1,1,1,⋯] 的删除序列，这代表只要序列有一个元素能在 11 以外的位置删除，就能产生新的删除序列，则原序列就是不明确的。

因为可以通过移除第一项，让 a[i]a[i] 往前挪，必然会经过 [2,i][2,i] 的所有位置，所以若要使 a[i]a[i] 可在 11 以外的位置删除，需要 a[i]a[i] 存在 [2,i][2,i] 内的数与其没有公共质因子，更进一步，即不包含所有前缀素数（[2,i][2,i] 所有数的质因子种类，即其中所有素数），这样就一定存在 2≤j≤i2≤j≤i 使 gcd(j,a[i])=1gcd(j,a[i])=1 。

注意到，计算在 a[i]a[i] 位置上 [1,m][1,m] 中符合条件的数的个数很困难，但计算包含所有前缀质因子的情况很容易， mmulimmuli 就是 [1,m][1,m] 所有前缀质因子都存在的数的个数，其中 mulimuli 是位置 ii 的前缀质因子乘积。

我们计算出 [1,n][1,n] 每个位置的 mmulimmuli ，即每个位置其前缀质因子都存在数的个数，把他们乘法原理乘在一起，就代表长度为 nn 明确的数列的个数 ∏ni=1mmuli∏i=1nmmuli ，因为每个位置组合的都是包含所有前缀质因子，除了在 11 处删除，其他地方 gcd(i,a[i])≠1gcd(i,a[i])≠1 不能删。

最后对于长度 nn 的数列，所有情况一共 mnmn 种，所以最后不明确的数列个数为 mn−∏ni=1mmulimn−∏i=1nmmuli 。

我们对 [1,n][1,n] 所有长度的答案求和，有 ans=∑ni=1(mi−∏ij=1mmulj)ans=∑i=1n(mi−∏j=1immulj) ，注意到 mimi 、 mulimuli 以及 ∏ij=1mmulj∏j=1immulj 可以从 11 递推，过程中加到答案里即可。

时间复杂度 O(n)O(n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h>#define ll long long using namespace std; const int mod = 998244353; int cnt;int vis[300007];int prime[300007] = { 1 };void euler_screen(int n) { for (int i = 2;i <= n;i++) { if (!vis[i]) prime[++cnt] = i; for (int j = 1;j <= cnt && i * prime[j] <= n;j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } }} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; ll m; cin >> n >> m; euler_screen(n); int base = 1, mul = 1, ans = 0; ll fact = 1; for (int i = 1;i <= n;i++) { if (!vis[i] && fact <= m) fact *= i; base = 1LL * m % mod * base % mod; mul = 1LL * m / fact % mod * mul % mod; ans = ((ans + base) % mod - mul + mod) % mod; } cout << ans << '\n'; return 0;}

知识点：bfs。

思考明白了就是一个很简单的01bfs。

注意到我们需要让从第一行到第 nn 行不存在路径，反过来想就是需要一条从第一列到第 mm 列连续的横向仙人掌路径，才能阻挡所有竖向路径，这个路径要求花费最少，于是问题转化问从第一列出发到第 mm 列的仙人掌最短路，起点是第一列所有点，有仙人掌的格子花费为 00 ，没有的花费是 11 。

搜索过程中用一个 map 记录前驱坐标即可复原路径。

这道题主要在这个思考和转化的过程。

时间复杂度 O(nm)O(nm)

空间复杂度 O(nm)O(nm)

#include <bits/stdc++.h>#define ll long long using namespace std; const int dir[4][2] = { {1,1},{1,-1},{-1,1},{-1,-1} };const int dir2[4][2] = { {1,0},{0,1},{0,-1},{-1,0} }; bool solve() { int n, m; cin >> n >> m; vector<vector<char>> dt(n + 1, vector<char>(m + 1)); for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> dt[i][j]; auto check = [&](int x, int y) { bool ok = 1; for (int i = 0;i < 4;i++) { int xx = x + dir2[i][0]; int yy = y + dir2[i][1]; if (xx <= 0 || xx > n || yy <= 0 || yy > m) continue; ok &= dt[xx][yy] != '#'; } return ok; }; deque<pair<int, int>> dq; vector<vector<bool>> vis(n + 1, vector<bool>(m + 1)); map<pair<int, int>, pair<int, int>> pre; pair<int, int> p = { 0,0 }; for (int i = 1;i <= n;i++) { if (dt[i][1] == '#') dq.push_front({ i,1 }), vis[i][1] = 1, pre[{i, 1}] = { 0,0 }; else if (check(i, 1)) dq.push_back({ i,1 }), vis[i][1] = 1, pre[{i, 1}] = { 0,0 }; } while (!dq.empty()) { auto [x, y] = dq.front(); dq.pop_front(); if (y == m) { p = { x,y }; break; } for (int i = 0;i < 4;i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if (xx <= 0 || xx > n || yy <= 0 || yy > m || vis[xx][yy]) continue; if (dt[xx][yy] == '#') dq.push_front({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y }; else if (check(xx, yy)) dq.push_back({ xx,yy }), vis[xx][yy] = 1, pre[{xx, yy}] = { x,y }; } } auto &[px, py] = p; if (!px && !py) return false; cout << "YES" << '\n'; while (px || py) { dt[px][py] = '#'; p = pre[{px, py}]; } for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { cout << dt[i][j]; } cout << '\n'; } return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << '\n'; } return 0;}