首先还原时显然每次都只有一种可能的操作，就是把较大的数变为两个数的差。直接一步步模拟然后特判一下 的情况（不特判的话会超时）就能拿到 分了。
这个过程其实比较容易想到就是辗转相减法。那么其实中间可以用取模优化来加速，其实也就是辗转相除法。唯一的小麻烦就是可能最后一步取模会变得比原本的数更小，特判一下不要除多了即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b, x, y;
int ans;
signed main()
{
freopen("shu.in", "r", stdin);
freopen("shu.out", "w", stdout);
cin >> a >> b >> x >> y;
while (x != a || y != b)
{
if (x > y)
{
int nxt = x % y;
if (nxt < a)
nxt = a;
ans += (x - nxt) / y;
x = nxt;
}
else
{
int nxt = y % x;
if (nxt < b)
nxt = b;
ans += (y - nxt) / x;
y = nxt;
}
}
cout << ans;
return 0;
}
其实容易发现，就是所有大于等于 的位置 都可以变为 。那么直接广度优先搜索是最稳妥的方法。
当然 dp 学的好的同学很容易发现可以直接用类似于背包的方法搞定。
// dp
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("fan.in", "r", stdin);
freopen("fan.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<int> a(m), b(m);
for (int i = 0; i < m; i++)
{
cin >> a[i] >> b[i];
}
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < m; j++)
{
if (i >= a[j])
{
dp[i] = max(dp[i], dp[i - a[j] + b[j]] + a[j] - b[j]);
}
}
}
cout << n - dp[n];
return 0;
}
// bfs
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e[5005];
queue<int> q;
bool f[5005];
int main()
{
freopen("fan.in", "r", stdin);
freopen("fan.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int ai, bi;
cin >> ai >> bi;
for (int j = ai; j <= n; j++)
e[j].push_back(j - ai + bi);
}
q.push(n);
f[n] = true;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v : e[u])
{
if (!f[v])
{
f[v] = true;
q.push(v);
}
}
}
for (int i = 0; i <= n; i++)
if (f[i])
{
cout << i;
return 0;
}
return 0;
}
来源：https://www.luogu.com.cn/problem/AT_abc341_d
这题是在原题的基础上做了一点点小加强，增加了一个数的送分情况和三个数的更复杂的容斥。
首先写完暴力枚举的代码后，容易想到可以二分处理，判断小于等于 mid 的数中，被保留的是否大于等于 个。这样问题就转换成了 以内最多有多少个数恰好是 中的一个的倍数。
这个就可以容斥处理了， 的倍数有 个， 的倍数有 个。显然这两个数的公倍数不能要，这些公倍数都是 的倍数，这些公倍数都被多加了两次，所以去掉两倍的即可。
三个数时用类似的方法容斥即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1'000'000'000'000'000'000;
int n, k;
int a[5];
int lcm12, lcm23, lcm13, lcm123;
int gcd(int a, int b)
{
if (!b)
return a;
return gcd(b, a % b);
}
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}
// 小于等于 mid 的数中，被保留的是否大于等于 k
bool check(int mid)
{
int cnt = 0;
if (n == 1)
cnt += mid / a[1];
else if (n == 2)
{
cnt += mid / a[1];
cnt += mid / a[2];
cnt -= 2 * (mid / lcm12);
}
else
{
cnt += mid / a[1];
cnt += mid / a[2];
cnt += mid / a[3];
cnt -= 2 * (mid / lcm12);
cnt -= 2 * (mid / lcm23);
cnt -= 2 * (mid / lcm13);
cnt += 3 * (mid / lcm123);
}
return cnt >= k;
}
signed main()
{
freopen("mei.in", "r", stdin);
freopen("mei.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
if (n == 2)
lcm12 = lcm(a[1], a[2]);
else if (n == 3)
{
lcm12 = lcm(a[1], a[2]);
lcm23 = lcm(a[2], a[3]);
lcm13 = lcm(a[1], a[3]);
lcm123 = lcm(lcm12, lcm23);
}
int l = 1;
int r = INF;
int ans = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans;
return 0;
}
其实第四题是比较简单的，这样安排是为了在考前提醒大家不要被前面题目卡到，一开始就要看完四道题目再来决定时间分配。真实比赛中第四题可能是最难的，但是也要一开始就看看有没有简单的子任务可以做，需要留充足时间把送的分拿满。
#include <bits/stdc++.h>
using namespace std;
int n;
char g[505][505];
bool vis[505][505];
// @ 数量 . 数量
vector<pair<int, int>> v;
bool cmp(pair<int, int> x, pair<int, int> y)
{
// x.first/(x.first+x.second) < y.first/(y.first+y.second)
int xy = x.first * (y.first + y.second);
int yx = y.first * (x.first + x.second);
if (xy != yx)
return xy < yx;
return x.first < y.first;
}
queue<pair<int, int>> q;
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
pair<int, int> bfs(int x, int y)
{
// @ .
pair<int, int> res = make_pair(0, 0);
// 起点入队
q.push(make_pair(x, y));
vis[x][y] = true;
if (g[x][y] == '@')
res.first++;
else
res.second++;
// bfs
while (!q.empty())
{
pair<int, int> pos = q.front();
q.pop();
for (int i = 0; i < 8; i++)
{
int nx = pos.first + dx[i];
int ny = pos.second + dy[i];
if (!vis[nx][ny] && g[nx][ny] != '#')
{
q.push(make_pair(nx, ny));
vis[nx][ny] = true;
if (g[nx][ny] == '@')
res.first++;
else
res.second++;
}
}
}
return res;
}
int main()
{
freopen("kong.in", "r", stdin);
freopen("kong.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> g[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
vis[i][j] = false;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!vis[i][j] && g[i][j] != '#')
v.push_back(bfs(i, j));
sort(v.begin(), v.end(), cmp);
cout << v.size() << " " << v[0].first;
return 0;
}