未补完
G. Go to Play Maimai DX
算法：双指针
做法：从左到右用两个指针维护一段区间且右指针不断右移，当这个区间满足题目所给的性质，我们取出区间长度，然后再将左指针右移，直到右指针到边界且左指针指到不符合题目的性质的位置结束，期间不断对符合题目性质的区间长度取最小值。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 100010;
int n, k;
int w[N];
bool check(int cnt[])
{
if (cnt[1] >= 1 && cnt[2] >= 1 && cnt[3] >= 1 && cnt[4] >= k)return true;
return false;
}
void solve()
{
cin >> n >> k;
int cnt[5] = { 0 };
int ans = 1e9;
for (int i = 1; i <= n; i++)cin >> w[i];
for (int i = 1, j = 1; j <= n; )
{
while (!check(cnt) && j <= n)cnt[w[j]]++, j++;
while (check(cnt))ans = min(ans, j - i), cnt[w[i]]--, i++;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
D. Cirno's Perfect Equation Class
算法：试除法求约数， gcd
做法：对于 \(k * a + b = c\)，我们可以得到 \(k * a + c / x = c\)，那么 \(c / x\) 必须为整数，即需要整除。那么我们求出 \(c\) 的约数，随后再用 \(c\) 除以约数可得 \(b\)，再判断 \((c - b) / k\) 是否为整数，是则得到 \(a\)，否则这个 \(b\) 不存在。最后我们判断一下 \(a\) 和 \(b\) 是否都大于等于1且 \(gcd(a, b) >= n\) 即可。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 200010, INF = 1e9;
int k, n, a, b, c;
vector<int> gt(int c)
{
vector<int> ans;
for (int i = 1; i <= c / i; i++)
{
if (c % i == 0)
{
ans.push_back(i);
if (c / i != i)ans.push_back(c / i);
}
}
return ans;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
cin >> k >> c >> n;
auto num = gt(c);
int ans = 0;
for (int i = 0; i < num.size(); i++)
{
b = c / num[i];
if((c - b) % k == 0)
{
a = (c - b) / k;
if (gcd(a, b) >= n && a >= 1 && b >= 1)ans++;
}
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
solve();
}
return 0;
}
H. Nazrin the Greeeeeedy Mouse
算法：dp
做法：我们先设有 \(f_{i, j, k}\)，表示在第 \(i\) 到第 \(j\)个蛋糕中我们有一个大小为 \(k\) 的包对这 \(i - j + 1\) 个蛋糕的获取或打洞的集合。这就有点像 01 背包问题了。我们有如下方程： $$f_{i, j, k} = max(f_{i, j - 1, k} \ , f_{i, j - 1, k - a[j]} + b[j])$$ 即第 \(j\) 个蛋糕在从第 \(i\) 到第 \(j\)个蛋糕中且大小为 \(k\) 的包中到底取不取。
我们再取前缀有 \(f_{i, j, k} = max(f_{i, j, k - 1} \ , f_{i, j, k})\)。
我们再设 \(g_{i, j}\)，表示第 \(i\) 个包已经取到了第 \(j\) 个蛋糕的集合。
那么我们有如下方程：$$g_{i, j} = max(g_{i - 1, j} \ , g_{i - 1, k} + f_{k + 1, j, a[i]})$$ 其中 \(k \in [0, j - 1]\)
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 200, INF = 1e9, M = 100010;
int n, m;
int a[N], b[N];
int f[N + 5][N + 5][N + 5], g[N + 5][N + 5], bag[M], used[N];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
for (int w = 0; w <= N; w++)
{
if (w >= a[j])f[i][j][w] = max(f[i][j - 1][w], f[i][j - 1][w - a[j]] + b[j]);
else f[i][j][w] = f[i][j - 1][w];
}
for (int w = 1; w <= N; w++)
f[i][j][w] = max(f[i][j][w], f[i][j][w - 1]);
}
}
int cnt = 0, ans = 0;
for (int i = 1; i <= m; i++)cin >> bag[i];
for (int i = max(1, m - n); i <= m; i++)used[++cnt] = bag[i];
for (int i = 1; i <= cnt; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 0; k < j; k++)
g[i][j] = max(g[i][j], g[i - 1][k] + f[k + 1][j][used[i]]);
ans = max(ans, g[i][j]);
}
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}