忙于期末，久久未写，今日一写，全都忘了

C. Candy Store

题目：

思路：

数学思维

 我们假设一个标签 cost 可以覆盖一个连续的区间，那么这个 cost 就满足

cost = bl * dl = bl+1 * dl+1 = ... = br-1 * dr-1 = br * dr

由于 d[i] 是可以自己定的，但是 b[i] 是固定的，所以这个 cost 首先一定要满足 cost % b[i] == 0，即 cost % lcm(b[i], b[i+1] , b[i+2] ...) = 0，所以 cost 起码得是区间 l~r 的 b 的 lcm，即 cost = lcm*k

那么如何利用 a[i] % d[i] = 0 呢？我们同时将两个数乘上 b[i]，那么就是 (a[i] * b[i]) % cost = 0

所以这时我们就把 d[i] 转换为了 cost 了， 那么现在第二个条件也就出来了，即 cost 起码还得是 gcd(a[i]*b[i], a[i+1]*b[i+1], ...) 的因数

最后根据贪心的想法，我们这样一直取连续段的 cost 肯定是最优的，如果我们不选的话，那么下一段的限制更多，其实更加不利

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"
int gcd(int a,int b)
{return !b ? a : gcd(b, a % b);
}
int lcm(int a,int b)
{return a * b / gcd(a, b);
}
void solve()
{int n;cin >> n;vector<pair<int,int>> candy(n);for (int i = 0; i < n; i++){cin >> candy[i].first >> candy[i].second;}int g = 0, l = 1;int ans = 1;for (int i = 0; i < n; i++){g = gcd(candy[i].first * candy[i].second, g);l = lcm(candy[i].second, l);if (g % l)ans++, l = candy[i].second, g = candy[i].first * candy[i].second;}cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B. Square Pool

题目：

思路：

有点物理思维

很简单，由于是完全弹性碰撞，而且都是 45° 碰撞，所以我们交换过后其实相当于没交换，相当于直接穿过，所以直接计算在对角线的小球即可

因为不需要输出具体是那些球进去了，所以还是很简单的

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n, s;cin >> n >> s;vector<pair<int, int>> vel(n), pos(n);int ans = 0;for (int i = 0; i < n; i++){cin >> vel[i].first >> vel[i].second >> pos[i].first >> pos[i].second;if (vel[i].first == vel[i].second){ans += pos[i].first == pos[i].second;}else{ans += (pos[i].first + pos[i].second == s);}}cout << ans << endl;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}