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

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;
}