A题：Diagonals
题意
给定一个n x n的网格，k个筹码，放在某个位置，则其对应的右上-左下对角线被占用，问占用的对角线数量最少是多少？
思路
模拟
每次我们都往格子最多的对角线上放，然后次多...
很容易看出来
代码
inline void solve() {int n, k; cin >> n >> k;if (k == 0) return cout << 0 << endl, void();if (k - n <= 0) return cout << 1 << endl, void();k -= n;int ans = 2;for (int i = n - 1; i; i -- ) {if (k - i <= 0) return cout << ans << endl, void();k -= i, ans += 1;if (k - i <= 0) return cout << ans << endl, void();k -= i, ans += 1;}return;
}B1：Bouquet (Easy Version)
题意
一个小女孩去买花，花店中有n种花，每种花有ai个花瓣
小女孩买来的花束中要求任意两个花瓣数相差不超过1
买ai个花瓣的花，需要ai元，她有m元
问最多花多少元
思路
如果你是用map做的话，B1和B2就会做的飞快）
我们贪心地想，买的多花的也就越多，那么对于t个花瓣的和t+1个花瓣的
我们尽可能地去买t个花瓣的，再去看t+1个花瓣能买多少
但是这再最后一个样例中是错误的
还可以通过少买一个t个花瓣的，多买一个t+1个花瓣的操作，来实现多花一块
那我们只需要先按贪心的来，再看能进行上述操作最多几次即可。
代码
inline ll min(ll a, ll b) {return a > b ? b : a;
}
inline ll max(ll a, ll b) {return a > b ? a : b;
}
inline void solve() {int n; ll k; cin >> n >> k;map<int, int> cnt;for (int i = 1; i <= n; i ++ ) {int x; cin >> x;cnt[x] += 1;}ll ans = 0;for (auto [t, c] : cnt) {ll res = t * min(c, k / t);if (cnt.count(t + 1)) {ll cnt0 = min(c, k / t);ll last = k - res;ll cnt1 = min(last / (t + 1), cnt[t + 1]);res += cnt1 * (t + 1) + min(cnt0, min(cnt[t + 1] - cnt1, last - cnt1 * (t + 1)));}ans = max(ans, res);}cout << ans << endl;return;
}B2：Bouquet (Hard Version)
没啥区别，只是对于map的输入改了下而已，笑qwq
代码
inline ll min(ll a, ll b) {return a > b ? b : a;
}
inline ll max(ll a, ll b) {return a > b ? a : b;
}
inline void solve() {int n; ll k; cin >> n >> k;vector<PII> a(n);for (int i = 0; i < n; i ++ ) cin >> a[i].first;for (int i = 0; i < n; i ++ ) cin >> a[i].second;map<int, int> cnt;for (int i = 0; i < n; i ++ ) {cnt[a[i].first] = a[i].second;}ll ans = 0;for (auto [t, c] : cnt) {ll res = t * min(c, k / t);if (cnt.count(t + 1)) {ll cnt0 = min(c, k / t);ll last = k - res;ll cnt1 = min(last / (t + 1), cnt[t + 1]);res += cnt1 * (t + 1) + min(cnt0, min(cnt[t + 1] - cnt1, last - cnt1 * (t + 1)));}ans = max(ans, res);}cout << ans << endl;return;
}C题：Squaring
题意
给定一个数组，每次你可以选定一个元素使其成为本身的平方，问至少经过几次操作可以使得整个数组不递减？
思路
平方操作，时间上肯定过的去，但是对于最后一个样例，肯定会爆long long
所以我们的比较，只能是基于ai的本身上
我们可以用一个数组来记录每个位置各用了多少次操作
对于i + 1的位置，若i的位置用了p次操作
两边可以不断开方，直到剩到一个数本身ai或者ai+1
即可以为ai <= ai+1的k次 k = q - p 由贪心，k要小
也可以是ai的k次 <= ai k = p - q 由贪心，k要大
我们通过枚举k就可以知道q，又因为平方增长快，k的枚举范围很小
此外，最后ans将所有次数相加的时候，要开long long，爆了一次...
代码
inline void solve() {int n; cin >> n;vector<ll> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];int j = 1;while (j <= n && a[j] == 1) j += 1;vector<int> c(n + 1);for (int i = max(j, 2); i <= n; i ++ ) {if (a[i] == 1) return cout << -1 << endl, void();int k = 0;if (a[i] < a[i - 1]) {ll cur = a[i];while (cur < a[i - 1]) {cur *= cur;k += 1;}c[i] = k + c[i - 1];}else {if (a[i - 1] == 1) continue;ll cur = a[i - 1];while (cur * cur <= a[i]) {cur *= cur;k += 1;}c[i] = max(0, c[i - 1] - k);}}ll ans = 0;for (int i = 1; i <= n; i ++ ) ans += c[i];cout << ans << endl;return;
}
