题目链接：codeforces 1621D 题解 不难得出右下角的所有雪全清，接下来就是找到右上角到右下角的路径。关键是找到到右下角区域的入口。根据移动方式，再贪心只选择一个入口，画图可知只有八个入口，取最小值即可。 参考代码 12345678910111213141516171819202122232425262728#include <iostream>using namespace std;typedef long long ll;const int maxn = 550;int n;ll a[maxn][maxn];void solver() { ll ans = 0; cin >> n; for (int i = 1; i <= n * 2; i++) { for (int j = 1; j <= n * 2; j++) { cin >> a[i][j]; if (i >= n+1 && j >= n+1) { ...

题目链接：codeforces1 1620D 题解 根据贪心思想，先满足最大的那个数至多需要的面值为 的硬币数 ，然后再枚举面值为 和 的硬币数是否有可行解，答案取最小值即可。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <algorithm>#include <vector>using namespace std;typedef long long ll;void solver() { ll n; cin >> n; vector<ll> a(n); for (ll &i:a) cin >> i; sort(a.begin(), a.end()); int ans = 0x3f3f3f3f; int cur = a.back() / 3; for (int on ...

题目链接：codeforces 1623C 题解 二分答案，对最小高度二分。 对于当前假设的高度 ，每次操作的时候，采取贪心策略，倒序枚举，把当前的石头数尽可能地放到前两堆。需要注意的是，当前堆石头数减少的数量一定是 或是 的正整数倍数。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>using namespace std;typedef long long ll;const int N = 2e5 + 10;ll n, mx;ll a[N], b[N];bool check(ll x) { for (int i = 1; i <= n; i++) b[i] = a[i]; ll d; for (int i = n; i >= 3; i--) { if (b[i] < x) { return false; } ...

题目链接：codeforces1365E 题意 给定一个序列，定义其非空子序列（大小为 ）的价值是每个元素的二进制数中第 位上 的个数如果大于 ，则 ans += 2^i，求最大的价值。 题解 显然，当 时全选。 当 时，每个位上需要的 也会增加。假设我们已经选了 个数，当选第 个的时候，我们可以把他加进来，但这会使得后面需要的 增加；既然第 个数可以加进来，说明它可以替换掉三个数中的某一个，所以每次枚举 个数的或和即可。 参考代码 12345678910111213141516171819202122#include <iostream>using namespace std;typedef long long ll;const int N = 510;int n;ll a[N];int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } ll ans = 0; for (int i = 1; i ...

题目链接：codeforces1445C Division 题解 分类讨论： 当 时，显然答案是 ； 当 时，如果 ，显然答案是 ； 当 时，且 ，想到唯一分解定理，把 ， 拆成若干的素数相乘，当 减少若干个 的质因子，满足不能被 整除时即可得到我们要的答案。观察到 比较小，所以去找 的质因子。 参考代码 123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <vector>#include <cmath>using namespace std;typedef long long ll;int main() { int t; cin >> t; while (t--) { ll p, q; cin >> p >> q; if (p < q) cout << p << endl; ...

题目链接：codeforces1427C The Hard Work of Paparazzi 题解 直接 枚举。观察 比较小，当 时，不用从头扫一遍，只要从 开始即可，用一个数组维护前 个的最大值。 参考代码 12345678910111213141516171819202122232425262728293031#include <iostream>#include <cstring>using namespace std;const int N = 1e5 + 10;int r, n;int t[N], x[N], y[N];int dp[N], tmp[N];int main() { cin >> r >> n; for (int i = 1; i <= n; i++) { cin >> t[i] >> x[i] >> y[i]; } memset(dp, -0x3f, sizeof(dp)); dp[0] = 0; x[0] ...

题目链接：codeforces1183F Topforces Strikes Back 题解 分情况讨论， 选一个数，一定是选最大的那个数，假设是 。 选两个数，再选的这个数一定是最大的不是 的约数的数，假设是 。 证明： 假设当前两个数是 ，。 如果其中有一个是 的约数，则用 替换这个数。 如果两个都不是 的约数，则用 替换 。 如果两个都是 的约数，有 ，则只取 即可。 选三个数，第三个数一定是最大的不是 的约数的数，假设是 。但从上面的证明可以看出，有 ，这个时候我们只要判断是否存在这种情况，取最大值就好了。 参考代码 123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <cstring>#include <vector>#include <algorithm>using namespace std;const int N = 2e5 + 10;int a[N], flag ...

题目链接：codeforces1183H Subsequences (hard version) 题解 求前 长的子序列。定义dp[i][j] 为前 个长度为 的子序列个数，首先将 dp[i-1][j] 的状态转移到 dp[i][j]，再加上不包含当前 s[i] 的子序列个数，即 dp[i-1][j-1]。又因为前面可能会有 s[last] 与 s[i] 相等，我们只要减去 dp[last-1][j-1] 即可，last 是在 前面离 最近的相等字符的下标。 参考代码 1234567891011121314151617181920212223242526272829303132333435#include <iostream>using namespace std;typedef long long ll;char s[110];ll dp[110][110];int pre[110];int main() { ll n, k; cin >> n >> k >> s+1; for (int i = 1; i ...

题目链接：codeforces 1433G 题解 首先预处理在没有免费边情况下的最短路，再暴力枚举边即可。 假设当先线路为 j，对于边 (a, b) ，它有两种情况： 免费后不在最短路上，结果是 f[j.first][j.second]。 免费后在最短路上，因为这条边的价值改变了，可能最短路会变，所以要讨论，结果是 min(f[j.second][a]+f[j.first][b], f[j.first][a]+f[j.second][b])。 时间复杂度为 。 参考代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <iostream>#include <vector>#include <cstring>#include <queue>using namespace std;typedef long ...