Rated for Div. 2 Educational Codeforces Round 138 A-E _生活百科

比赛链接
A题解【Rated for Div. 2 Educational Codeforces Round 138A-E】知识点：贪心。
注意到 $m\geq n$ 时，不存在某一行或列空着，于是不能移动。
而 $m<n$ 时，一定存在，可以移动。
时间复杂度 $O(1)$
空间复杂度 $O(1)$
代码#include <bits/stdc++.h>#define ll long longusing 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;}B题解知识点：贪心。
每次干掉两端 $b$ 最小的即可，能保证最大的 $b$ 没有增加花费，其他 $b$ 只增加花费一次。
时间复杂度 $O(n)$
空间复杂度 $O(n)$
代码#include <bits/stdc++.h>#define ll long longusing 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;}C题解知识点：博弈论，贪心，二分。
本来数据范围能暴力，但执着找规律推结论，结果推假了wwwwwwwwww，不如直接暴力QAQ 。
显然二分 $k$ 可以， $k \in[1,\lceil \frac{n}{2} \rceil] $ 。二者选取的贪心策略也很明显， A尽量取大的，B取最小的，推到这一步可以直接模拟了。
但进一步可以推出，A取后 $k$ 个之后，B一定取了前 $k-1$ 个，那么我们把前 $k-1$ 个空出来，让A直接从 $k$ 开始取是最优的，正着取的第 $i$ 个是第 $k-i+1$ 回合，只要小于等于 $i$ 即可。
时间复杂度 $O(n \log n)$
空间复杂度 $O(n)$
代码#include <bits/stdc++.h>#define ll long longusing 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;}D题解知识点：数论，筛法。
注意到，我们要求的是每个元素不超过 $m$ 的正整数，长度 $[1,n]$ 的每个长度的不明确的序列个数之和。我们先考虑长度为 $n$ 的情况，其他长度可以同理。
所有序列天生有一组 $[1,1,1,1,\cdots]$ 的删除序列，这代表只要序列有一个元素能在 $1$ 以外的位置删除，就能产生新的删除序列，则原序列就是不明确的。
因为可以通过移除第一项，让 $a[i]$ 往前挪，必然会经过 $[2,i]$ 的所有位置，所以若要使 $a[i]$ 可在 $1$ 以外的位置删除，需要 $a[i]$ 存在 $[2,i]$ 内的数与其没有公共质因子，更进一步，即不包含所有前缀素数（$[2,i]$ 所有数的质因子种类，即其中所有素数），这样就一定存在 $2\leq j\leq i$ 使 $gcd(j,a[i]) = 1$。
注意到，计算在 $a[i]$ 位置上 $[1,m]$ 中符合条件的数的个数很困难，但计算包含所有前缀质因子的情况很容易，$\frac{m}{mul_i}$ 就是 $[1,m]$ 所有前缀质因子都存在的数的个数，其中 $mul_i$ 是位置 $i$ 的前缀质因子乘积。
我们计算出 $[1,n]$ 每个位置的 $\frac{m}{mul_i}$ ，即每个位置其前缀质因子都存在数的个数，把他们乘法原理乘在一起，就代表长度为 $n$ 明确的数列的个数 $\prod_{i=1}^n \frac{m}{mul_i}$ ，因为每个位置组合的都是包含所有前缀质因子，除了在 $1$ 处删除，其他地方 $gcd(i,a[i]) \neq 1$ 不能删。
最后对于长度 $n$ 的数列，所有情况一共 $m^n$ 种，所以最后不明确的数列个数为 $m^n - \prod_{i=1}^n \frac{m}{mul_i}$。
我们对 $[1,n]$ 所有长度的答案求和，有 $ans = \sum_{i=1}^n (m^i - \prod_{j=1}^i \frac{m}{mul_j})$，注意到 $m^i$ 、 $mul_i$ 以及 $\prod_{j=1}^i \frac{m}{mul_j}$ 可以从 $1$ 递推，过程中加到答案里即可。

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

推荐阅读

金鱼眼面相解析，有金鱼眼的人运势怎么样

开元通宝680万图片 &#8211; 开元通宝2020价格

白煮牛肉的家常做法大全白煮牛肉的家常做法

汽车贴膜前需要洗车吗汽车贴膜前要洗车吗?

手机无响应的解决方法应该怎么解决呢

母亲节要买什么礼物,分享几款走心的

蓝牙耳机使用小技巧蓝牙耳机的正确使用方法

越狱第3季中第几集越狱成功？

双子座的床上功夫

梦见下牙掉了,但没流血是什么意思

2022年护士年终工作总结 2022美工个人年终工作总结

诗歌鉴赏蜀相咏史怀古诗蜀相的作者

猫咪渴了的表现

瘦麒麟臂方法瘦胳膊最有效的方法

形容经历了事情的成语是什么

抗皱六胜肽精华液的使用方法六胜肽抗皱精华液使用方法

糖不甩怎么做才Q

怎么去胶？

宝马有什么技术

关于本玉12号简述本玉12号