知识点：贪心。
注意到 (m\geq n) 时，不存在某一行或列空着，于是不能移动。
而 (m
时间复杂度 (O(1))
空间复杂度 (O(1))
#include
#define ll long long
using namespace std;
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i > 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) 只增加花费一次。
时间复杂度 (O(n))
空间复杂度 (O(n))
#include
#define ll long long
using namespace std;
int a[200007], b[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i > a[i];
for (int i = 1;i > b[i];
ll sum = 0;
for (int i = 1;i > t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
知识点：博弈论，贪心，二分。
本来数据范围能暴力，但执着找规律推结论，结果推假了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
#define ll long long
using namespace std;
int n;
int a[107];
bool check(int mid) {
bool ok = 1;
for (int i = 1;i > n;
for (int i = 1;i > a[i];
sort(a + 1, a + n + 1);
int l = 1, r = n + 1 >> 1;
while (l > 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;
}
知识点：排列组合，分解质因数。
注意到，我们要求的是每个元素不超过 (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) 递推，过程中加到答案里即可。
时间复杂度 (O(n))
空间复杂度 (O(n))
#include
#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 >> m;
euler_screen(n);
int base = 1, mul = 1, ans = 0;
ll fact = 1;
for (int i = 1;i
知识点：bfs。
思考明白了就是一个很简单的01bfs。
注意到我们需要让从第一行到第 (n) 行不存在路径，反过来想就是需要一条从第一列到第 (m) 列连续的横向仙人掌路径，才能阻挡所有竖向路径，这个路径要求花费最少，于是问题转化问从第一列出发到第 (m) 列的仙人掌最短路，起点是第一列所有点，有仙人掌的格子花费为 (0) ，没有的花费是 (1) 。
搜索过程中用一个 map 记录前驱坐标即可复原路径。
这道题主要在这个思考和转化的过程。
时间复杂度 (O(nm))
空间复杂度 (O(nm))
#include
#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> dt(n + 1, vector(m + 1));
for (int i = 1;i > 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 n || yy m) continue;
ok &= dt[xx][yy] != '#';
}
return ok;
};
deque> dq;
vector> vis(n + 1, vector(m + 1));
map, pair> pre;
pair p = { 0,0 };
for (int i = 1;i n || 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 > t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
Original: https://www.cnblogs.com/BlankYang/p/16815158.html
Author: 空白菌
Title: Educational Codeforces Round 138 (Rated for Div. 2) A-E
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/800357/
转载文章受原作者版权保护。转载请注明原作者出处！